Java сортировка через Comparator <T>проводит большую часть своего времени в сравнении (объект, объект) - PullRequest
Новая
       78

Java сортировка через Comparator <T>проводит большую часть своего времени в сравнении (объект, объект)

14 голосов
/ 06 октября 2011

Я заметил кое-что странное во время профилирования нашей базы кода.Казалось, что сортировка с типизированным компаратором (например, Comparator<MyClass>) всегда сначала вызывала метод Comparator<MyClass>.compare(Object,Object), который затем вызывал метод Comparator<MyClass>.compare(MyClass,MyClass).Кроме того, подавляющее большинство времени было потрачено на Comparator<MyClass>.compare(Object,Object).Для дальнейшего изучения я создал небольшую тестовую программу: 

public class Sandbox {
    public static void main(String argv[]) {
        for(int j=0; j<100; j++) {
            int n = 10000;
            SortMe[] sortMes = new SortMe[n];
            for (int i=0; i<n; i++) {
                sortMes[i] = new SortMe(Math.random());
            }
            Arrays.sort(sortMes, new SortMeComp());
            System.out.println(Arrays.toString(sortMes));
        }
        for(int j=0; j<100; j++) {
            int n = 10000;
            SortMe[] sortMes = new SortMe[n];
            for (int i=0; i<n; i++) {
                sortMes[i] = new SortMe(Math.random());
            }
            Arrays.sort(sortMes, new SortMeCompTypeless());
            System.out.println(Arrays.toString(sortMes));
        }
    }
}

Типизированный компаратор: 

public class SortMeComp implements Comparator<SortMe>{
    public int compare(SortMe one, SortMe two) {
        if(one.getValue()>two.getValue()) {
            return -1;
        } else if (one.getValue()<two.getValue()) {
            return 1;
        } else {
            return 0;
        }
    }
}

Нетипизированный компаратор, который я создал для сравнения: 

public class SortMeCompTypeless implements Comparator{
    public int compare(Object oneObj, Object twoObj) {
        SortMe one = (SortMe) oneObj;
        SortMe two = (SortMe) twoObj;
        if(one.getValue()>two.getValue()) {
            return -1;
        } else if (one.getValue()<two.getValue()) {
            return 1;
        } else {
            return 0;
        }
    }
}

Вот результаты (из YourKit profiler ; дайте мне знать, если у вас есть скриншот): 

+----------------------------------------------------+-----------------+-----------------+--------------------+
|                        Name                        |    Time (ms)    |  Own Time (ms)  |  Invocation Count  |
+----------------------------------------------------+-----------------+-----------------+--------------------+
|  +---java.util.Arrays.sort(Object[], Comparator)   |  23,604  100 %  |          8,096  |               200  |
|    |                                               |                 |                 |                    |
|    +---SortMeComp.compare(Object, Object)          |  11,395   48 %  |          7,430  |        12,352,936  |
|    | |                                             |                 |                 |                    |
|    | +---SortMeComp.compare(SortMe, SortMe)        |   3,965   17 %  |          3,965  |        12,352,936  |
|    |                                               |                 |                 |                    |
|    +---SortMeCompTypeless.compare(Object, Object)  |   4,113   17 %  |          4,113  |        12,354,388  |
+----------------------------------------------------+-----------------+-----------------+--------------------+

Я запустил профиль без фильтрации, и вы видите рекурсивные вызовыобъединить сортировку (которая просто затрудняет чтение), но ничего интересного.

Так что здесь происходит?Откуда этот метод SortMeComp.compare (Object, Object)?Мы полагали, что это что-то, что Java создает внутри для работы с дженериками, но что может занять так много времени?Я бы подумал, что jvm будет рассматривать общий метод как «нетипизированный» метод / Object.Как видите, простое приведение гораздо быстрее.Кроме того, я думаю, что это именно та вещь, которая будет JITED, даже если jvm нужно делать что-то наперед.Что здесь происходит?

Кстати: 

$ java -version
java version "1.6.0_26"
Java(TM) SE Runtime Environment (build 1.6.0_26-b03)
Java HotSpot(TM) 64-Bit Server VM (build 20.1-b02, mixed mode)

Редактировать:

В ответ на ответ savinos я попытался смоделировать дополнительный вызов метода с помощью «нетипизированного»Компаратор, который просто приводит к типизированному сравнению: 

public class SortMeCompMethodCalls implements Comparator{
    public int compare(Object oneObj, Object twoObj) {
        return compare((SortMe)oneObj, (SortMe)twoObj);
    }
    public int compare(SortMe one, SortMe two) {
        if(one.getValue()>two.getValue()) {
            return -1;
        } else if (one.getValue()<two.getValue()) {
            return 1;
        } else {
            return 0;
        }
    }
}

Вот результаты: 

+---------------------------------------------------------+-----------------+-----------------+--------------------+
|                          Name                           |    Time (ms)    |  Own Time (ms)  |  Invocation Count  |
+---------------------------------------------------------+-----------------+-----------------+--------------------+
|  +---java.util.Arrays.sort(Object[], Comparator)        |  31,044  100 %  |          8,061  |               200  |
|    |                                                    |                 |                 |                    |
|    +---SortMeComp.compare(Object, Object)               |  11,554   37 %  |          7,617  |        12,354,392  |
|    | |                                                  |                 |                 |                    |
|    | +---SortMeComp.compare(SortMe, SortMe)             |   3,936   13 %  |          3,936  |        12,354,392  |
|    |                                                    |                 |                 |                    |
|    +---SortMeCompMethodCalls.compare(Object, Object)    |  11,427   37 %  |          7,613  |        12,352,146  |
|      |                                                  |                 |                 |                    |
|      +---SortMeCompMethodCalls.compare(SortMe, SortMe)  |   3,814   12 %  |          3,814  |        12,352,146  |
+---------------------------------------------------------+-----------------+-----------------+--------------------+

Так что, похоже, савинос прав!Дополнительное время - это только дополнительный вызов метода (плюс немного для приведения).Это кажется мне безумным;Вы думаете, что это будет JIT JED далеко?Ах, хорошо.

Я удалил редактирование 2 и добавил его в качестве ответа, как и должно было быть изначально.

Ответы [ 4 ]

10 голосов
/ 06 октября 2011

Я могу ошибаться, но я бы сказал, что разница между компаратором "Object" и типизированным компаратором (который вызывается универсальным) просто вызвана дополнительным вызовом функции.

Учтите, что вы выполняете 12 352 936 вызовов, что означает примерно 5,7 * 10 ^ -7 секунд на вызов функции, что не является необоснованным.

2 голосов
/ 06 октября 2011

Немного не по теме, но вы должны стремиться к быстрому ...

Вы сократите время внутреннего сравнения () примерно на 50% со случайными данными, если вы измените его на что-тонапример: 

public int compare(SortMe one, SortMe two) {
    return one.getValue() - two.getValue();
}

Однако это действительно только в том случае, если величина диапазона входов меньше 2 ^ 31 .Если больше, разница переполняется.

0 голосов
/ 15 апреля 2014

Я начал задаваться вопросом, был ли весь этот объект артефактом трассировки (я использовал профилирование трассы, а не выборку). В прошлом я видел искажения, вызывающие искажения в тяжелых областях вызова методов. Итак, я сделал тест на прямую синхронизацию: 

public class Sandbox {
    public static void main(String argv[]) {
        long startTime = System.currentTimeMillis();
        sortTest(10000, 10000, new SortMeComp());
        System.err.println("\n"+(System.currentTimeMillis()-startTime));
        startTime = System.currentTimeMillis();
        sortTest(10000, 10000, new SortMeCompTypeless());
        System.err.println("\n"+(System.currentTimeMillis()-startTime));
    }

    public static void sortTest(int n, int l, Comparator<SortMe> c) {
        for(int i=0; i<n; i++) {
            SortMe[] sortMes = new SortMe[l];
            for(int j=0; j<l; j++) {
                sortMes[j] = new SortMe(Math.random());
            }
            System.out.print(sortMes[(int)(Math.random()*l)].getValue());
            Arrays.sort(sortMes, c);
        }
    }
}

Вот результаты: 

[bunch of doubles...]
sortTest(10000, 10000, new SortMeComp()): 18168
[bunch of doubles...]
sortTest(10000, 10000, new SortMeCompTypeless()): 19366

Как видите, типизированный на самом деле работает быстрее, что и следовало ожидать, поскольку он не выполняет приведение. Таким образом, похоже, что разница, которую я видел, была полностью связана с отслеживанием. Моя вера в Hotswap восстановлена!

Кстати, я вставил printlns просто для того, чтобы убедиться, что jvm никак не оптимизирует цикл.

0 голосов
/ 17 мая 2013

Откуда этот метод SortMeComp.compare(Object,Object)? Мы подумали, что это то, что Java создает внутри для работы с дженериками,

Это правильно. Он вставляется компилятором как метод, который вы написали SortMeComp.compare(SortMe one, SortMe two).

...