elizarov


Блог Романа Елизарова


Previous Entry Share Next Entry
Оптимизация важна или ByteBuffer vs int[]
elizarov

В серии записей, начатых с заголовка "Память это новый диск", я в цифрах показал, что производительность структур данных определяется в первую очередь объемом занимаемой ими памяти, а точнее объемом памяти которую нужно просмотреть при выполнения нужной нам операции. Может показаться, что оптимизации кода нет места в этом мире быстрых процессоров и медленной памяти, но это конечно не так.

В своих примерах я очень аккуратно выбирал тестовый код, добиваясь почти оптимального выполнения для той или иной структуры данных. В наиболее оптимальном варианте структуры данных для списка целых чисел — массиве целых чисел, мы видели оптимальный SISD ассемблерный код для сложения чисел в этом списке — одну инструкция на элемент. Это значит, что время выполнения точно соответствовало объему памяти при прочих равных — при оптимальном коде для соответствующих структур данных. Если же код написан не оптимально или используемый компилятор не может его оптимально преобразовать в ассемблерные инструкции, то и производительность будет далека от оптимума.

Рассмотрим в качестве примера интересную альтернативу массивам примитивных чисел на Java — класс ByteBuffer. Этот класс очень привлекателен тем, что во-первых позволяет в одном массиве данных смешивать разные типы данных, а во вторых позволяет выделять память за пределами обычной кучи языка Java, используя так называемые прямые буфера (direct buffers). Эти уникальные свойства и задают основной круг применения класса ByteBuffer: сериализация разнородных данных, хранение кэшей в памяти за пределами кучи и т.п. Так же, работа с неблокирующим вводом выводом и, в частности, с отображениями файлов в память возможна в языке Java только через класс ByteBuffer.

Чтобы понять стоимость использования класса ByteBuffer с точки зрения оптимального кода, напишем реализацию списка целых чисел через ByteBuffer:

    public class ViaByteBuffer1 implements IntList { 
        private ByteBuffer buf = ByteBuffer.allocateDirect(32); 
        private int size; 
 
        public int size() { 
            return size; 
        } 
 
        public void add(int value) { 
            if (buf.position() >= buf.capacity()) { 
                ByteBuffer larger = ByteBuffer.allocateDirect(buf.capacity() * 2); 
                buf.rewind(); 
                larger.put(buf); 
                buf = larger; 
            } 
            buf.putInt(value); 
            size++; 
        } 
 
        public int getInt(int index) { 
            if (index < 0 || index >= size) 
                throw new IndexOutOfBoundsException(); 
            return buf.getInt(index * 4); 
        } 
    }

Проведем тест на скорость сложения разного количества случайных элементов добавленных в этот список, в сравнении со списком поверх массива целых чисел. В таблице показано время на отдну итерацию в наносекундах при разных размерах списка.

РазмерViaByteBuffer1ViaJavaArray
1 0001.030.37
10 0001.030.40
100 0001.080.44
1 000 0001.200.66
10 000 0001.220.75

Видно, что реализация через ByteBuffer заметно медленней, чем реализация через int[]. Даже при 10M элементах, где доступ к памяти должен доминировать (ибо 40МБ данных уже совсем не влезают в кэш процессора), ByteBuffer работает на 60% медленней. А при маленьком размере (когда все данные лежат в кэше) почти в 3 раза медленней. Почему это происходит?

Первая и очевидная проблема заключается в том, что метод ByteBuffer.putInt кладет байты в определенном порядке. По умолчанию используется сетевой порядок — наиболее значимый байт идет первым. В то время как для платформы x86 естественным является порядок, когда наименее значимый байт идет первым.

Именно необходимость переставлять байты для арифметических операций (арифметика в x86 умеет работать только с естественным для неё порядком байт) и отнимает основное дополнительное время. В данном случае, память уже не является единственным узким местом. Благодаря аппаратной предзагрузке, данные оказываются в кэше процессора заранее, а вот работа с ними превращается в набор нетривиальных операций. Да и для оптимизатора такой код не очень прозрачен.

Поменяем используемый в нашем тесте ByteBuffer, меняя порядок на естественный порядок, сразу после его создания (полный код здесь).

        private static ByteBuffer allocate(int size) { 
            ByteBuffer buf = ByteBuffer.allocateDirect(size); 
            buf.order(ByteOrder.nativeOrder()); 
            return buf; 
        }

Результаты становятся существенно лучше:

РазмерViaByteBuffer2 (native order)ViaJavaArray
1 0000.770.37
10 0000.770.40
100 0000.860.44
1 000 0000.910.66
10 000 0000.940.75

Однако, все равно видно что работа с ByteBuffer не настолько хорошо оптимизируется, как прямая работа с int[]. Если данные лежат в кэше, то видим проигрыш в скорости работы примерно в два раза. Собственно, это и является основным контраргументом, который надо учитывать используя ByteBuffer для решения той или иной задачи. Для некоторых задач эта разница в производительности будет не важна, а для других наоборот критична. Выбор (если он есть) можно сделать только проведя замеры с учетом специфики решаемой задачи.

UPDATE: А что будет если заменить прямой буфер (direct buffer), выделяемый методом ByteBuffer.allocateDirect, на буфер в куче, выделяемый методом ByteBuffer.allocate, вы можете прочитать в следующей записи.


  • 1
Ну и еще небольшой оверхед на вызовы методов в версии с ByteBuffer. Думаю, если работать с памятью напрямую через Unsafe будет как и с array.

Оверхеда нет. Всё инлайнится. И DirectByteBuffer именно через unsafe работает.

Еще allocateDirect подороже будет чем Arrays.copyOf. А остальных причин не вижу.

Можете сами посмотреть на результирующий код и увидеть конкретно в чем причины такой разницы во времени. Не любопытно?

Хотя, по сути, если не вдаваться в детали, я уже дал исчерпывающий ответ прямо в посте: "работа с ByteBuffer не настолько хорошо оптимизируется, как прямая работа с int[]".

Хм, на моем Air (Core Duo 2, Lion, Jdk 6) ViaByteBuffer1 работает быстрее ViaByteBuffer2, и оба в 10-12 раз медленнее, чем ViaJavaArray. Кстати, если выполнять оба теста за прогон (передать ViaJavaArray ViaByteBuffer1 в качестве параметров), то они существенно медленнее работают, ViaJavaArray так проседает в 6 раз. Возможно тема стоимости полиморфизма в горячем коде требует исследования.

Зная специфику Вашей профессиональной деятельности, подозреваю что Вы проводите тесты под Client HotSpot VM. Я же всегда в первую очередь тестирую под Server ("java -server") — профессиональная деформация, в том числе и для этого цикла заметок.

Что касается темы полиморфизма, то я специально написал тестовый код так, чтобы можно было гонять несколько тестов за раз, так как я планирую глубоко раскрыть тему полиморфизма и производительности в одной из будущих заметок. Для повторения результатов этой заметки очень важно запускать каждый тест по отдельности.

-server я указал, а еще под Маком начиная с некоторого момента все выполняется по умолчанию под 64 бит jdk, соответственно -server автоматически.

Я совсем упустил из виду тот факт, что Вы под Jdk 6 это запускаете. Он намного хуже оптимизирует код метода getInt в direct ByteBuffer. Я бы даже сказал, что он вообще его не оптимизирует, то есть тупо выполняет всё то, что там написано (а там много понаписано). В то время как Jdk 7 умеет полностью устранить даже "ручками" написанный код проверки границ (метод checkIndex) и сделать не сильно отличающийся от работы с массивом код. Соответственно, на фоне такой слабой оптимизации дополнительное переворачивание байтов, которое выполняет ViaByteBuffer1 по сравнению с ViaByteBuffer2, уже не сильно заметно.

B+HTree, now powering IntelliJ IDEA 11 indices

Если бы все было так просто :), на Open JDK 1.7_b220 64 bit Server все еще на 1-2 ns медленнее. Возможно дело в 64 бит JDK...

Re: B+HTree, now powering IntelliJ IDEA 11 indices

На 1-2 нс медленней чем у меня или на 1-2 нс медленней чем int[]?

Open JDK прям сейчас под рукой у меня нет чтобы проверить (а на 1.6 я проверил и в ассемблер заглянул — всё так как я написал). Результаты в этой статье получены под 1.7.0_01. Сейчас у меня 1.7.0_02 (build 1.7.0_02-b13), Java HotSpot(TM) Server VM (build 22.0-b10, mixed mode) — результаты те же.

Можете сами под отладчиком посмотреть какой код там получается? Чисто теоретически, эти конкретно оптимизации от 64/32 VM не должны зависеть (они происходят на уровне промежуточного представления). Может дело в Open JDK (там их просто нет?).

ViaByteBuffer2 OpenJDK 1.7_b220 64bit выполняет на 1-2ns медленнее, чем для Apple JDK 1.6 64 bit (9.5-10.5 ns vs 6.5ns), ViaByteBuffer1 (8.2-8.5 OpenJDK7 ns vs 4.5-5ns)
Занятно, что проблема оказалась в 64бит JDK: если выполнять под 32bit (-d32 -server), то результаты будут ожидаемые (как в посте и сравнимы с ViaJavaArray): ViaByteBuffer2 0.6-1ns (Open Jdk 7) vs 7.5-8ns (Apple JDK 6), ViaByteBuffer1 1.3-1.6ns (Open JDK 7) vs 4-4.2ns (AppleJDK 7)

ЗЫ Извиняюсь за заголовок ответа, вышло случайно :)

Спасибо. Действительно занятно. Вообще, 64бит vs 32бит на x86 это очень плодотворная и интересная тема — у меня есть несколько своих баек на этот счет. Как-нибудь напишу на эту тему отдельную запись, пока это вообще всё актуально (всё идет к тому, что 32бит скоро вымрут).

Я весьма подробно раскрыл тему стоимости полиморфизма в новой заметке здесь.

  • 1
?

Log in

No account? Create an account