Массивы против контейнеров в задачах матмоделирования

Введение

Так уж сложилось, что моя работа тесно связана с математическим моделированием физических процессов. Математическое моделирование — это совершенно особенная область программирования. Расчет даже относительно простого физического процесса может занимать несколько дней и даже недель. Поэтому на первый план выходит производительность программы, пускай даже в ущерб удобству написания и чтения кода. Однако до недавнего времени быстродействие моих программ меня мало заботило: вполне хватало грубых сеток, для которых расчеты занимали что-то около суток. Но постепенно сетки становились все подробнее, и время работы программ неуклонно росло. Тогда я стал искать узкие места в своей программе. Сначала в алгоритмах. Потом дело дошло до структур данных. И тут меня очень заинтересовал вопрос «а что же лучше использовать для хранения векторов: массивы или контейнеры?» В математическом моделировании операции с векторами и матрицами большой размерности, в частности итерационные методы решения СЛАУ, занимают одну из ключевых позиций. Теоретически, работа с массивами должна быть более быстрой, но работа с контейнерами более удобна. Весь вопрос в том как перевести это «более» в язык цифр? Стоит ли удобство таких затрат? Поиск по интернету внятных ответов так и не дал. Встречались либо расплывчатые формулировки из категории «более-менее», «существенно-несущественно» либо, в лучшем случае, простейшие тесты на многократное повторение одних и тех же действий над элементами вектора. Но тесты это одно, а боевая действительность — совсем другое. Тем более, проведя кое-какие из таких тестов самостоятельно, я с удивлением обнаружил, что на разных тестах преимущество имеют разные структуры данных. Тогда в качестве теста я решил использовать реальную физическую задачу.

Задача

В качестве теста я взял известную в теплофизике задачу о конвективном течении в бесконечно протяженной трубе квадратного сечения заполненной жидкостью и подогреваемой сбоку. Поскольку труба имеет бесконечную протяженность (для определенности — вдоль координаты z) и краевые условия не зависят от z, то задачу можно рассматривать как двумерную. Левая и правая стенки поддерживаются при постоянных, но разных, температурах. Верхняя и нижняя стенки тплоизолированы. На всех стенках заданы условия непротекания и прилипания, т.е. равенство нулю всех компонент скорости. Конвективный теплообмен в жидкости описывается системой уравнений энергии, Навье-Стокса и неразрывности в координатах температура-вихрь-функция тока:
image
Задача решалась методом конечных элементов на треугольной сетке с линейными базисными функциями. Размер секи 100х100 узлов. В качестве решателя СЛАУ использовался ЛОС с LU предобуславливанием.

Исходные коды

Исходные коды программ можно взять здесь.

Результаты тестирования

Итак. Собственно то, для чего все и затевалось. Было написано три программных реализации решения вышеописанной задачи. В качестве языка программирования использовался c++. В первой программе для хранения матриц и векторов использовались динамические массивы, во второй — контейнеры std::vector, в третьей — контейнеры QVector. Времена работы программы (в тиках) предствлены в таблице:
Release
1 2 3 4 5 Среднее Потери времени
Массивы 21820000 21760000 21730000 21660000 21850000 21764000 0%
std::vector 26680000 26660000 26900000 26870000 26790000 26780000 23%
QVector 43760000 43770000 43820000 43840000 43770000 43792000 101%
Debug
1 2 3 4 5 Среднее Потери времени
Массивы 50290000 50630000 50760000 - - 50560000 0%
std::vector 118830000 119560000 118240000 - - 118877000 135%
QVector 306800000 297400000 294400000 - - 299530000 492%

Выводы

Итак, основной вывод по результатам тестирования можно сделать следующий: использование контейнеров недопустимо при решении задач матмоделирования. Никакое удобство написание кода, никакая безопасность кода не могут оправдать падение производительности в 23%. Скажу честно, я не ожидал такого заметного падения. Тем более нериятным сюрпризом для меня стали результаты тестирования QVector'а, ведь имнно его я использовал в своей программе. Такое серьезное отставание по всей видимости объясняется использованием концепции SharedMemory. Экономя на копировании, мы проигроваем на доступе к элементам контейнера, ведь при изменении каждого! элемента происходит дополнительная проверка на необходимость выполнения отложенного копирования.

Бонус: Результаты математического моделирования

Температура:
Функция тока:
Вихрь:
Vx:
Vy:
AdBlock has stolen the banner, but banners are not teeth — they will be back

More
Ads

Comments 80

    +1
    Спасибо!

    Действительно, контейнеры Qt — не то же самое, что и контейнеры STL. Хотя std::vector, говоят, — это просто обертка над обычным C-like массивом. Еще можно было бы испытать QList, по семантике он близок к QVector, но работает по-другому. Я несколько раз встречал, чтобы использовали преимущественно список, а не вектор.
      0
      Есть подозрение, что std::vector при обращении к элементам делает проверку на выход за границу массива.
      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(); }
        0
        > Есть подозрение

        То есть вы не знаете, не потрудились уточнить в спецификации, а делаете такие выводы?

        > использование контейнеров недопустимо при решении задач матмоделирования

        Подскажу: std::vector.operator[] не делает никаких проверок, а .at() делает.

        > shared memory
        Это называется copy-on-write.
        0
        Попробуйте на досуге QArray
          0
          Я так понял, это только в Qt 4.8
        0
        Спасибо за «бонус» :) Завораживают.
          +3
          Поправьте название колонки, все таки на быстродействие стойкая ассоциация «больше — лучше», сначала очень удивился, как это массивы так сливают.
            +2
            Странно это все как-то. А какие операции-то делают с массивами и контейнерами? Потому что различия меджу std::vector и массивами быть не должно про аккуратной с ними работе.
              +1
              И еще вопрос, имеющий касательное отношение — SSE используется?
                0
                Явно — нет. К своему стыду даже не знаю, что это такое. Википедия тоже ясности не внесла. Можете вкратце рассказать?
                  +1
                  Это набор инструкций процессора который позволяет работать с данными суммарной длинной 128 (а сейчас уже есть и AVX с 256 бит), например сразу двумя числами double или четыремя float.
                  Само собой писать на ассемблере не обязательно, можно использовать intrinsic-функции которые оборачивают эти инструкции (или даже сделать класс обертку с перегруженми операторами). Иногда компилятор сам додумывается до оптимизаций с использованием SSE, но почему-то редко.

                0
                Умножение матрицы на вектор, скалярное произведение векторов, сложение и вычитание векторов, умножение вектора на скаляр.
                Но! Есть две структуры данных, которые должны храниться в двумерных массивах. Они никогда не изменяются, но к ним идет активное обращение. Они тоже были реализованы для чистоты эксперимента через std::vector (т.е. получилось std::vector<std::vector>). Возможно, падение скорости получилось таким заметным из-за этого.
                0
                Массивы были объявлены как статические или как динамические?
                И все таки для таких программ больше фортран подходит.
                  0
                  Динамические. Работать со статикой ИМХО — муветон. Либо мы получаем перерасход памяти, выделяя под массивы заведомо значительно больше памяти чем надо, либо рискуем выйти за границы.

                  А в фортране есть стандартные контейнеры (списки и т.д.)? А то я с ним знаком лишь поверхностно и то только со стандартом Фортран'66. А без списков некоторые алгоритмы реализовывать крайне трудно.
                    0
                    Не о 66 фортране речи не идет. Нужно брать компиляторы (например, от intel), которые поддерживают 2003 стандарт и выше. Из стандартных контейнеров только различные виды массивов. Хотя никто не запрещает реализовать собственный функционал.
                    Если хотите поподробнее познакомиться, полистайте книгу А.М. Горелик «Программирование на современном Фортране». Книга нетолстая и написана без воды.
                  0
                  Для задачи с размерность 100х100 результат очевиден: чем проще код тем меньше в нем накладных расходов
                  Совсем другой подход когда для расчетов нужно написать программу для гетерогенного кластера из ~60 нод, и расчет занимает 6-7 месяцев…
                    0
                    Вы std::vector преаллоцировали? Если нет — то всё понятно.
                      0
                      Естественно преаллоцировал. Размер ведь известен.
                        0
                        Тогда там тормозит что-то другое, но не контейнеры, потому что обычный std::vectotor.operator[] в релизе это то же самое, что и обращение к массиву.
                          0
                          Чему-то другому там тормозить очень сложно, т.к. за исключением способа хранения данных программы идентичны.
                            0
                            Посмотрите в вашем STL как реализован operator[]. Какую версию компилятора и ОС вы используете?
                              0
                              g++ 4.4, Linux Mint
                      +1
                      Если кому интересно — приложил к топику исходные коды программ.
                        +1
                        Код такой же, но не совсем. Кроме замены контейнеров, вы заменили тип индексов с int на size_t (последний в 2 раза больше на 64-битной системе). Хотя для случая массивов корректным будет использование int, разницы не будет до тех пор, пока размеры массивов не станут слишком большими.

                        --- 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
                          0
                          У меня 32-х битная система.

                          В исходном варианте кода отказ от 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); }
                          Довольно странное решение.
                            0
                            32-битной системы у меня нигде нет, поэтому ничего не могу сказать по поводу того, что там происходит.
                        0
                        А как std::valarray?
                        А насколько хуже будет, если вектор не проаллоцирован?
                        А если deque?
                        Можете провести такие эксперименты? Было бы очень интересно!
                          0
                          В воскресенье, как раз выходной у меня будет — проверю.
                            +1
                            Итак:
                            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;
                            }
                              0
                              Спасибо, интересно!
                            +1
                            Нелишне указать настройки компилятора. При правильном обращении с std::vector (в частности, как было указано выше, кешировать длину вектора перед циклами) он не должен быть медленнее.
                              +1
                              И, да, для Вашей задачи имеет смысл смотреть в сторону GPU-вычислений: CUDA, OpenCL.
                                +1
                                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
                                0
                                Использую свой класс-обёртку над массивами с переопределённым оператором скобок operator()(ix,iy,iz,it).
                                Оверхед по доступу к элементу по отношению ко времени вычислений в моей задаче ничтожен (проверено профайлером).
                                  +1
                                  Посмотрел на сгенерированный машинный код (-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.
                                    +1
                                    Ещё в догонку по поводу доступа к вектору и массиву:

                                    массив выделяется, например, так
                                    T* p = new T[size];
                                    и компилятор запросто кэширует указатель в регистре, и при использовании p[] ему не нужно лишних телодвижений (просто сложение указателя со смещением, что на x86 поддерживается командами адресации навроде [rcx + rax]).

                                    Вектор сложней по устройству:
                                    class v
                                    {
                                    T* p;
                                    size_t size;
                                    }

                                    то есть при обращении v[], сначала нужно загрузить в регистр адрес объекта v, а потом по смещению выбрать уже адрес массива и индексировать, добавляется лишняя операция.

                                    В тривиальных случаях адреса и объекта и массива размещаются в регистрах (или они загружаются в регистры непосредственно перед циклом) и не надо тратить время на два обращения. Но в более сложных случаях, когда участвуют много векторов сразу — регистров, видимо, не хватает и получается оверхед на получения адреса массива из памяти. Возможно это так же влияет на применимость loop unrolling.
                                      0
                                      Вопрос в том, насколько это всё важно, возможно что это всё мелочи, а потери производительности из-за чего-то совсем другого.
                                      0
                                      И, да, картинки красивые =)
                                      0
                                      Кстати о птичках. Что-то мы совсем забыли об операции/операторе копирования.
                                      Массивы-то копируются через memcpy, быстрее не придумаешь. А вот залез я в оператор копирования std::vector и увидел:
                                      vector&
                                      operator=(vector&& __x)
                                      {
                                      // NB: DR 675.
                                      this->clear();
                                      this->swap(__x);
                                      return *this;
                                      }

                                      Думаю, как раз здесь и идут потери времени.
                                        0
                                        Надо будет на досуге проверить
                                          +3
                                          Это из нового стандарта. Передача владения объектом, а не оператор «копирования». Он то как раз работает очень быстро — просто обменивает массивы содержимым. Сами данные никуда не копируются, конечно.
                                            +2
                                            Обратите внимание на && вместо &, и в гугле поищите «rvalue reference» (если ещё предыдущий коммент не натолкнул на это).
                                              0
                                              Насколько я понял rvalue reference дает выгоду только при работе с временными объектами. В программе же присваивание происходит между постоянными, поименованными объектами. В этом случае происходит (и обязано происходить) глубокое копирование. А теперь прибавляем к этому предварительную очистку вектора-приемника.
                                                +1
                                                Тот код, который вы процитировали, будет вызван только для «умирающих» объектов. Для «живого» объекта будет использован другой оператор присваивания, с параметром const vector& или просто vector (опять же оптимизируется за счёт swap и rvalue reference).
                                            0
                                            У Вас есть ещё наработки по матмоделированию, которые можно было бы положить в основу новых статей? Если да — то обязательно пишите, тема очень интересная!
                                              +2
                                              1) Надеюсь, вы выделяете память для обычных прямоугольных массивов с помощью цикла new для каждой строки исключительно для тестирования и никогда не будете этого делать в реальных приложениях.

                                              2) При работе с одномерным std::vector можно всегда передать в ресурсоёмкую функцию указатель &a[0] и там работать, как с обычным массивом. Так что вывод про std::vector неправилен. Обобщение на std::vector<std::vector <...> > недопустимо.
                                                0
                                                1) А разве как-то можно еще выделить память под динамический прямоугольный массив? И чем это плохо? Ну то что почти наверняка будет фрагментация памяти и невозможность работать с массивом через смещение от начала — это я понимаю. Есть еще какие-то проблемы?

                                                2) А смысл использовать std::vector если все сводится к работе с ним как с обычным массивом?
                                                  0
                                                  1) Использовать плоский массив (для вектора тоже применимо): arr = new int[n*m]; use(a[i + j * n]); Преимущество: меньше нагрузка на аллокатор. Для больших размерностей аллокатор с большей вероятностью посчитает такой массив как large object и не будет его выделять из своих пулов, а сразу вызовет mmap(). (В то время как одна отдельная строка может и не считаться large object)
                                                    0
                                                    В принципе я к этому же пришел. Но поскольку это не совсем удобно, то как раз собирался протестировать сколько это будет давать в производительности в конкретных цифрах и стоит ли оно того.
                                                      +1
                                                      Что значит «не совсем удобно»? Достаточно ведь тонкой обёртки над массивом, например с методом operator()(int i, int j) { return arr[i + j * n]; } чтобы писать v(i,j). Вообще, вам, насколько я понимаю, фактически не нужен std::vector, вы ведь не меняете размер массива, всегда можно сделать более тонкую обёртку и её использовать, всё-таки у std::vector назначение немного другое.

                                                      Прямоугольный массив в виде vector это совсем странно. Вообще, наверняка эффективные реализации двумерных массивов и т.п. можно найти в математических библиотеках, имхо именно там стоит поискать как нужно делать, а возможно и просто взять уже готовое.
                                                        0
                                                        М-да, хабрапарсер как всегда жжот, я имел в виду что vector из vector это совсем странно для прямоугольных массивов.
                                                    +1
                                                    2) Смысл использовать std::vector в данном случае сводится практически к тому, чтобы вручную не работать с памятью. Плюс всяческие проверки в Debug-режиме. Но для этого достаточно и более тонкой обёртки над обычным массивом.
                                                      0
                                                      Хм, я имел в виду абсолютно не скорость работы аллокатора. Обычно память выделяется до начала ресурсоёмких операций и время выделения ничтожно мало по сравнению с временем основного вычисления.

                                                      Я говорю про то, что описано в habrahabr.ru/blogs/hi/111021/, четвёртое правило. Позволю себе процитировать:
                                                      Есть такое свойство локальности ссылок — свойство программ повторно/часто обращаться к одним и тем же объектам; и имеет место временная (temporal) локализация и пространственная (spatial) локализация. Кэширование идет с упреждением, и на этом основании есть смысл обращаться по последовательным адресам, чтобы избежать промахов по кэшу.

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

                                                      2) На уровне пользовательской логики программы — std::vector (например, как член класса MainWindow). Производительность тут не нужна, зато в результате избавляемся от необходимости контроля за выделением памяти и получаем ряд полезных функций типа push_back.
                                                      А на уровне ресурсозатратных функций работаем с голым массивом и не имеем никаких непредвиденных расходов (например, на v.size(), которая в варианте STL от SGI считается как разность указателей на начало и конец).
                                                        0
                                                        А на уровне ресурсозатратных функций работаем с голым массивом и не имеем никаких непредвиденных расходов

                                                        valarray…
                                                          0
                                                          Он при resize переинициализирует все элементы одним и тем же значением. Это не всегда удобно.
                                                    +1
                                                    В новом стандарте появится std::array. Отличие от массива только в проверке на границы.
                                                      +1
                                                      Не думали написать серию статей, посвященых мат. моделированию? Я бы с большим интересом почитал. Думаю, десяток-другой хабрапользователей тоже.
                                                        +2
                                                        А у меня такой глупый вопрос: Вы какой компилятор использовали и какую версию STL? Возможно, у вас Thread Safe реализация. Потому что, насчёт проверки границ… Не понятно, на самом деле. У Вас же проходы по массивам, в основном, линейные. И в этих случаях компилятор с лёгкостью оптимизирует проверки, вынося их из тела цикла. Не должно быть 24 процента.
                                                          0
                                                          Если у вас есть 32-разрядная машина с современным gcc, я бы хотел вас попросить провести тесты. Чуть выше я проводил тест на x86-64 и после приведения кода в точное соответствие друг другу получил разницу меньше 1%.
                                                            0
                                                            Машина есть, но я как-то не специалист по Qt и компиляцию не осилил… Оно мне там выдаёт какие-то странные ошибки насчёт отсутствия функций, но, вроде, в подключенной библиотеке эти функции есть… Поэтому, наверное, это я что-то не так с Qt делаю… А учится — времени нет. Если бы Вы написали, что именно нужно написать в командной строке, чтобы компиляция прошла успешна, я бы провёл тесты.
                                                              0
                                                              apt-get install qt4-dev-tools
                                                              cd arrays_vs_containers && qmake && make
                                                                0
                                                                Результаты в секундах таковы [], vector, qt: 45, 48, 75
                                                                  0
                                                                  Спасибо за тест! Разница в 7%… Какая у вас версия gcc?
                                                                    0
                                                                    gcc version 4.4.4 20100726 (Red Hat 4.4.4-13) (GCC)
                                                                    0
                                                                    Хм… А чего ж оно у меня такую разницу дает? У кого-нибудь есть идеи?
                                                                      0
                                                                      Может, qmake какие-нибудь корявые флаги для компилятора подставляет? Нельзя посмотреть их?
                                                                        0
                                                                        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
                                                                        0
                                                                        От процессора похоже сильно зависит, попробуйте на разных системах запустить.
                                                              +1
                                                              Когда качал исходники, был уверен, что увижу там антипаттерн vector < vector >. Скачал, увидел. Такой код всегда будет тормозным, потому что не способствует кэшированию, в нем много косвенности. Разница между вектором и массивом тут не при чем — код с массивами тоже этим будет страдать.
                                                              Уметь писать cache friendly алгоритмы и структуры данных ученому не нужно. Однако почему-то каждый, кто работает с матрицами уверен, что его программа не проживет без самописного кода LU разложения, переписанного по книжке Численные методы 1982 года (ну или около того), ведь сделать велосипед проще, чем читать английский мануал по LAPACK.

                                                              Что нужно делать — не велосипедить, а использовать библиотеки типа blitz++ или даже cublas, с родными для них структурами данных, чтобы не выделять прямоугольный массив с помощью цикла с new.
                                                                0
                                                                А никто и не велосипедит. У меня специальность «Прикладная математика и информатика». И все ЛОСы, LU разложения и т.д. были когда-то написаны в рамках лабораторных работ.

                                                                На самом деле я не против воспользоваться сторонними библиотеками, но есть несколько требований:
                                                                1) Исчерпывающая и понятная документация, в том числе и математическая
                                                                2) Поддержка g++ и MSVC
                                                                3) Распространение в бинарниках под оба компилятора
                                                                  +1
                                                                  Это и есть велосипеды. Студенту дают фундамент, а не требуют делать многолетнюю работу по вылизыванию стандартных алгоритмов.
                                                                  Вот есть CUBLAS. Ее писали спецы из NVidia, которые знают свое железо досконально. То же с Intel MKL, я думаю. Бенчмарки есть, так что выбрать подходящее можно.
                                                                  Распространение в бинарниках под оба компилятора

                                                                  Функции из dll не инлайнятся, это может быть очень плохим, особенно для всяких мелочей типа operator()(int i, int j) { return arr[i + j * n]; }.
                                                                  Думаю, к тормозам QVector динамическая линковка дает определенный процент.
                                                                    0
                                                                    Хм… Так очень часто этих библиотек недостаточно. Объёмы данных в реальных вычислительных задачах настолько огромные, что надо под каждую надо писать свои хранилища данных, свои схемы их распределения по кластерам и т.д. и т.п. MKL и CUBLAS можно использовать в относительно простых случаях, но они особо никому не интересны. Так что, математик-расчётчик должен разбираться в велосипедах, чтобы перекраивать их под езду по пересечённой местности.
                                                                      +1
                                                                      Я не могу ничего сказать по поводу сфероконей, потому что кода не видел, а int** для двумерного массива у автора видел.
                                                                      0
                                                                      А почему бинарники — это сразу dll? А из статических библиотек компиляторы могут «приинлайнить» функции при линковке. Ну а operator()(int i, int j) — то уж очевидно должна быть инлайном в .h, так что пример неудачный :)
                                                                  0
                                                                  Подобные мелочи должны располагаться в h-файлах. Соответственно ничто не мешает им инлайниться. А вот заморачиваться со сборкой библиотек, особенно под винду удовольствие небольшое.

                                                                  С MKL немного работал. Жутко не понравилась документация. Во-первых ориентирована на фортран, а c++ на уровне отписки, лишь бы было. Во-вторых, математическая часть местами неясна (например форматы матриц). В-третьих, в некоторых функциях смысл параметров из описания далеко не очевиден. К тому же, mkl распространяется не для MCVC компилятора, а для интеловского компилятора, который прикручивается к студии. Но это не одно и тоже.

                                                                  Про CUBLAS ничего сказать не могу. Надо будет поизучать.
                                                                    0
                                                                    CUBLAS под CUDA, вам вряд ли подойдет. Хотя если использовать CUDA, операции с матрицами будут очень быстрыми, хотя с точностью не все так хорошо. Под x86 я использовал boost::ublas, но она не очень шустрая, просто зависимость лишнюю не тянул.
                                                                    Фортрановские библиотеки конечно не удобные, смотрите плюсовые. На википедии есть список, я думаю лучше потратить вечер на выбор подходящей библиотеки, чем спотыкаться об камни типа QVector
                                                                      0
                                                                      Может, тут, кстати, и имеет смысл собрать библиотеки при помощи Clang. И собрать их в LLVM. Link time optimization — крутая штука, которая очень помогает, когда используются библиотеки. Попробуйте.
                                                                      0
                                                                      Итак, подводим итоги недели. Некоторым людям удалось добиться равной производительности массивов и std контейнеров. На моей машине упорно не получается. С изначальных 23% удалось сбросить 7% (половину путем сохранения vector.size() в отдельную переменную, еще половину — путем замены std::vector на std::valarray). В итоге отставание «всего» 14%. Но это по прежнему много.

                                                                      Таким образом, после всех обсуждений, поражение контейнеров уже не представляется таким уж разгромным, но пока все ещё очевидно.
                                                                        0
                                                                        Как и положено математику, арифметику не знаю :)
                                                                        Сбросить удалось 9% (23-14=9)
                                                                        0
                                                                        Статья вышла относительно давно, и я уверен, Вы не стоите на месте, развиваетесь, так что не знаю, насколько актуален будет мой совет. Я также понимаю, что преподавателя не всегда возможно убедить, и если в методичке указано писать на С++, то преподаватель может это потребовать.

                                                                        И всё равно при всём при этом меня сильно удивляет, что Вы решаете сугубо математическую расчётную задачу на С++. Я бы вам советовал ознакомиться со специализированными пакетами/языками, такими как MatLab, Mathematica, Maple (из коммерческих) и Octave, R (из бесплатных). Из перечисленного я пробовал только Octave и остался очень доволен.

                                                                        Работа с векторами, матрицами, скалярами давно уже написана, и написана качественно и быстро. Вам не только не нужно будет реализовывать эти базовые операции самому (понятно, что самому их хотя бы раз в жизни нужно реализовать, чтобы понимать, как работает), но они ещё будут и эффективно работать используя инструкции векторизации (SSE и прочее), параллельное выполнение и возможности GPU (CUDA, OpenCL).

                                                                        Ваш код станет быстрее, при этом сократится в разы, станет проще, понятнее, его станет приятнее писать и отлаживать.

                                                                        Only users with full accounts can post comments. Log in, please.