elizarov


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


Previous Entry Share Next Entry
Алгоритмы + структуры данных = программы или ArrayList vs int[]
elizarov

Алгоритмы + структуры данных = программы. Это классическое изречение Никлауса Вирта, вынесенное им в название книги, нисколько не потеряло своей актуальности, а с развитием объектно-ориентированного программирования даже получило новый смысл. В предыдущей записи я вынес в заголовок утверждение о том, что память это новый диск. В современном мире при дизайне высокопроизводительных приложений очень важную роль играют структуры данных, а именно объем занимаемой ими памяти.

Пример, который я приведу, будет весьма оторван от реальности (что типично для книг и блогов), но проиллюстрирует одну из концепций, благодаря которой ядро QDS, используемое в нашем продукте dxFeed, легко справляется с миллионами котировок в секунду.

Что делать, если всё ваше приложение построено вокруг работы с данными, с большим количеством данных, каждый элемент которых в общем-то не большой и не требует сложной обработки? Первым делом нужно убедиться что именно здесь узкое место вашего продукта, ведь преждевременная оптимизация - корень всех бед.

В предыдущей записи я показал экстремальный пример, когда элемент данных это одно целое число. Даже скорость работы простой итерация по коллекции этих чисел существенно зависит от способа организации данных, от структуры данных. ArrayList<Integer> обогнал LinkedList<Integer> примерно в два раза, ибо в первом элемент занимает 20 байт против 40 байтов во втором (на 32-битной JVM). Чтобы добиться максимальной скорости обработки большого массива данных, надо чтобы эти данные занимали как можно меньше памяти. Для массива целых чисел наиболее подходящая для этого структура это массив целых чисел int[], который тратит ровно 4 байта на каждое целое число.

Объектно-ориентированное программирование наш друг и помощник, который очень очень редко конфликтует с требованиями производительности, поэтому мы инкапсулируем сущность "список целых чисел" в простейший интерфейс IntList, который реализуем без хитростей через ArrayList<Integer> и через int[]:

import java.util.*; 
 
public interface IntList { 
    public int size(); 
    public void add(int value); 
    public int getInt(int index); 
 
    public class ViaArrayList extends ArrayList<Integer> implements IntList { 
        public void add(int value) { 
            super.add(value); 
        } 
 
        public int getInt(int index) { 
            return get(index); 
        } 
    } 
 
    public class ViaJavaArray implements IntList { 
        private int[] array = new int[8]; 
        private int size; 
 
        public int size() { 
            return size; 
        } 
 
        public void add(int value) { 
            if (size >= array.length) 
                array = Arrays.copyOf(array, array.length * 2); 
            array[size++] = value; 
        } 
 
        public int getInt(int index) { 
            if (index < 0 || index >= size) 
                throw new IndexOutOfBoundsException(); 
            return array[index]; 
        } 
    } 
} 

Замерив скорость итерации по этим двум реализациям, получим на моей машине следующие результаты (в наносекундах на одну итерацию):

РазмерViaArrayListViaJavaArray
1 0001.100.37
10 0001.410.40
100 0001.490.44
1 000 0003.080.66
10 000 0003.810.75

Наблюдательный читатель заметит, что в этом тесте ArrayList<Integer> работал чуть быстрей при тех же размерах, чем в прошлый раз. Это объясняется тем, что метод runIteration в прошлый раз использовал конструкцию for-each (которая создает объект Iterator), а в новой версии теста (которую целиком можно найти в файле IntListIterationTiming здесь) он был заменен на цикл по индексу:

    private int runIteration() { 
        int sum = 0; 
        for (int i = 0, n = list.size(); i < n; i++) 
            sum += list.getInt(i); 
        return sum; 
    }

Это напоминает о том, что алгоритм работы с данными все же имеет значение, просто в этом примере он оказывает не такое существенно влияние как структура хранения этих данных.

В целом в этом тесте наглядно видно, что итерация по int[] примерно в 5 раз быстрей итерации по ArrayList<Integer>, что особенно хорошо заметно на размере в 10М элементов, когда никакая из структур уже не влезает в кэш моего процессора. Разница в скорости работы здесь определяется исключительно размером занимаемой памяти (20 байт на число в ArrayList<Integer> против 4 байта на число в int[]).

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

UPDATE: А можно ли сделать быстрей на C++? Читайте дальше.


  • 1
Кстати, о структурах данных... Случайно нарвался на любопытную хрень. Думал даже у себя написать, но тут у тебя явно бОльшее количество "нужных" людей прочитает :)

Дано:

struct point
{
int x,y;
point(int ax, int ay) { x = ax; y = ay; };
point () {};
};

Казалось бы, ничего не предвещает беды. Но выяснилось, что копирование такой структуры превращается в обычное копирование 8 байт одним махом. Что имеем? Имеем код типа

...
point a(, );
...
arr[index]=a;

Т.е. сначала мы на стек в локальную переменную пишем два раза по 4 байта, а потом чуть позже читаем оттуда же все 8 и пишем в другое место.
Если открыть Optimization Guide по любому современному х86-му процу, то увидим там раздел Load-to-Store Forwarding. Что это такое? Это значит, что если мы что-то пишем в память, а потом из этой же памяти читаем, то процессор операцию чтения отработает за 1 такт, просто перекинув данные, которые туда писали, внутри себя. Но, внимательный читатель заметит, что почти весь раздел Optimization Guide'а посвещен как раз таки исключениям, которые не позвонляют этот самый Forwarding сделать. Одно из них - Wide-to-Narrow restriction. А именно, если мы пишем в память что-то маленькое, а потом читаем оттуда же что-то большое, то все. Модуль forwarding'а отключился и работать не может. Более того, такая ситуация отрабатывается через invalidate кеш-линии. Т.е. проц будет ждать, пока первая запись дойдет до памяти, потом заново вытащит эту память в кеш, и только тогда прочитает.
Очевидно, в этом примере я нарвался именно на такой эксепшен. Чтоб победить, я добавил в код структуры operator= для копирования поэлементно. Результат: +2% на всей большой проге, и какие-то дикие разы в конкретном данном месте.
Вывод: не поленитесь проверить, как ваш компилятор сделает копирование маленькой структуры. А лучше просто не поленитесь написать оператор копирования. Для надежности :)

Спасибо. Любопытный пример. Вывод #2 - старайтесь избегать перекладываний из памяти в память там, где важна производительность.

Отож.

Zero copy - вообще ключ к многему счастью.

Ух, как интересно. Спасибо.

здесь, наверное, стоит упомянуть про http://trove.starlight-systems.com/

Я лично не любитель библиотек для оборачивания массивов примитивов (trove не идин такой - если уж упоминать, то все). Они редко нужны на практике (ну кому на самом деле нужен просто список целых чисел?), а уж если и нужны, то с каким-нибудь специфичным фунционалом, который все-равно писать самому.

А что касается остального, то я планирую, например, поделиться способами написания существенно более быстрых хэшей, чем те которые можно найти в готовых библиотеках (уж если нужна скорость, то зачем ограничивать себя скорость которую дает trove?).

Размер, понятное дело, имеет значение.

Но - даже с 0.75ns/item - вы получили чуть больше 5Gb/sec. А должны бы, в теории, упереться в память.

Отсюда вопрос - а bandwidth памяти у вас в машине какая? Ну там по Sisoft Sandra или еще по чему? Должно же быть ну 10Gb/sec хотя бы?

У меня на машине DDR3 работающая на частоте 532 MHz. Это значит, что она выполняет 1064M передач в секунду (по 8 байт за передачу). То есть может теоретически поддерживать скорость передачи в 8.5Gb/sec (то есть мы пока выжали из моей системы ~63% от максимума). Можно ли выжать из неё всю скорость на практике? Я раскрою эту тему в будущем. NOTE: Здесь и выше, 1Gb = 109 байт.



Edited at 2011-11-08 09:12 am (UTC)

В i5 должно быть два канала памяти, хотя не факт что они разведены на ноуте.

Если разведены и заняты все слоты памяти - то, соответственно, лимит должен быть вдвое выше.

У меня два канала, но с ними всё не так просто (как и вообще с максимальной пропускной способностью памяти). вот здесь чувак потратил много времени пытаясь выжать максимум из кода на ассемблере и получил массу не очевидных результатов.

Сколько (и как) реально можно выжать из моей машины? Посмотрим...

Все же не совсем понятно почему итерация по массиву быстрее. Если посмотреть исходный код ArrayList:

public E get(int index) {

RangeCheck(index);
//if (index >= size)
// throw new IndexOutOfBoundsException(
// "Index: "+index+", Size: "+size);

return (E) elementData[index];
}

То что надо считать 2 ссылки вместо одной?
Сам вызов метода get?
Сам вызов метода RangeCheck?
Каст?

Разница в объеме памяти, к который приходится обращаться во время прогона цикла.

  • 1
?

Log in

No account? Create an account