Медленная запись для выстраивания в C++
Я просто задавался вопросом, является ли это ожидаемым поведением в C++. Код ниже выполнений на уровне приблизительно 0,001 мс:
for(int l=0;l<100000;l++){
int total=0;
for( int i = 0; i < num_elements; i++)
{
total+=i;
}
}
Однако, если результаты записаны в массив, время выполнения стреляет в 15 мс:
int *values=(int*)malloc(sizeof(int)*100000);
for(int l=0;l<100000;l++){
int total=0;
for( unsigned int i = 0; i < num_elements; i++)
{
total+=i;
}
values[l]=total;
}
Я могу ценить, что запись в массив занимает время, но действительно ли время пропорционально?
Аплодисменты все
4 ответа
для Integral будет преобразован из интегрального типа в любой числовой тип, включая другие интегральные типы
Посмотрите на функцию повышения, это библиотека только заголовка, которая немного наводит порядок (IMHO): http://www.boost.org/doc/libs/1_42_0/doc/html/function.html
typedef boost::function<double (double)> func_t;
func_t to_be_used = &get_bipolar;
(NB: для VC6 требуется другой синтаксис)
-121--3286647-Первый пример может быть реализован с использованием только регистров CPU. К ним можно получить доступ миллиарды раз в секунду. Во втором примере используется столько памяти, что она, безусловно, переполняет L1 и, возможно, L2 кэш (в зависимости от модели ЦП). Это будет медленнее. Тем не менее, 15 мс/100.000 записей выходит до 1,5 нс на запись - 667 МГц эффективно. Это не медленно.
Похоже, что в первом случае компилятор полностью оптимизирует этот цикл.
Общий эффект цикла - бездействие, поэтому компилятор просто удаляет его.
It's very simple. В первом случае у Вас всего 3 переменные, которые можно легко хранить в GPR (регистре общего назначения), но это не значит, что они все время там, а скорее всего они находятся в кэш-памяти L1, что означает, что к ним можно очень быстро получить доступ.
Во втором случае у Вас более 100k переменных, а для их хранения требуется около 400kB. Для регистров и кэш-памяти L1 это практически бесконечно много. В лучшем случае это может быть в кэш-памяти L2, но, вероятно, не все из них будут в L2. Если что-то не находится в регистрах, L1, L2 (я предполагаю, что в вашем процессоре нет L3), это означает, что вам нужно искать это в оперативной памяти, и это занимает muuuuuch больше времени.
Я подозреваю, что то, что вы видите, является эффектом виртуальной памяти и, возможно, подкачки. Вызов malloc выделяет приличного размера кусок памяти, который, вероятно, представлен несколькими виртуальными страницами. Каждая страница связана с памятью процесса отдельно.
Вы также можете измерить стоимость вызова malloc в зависимости от того, как вы таймировали цикл. В любом случае, производительность будет очень чувствительна к параметрам оптимизации компилятора, параметрам потоков, версиям компилятора, версиям среды выполнения и практически ко всему остальному. Вы не можете с уверенностью предположить, что стоимость линейно зависит от размера выделения. Единственное, что вы можете сделать, это измерить ее и выяснить, как лучше оптимизировать когда будет доказано, что это проблема.