оптимизация `std :: vector operator []` (векторный доступ), когда это становится узким местом

Question

gprof говорит, что мое высокопроизводительное приложение тратит 53% своего времени внутри std::vector <...> operator [] (unsigned long), 32% которого идет на один интенсивно используемый вектор.Хуже того, я подозреваю, что мой параллельный код не может масштабироваться выше 3-6 ядер из-за проблем с памятью.Хотя мое приложение тратит много времени на доступ и запись в память, мне кажется, что я должен быть в состоянии (или, по крайней мере, попытаться) работать лучше, чем 52%.Стоит ли вместо этого использовать динамические массивы (в большинстве случаев размер остается постоянным)?Может ли это помочь с возможными узкими местами?

На самом деле, мое предпочтительное решение было бы устранить узкое место и оставить векторы для удобства.Исходя из вышеизложенного, есть ли вероятные виновники или решения (tcmalloc отсутствует)?

Answer 1

Вы изучали сам шаблон доступа к памяти? Это может быть неэффективно - кешировать недружелюбно.

Answer 2

Я подозреваю, что gprof предотвращает включение функций. Попробуйте использовать другой метод профилирования. std::vector operator [] не может быть узким местом, поскольку оно мало отличается от доступа к массиву. Реализация SGI показана ниже:

reference operator[](size_type __n) { return *(begin() + __n); }
iterator begin() { return _M_start; }

Answer 3

Вы пытались использовать необработанный указатель при доступе к массиву?

// regular place

for (int i = 0; i < arr.size(); ++i)
    wcout << arr[i];

// In bottleneck

int *pArr = &arr.front();

for (int i = 0; i < arr.size(); ++i)
    wcout << pArr[i];

Answer 4

Вы не можете доверять gprof для высокоскоростного профилирования кода, вместо этого вы должны использовать пассивный метод профилирования, такой как oprofile, чтобы получить реальное изображение.

В качестве альтернативы вы можете профилировать путем ручного изменения кода(например, вызов вычисления 10 раз вместо одного и проверка увеличения времени выполнения).Обратите внимание, что на это, однако, будут влиять проблемы с кешем, поэтому YMMV.

Answer 5

Класс векторов очень нравится и обеспечивает определенное удобство за счет производительности, что хорошо, когда вам не особенно нужна производительность.

Если вам действительно нужна производительность, вам не будет слишком больно обходить векторный класс и переходить непосредственно к простому старому массиву ручной работы, статически или динамически размещаемому. Затем 1) время, которое вы в настоящее время тратите на индексирование, должно по существу исчезнуть, ускоряя ваше приложение на эту величину, и 2) вы можете перейти к тому, что «следующая важная вещь» занимает время в вашем приложении.

EDIT: Большинство программ имеют гораздо больше возможностей для ускорения, чем вы могли бы предположить. Я сделал сквозной проект , чтобы проиллюстрировать это. Если я могу подвести итог очень быстро, это будет выглядеть так:

• Исходное время составляет 2,7 мсек на «задание» (количество «заданий» можно варьировать, чтобы получить достаточно времени выполнения для его анализа).

• Первый разрез показал, что примерно 60% времени было потрачено на векторные операции, включая индексацию, добавление и удаление. Я заменил на аналогичный векторный класс из MFC, и время сократилось до 1,8 мсек / задание. (Это ускорение в 1,5 или 50%.)

• Даже с этим классом массива примерно 40% времени было потрачено в операторе индексации []. Я хотел, чтобы он индексировался напрямую, поэтому я принудительно индексировал его напрямую, а не через операторную функцию. Это сокращает время до 1,5 мсек / задание, ускорение в 1,2 раза.

• Теперь примерно 60% времени добавляет / удаляет элементы в массивах. Дополнительная фракция была потрачена на «новый» и «удалить». Я решил бросить массивы и сделать две вещи. Один из них заключался в использовании списков «Сделай сам» и для объединения используемых объектов. Первое время сократилось до 1,3 мсек (1,15х). Второй уменьшил его до 0,44 мсек (2,95х).

• С того времени я обнаружил, что около 60% времени было в коде, который я написал для индексирования в списке (как если бы это был массив). Я решил, что это можно сделать, просто указав прямо в список. Результат: 0,14 мсек (3,14х).

• Теперь я обнаружил, что почти все время проводилось в линии диагностического ввода-вывода, которую я печатал на консоли. Я решил избавиться от этого: 0,0037 мсек (38x).

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

То, что я хочу, чтобы вы убрали, - это если вам нужно достаточно плохое исполнение, чтобы отклониться от того, что можно считать принятым способом ведения дел, вам не нужно останавливаться после одного «узкого места». То, что вы получили большое ускорение, не означает, что их больше нет. Фактически, следующее «узкое место» может быть больше, чем первое, с точки зрения фактора ускорения. Так что повысьте свои ожидания в отношении ускорения, которое вы можете получить, и делайте все возможное.