Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 80
Спасибо!
Действительно, контейнеры Qt — не то же самое, что и контейнеры STL. Хотя std::vector, говоят, — это просто обертка над обычным C-like массивом. Еще можно было бы испытать QList, по семантике он близок к QVector, но работает по-другому. Я несколько раз встречал, чтобы использовали преимущественно список, а не вектор.
Действительно, контейнеры Qt — не то же самое, что и контейнеры STL. Хотя std::vector, говоят, — это просто обертка над обычным C-like массивом. Еще можно было бы испытать QList, по семантике он близок к QVector, но работает по-другому. Я несколько раз встречал, чтобы использовали преимущественно список, а не вектор.
Есть подозрение, что std::vector при обращении к элементам делает проверку на выход за границу массива.
QList теоретически должен быть еще медленнее, чем QVector: во-первых, shared memory никто не отменял, во-вторых, QList не позволяет выделить сразу всю необходимую память, в-третьих, QList хранит объекты простых и сложных типов по разному, что еще более замедляет доступ к его элементам. Сравните:
QList теоретически должен быть еще медленнее, чем QVector: во-первых, shared memory никто не отменял, во-вторых, QList не позволяет выделить сразу всю необходимую память, в-третьих, QList хранит объекты простых и сложных типов по разному, что еще более замедляет доступ к его элементам. Сравните:
template inline T &QVector::operator[](int i)
{ Q_ASSERT_X(i >= 0 && i < d->size, "QVector::operator[]", "index out of range");
return data()[i]; }
template inline T &QList::operator[](int i)
{ Q_ASSERT_X(i >= 0 && i < p.size(), "QList::operator[]", "index out of range");
detach(); return reinterpret_cast<Node *>(p.at(i))->t(); }
> Есть подозрение
То есть вы не знаете, не потрудились уточнить в спецификации, а делаете такие выводы?
> использование контейнеров недопустимо при решении задач матмоделирования
Подскажу: std::vector.operator[] не делает никаких проверок, а .at() делает.
> shared memory
Это называется copy-on-write.
То есть вы не знаете, не потрудились уточнить в спецификации, а делаете такие выводы?
> использование контейнеров недопустимо при решении задач матмоделирования
Подскажу: std::vector.operator[] не делает никаких проверок, а .at() делает.
> shared memory
Это называется copy-on-write.
Попробуйте на досуге QArray
Спасибо за «бонус» :) Завораживают.
Поправьте название колонки, все таки на быстродействие стойкая ассоциация «больше — лучше», сначала очень удивился, как это массивы так сливают.
Странно это все как-то. А какие операции-то делают с массивами и контейнерами? Потому что различия меджу std::vector и массивами быть не должно про аккуратной с ними работе.
И еще вопрос, имеющий касательное отношение — SSE используется?
Явно — нет. К своему стыду даже не знаю, что это такое. Википедия тоже ясности не внесла. Можете вкратце рассказать?
Это набор инструкций процессора который позволяет работать с данными суммарной длинной 128 (а сейчас уже есть и AVX с 256 бит), например сразу двумя числами double или четыремя float.
Само собой писать на ассемблере не обязательно, можно использовать intrinsic-функции которые оборачивают эти инструкции (или даже сделать класс обертку с перегруженми операторами). Иногда компилятор сам додумывается до оптимизаций с использованием SSE, но почему-то редко.
Само собой писать на ассемблере не обязательно, можно использовать intrinsic-функции которые оборачивают эти инструкции (или даже сделать класс обертку с перегруженми операторами). Иногда компилятор сам додумывается до оптимизаций с использованием SSE, но почему-то редко.
Умножение матрицы на вектор, скалярное произведение векторов, сложение и вычитание векторов, умножение вектора на скаляр.
Но! Есть две структуры данных, которые должны храниться в двумерных массивах. Они никогда не изменяются, но к ним идет активное обращение. Они тоже были реализованы для чистоты эксперимента через std::vector (т.е. получилось std::vector<std::vector>). Возможно, падение скорости получилось таким заметным из-за этого.
Но! Есть две структуры данных, которые должны храниться в двумерных массивах. Они никогда не изменяются, но к ним идет активное обращение. Они тоже были реализованы для чистоты эксперимента через std::vector (т.е. получилось std::vector<std::vector>). Возможно, падение скорости получилось таким заметным из-за этого.
Массивы были объявлены как статические или как динамические?
И все таки для таких программ больше фортран подходит.
И все таки для таких программ больше фортран подходит.
Динамические. Работать со статикой ИМХО — муветон. Либо мы получаем перерасход памяти, выделяя под массивы заведомо значительно больше памяти чем надо, либо рискуем выйти за границы.
А в фортране есть стандартные контейнеры (списки и т.д.)? А то я с ним знаком лишь поверхностно и то только со стандартом Фортран'66. А без списков некоторые алгоритмы реализовывать крайне трудно.
А в фортране есть стандартные контейнеры (списки и т.д.)? А то я с ним знаком лишь поверхностно и то только со стандартом Фортран'66. А без списков некоторые алгоритмы реализовывать крайне трудно.
Не о 66 фортране речи не идет. Нужно брать компиляторы (например, от intel), которые поддерживают 2003 стандарт и выше. Из стандартных контейнеров только различные виды массивов. Хотя никто не запрещает реализовать собственный функционал.
Если хотите поподробнее познакомиться, полистайте книгу А.М. Горелик «Программирование на современном Фортране». Книга нетолстая и написана без воды.
Если хотите поподробнее познакомиться, полистайте книгу А.М. Горелик «Программирование на современном Фортране». Книга нетолстая и написана без воды.
Для задачи с размерность 100х100 результат очевиден: чем проще код тем меньше в нем накладных расходов
Совсем другой подход когда для расчетов нужно написать программу для гетерогенного кластера из ~60 нод, и расчет занимает 6-7 месяцев…
Совсем другой подход когда для расчетов нужно написать программу для гетерогенного кластера из ~60 нод, и расчет занимает 6-7 месяцев…
Вы std::vector преаллоцировали? Если нет — то всё понятно.
Если кому интересно — приложил к топику исходные коды программ.
Код такой же, но не совсем. Кроме замены контейнеров, вы заменили тип индексов с int на size_t (последний в 2 раза больше на 64-битной системе). Хотя для случая массивов корректным будет использование int, разницы не будет до тех пор, пока размеры массивов не станут слишком большими.
С одним таким патчем я наблюдаю следующее время:
array: 10610000
std_vector: 10910000
std_vector_mod: 10680000 — отличается от array меньше, чем на 1%
g++ 4.6, x86-64 (это важно, на x86-64 gcc использует SSE для floating point), Debian Sid, Intel i5-750
--- std_vector/main.cpp 2011-06-17 19:06:15.000000000 +0300
+++ std_vector_mod/main.cpp 2011-06-17 23:37:43.000000000 +0300
@@ -151,10 +151,11 @@
void matrixMultByVector(const std::vector<int> &ig, const std::vector<int> &jg, const std::vector<double> &ggl, const std::vector<double> &di,
const std::vector<double> &ggu, const std::vector<double> &vector, std::vector<double> &result)
{
- for(size_t i = 0; i < result.size(); i++)
+ int N = result.size();
+ for(int i = 0; i < N; i++)
result[i] = vector[i]*di[i];
- for(size_t i = 0; i < result.size(); i++)
+ for(int i = 0; i < N; i++)
for(int j = ig[i]; j < ig[i + 1]; j++)
{
result[i] += vector[jg[j]]*ggl[j];С одним таким патчем я наблюдаю следующее время:
array: 10610000
std_vector: 10910000
std_vector_mod: 10680000 — отличается от array меньше, чем на 1%
g++ 4.6, x86-64 (это важно, на x86-64 gcc использует SSE для floating point), Debian Sid, Intel i5-750
У меня 32-х битная система.
В исходном варианте кода отказ от size_t в пользу int наоборот дает дополнительное падение скорости на 1-2%. С помощью предложенного патча (расширенного на всю программу) удалось снизить потери скорости с 23% только лишь до 19%. В любом случае, я не считаю такое решение приемлемым, т.к. заниматься низкоуровневой оптимизацией — это от лукавого. С подобными задачами должен справляться компилятор. Не в пользу std::vector говорит и реализация функии size:
В исходном варианте кода отказ от size_t в пользу int наоборот дает дополнительное падение скорости на 1-2%. С помощью предложенного патча (расширенного на всю программу) удалось снизить потери скорости с 23% только лишь до 19%. В любом случае, я не считаю такое решение приемлемым, т.к. заниматься низкоуровневой оптимизацией — это от лукавого. С подобными задачами должен справляться компилятор. Не в пользу std::vector говорит и реализация функии size:
size_type
size() const
{ return size_type(this->_M_impl._M_finish - this->_M_impl._M_start); }
Довольно странное решение.
А как std::valarray?
А насколько хуже будет, если вектор не проаллоцирован?
А если deque?
Можете провести такие эксперименты? Было бы очень интересно!
А насколько хуже будет, если вектор не проаллоцирован?
А если deque?
Можете провести такие эксперименты? Было бы очень интересно!
В воскресенье, как раз выходной у меня будет — проверю.
Итак:
1) std::vallaray ускоряет решение на 4% по сравнению с std::vector;
Здесь вставлю небольшую ремарку. Два других предложенных для теста варианта абсолютно не подходят для решаемой задачи. Очень странно было бы выбрать для представления n-мерного вектора в вещественном пространстве двустороннюю очередь, почти наверняка разработанную и оптимизированную под другие задачи. И очень странно добавлять циклом n 0-х элементов в вектор, если его размер известен и можно выделить память сразу под все элементы. Но для интереса потестил. Результаты вполне логичные.
2) Без преаллокации идет потеря производительности 2%;
3) С std::deque вообще кошмар. Потеря скорости 1560%. Одна тысяча пятьсот шестьдесят! Тут наверняка дело в дорогом operator[]
1) std::vallaray ускоряет решение на 4% по сравнению с std::vector;
Здесь вставлю небольшую ремарку. Два других предложенных для теста варианта абсолютно не подходят для решаемой задачи. Очень странно было бы выбрать для представления n-мерного вектора в вещественном пространстве двустороннюю очередь, почти наверняка разработанную и оптимизированную под другие задачи. И очень странно добавлять циклом n 0-х элементов в вектор, если его размер известен и можно выделить память сразу под все элементы. Но для интереса потестил. Результаты вполне логичные.
2) Без преаллокации идет потеря производительности 2%;
3) С std::deque вообще кошмар. Потеря скорости 1560%. Одна тысяча пятьсот шестьдесят! Тут наверняка дело в дорогом operator[]
reference
operator[](difference_type __n) const
{ return *(*this + __n); }
_Self&
operator+=(difference_type __n)
{
const difference_type __offset = __n + (_M_cur - _M_first);
if (__offset >= 0 && __offset < difference_type(_S_buffer_size()))
_M_cur += __n;
else
{
const difference_type __node_offset =
__offset > 0 ? __offset / difference_type(_S_buffer_size())
: -difference_type((-__offset - 1)
/ _S_buffer_size()) - 1;
_M_set_node(_M_node + __node_offset);
_M_cur = _M_first + (__offset - __node_offset
* difference_type(_S_buffer_size()));
}
return *this;
}
_Self
operator+(difference_type __n) const
{
_Self __tmp = *this;
return __tmp += __n;
}
Нелишне указать настройки компилятора. При правильном обращении с std::vector (в частности, как было указано выше, кешировать длину вектора перед циклами) он не должен быть медленнее.
И, да, для Вашей задачи имеет смысл смотреть в сторону GPU-вычислений: CUDA, OpenCL.
g++ -c -pipe -O2 -Wall -W -D_REENTRANT -DQT_NO_DEBUG -DQT_CORE_LIB -I/opt/QtSDK/Desktop/Qt/473/gcc/mkspecs/linux-g++ -I../../arrays_vs_containers/qvector -I/opt/QtSDK/Desktop/Qt/473/gcc/include/QtCore -I/opt/QtSDK/Desktop/Qt/473/gcc/include -I. -I../../arrays_vs_containers/qvector -I. -o main.o ../../arrays_vs_containers/qvector/main.cpp
g++ -Wl,-O1 -Wl,-rpath,/opt/QtSDK/Desktop/Qt/473/gcc/lib -o qvector main.o -L/opt/QtSDK/Desktop/Qt/473/gcc/lib -lQtCore -lpthread Дефолтные настройки от qmake
Использую свой класс-обёртку над массивами с переопределённым оператором скобок operator()(ix,iy,iz,it).
Оверхед по доступу к элементу по отношению ко времени вычислений в моей задаче ничтожен (проверено профайлером).
Оверхед по доступу к элементу по отношению ко времени вычислений в моей задаче ничтожен (проверено профайлером).
Посмотрел на сгенерированный машинный код (-Fa -FAs) array и std_vector (release, Microsoft ® C/C++ Optimizing Compiler Version 16.00.40219.01 for x64).
Листинги близки по содержанию, но видно, что в случае std_vector во-первых используется больше переменных в памяти. Во-вторых в array вовсю используется loop unrolling, а в случае с std_vector — нет. В-третьих случае с array адрес массива берётся напрямую из переменной (а некоторые кэшируются непосредственно в регистрах), а в случае в std::vector сначала из переменной считывается адрес объекта vector, а потом уже из памяти, где расположен объект считывается адрес массива (это какбэ очевидно из устройства vector).
Это то, что видно невооружённым взглядом. Думаю, что это проблема оптимизатора, а не, собственно, std::vector (хотя автору всё равно кто виноват, ему результаты нужны, а не подробности работы компилятора =)
Попробовал написать тривиальный пример с std::vector — компилятор оптимизирует один в один с array. Стал его постепенно усложнять (добавлять вложенных циклов и зависимых векторов) и, с определённого момента оптимизатор перестал справляться и начались расхождения с версией array. Затрудняюсь в причинах такого поведения, но факт, так сказать налицо. Оптимизировать шаблонный код сложней чем линейный код в стиле C.
Листинги близки по содержанию, но видно, что в случае std_vector во-первых используется больше переменных в памяти. Во-вторых в array вовсю используется loop unrolling, а в случае с std_vector — нет. В-третьих случае с array адрес массива берётся напрямую из переменной (а некоторые кэшируются непосредственно в регистрах), а в случае в std::vector сначала из переменной считывается адрес объекта vector, а потом уже из памяти, где расположен объект считывается адрес массива (это какбэ очевидно из устройства vector).
Это то, что видно невооружённым взглядом. Думаю, что это проблема оптимизатора, а не, собственно, std::vector (хотя автору всё равно кто виноват, ему результаты нужны, а не подробности работы компилятора =)
Попробовал написать тривиальный пример с std::vector — компилятор оптимизирует один в один с array. Стал его постепенно усложнять (добавлять вложенных циклов и зависимых векторов) и, с определённого момента оптимизатор перестал справляться и начались расхождения с версией array. Затрудняюсь в причинах такого поведения, но факт, так сказать налицо. Оптимизировать шаблонный код сложней чем линейный код в стиле C.
Ещё в догонку по поводу доступа к вектору и массиву:
массив выделяется, например, так
T* p = new T[size];
и компилятор запросто кэширует указатель в регистре, и при использовании p[] ему не нужно лишних телодвижений (просто сложение указателя со смещением, что на x86 поддерживается командами адресации навроде [rcx + rax]).
Вектор сложней по устройству:
class v
{
T* p;
size_t size;
}
то есть при обращении v[], сначала нужно загрузить в регистр адрес объекта v, а потом по смещению выбрать уже адрес массива и индексировать, добавляется лишняя операция.
В тривиальных случаях адреса и объекта и массива размещаются в регистрах (или они загружаются в регистры непосредственно перед циклом) и не надо тратить время на два обращения. Но в более сложных случаях, когда участвуют много векторов сразу — регистров, видимо, не хватает и получается оверхед на получения адреса массива из памяти. Возможно это так же влияет на применимость loop unrolling.
массив выделяется, например, так
T* p = new T[size];
и компилятор запросто кэширует указатель в регистре, и при использовании p[] ему не нужно лишних телодвижений (просто сложение указателя со смещением, что на x86 поддерживается командами адресации навроде [rcx + rax]).
Вектор сложней по устройству:
class v
{
T* p;
size_t size;
}
то есть при обращении v[], сначала нужно загрузить в регистр адрес объекта v, а потом по смещению выбрать уже адрес массива и индексировать, добавляется лишняя операция.
В тривиальных случаях адреса и объекта и массива размещаются в регистрах (или они загружаются в регистры непосредственно перед циклом) и не надо тратить время на два обращения. Но в более сложных случаях, когда участвуют много векторов сразу — регистров, видимо, не хватает и получается оверхед на получения адреса массива из памяти. Возможно это так же влияет на применимость loop unrolling.
И, да, картинки красивые =)
Кстати о птичках. Что-то мы совсем забыли об операции/операторе копирования.
Массивы-то копируются через memcpy, быстрее не придумаешь. А вот залез я в оператор копирования std::vector и увидел:
Думаю, как раз здесь и идут потери времени.
Массивы-то копируются через memcpy, быстрее не придумаешь. А вот залез я в оператор копирования std::vector и увидел:
vector&
operator=(vector&& __x)
{
// NB: DR 675.
this->clear();
this->swap(__x);
return *this;
}Думаю, как раз здесь и идут потери времени.
Надо будет на досуге проверить
Это из нового стандарта. Передача владения объектом, а не оператор «копирования». Он то как раз работает очень быстро — просто обменивает массивы содержимым. Сами данные никуда не копируются, конечно.
Обратите внимание на && вместо &, и в гугле поищите «rvalue reference» (если ещё предыдущий коммент не натолкнул на это).
Насколько я понял rvalue reference дает выгоду только при работе с временными объектами. В программе же присваивание происходит между постоянными, поименованными объектами. В этом случае происходит (и обязано происходить) глубокое копирование. А теперь прибавляем к этому предварительную очистку вектора-приемника.
У Вас есть ещё наработки по матмоделированию, которые можно было бы положить в основу новых статей? Если да — то обязательно пишите, тема очень интересная!
1) Надеюсь, вы выделяете память для обычных прямоугольных массивов с помощью цикла new для каждой строки исключительно для тестирования и никогда не будете этого делать в реальных приложениях.
2) При работе с одномерным std::vector можно всегда передать в ресурсоёмкую функцию указатель &a[0] и там работать, как с обычным массивом. Так что вывод про std::vector неправилен. Обобщение на std::vector<std::vector <...> > недопустимо.
2) При работе с одномерным std::vector можно всегда передать в ресурсоёмкую функцию указатель &a[0] и там работать, как с обычным массивом. Так что вывод про std::vector неправилен. Обобщение на std::vector<std::vector <...> > недопустимо.
1) А разве как-то можно еще выделить память под динамический прямоугольный массив? И чем это плохо? Ну то что почти наверняка будет фрагментация памяти и невозможность работать с массивом через смещение от начала — это я понимаю. Есть еще какие-то проблемы?
2) А смысл использовать std::vector если все сводится к работе с ним как с обычным массивом?
2) А смысл использовать std::vector если все сводится к работе с ним как с обычным массивом?
1) Использовать плоский массив (для вектора тоже применимо): arr = new int[n*m]; use(a[i + j * n]); Преимущество: меньше нагрузка на аллокатор. Для больших размерностей аллокатор с большей вероятностью посчитает такой массив как large object и не будет его выделять из своих пулов, а сразу вызовет mmap(). (В то время как одна отдельная строка может и не считаться large object)
В принципе я к этому же пришел. Но поскольку это не совсем удобно, то как раз собирался протестировать сколько это будет давать в производительности в конкретных цифрах и стоит ли оно того.
Что значит «не совсем удобно»? Достаточно ведь тонкой обёртки над массивом, например с методом
Прямоугольный массив в виде vector это совсем странно. Вообще, наверняка эффективные реализации двумерных массивов и т.п. можно найти в математических библиотеках, имхо именно там стоит поискать как нужно делать, а возможно и просто взять уже готовое.
operator()(int i, int j) { return arr[i + j * n]; } чтобы писать v(i,j). Вообще, вам, насколько я понимаю, фактически не нужен std::vector, вы ведь не меняете размер массива, всегда можно сделать более тонкую обёртку и её использовать, всё-таки у std::vector назначение немного другое.Прямоугольный массив в виде vector это совсем странно. Вообще, наверняка эффективные реализации двумерных массивов и т.п. можно найти в математических библиотеках, имхо именно там стоит поискать как нужно делать, а возможно и просто взять уже готовое.
2) Смысл использовать std::vector в данном случае сводится практически к тому, чтобы вручную не работать с памятью. Плюс всяческие проверки в Debug-режиме. Но для этого достаточно и более тонкой обёртки над обычным массивом.
Хм, я имел в виду абсолютно не скорость работы аллокатора. Обычно память выделяется до начала ресурсоёмких операций и время выделения ничтожно мало по сравнению с временем основного вычисления.
Я говорю про то, что описано в habrahabr.ru/blogs/hi/111021/, четвёртое правило. Позволю себе процитировать:
Это раз. На пятом правиле советую не зацикливаться, поскольку современные компиляторы достаточно неплохо векторизуют работу с блоками по 4 числа, но со стороны программиста необходимо, чтобы эти блоки лежали в памяти последовательно. Это два.
2) На уровне пользовательской логики программы — std::vector (например, как член класса MainWindow). Производительность тут не нужна, зато в результате избавляемся от необходимости контроля за выделением памяти и получаем ряд полезных функций типа push_back.
А на уровне ресурсозатратных функций работаем с голым массивом и не имеем никаких непредвиденных расходов (например, на v.size(), которая в варианте STL от SGI считается как разность указателей на начало и конец).
Я говорю про то, что описано в habrahabr.ru/blogs/hi/111021/, четвёртое правило. Позволю себе процитировать:
Есть такое свойство локальности ссылок — свойство программ повторно/часто обращаться к одним и тем же объектам; и имеет место временная (temporal) локализация и пространственная (spatial) локализация. Кэширование идет с упреждением, и на этом основании есть смысл обращаться по последовательным адресам, чтобы избежать промахов по кэшу.
Это раз. На пятом правиле советую не зацикливаться, поскольку современные компиляторы достаточно неплохо векторизуют работу с блоками по 4 числа, но со стороны программиста необходимо, чтобы эти блоки лежали в памяти последовательно. Это два.
2) На уровне пользовательской логики программы — std::vector (например, как член класса MainWindow). Производительность тут не нужна, зато в результате избавляемся от необходимости контроля за выделением памяти и получаем ряд полезных функций типа push_back.
А на уровне ресурсозатратных функций работаем с голым массивом и не имеем никаких непредвиденных расходов (например, на v.size(), которая в варианте STL от SGI считается как разность указателей на начало и конец).
В новом стандарте появится std::array. Отличие от массива только в проверке на границы.
Не думали написать серию статей, посвященых мат. моделированию? Я бы с большим интересом почитал. Думаю, десяток-другой хабрапользователей тоже.
А у меня такой глупый вопрос: Вы какой компилятор использовали и какую версию STL? Возможно, у вас Thread Safe реализация. Потому что, насчёт проверки границ… Не понятно, на самом деле. У Вас же проходы по массивам, в основном, линейные. И в этих случаях компилятор с лёгкостью оптимизирует проверки, вынося их из тела цикла. Не должно быть 24 процента.
Если у вас есть 32-разрядная машина с современным gcc, я бы хотел вас попросить провести тесты. Чуть выше я проводил тест на x86-64 и после приведения кода в точное соответствие друг другу получил разницу меньше 1%.
Машина есть, но я как-то не специалист по Qt и компиляцию не осилил… Оно мне там выдаёт какие-то странные ошибки насчёт отсутствия функций, но, вроде, в подключенной библиотеке эти функции есть… Поэтому, наверное, это я что-то не так с Qt делаю… А учится — времени нет. Если бы Вы написали, что именно нужно написать в командной строке, чтобы компиляция прошла успешна, я бы провёл тесты.
apt-get install qt4-dev-tools
cd arrays_vs_containers && qmake && make
cd arrays_vs_containers && qmake && make
Результаты в секундах таковы [], vector, qt: 45, 48, 75
Спасибо за тест! Разница в 7%… Какая у вас версия gcc?
Хм… А чего ж оно у меня такую разницу дает? У кого-нибудь есть идеи?
Может, qmake какие-нибудь корявые флаги для компилятора подставляет? Нельзя посмотреть их?
g++ -c -pipe -O2 -Wall -W -D_REENTRANT -DQT_NO_DEBUG -DQT_CORE_LIB -I/opt/QtSDK/Desktop/Qt/473/gcc/mkspecs/linux-g++ -I../../arrays_vs_containers/std_vector -I/opt/QtSDK/Desktop/Qt/473/gcc/include/QtCore -I/opt/QtSDK/Desktop/Qt/473/gcc/include -I. -I../../arrays_vs_containers/std_vector -I. -o main.o ../../arrays_vs_containers/std_vector/main.cpp
g++ -Wl,-O1 -Wl,-rpath,/opt/QtSDK/Desktop/Qt/473/gcc/lib -o std_vector main.o -L/opt/QtSDK/Desktop/Qt/473/gcc/lib -lQtCore -lpthread От процессора похоже сильно зависит, попробуйте на разных системах запустить.
Когда качал исходники, был уверен, что увижу там антипаттерн vector < vector >. Скачал, увидел. Такой код всегда будет тормозным, потому что не способствует кэшированию, в нем много косвенности. Разница между вектором и массивом тут не при чем — код с массивами тоже этим будет страдать.
Уметь писать cache friendly алгоритмы и структуры данных ученому не нужно. Однако почему-то каждый, кто работает с матрицами уверен, что его программа не проживет без самописного кода LU разложения, переписанного по книжке Численные методы 1982 года (ну или около того), ведь сделать велосипед проще, чем читать английский мануал по LAPACK.
Что нужно делать — не велосипедить, а использовать библиотеки типа blitz++ или даже cublas, с родными для них структурами данных, чтобы не выделять прямоугольный массив с помощью цикла с new.
Уметь писать cache friendly алгоритмы и структуры данных ученому не нужно. Однако почему-то каждый, кто работает с матрицами уверен, что его программа не проживет без самописного кода LU разложения, переписанного по книжке Численные методы 1982 года (ну или около того), ведь сделать велосипед проще, чем читать английский мануал по LAPACK.
Что нужно делать — не велосипедить, а использовать библиотеки типа blitz++ или даже cublas, с родными для них структурами данных, чтобы не выделять прямоугольный массив с помощью цикла с new.
А никто и не велосипедит. У меня специальность «Прикладная математика и информатика». И все ЛОСы, LU разложения и т.д. были когда-то написаны в рамках лабораторных работ.
На самом деле я не против воспользоваться сторонними библиотеками, но есть несколько требований:
1) Исчерпывающая и понятная документация, в том числе и математическая
2) Поддержка g++ и MSVC
3) Распространение в бинарниках под оба компилятора
На самом деле я не против воспользоваться сторонними библиотеками, но есть несколько требований:
1) Исчерпывающая и понятная документация, в том числе и математическая
2) Поддержка g++ и MSVC
3) Распространение в бинарниках под оба компилятора
Это и есть велосипеды. Студенту дают фундамент, а не требуют делать многолетнюю работу по вылизыванию стандартных алгоритмов.
Вот есть CUBLAS. Ее писали спецы из NVidia, которые знают свое железо досконально. То же с Intel MKL, я думаю. Бенчмарки есть, так что выбрать подходящее можно.
Функции из dll не инлайнятся, это может быть очень плохим, особенно для всяких мелочей типа operator()(int i, int j) { return arr[i + j * n]; }.
Думаю, к тормозам QVector динамическая линковка дает определенный процент.
Вот есть CUBLAS. Ее писали спецы из NVidia, которые знают свое железо досконально. То же с Intel MKL, я думаю. Бенчмарки есть, так что выбрать подходящее можно.
Распространение в бинарниках под оба компилятора
Функции из dll не инлайнятся, это может быть очень плохим, особенно для всяких мелочей типа operator()(int i, int j) { return arr[i + j * n]; }.
Думаю, к тормозам QVector динамическая линковка дает определенный процент.
Хм… Так очень часто этих библиотек недостаточно. Объёмы данных в реальных вычислительных задачах настолько огромные, что надо под каждую надо писать свои хранилища данных, свои схемы их распределения по кластерам и т.д. и т.п. MKL и CUBLAS можно использовать в относительно простых случаях, но они особо никому не интересны. Так что, математик-расчётчик должен разбираться в велосипедах, чтобы перекраивать их под езду по пересечённой местности.
А почему бинарники — это сразу dll? А из статических библиотек компиляторы могут «приинлайнить» функции при линковке. Ну а operator()(int i, int j) — то уж очевидно должна быть инлайном в .h, так что пример неудачный :)
Подобные мелочи должны располагаться в h-файлах. Соответственно ничто не мешает им инлайниться. А вот заморачиваться со сборкой библиотек, особенно под винду удовольствие небольшое.
С MKL немного работал. Жутко не понравилась документация. Во-первых ориентирована на фортран, а c++ на уровне отписки, лишь бы было. Во-вторых, математическая часть местами неясна (например форматы матриц). В-третьих, в некоторых функциях смысл параметров из описания далеко не очевиден. К тому же, mkl распространяется не для MCVC компилятора, а для интеловского компилятора, который прикручивается к студии. Но это не одно и тоже.
Про CUBLAS ничего сказать не могу. Надо будет поизучать.
С MKL немного работал. Жутко не понравилась документация. Во-первых ориентирована на фортран, а c++ на уровне отписки, лишь бы было. Во-вторых, математическая часть местами неясна (например форматы матриц). В-третьих, в некоторых функциях смысл параметров из описания далеко не очевиден. К тому же, mkl распространяется не для MCVC компилятора, а для интеловского компилятора, который прикручивается к студии. Но это не одно и тоже.
Про CUBLAS ничего сказать не могу. Надо будет поизучать.
CUBLAS под CUDA, вам вряд ли подойдет. Хотя если использовать CUDA, операции с матрицами будут очень быстрыми, хотя с точностью не все так хорошо. Под x86 я использовал boost::ublas, но она не очень шустрая, просто зависимость лишнюю не тянул.
Фортрановские библиотеки конечно не удобные, смотрите плюсовые. На википедии есть список, я думаю лучше потратить вечер на выбор подходящей библиотеки, чем спотыкаться об камни типа QVector
Фортрановские библиотеки конечно не удобные, смотрите плюсовые. На википедии есть список, я думаю лучше потратить вечер на выбор подходящей библиотеки, чем спотыкаться об камни типа QVector
Может, тут, кстати, и имеет смысл собрать библиотеки при помощи Clang. И собрать их в LLVM. Link time optimization — крутая штука, которая очень помогает, когда используются библиотеки. Попробуйте.
Итак, подводим итоги недели. Некоторым людям удалось добиться равной производительности массивов и std контейнеров. На моей машине упорно не получается. С изначальных 23% удалось сбросить 7% (половину путем сохранения vector.size() в отдельную переменную, еще половину — путем замены std::vector на std::valarray). В итоге отставание «всего» 14%. Но это по прежнему много.
Таким образом, после всех обсуждений, поражение контейнеров уже не представляется таким уж разгромным, но пока все ещё очевидно.
Таким образом, после всех обсуждений, поражение контейнеров уже не представляется таким уж разгромным, но пока все ещё очевидно.
Статья вышла относительно давно, и я уверен, Вы не стоите на месте, развиваетесь, так что не знаю, насколько актуален будет мой совет. Я также понимаю, что преподавателя не всегда возможно убедить, и если в методичке указано писать на С++, то преподаватель может это потребовать.
И всё равно при всём при этом меня сильно удивляет, что Вы решаете сугубо математическую расчётную задачу на С++. Я бы вам советовал ознакомиться со специализированными пакетами/языками, такими как MatLab, Mathematica, Maple (из коммерческих) и Octave, R (из бесплатных). Из перечисленного я пробовал только Octave и остался очень доволен.
Работа с векторами, матрицами, скалярами давно уже написана, и написана качественно и быстро. Вам не только не нужно будет реализовывать эти базовые операции самому (понятно, что самому их хотя бы раз в жизни нужно реализовать, чтобы понимать, как работает), но они ещё будут и эффективно работать используя инструкции векторизации (SSE и прочее), параллельное выполнение и возможности GPU (CUDA, OpenCL).
Ваш код станет быстрее, при этом сократится в разы, станет проще, понятнее, его станет приятнее писать и отлаживать.
И всё равно при всём при этом меня сильно удивляет, что Вы решаете сугубо математическую расчётную задачу на С++. Я бы вам советовал ознакомиться со специализированными пакетами/языками, такими как MatLab, Mathematica, Maple (из коммерческих) и Octave, R (из бесплатных). Из перечисленного я пробовал только Octave и остался очень доволен.
Работа с векторами, матрицами, скалярами давно уже написана, и написана качественно и быстро. Вам не только не нужно будет реализовывать эти базовые операции самому (понятно, что самому их хотя бы раз в жизни нужно реализовать, чтобы понимать, как работает), но они ещё будут и эффективно работать используя инструкции векторизации (SSE и прочее), параллельное выполнение и возможности GPU (CUDA, OpenCL).
Ваш код станет быстрее, при этом сократится в разы, станет проще, понятнее, его станет приятнее писать и отлаживать.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Массивы против контейнеров в задачах матмоделирования