Как лучше быстро заполнить вектор?

Question

У меня есть код для симуляции, над которым я работаю, и я только что избавился от всех низко висящих фруктов, что касается оптимизации. Код теперь тратит половину своего времени на перемещение векторов назад. (Размер конечных векторов известен, и я зарезервирую соответственно)

По сути, я переставляю один вектор в перестановку другого или заполняю вектор случайными элементами.

Есть ли более быстрые способы отодвинуться назад в вектор? Или отталкивание / копирование нескольких элементов?

std::vector<unsigned int, std::allocator<unsigned int> >::push_back(unsigned int const&)

Заранее спасибо.

РЕДАКТИРОВАТЬ: Дополнительная информация; Я также запускаю сборку релиза с -O3: необходимо сохранить оригинальный вектор.

Answer 1

Вы можете взглянуть на

• c ++ 0x (что позволяет много оптимизаций в этой области в концепции move semantics)
• EASTL (которая имеет превосходную производительность, в основном благодаря использованию пользовательских распределителей (_Вы можете запустить его примерно через час, и единственным видимым изменением будет std::vector -> eastl::vector и некоторые дополнительные объекты ссылок).
• вы можете зайти в google perftools tcmalloc (хотя, очевидно, вы уже оптимизировали с помощью предварительного выделения, это не должно иметь большого значения).

Лично я бы не ожидал большого выигрыша, если на самом деле обработка векторов является узким местом. Я бы действительно посмотрел на распараллеливание с (в порядке предпочтения):

• GNU openmp (CPPFLAGS+=-D_GLIBCXX_PARALLEL -fopenmp)
• просто openmp и 'manual' #pragma parallel for
• Intel TBB (наиболее уместно при использовании компилятора Intel)

Должно быть, я забыл вещи. О да, смотри здесь: http://www.agner.org/optimize/

Редактировать : Я всегда забываю самые простые вещи: используйте memcpy / memmove для массового добавления POD-элементов к предварительно выделенным векторам.

Answer 2

Если вы предварительно резервируете пространство, тогда ваш вектор будет работать так же быстро, как и массив. Вы не можете математически сделать это быстрее; перестань беспокоиться и переходи к чему-то другому!

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

Answer 3

push_back на int чрезвычайно эффективно.Поэтому я бы искал возможности для оптимизации в других местах.

Первое правило микрооптимизации Nemo: математика - это быстро;память медленнаяСоздание огромного вектора очень неудобно для кэша.

Например, вместо создания перестановки исходного вектора, вы можете просто вычислить, какой элемент вам нужен , как вам нужно , и затем получить доступэтот элемент непосредственно из исходного вектора?

Точно так же, вам действительно нужен вектор случайных целых чисел?Почему бы просто не генерировать случайное число , когда оно необходимо ?(Если вам нужно запомнить это на потом, тогда идите вперед и вставьте его в вектор, затем ... Но не раньше.)

push_back на int примерно так же быстро, как и собираетсяполучить.Держу пари, что вы едва заметите разницу, даже если избавитесь от reserve (потому что перераспределение происходит не часто и уже будет использовать очень быструю массовую копию).Таким образом, вам нужно расширить свой кругозор, чтобы повысить производительность.

Answer 4

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

Answer 5

Если вы используете отладочную версию STL, во всех вызовах STL есть издержки отладки (особенно в итераторах).

Я бы посоветовал заменить вектор STL на обычный массив. Если вы используете тривиально копируемые типы, вы можете легко скопировать несколько элементов с помощью вызова memcpy.