Какой самый быстрый? Boost :: multi_array или std :: vector?
Какой самый быстрый? boost::multi_array или std::vector?
У меня будут (не постоянные) 17.179.869 элементы, хранящиеся в 3 измерениях, к которым нужно будет обращаться внутри for Цикл очень быстро и очень часто. Что будет наиболее эффективным? std::vector или boost::multi_array?
(Я не ожидаю, что это будет сделано в течение секунды, но я бы хотел, чтобы это было как можно более эффективным, потому что разница в наносекунды может сэкономить много времени.)
Решение
Лучший совет — оценить его самостоятельно.
В любом случае, поскольку у вас постоянный размер, есть и другие решения:
- простые массивы C (например,
int data[X][Y][Z]) - простой одномерный массив C, в котором вы сами вычисляете индексы, например
X*W*H + Y*W + Z, может быть полезен в некоторых ситуациях std::array, который в основном представляет собой массив C ++ с некоторым синктактическим сахаром, взятым из коллекций STLstd::vectorЯ думаю, это первое решение, которое можно попробоватьboost::multi_array, который предназначен для поддержки N размерных массивов, так что он может быть излишним для вашей цели, но, вероятно, имеет лучшую локализацию данных по сравнению с вектором.
Другие решения
Эти векторные классы библиотеки разработаны так, чтобы быть простыми в использовании и относительно безопасными.
Они настолько быстры, насколько могут быть в их дизайне, но ничто не сравнится с выполнением этого самостоятельно (за исключением, возможно, сборки вручную).
Для размера, о котором вы говорите (2e10 элементов), я бы больше интересовался эффективностью, чем удобством для пользователя.
Если ваш внутренний цикл выполняет очень мало вычислений для каждого элемента, вы обнаружите, что вычисления индексации являются доминирующими,
который предлагает сделать некоторую раскрутку и переход по указателю.
(Может быть Вы можете рассчитывать на то, что компилятор развернет его, но меня это не волнует.)
Единственный способ узнать наверняка — попробовать оба варианта и профилировать код. Однако, как куча идей, это то, что я думаю, вы найдете.
- Для большого количества элементов, с которыми вы имеете дело (2e10 +), доступ к элементам не будет столь же значительным, как давление кеша для загрузки этих элементов в кеш процессора. Предварительный загрузчик будет сидеть там, пытаясь загрузить эти элементы, что займет большую часть времени.
- Доступ к двум (или трехмерным) несмежным массивам C означает, что ЦП вынужден извлекать данные из разных частей памяти. boost :: multi_array решает это несколько закулисно, сохраняя его как непрерывный блок; но у этого есть свои накладные расходы для этого. Как сказал @Jack, лучше всего использовать простые 1D-массивы с индексами, и даже тогда вы можете сделать что-то, чтобы обеспечить минимальное индексирование (например, запоминание).
- Работа, которую вы выполняете в цикле, существенно повлияет на ваше время. Предсказатель ветвления будет самым большим вкладчиком. Если это простая математическая операция, нет операторов if / else, вы, вероятно, получите лучшую производительность, и компилятор, скорее всего, оптимизирует ее под инструкции SSE. Если у вас есть составные типы (а не int / float / char), вам придется правильно их размещать, чтобы оптимизировать доступ.
- Я почти предложил бы попробовать оба варианта, а затем вернуться с новым вопросом SO, в котором написан ваш цикл, и спросить, как оптимизировать эту часть. Почти всегда компилятору могут быть даны подсказки, чтобы он знал ваши намерения.
В конце дня попробуйте и посмотрите