Здравствуйте, kov_serg, Вы писали:

_>           Ajk=A[j*n+k]; op++; if (Aij>Ajk) continue;

Это, конечно, треш

В первом варианте в op считается число доступов, и в sum0 оно получается больше чем в sum1. Хорошо.
Но время работы такого кода будет описываться в первую очередь не той частью, что записана в строке слева, а той, что находится справа. Этот вставленный continue с условием внутри цикла полностью убьёт конвейер процессора.
В результате на случайных матрицах новый код будет работать куда медленнее старого. Просто из-за того, что такое условие будет постоянно неверно предсказываться и процессор будет занят не вычислениями, а борьбой с рандомными сбросами конвейера.



_>Так что можно просто попробовать сократить доступ к данным

Ну раз уж зашел разговор о проблемах процессора, то нельзя не заметить, что тут в обоих вариантах везде ещё и мимо кеша чтение происходит.
Если матрицу предварительно транспонировать и строчку Aki=A[k*n+i]; заменить на Aki=At[k+n*i];, то внезапно получается стократное ускорение, и даже наивный алгоритм, который считает выражение в лоб, вполне укладывается в пару секунд без дополнительных алгоритмических оптимизаций. А всего-то нужно поменять индексы местами, чтобы читать из памяти последовательно

Здравствуйте, kov_serg, Вы писали:

_>           Ajk=A[j*n+k]; op++; if (Aij>Ajk) continue;

Это, конечно, треш

В первом варианте в op считается число доступов, и в sum0 оно получается больше чем в sum1. Хорошо.
Но время работы такого кода будет описываться в первую очередь не той частью, что записана в строке слева, а той, что находится справа. Этот вставленный continue с условием внутри цикла полностью убьёт конвейер процессора.
В результате на случайных матрицах новый код будет работать куда медленнее старого. Просто из-за того, что такое условие будет постоянно неверно предсказываться и процессор будет занят не вычислениями, а борьбой с рандомными сбросами конвейера.



_>Так что можно просто попробовать сократить доступ к данным

Ну раз уж зашел разговор о проблемах процессора, то нельзя не заметить, что тут в обоих вариантах везде ещё и мимо кеша чтение происходит.
Если матрицу предварительно транспонировать и строчку Aki=A[k*n+i]; заменить на Aki=At[k+n*i];, то внезапно получается стократное ускорение, и даже наивный алгоритм, который считает выражение в лоб, вполне укладывается в пару секунд без дополнительных алгоритмических оптимизаций (при n=3000). А всего-то нужно поменять индексы местами, чтобы читать из памяти последовательно


Хотя, конечно, можно заметить, что все слагаемые входят в сумму тройками, которые отличаются только циклической перестановкой, и замена for(j=0;j<n;j++) на for(j=i+1;j<n;j++) (и для k) позволит выкинуть лишнее вычисления, если просто домножить сумму на 3 в конце.


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