У меня есть строка-главным итератора для 2D-массива, с оператором derefence следующим образом:C++ 2D эффективность матрицы итератора по сравнению с вложенным для цикла
int& Iterator::operator*(){ return matrix_[y_][x_]; } //matrix_ has type int**
(префикс) Оператор инкремента выглядит следующим образом:
Iterator& Iterator::operator++()
{
if((++x_ == xs_) && (++y_ != ys_)) //ys_, xs_ are the dimensions of the matrix
x_ = 0;
return *this;
}
я могу использовать этот итератор с оптимизированной версией станд :: преобразование (не возвращает не-необходимый результат, для того, чтобы сэкономить несколько инструкций)
template < class InputIterator, class OutputIterator, class UnaryOperator >
inline void MyTransform(InputIterator first1, InputIterator last1,
OutputIterator result, UnaryOperator op)
{
for (; first1 != last1; ++first1, ++result)
*result = op(*first1);
}
называть его таким образом:
MyTransform(matrix1.begin(),matrix1.end(),matrix2.begin(), MyFunctor());
Однако, когда я сравнить производительность в классических, вложенных для цикла:
MyFunctor() f;
for (int y=0; y<ySize; y++)
for (int x=0; x<xSize; x++)
matrix2.[y][x] = f(matrix1.[y][x]);
Итератор решение на основе прибл. На 25% медленнее, чем вложенное решение for-loop. Это относится как к компиляторам MSVC, так и к Intel C++ (оба из которых кажутся автоматически встроенными по мере необходимости).
Теперь проблема не связана с оператором инкремента итератора, как если бы я выполнял следующее (уродливое) гибридное решение, объединяющее обход итератор и необработанный массив доступа (последний индексировался с использованием внутренних подсчетов итераторов):
MyFunctor f;
for (; mat1Begin != mat1End; ++mat1Begin, ++mat2Begin)
{
//mat1 and mat2 are type int**
mat2[mat2Begin.y_][mat2Begin.x_] = f(mat1[mat1Begin.y_][mat1Begin.x_]);
}
Это на самом деле немного быстрее, чем вложенное решение для петли. Это говорит о том, что при выполнении задания происходит поражение производительности при разыменовании итератора.
Мой вопрос, почему разыменования итераторы в назначении
*result = op(*first1);
понесены такой массивный удар по производительности, по отношению к сырому доступа к массиву? Есть ли какой-либо метод, который я могу использовать для этого простого дизайна, чтобы получить производительность (почти), эквивалентную версии raw-массива?
В ответ на полезную обратную связь от этого сообщества, я изменил код так, чтобы внешний счетчик цикла кэшируется, так что код теперь выглядит следующим образом:
int& Iterator::operator*()
{
return column_[x_];
}
Iterator& Iterator::operator++()
{
if(++x_ == xs_) //ys_, xs_ are the dimensions of the matrix
{
if(++y_ != ys_)
{
x_ = 0;
column_ = matrix_[y_];
}
}
return *this;
}
Это повышает производительность до ~ 85 % от производительности необработанного 2D-массива для компилятора Intel C++ и аналогичного для компилятора MSVC (на самом деле вызов в MyTransform медленнее на MSVC - гораздо больше сборочных инструкций сгенерировано), но давайте проигнорируем это пока, поскольку меня больше интересует цикл/поведение разыменования).
Когда я конвертирую код в арифметику указателя (снова кешируя столбец) следующим образом, производительность значительно хуже, чем исходный 2D-массив (~ 70%) на компиляторе Intel, но опять же ~ 85% необработанного 2D массив под MSVC компилятором
int& Image32Iterator::operator*()
{
return *ptr_;
}
//prefix
Image32Iterator& Image32Iterator::operator++()
{
if(++ptr_ == ptrEnd_)
{
if(++row_ != rowEnd_)
{
ptrEnd_ = (ptr_ = *row_) + xs_;
}
}
return *this;
}
Так что я пытаюсь понять, если ~ 85% производительности максимальное я могу получить с помощью итератора на основе решения. Я удивлен, что арифметическое решение указателя выполняет гораздо худшее (искажение, поскольку я пытался использовать арифметику указателя, чтобы увидеть, могу ли я получить> 85%!).
Я продолжу расследование и обновление с помощью находок, но любое понимание приветствуется ...
... Итак, сфокусировавшись на вопросе о том, почему арифметическая версия итератора с указателем-арифметикой так плохо работает для Intel, тогда как она отлично подходит для компилятора MSVC, я посмотрел на сборку, и проблема кажется быть в коде, сгенерированном для цикла. Для всех других функций (т. Е. Конструкторы, операторы итератора и разыменования, оператор неравенства и т. Д. Сгенерированный код практически одинаковый для Intel и MSVC, если что-то для Intel это немного более красноречиво).
Вот ассемблер для сгенерированного кода Intel, за которым следует ассемблер для сгенерированного MSVC кода. Я изменился с цикл на время цикла, чтобы сделать сгенерированный ассемблер легче читать:
Intel сгенерированный код:
while(begin != end)
01392D31 push eax
01392D32 lea eax,[begin]
01392D35 lea edx,[end]
01392D38 mov dword ptr [esp],edx
01392D3B mov ecx,eax
01392D3D call ImageExperiments::Image32Iterator::operator!= (139103Ch)
01392D42 mov byte ptr [ebp-74h],al
01392D45 movzx eax,byte ptr [ebp-74h]
01392D49 movzx eax,al
01392D4C test eax,eax
01392D4E je ImageExperiments::greyscale_iterator2+0BCh (1392DACh)
{
*it8 = gsf(*begin);
01392D50 lea eax,[begin]
01392D53 mov ecx,eax
01392D55 call ImageExperiments::Image32Iterator::operator* (13910A5h)
01392D5A mov dword ptr [ebp-10h],eax
01392D5D push eax
01392D5E lea eax,[gsf]
01392D61 mov edx,dword ptr [ebp-10h]
01392D64 mov edx,dword ptr [edx]
01392D66 mov dword ptr [esp],edx
01392D69 mov ecx,eax
01392D6B call ImageExperiments::GreyScaleFunctor::operator() (139101Eh)
01392D70 mov byte ptr [ebp-72h],al
01392D73 movzx eax,byte ptr [ebp-72h]
01392D77 mov byte ptr [ebp-71h],al
01392D7A lea eax,[it8]
01392D7D mov ecx,eax
01392D7F call ImageExperiments::Image8Iterator::operator* (1391050h)
01392D84 mov dword ptr [ebp-0Ch],eax
01392D87 mov eax,dword ptr [ebp-0Ch]
01392D8A movzx edx,byte ptr [ebp-71h]
01392D8E mov byte ptr [eax],dl
++begin;
01392D90 lea eax,[begin]
01392D93 mov ecx,eax
01392D95 call ImageExperiments::Image32Iterator::operator++ (1391028h)
01392D9A mov dword ptr [ebp-8],eax
++it8;
01392D9D lea eax,[it8]
01392DA0 mov ecx,eax
01392DA2 call ImageExperiments::Image8Iterator::operator++ (1391014h)
01392DA7 mov dword ptr [ebp-4],eax
01392DAA jmp ImageExperiments::greyscale_iterator2+41h (1392D31h)
}
}
00CA2DAC leave
00CA2DAD ret
MSVC сгенерированный код:
while(begin != end)
010316E0 lea eax,[end]
010316E3 push eax
010316E4 lea ecx,[begin]
010316E7 call ImageExperiments::Image32Iterator::operator!= (1031096h)
010316EC movzx ecx,al
010316EF test ecx,ecx
010316F1 je ImageExperiments::greyscale_iterator2+74h (1031724h)
{
*it8 = gsf(*begin);
010316F3 lea ecx,[begin]
010316F6 call ImageExperiments::Image32Iterator::operator* (10311EAh)
010316FB mov eax,dword ptr [eax]
010316FD push eax
010316FE lea ecx,[gsf]
01031701 call ImageExperiments::GreyScaleFunctor::operator() (1031032h)
01031706 mov bl,al
01031708 lea ecx,[it8]
0103170B call ImageExperiments::Image8Iterator::operator* (1031118h)
01031710 mov byte ptr [eax],bl
++begin;
01031712 lea ecx,[begin]
01031715 call ImageExperiments::Image32Iterator::operator++ (1031041h)
++it8;
0103171A lea ecx,[it8]
0103171D call ImageExperiments::Image8Iterator::operator++ (103101Eh)
}
01031722 jmp ImageExperiments::greyscale_iterator2+30h (10316E0h)
}
01031724 pop edi
01031725 pop esi
01031726 pop ebx
01031727 mov esp,ebp
01031729 pop ebp
0103172A ret
Так выглядит мне, как компилятор Intel, генерируется ок. На 50% больше инструкций. Я пробовал квалифицировать указатели с __restrict, чтобы понять, не повлияет ли это на поколение Intel, но это не так. Если у кого-то есть какие-либо предположения относительно того, почему код цикла из компилятора Intel настолько громоздкий/медленный, по сравнению с компилятором MSVC++, мне было бы очень интересно!
Я предполагаю, что здесь стоит сравнить ассемблер в обоих случаях. –
Кроме того, во втором тесте с итераторами вы попытались заменить эту строку
mat2[mat2Begin.y_][mat2Begin.x_] = f(mat1[mat1Begin.y_][mat1Begin.x_]);на назначение, основанное на итераторе, чтобы убедиться, что даже после утилизации всей инфраструктуры MyTransform производительность по-прежнему ухудшается с помощью разыменования? –Да, я пробовал это, это не имеет ничего общего с машиной преобразования. – TPJ