производительность STL

По наводке - STL vector performance

Выводы неутешительны - std::vector в среднем в 30 (ТРИДЦАТЬ) раз медленнее чем работа с чистым массивом на C (ну либо голом C++ без STL).

Но это только на первый взгляд.

1. Тестирование для STL pre-alloc было не совсем правильным. Нужно использовать reserve.
2. Размер NUM_ITERATIONS имеет значение...
3. Способ реаллокации памяти имеет значение...

Я повторил эти тесты, добавил reserve в код для "STL pre-alloc". А также расширил код, протестировав boost::array и boost::scoped_array.

Также я протестировал для различных значений NUM_ITERATIONS (от 10000 до 150000 с шагом 10000).

Результат (только для Average, CPI)

STL re-alloc  - Average, CPI: 65
C re-alloc    - Average, CPI: 62

STL pre-alloc       - Average, CPI: 10
C pre-alloc         - Average, CPI: 9
boost::array        - Average, CPI: 2
boost::scoped_array - Average, CPI: 10

Забавным здесь является не только то что нет разницы между "STL pre-alloc", "C pre-alloc",boost::array,boost::scoped_array.

Нет заявленной разницы между "STL re-alloc" и "C re-alloc". Я удивился, поскольку предполагал что разница будет... Удивление прошло когда я начал _уменьшать_ значение NUM_ITERATIONS. При NUM_ITERATIONS равном 5000 и меньше возникла разница в 2 раза.

Откуда берется эта разница? Смотрим в реализацию и видим что код реалокации памяти на С++ всегда выделяет новый больший блок памяти, потом копирует туда старый блок. Как по мне это имеет смысл в свете возможности использования vector с не POD типами.

Когда я изменил код реалокации в "C re-alloc" на:

                // Match STL vector allocation algorithm

                int* new_work =  (int *)malloc((size + size / 2) * sizeof(int));

                for ( long c = 0; c < array_size; ++c ) new_work[c] = work[c];

                free(work);

                work = newwork;

                size = size + size / 2;

разница в производительности между "C re-alloc" и "STL re-alloc" исчезла навсегда.

Еще о забавном тестировании производительности - C plus plus:Modern C plus plus:Vectors

Читаем секцию Safe & Fast, много смеемся...

The std::vector version builds its array 256 times larger, and yet is roughly 60 times faster.

Код на "С" с которым они "сравнивали" производительность (фрагмент с реалокацией массива)

void append_to_array(long *&array, long &array_size, long what) {

        long *newarray = new long[array_size+1];

        for ( long i = 0; i < array_size; ++i ) newarray[i] = array[i];

        newarray[array_size] = what;

        delete[] array;

        array = newarray;

        ++array_size;

}

Вывод - если вы работаете с POD типами, хотите работать с динамическим массивом и вам нужна максимальная производительность - пишите на С напишите свою реализацию vector :). А можете просто использовать "reserve".