数组排序与parallelSort性能比较

Question

我已经下载了java8-ea发行版并在Array.sort和之间进行了快速比较Arrays.parallelSort.

这就是结果:

我可以理解,praralleSort至少应该像普通老式机器一样sort,如果不是更快......但事实并非如此.

对以下规格进行了比较:

惠普ProBook Intel Core i5与4G RAM上Ubuntu 13.04 Linux同版本的JDK:Java HotSpot(TM) 64-Bit Server VM (build 25.0-b23, mixed mode)

我通过这种方式创建了一个包含三个字段的Custom对象数组(以保留顺序添加对象):

package com.cmd;

import java.util.Arrays;

public class Main {

    public static void main(String[] args) {

        for (int i=100; i <= 10_000_000; i*=10){
            runTest(i);
        }
    }

    private static void runTest(final int size){

        // Fist obtain two Arrays of same data
        Employee[] empArrForSort = createVeryLargeEmpArray(size);
        Employee[] empArrForSortCopy = Arrays.copyOf(empArrForSort, empArrForSort.length);

        long start = System.currentTimeMillis();
        Arrays.sort(empArrForSort, (e1, e2) -> new Integer(e1.getId()).compareTo(e2.getId()));
        logStart(size + ": sort", start);

        start = System.currentTimeMillis();
        Arrays.parallelSort(empArrForSortCopy, (e1, e2) -> new Integer(e1.getId()).compareTo(e2.getId()));
        logStart(size + ": parallel sort", start);
    }


    private static void logStart(String label, long startTimeMillis) {
        System.out.println("End " + label + " the array. It took: " + (System.currentTimeMillis() - startTimeMillis) + " ms");
    }

    private static Employee[] createVeryLargeEmpArray(final int size) {

        Employee[] ret = new Employee[size];

        for (int i = 0; i < ret.length; i++) {
            ret[i] = Employee.createEmployee(ret.length - i, "Mohammad" + i, "");
        }

        return ret;
    }

    static class Employee {

        private int id;
        private String name;
        private String email;

        private Employee(int id, String name, String email) {
            this.id = id;
            this.name = name;
            this.email = email;
        }

        public static Employee createEmployee(int id, String name, String email) {
            return new Employee(id, name, email);
        }

        public int getId() {
            return id;
        }
    }

}

并且,另一个运行显示,当列表包含10,000,000时,Parallel仅执行填充,在所有其他情况下它看起来更好.

>java -Xmx2000m com.cmd.Main
End 100: sort the array. It took: 110 ms
End 100: parallel sort the array. It took: 6 ms
End 1000: sort the array. It took: 2 ms
End 1000: parallel sort the array. It took: 3 ms
End 10000: sort the array. It took: 11 ms
End 10000: parallel sort the array. It took: 11 ms
End 100000: sort the array. It took: 15 ms
End 100000: parallel sort the array. It took: 37 ms
End 1000000: sort the array. It took: 553 ms
End 1000000: parallel sort the array. It took: 187 ms
End 10000000: sort the array. It took: 640 ms
End 10000000: parallel sort the array. It took: 1099 ms

Answer 1

这里的要点是数组按保留顺序排序.这是一个非常独特的场景,并不意味着算法的一般性能.我使用无序数组运行相同的代码:

  ret[i] = Employee.createEmployee(rnd.nextInt(ret.length), "Mohammad" + i, "");

当parallelSort比简单排序快得多时,结果表明性能要慢得多.

End 100: sort the array. It took: 139 ms
End 100: parallel sort the array. It took: 4 ms
End 1000: sort the array. It took: 4 ms
End 1000: parallel sort the array. It took: 6 ms
End 10000: sort the array. It took: 35 ms
End 10000: parallel sort the array. It took: 30 ms
End 100000: sort the array. It took: 420 ms
End 100000: parallel sort the array. It took: 144 ms
End 1000000: sort the array. It took: 1341 ms
End 1000000: parallel sort the array. It took: 506 ms
End 10000000: sort the array. It took: 12200 ms
End 10000000: parallel sort the array. It took: 3971 ms