Какое снижение производительности при использовании std :: vector в C ++?
Как правило, мне интересно знать, несет ли стандартная библиотека шаблонов издержки производительности / скорости в кодах для численных / научных вычислений.
Например,
Объявляет массив как
double 2dmatrix [10][10]
собирается дать мне больше производительности, чем
std::vector<std::vector<double> > 2dmatrix(10,std::vector<double>(10,0.0))
?
Я также был бы признателен за некоторые общие идеи относительно того, имеет ли C лучшую производительность, чем C ++ для научных вычислений. Я написал свои коды в очень объектно-ориентированном стиле с использованием STL и C ++ 11. Я начинаю задумываться о том, стоит ли мне начинать изучать чистый C, будет ли он работать быстрее.
Любые мысли по этому поводу приветствуются.
Решение
Учитывая абстракцию это обеспечивает, C ++ std::vector настолько эффективен, насколько это возможно: 3 указателя в стеке и динамически распределяемые данные, которые в среднем выполняют 1 перераспределение на элемент в сценарии линейного роста (поскольку изменение размера увеличивает емкость более чем пропорционально, в 1,5-2 раза).
С эквивалент с использованием malloc() а также realloc() будет по крайней мере столь же дорогим и более громоздким (ручное изменение размера и т. д.). Кроме того, std::vector позволяет пользовательская настройка производительности через специальные распределители (на основе пула, с выделением стека и т. д.), которые в C ++ 11 не так сложны в использовании, как в C ++ 98.
Если вам не нужно динамическое изменение размера, вы можете кодировать как в C, так и в C ++ статический массив (или std::array в C ++).
В общем, для высокопроизводительных вычислений, C ++ имеет больше возможностей для оптимизации, в частности, за счет использования функциональных объектов, которые могут быть встроены (в отличие от обычных указателей на функции C). каноническим примером является сортировка
int comp( const void* a, const void* b ) {
return /* your comparison here */;
}
// C style sorting
qsort( arr, LARGE_SIZE, sizeof( int ), comp );
^^^^ <---- no-inlining through function pointer
// C++11 style sorting (use hand-made function object for C++98
std::sort(std::begin(arr), std::end(arr), [](auto a, auto b) {
return comp(&a, &b);
^^^^ <----- C++11 lambdas can be fully inlined
});
Другие решения
Издержки std :: vector:
- 3 указателя в стеке
- динамическое распределение (лениво, то есть ничего не выделяется, пока не потребуется)
Выделенный в стек массив может быть быстрее в некоторых случаях (для небольших объемов данных). Для этого вы можете использовать std::array<T, Length>,
Если вам нужна двумерная сетка, я бы разместил данные в одном векторе: std::vector<T>(width * height);, Затем вы можете написать ряд вспомогательных функций для получения элементов по координатам x и y. (Или вы можете написать класс оболочки.)
Если вы знаете размеры заранее и производительность является узким местом — используйте std::array из C ++ 11. Его производительность точно такая же, как у массивов в стиле C, потому что внутренне это выглядит
template<typename T, int N>
struct array {
T _data[N];
};
Это предпочтительный способ использования массивов, выделенных в стеке, в современном C ++. Никогда не используйте массивы в стиле C, если у вас есть современный компилятор.
Если у вас нет причин изменять размер массива и вы знаете его размер во время компиляции (как вы это делали в первом примере), лучшим выбором для шаблонов STL будет std::array шаблон. Он предоставляет вам все те же преимущества массива в стиле C.
double 2dmatrix[10][10];
// would become
std::array<std::array<double, 10>, 10> 2dmatrix;
Люди скажут: «Это зависит от того, что вы делаете».
И они правы.
Там есть пример Вот где традиционно разработанная программа, использующая std::vector была настроена производительность через серию из шести этапов, и время ее выполнения было сокращено с 2700 микросекунд на единицу работы до 3,7 при коэффициенте ускорения 730x.
Первое, что нужно было сделать, — это заметить, что большой процент времени уходит на выращивание массивов и удаление из них элементов.
Таким образом, был использован другой класс массива, который значительно сократил время.
Второе, что нужно было сделать, — это заметить, что большой процент времени все еще уходит на связанные с массивами действия.
Таким образом, массивы были полностью удалены, и вместо них использовались связанные списки, что привело к еще большему ускорению.
Тогда другие вещи использовали большой процент оставшегося времени, такие как newи deleteИнг
Затем эти объекты были переработаны в свободные списки, что привело к еще большему ускорению.
После еще нескольких этапов было принято решение прекратить попытки, потому что становилось все труднее находить вещи для улучшения, и ускорение было сочтено достаточным.
Дело в том, не просто выбрать что-то, что настоятельно рекомендуется, а затем надеяться на лучшее.
Скорее, построите его так или иначе, а затем выполните настройку производительности, как этот, и будьте готовы внести серьезные изменения в дизайн вашей структуры данных, исходя из того, на что вы тратите большой процент времени.
А также повторить это.
Вы можете изменить схему хранения с A на B, а затем с B на C.
Это совершенно нормально.
В научных вычислениях ошибки и неоптимальный код особенно расстраивают, потому что большие объемы данных неправильно обрабатываются, а драгоценное время тратится впустую.
std::vector может быть вашим узким местом или вашим лучшим исполнителем в зависимости от ваших знаний о его внутренней работе. Обратите особое внимание на reserve(), insert(), erase(); подумайте об изучении выравнивания и кэширования процессора, если ваша программа имеет многопоточность
Подумайте о том, сколько времени вам придется потратить на обеспечение согласованности — а потом и на поиск ошибок — если вы попытаетесь все управлять памятью самостоятельно, особенно когда вы постепенно добавляете функции в свое программное обеспечение. В конце концов, издержки std :: vector будут наименьшей из ваших проблем.
Для научных вычислений вам будет гораздо лучше использовать специализированную матричную библиотеку C ++, такую как броненосец. Это не только дает вам быструю обработку массива, но и много операций линейной алгебры, которые были тщательно отлажены.
Помимо соображений производительности, использование выделенной библиотеки матриц C ++ также позволит вам значительно снизить детализацию вашего кода, сделать меньше ошибок и, следовательно, ускорить разработку. Одним из примеров является то, что с матричной библиотекой C ++ вам не нужно беспокоиться об управлении памятью.
Наконец, если вам действительно нужно перейти на низкий уровень (т. Е. Использовать память напрямую через указатели), C ++ позволяет вам «опуститься» до уровня C. В Armadillo это делается через .memptr () функция-член.