15 февраля 2012 г.

Arrays.sort() через Unsafe

Наблюдая за тем, как Даг Ли в последних версиях FJ активно использует Unsafe для доступа к массивам, мне пришел в голову вопрос: а что будет, если взять реализацию Arrays.sort(), и переписать ее через Unsafe[.arrayBaseOffset(), .arrayIndexScale(), .putXXX(), .getXXX()]? Казалось бы, таким образом можно избавиться от range checks. Да, JIT умеет их и сам убирать -- но лишь тогда, когда может доказать, что конкретный сценарий доступа к массиву эти самые границы гарантированно не нарушает. В сортировке доступ к массиву идет довольно причудливым паттерном, и кажется, что JIT-у вряд ли по силам доказать отсутствие необходимости проверки границ.

Я не поленился -- переписал Arrays.sort(long[]) на прямой доступ. UnsafeArraysSorter.java (у меня все еще 1.6, так что тимсорта не ждите). Прогнал тесты -- и вот фиг вам. Классическая реализация стабильно немного быстрее (+2-3% -- разброс результатов здесь маленький, так что даже такая мелочь вполне заметна).

Сижу теперь, и думаю -- да как же это? Либо JIT в целом умнее, чем я думал, либо он что-то особенное знает об Arrays.sort() :) Второй вариант мне кажется вероятнее. А власти-то -- скрывают!

5 комментариев:

  1. Ну а ты бы не поленился, и посмотрел в assembly тут и там.

    ОтветитьУдалить
  2. Ну если бы у меня был настроен PrintAsm, все было бы проще, да. Я все мечтаю взяться за квест настроить его. Пока немного страшно :) "Тут водятся драконы"

    ...это ж совсем загадок не останется ;)

    ОтветитьУдалить
  3. Я вас умоляю. Настроить hotspot'овский декомпилятор -- дело пяти минут.
    https://wikis.oracle.com/display/HotSpotInternals/PrintAssembly

    ...а там же будет маппинг обратно на джавовый код, который Роман профукает, если будет нативным дебаггером цепляться.

    ОтветитьУдалить
  4. Вот вы все такие умные, небось каждый день по 50 страниц ассемблерных листингов читаете? А я со школы, с 486 с ним не возился. Страшно мне :)

    На самом деле, asm и правда не спасает. На первый взгляд -- код для Arrays и правда содержит проверки границ диапазонов, и прочую ересь, а unsafe код их, соответственно, не содержит. И банально по размеру Arrays-код в разы больше. Однако работает -- быстрее. Феномен :)

    ОтветитьУдалить