?

Log in

No account? Create an account

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
Я весьма подробно раскрыл тему стоимости полиморфизма в новой заметке здесь.

  • 1