LINUX.ORG.RU

Очень сильно отличие производительности исполняемого файла в Linux (gcc) и Windows (mingw64)

 ,


2

7

К вопросу о «кроссплатформенной» разработке.

Есть такой фрагмент кода (сильно порезанный кусок, можно ещё сильнее порезать, но на нём демонстрируется проблема):

// g++ -Ofast -ffast-math

#include <cstdio>
#include <cstdlib>
#include <cmath>

int main() {
    const int N = 1200;
    double* A;
    double* B;
    double C;
    int m;
    
    A = new double[N*N];
    B = new double[N]; 
    
    //srand(time(0));
    //srand( (unsigned)time( NULL ) );
    
    for (int i  = 0; i < N; i++) {
        for (int j =  0; j < N; j++) {
            A[N*i+j] = (double)rand() / ((double)10000);
        }
        B[i] = 0.0;
    }

    // Сильно порезанный фрагмент кода:    
    for (int k = 0; k < N-1; k++ )  {
        m = (k + 1);
        
        for (int i = k + 1; i < N; i++ )   {
            if ( fabs(A[N*(i) + (k)]) > fabs(A[N*(m-1) + k]) ) m = (i + 1);
        }
        B[k] = m;
        
        if ( (m + 1) != k ) B[N-1] = -B[N-1];
        
        C = A[N*(m-1) + k];
        A[N*(m-1) + k] = A[N*k + k];
        A[N*k + k] = C;
        
        if (C == 0) continue;
        
        for (int i = k + 1; i < N; i++ ) A[N*i + k] = -A[N*i + k]/C;
        
        for (int j = k + 1; j < N; j++ )  {
            C = A[N*(m-1)+ j];
            A[N*(m-1) + j] = A[N*k + j];
            A[N*k + j] = C;
            if ( C != 0 )  {
                // дольше всего выполняется этот блок цикла:
                for (int i = k + 1; i < N; i++ )  {
                    A[N*i + j] = A[N*i + j] + A[N*i + k]*C;
                }
            }    
        }
    }
    
    delete [] A;
    delete [] B; 
    
    return 0;
}

Суть проблемы в том, что собранный с одинаковыми опциями этот кусок выполняется на моём железе в Linux за 2.7 сек (gcc 4.8.4), а в Windows7 (mingw64 4.9.3, tdm-gcc 4.9.2) за 8.4 (т.е. разница ~3 раза). Ни на одном другом примере я такого проседания не наблюдал (разве что TDM-GCC генерит в некоторых случаях код заметно быстрее чем MinGW64, но не в этом случае). Понятно, что в этом блоке, который третий по вложенности цикл

for (int i = k + 1; i < N; i++ ) {
    A[N*i + j] = A[N*i + j] + A[N*i + k]*С;
}
не самое эффективное обращение к элементам, так как часто приходится прыгать между элементами, но что есть, то есть - такой алгоритм попался. Но даже если просто оставить прибавление действительного числа «С», то в Linux это ускорит выполнение на 0.5 сек (насколько ускорит в Windows не проверял).

Сталкивался ли кто с подобным поведением MinGW64, TDM-GCCd в плане сильного проседания производительности? Какие ещё ключи компилятора могут заметно ускорить выполнение этого фрагмента?

★★★★★

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

dave ★★★★★ ()

Всё верно: вендузятник должен страдать.

anonymous ()
Ответ на: комментарий от dave

Один и тот же стационарный комп Core i3 550 3.2 GHz. Ещё как-то проверял на работе на Core i7 4790k - ситуация та же, линукс там грузил с флешки. Только там этот код в Windows выполнялся в 2 раза медленнее (4 секунды против 1.8). Уже пытался полностью отключать энергосбережение (с проверкой, что частота постоянна) - ничего не поменялось.

В реализации Гаусса-Зейделя с релаксацией для уравнения Лапласа производительность так не проседала и была одинаковой для GCC и TMD-GCC (MinGW64 генерил код медленнее на 1.5 секунды) на временах выполнения порядка 5-6 секунд.

если просто оставить прибавление действительного числа «С»

Проверил в Windows: ускорило секунды на 3, но всё равно раза в 2 медленнее. Есть подозрение, что это из-за менеджера памяти.

grem ★★★★★ ()
Последнее исправление: grem (всего исправлений: 1)
Ответ на: комментарий от anonymous

Всё верно: вендузятник должен страдать.

Но не настолько же :)

grem ★★★★★ ()

Попробуй, например, -O2.

Ну а вообще ничего удивительного. Ты и размеры бинарей сравни, их же ворочать надо.

Bfgeshka ★★★★★ ()

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

anonymous ()

а как измеряли время выполнения кстати? отсечки времени и их вывод внутри программы, или внешние обертки для всего типа time?

arkhnchul ★★ ()

Очень лень вчитываться в твой алгоритм, но нет ли у тебя использования неиницилированной памяти в массиве? Может так чюдесно получаться, что в одном случае С чаще оказывается нулевой, а в другом нет. Стоит сначала занулить все массивы, ну чисто для теста, и посмотреть что получится

anonymous ()

Такие вопросы неплохо бы сопровождать как минимум ассемблером. Потом я бы рекомендовал посмотреть сколько код висит на блокировках (как в винде это сделать без понятия). Если включить libastral, то рискну предположить что под линуксом был взведён huge pages, а под виндой - нет.

alexanius ★★ ()

С какими ключами собиралось? Дебаг/релиз? Ты что-то делаешь не так, не верю в разницу при правильном подходе.

I-Love-Microsoft ★★★★★ ()
Ответ на: комментарий от I-Love-Microsoft

Почти что одинаковые операционки, что за херь про подход несёшь. Ах да, ему нужно было как-то воспользоваться Qt.

anonymous ()

Праздного любопытства ради спрошу - не пробовал в cygwin?

По теме - не раз и не два слышал на разных форумах (в основном в контексте Qt) что mingw(правда 32) есть тормоз в принципе по сравнению с нативными компилями, т.к. портируется в угоду простоте портирования а не эффективности. Тонкостей проблемы не назову, просто слышал звон...

Есть ещё такой вариант, что в винде например что-то отличается в том же менеджере памяти. И ещё такой момент - ты когда замерял, аффинити выставлял(так что бы на ядре(не на потоке, а на всём ядре) были только твой процесс и ядро ОС)? Если нет, то тут о чистоте замера теоретически речь особо и не идёт, работу планировщика никто не отменял однако.

pon4ik ★★★★★ ()

есть гипотеза что в windows просто кэши более засраны (ядром либо фоновой лабудой), для проверки достаточно запустить с N=400

anonymous ()
Ответ на: комментарий от Bfgeshka

Попробуй, например, -O2.
Ну а вообще ничего удивительного. Ты и размеры бинарей сравни, их же ворочать надо.

Bfgeshka, тот же эффект, но в Linux бинарник действительно в несколько раз меньше по объёму. Для приведённого в шапке кода точно не скажу, но для него чуть модифицирунного, но всё ещё одинакового в обеих системах ~10 Кб в Linux и ~80 Кб в Linux.

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

как измеряли время выполнения кстати? отсечки времени и их вывод внутри программы, или внешние обертки для всего типа time?

anonymous, arkhnchul,

Первоначально, когда обнаружил, весь массив, емнип, хранился в стэке, но ещё раз перепроверю. Сначала измемерял исключительно блок с тройным циклом и отдельно самый внутренний с помощью double time = omp_get_wtime();... (omp_get_wtime() - time), добавив при сборке ключ -fopenmp, т.к. распараллеливал им самый вложенный цикл и проверял, что он самый затратный по времени. Приведённый в теме пример измерял с помощью (measure-command {.\a.exe}).totalmilliseconds (в powershell) и time. Но судя по выводу отладочных сообщений вида «старт цикла», на выделение в куче происходит почти мгновенно.

Очень лень вчитываться в твой алгоритм, но нет ли у тебя использования неиницилированной памяти в массиве? Может так чюдесно получаться, что в одном случае С чаще оказывается нулевой, а в другом нет. Стоит сначала занулить все массивы, ну чисто для теста, и посмотреть что получится

Да, подозрения насчёт проверок равенства нулю «C» есть. Поэтому сгенерил файлик с данными массива и проверил считывая из него, чтобы входные данные были одинаковыми в обоих случаях. Разница осталась (в windows правда как-то долго из файла читает - пришлось снова добавить вызов «omp_get_wtime()„непосредственно перед циклом). Проверю ещё убрав эту проверку на равенство нулю, уж очень она мне не нравится в том виде, в котором она там есть. Также проверю что получается в массиве после преобразований в обоих случаях при одинаковых входных данных.

grem ★★★★★ ()
Ответ на: комментарий от alexanius

Такие вопросы неплохо бы сопровождать как минимум ассемблером. Потом я бы рекомендовал посмотреть сколько код висит на блокировках (как в винде это сделать без понятия). Если включить libastral, то рискну предположить что под линуксом был взведён huge pages, а под виндой - нет.

alexanius, попробую разобраться с выводом dump. И почитаю про huge pages и его принудительное включение.

Msvc пробовал собрать?

ncuxer, коллегу одного просил, результат на 4790k такой же медленный как на моём 4790k был. Самому студию лень ставить.

С какими ключами собиралось?

I-Love-Microsoft, в шапке кода в первой закомментированной строчке ключи указаны, соответсвенно, релиз. Разве что в windows всё-таки 32-битная(dwarf, thread posix) использовалась, а в linux 64-битный компилятор. Но на других примерах такая разница из-за битности не проявлялась нигде.

pon4ik, Праздного любопытства ради спрошу - не пробовал в cygwin?

Нет, пока не пробовал. Только для TDM-GCC, но это тоже порт.

Есть ещё такой вариант, что в винде например что-то отличается в том же менеджере памяти. И ещё такой момент - ты когда замерял, аффинити выставлял(так что бы на ядре(не на потоке, а на всём ядре) были только твой процесс и ядро ОС)? Если нет, то тут о чистоте замера теоретически речь особо и не идёт, работу планировщика никто не отменял однако.

Точно не помню, кажется было такое пару месяцев назад, когда в windows из командной строки при запуске выставлял «start /affinity», нужно бы ещё раз проверить.

anonymous,

есть гипотеза что в windows просто кэши более засраны (ядром либо фоновой лабудой), для проверки достаточно запустить с N=400

А вот с этим непонятно что делать тогда, если это так.

grem ★★★★★ ()
Ответ на: комментарий от grem

в windows всё-таки 32-битная(dwarf, thread posix) использовалась, а в linux 64-битный

Классика блджад))

anonymous ()
Ответ на: комментарий от grem

Спасибо. Я когда-то похожий тред создавал, под Windows у меня была просадка производительности до 10 раз. Но задачи оптимизировать не было, поэтому я не разбирался особо.

ncuxer ()

А у тебя в linux какой-нибудь openmp не подрубается автоматом? Слишком уж большая разница выходит. Разницу в 30-40% ещё можно списать на компиляторы (у меня был опыт, когда банальная смена VS C++ на Intel/GCC давала подобный результат), но не разницу в 3 раза.

Norgat ★★★★★ ()
Ответ на: комментарий от grem

Точно не помню, кажется было такое пару месяцев назад, когда в windows из командной строки при запуске выставлял «start /affinity», нужно бы ещё раз проверить

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

pon4ik ★★★★★ ()

Если не секрет, с какой целью был написан этот код?

anonymous ()

Раз речь о венде, то отключи антивирус.

anonymous ()

// дольше всего выполняется этот блок цикла:

Кстати используй внешний индекс. У тебя там и так адресная арифметика, так ещё и умножения. Ц-ц-ц-ц

Кстати глянь как компилятор оптимизирует это выражение.

anonymous ()
Ответ на: комментарий от alexanius

Если не секрет, с какой целью был написан этот код?

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

есть гипотеза что в windows просто кэши более засраны (ядром либо фоновой лабудой), для проверки достаточно запустить с N=400

Попробую для разных N позапускать ещё, до определённого момента зависимость времени в обеих системах должна быть одинаковой.


alexanius,

Такие вопросы неплохо бы сопровождать как минимум ассемблером.

main_asm.zip, там файлы *.s и *.dump созданные командами

g++ -S -o main_asm.s -Ofast -ffast-math main.cpp
as -alhnd main_asm.s > main_asm.dump

соответственно. В этот раз в обоих случаях использовал 64-битные компиляторы. Что с ними делать я не представляю. В исходном примере перед этим закомментировал проверки на равенство/неравенство нулю: для метода Гаусса там всё равно желательно, чтобы «не делилось» не только на ноль, но и просто на очень маленькие числа, а rand(), судя по всему, их не генерит. Разве что, когда я проверял в windows он мне сгенерил числа от 0 до 4, а в linux они были порядка десятков-сотен тысяц. По этой причине добавил чтение из файла main_2_test.zip и сохранение результата после преобразования, как можно видеть, результат одинаковый. Только , чтобы исключить учёт времени на чтение файла в 11 мб, пришлось добавить вызовы «omp_get_wtime()» перед и после циклов и ключ "-fopenmp", так как в windows он ещё и файл очень дольше читал, а хотелось измерить время только циклов.

pon4ik, сегодня попробовал отключить в BIOS всякие C1E, C3/C6, EIST, после чего загрузился в безопасном режиме без сетевых драйверов, собрал 64-битным компилятором и запустил через «start /affinity 2 a.exe» («/affinity 2» тоже ставил) - результат тот же. Вот поснимать с ядра всё остальное не догадался, но мне уже кажется, что это не поможет и либо всё упирается в менеджер памяти, либо сам компилятор такой код генерит. Нужно в Mint проверить включен ли huge pages.

Norgat, судя по выводу -verbose при сборке -gomp не был включен, да и вряд ли gcc умеет autoparallel как «icc ap» от Intel. COLLECT_GCC_OPTIONS (в первом архиве по ссылке выше в этом ответе есть вывод verbose) чуть отличаются: «'-mtune=generic' '-march=x86-64'» в win и «'-mtune=generic' '-march=x86-64'» в linux, но выставление таких же в win ничего не меняет.

grem ★★★★★ ()
Ответ на: комментарий от anonymous

Кстати используй внешний индекс. У тебя там и так адресная арифметика, так ещё и умножения. Ц-ц-ц-ц

Не совсем понял, пройтись по j вместо i? Это же поменяет результат.

Кстати глянь как компилятор оптимизирует это выражение.

К сожалению, не знаю как это проверить. Спасибо, если подскажешь.

grem ★★★★★ ()

gprof

собери под gprof и там и там, и сравни ботлнеки (найди двоичным поиском)

MinGW-ов под винду ходит сборок несколько, плюс сам Mingw в двух вариантах. поэтому — хз как они собирались. я бы сделал билдрут из-под линукса кроссборкой с правильно собранным gcc в целевую винду, и сравнивал одинаковые версии gcc и там, и там.

anonymous ()
Ответ на: комментарий от anonymous

есть гипотеза что в windows просто кэши более засраны (ядром либо фоновой лабудой), для проверки достаточно запустить с N=400

Прогнал в обеих системах запуски при N = от 100 до 1200 с шагом 100. До N = 500 включительно в windows профиль кривой зависимости времени от N фактически повторяет профиль кривой в linux и времена хотя бы сопоставимы, время даже примерно пропорционально N^3. Потом, уже при N = 600, в windows кривая резко уходит вверх. Похоже, что действительно кэш забивается чем-то лишним и обращения к элементам массива в данном случае резко замедляется.

grem ★★★★★ ()
Ответ на: комментарий от grem

Циклы, очень похоже что одинаковые так что думаю что дело в среде исполнения. Смотри в сторону блокировок и кэша (тут уже писали).

По замерам для чистоты я замерял командой time taskset -c 1 для того чтобы померить весь тест на одном cpu, у меня результаты довольно разбросаны (g++-6.3 -Ofast -ffast-math):

  • Intel XCore2 Duo E7300 (2.66GHz) - 6.2 сек.
  • Intel Xeon E5-2650 v2 (2.60GHz) - 7.6 сек.

PS.

  • Эльбрус-401Б (0.75GHz) - 2.47 сек. :P
alexanius ★★ ()

А если запускать в винде в виртуалке, в которой линукс гость?

hotpil ★★★ ()
Ответ на: комментарий от grem

Не совсем понял, пройтись по j вместо i? Это же поменяет результат

думаю имелась ввиду смена хранения и адресации матрицы row major <-> column major. по фрагменту непонятно в какие моменты задействована лин.алгебра на уровне библиотек - а без нее из A[x,y] можно делать адрес как угодно.

если реально этот цикл на одних A[x,y], transpose ради него должен окупиться. еще и автовекторизация должна заработать (кстати -march=native стоит добавлять подобной математике, а то avx например не включён)

если не вариант, можно глянуть в сторону _mm_prefetch против кэш миссов, но это уже низкий уровень

anonymous ()
Ответ на: комментарий от hotpil

Медленнее будет, чем просто в linux.

На самом деле, этот алгоритм можно распараллелить openmp, добавив перед вторым циклом что-то вроде #pragma omp parallel for private(k, j, C)

Даже результат такой же получится на выходе (другой очень бы не хотелось), только объявление j нужно будет сделать снаружи. На 4790k вместо 4.8 секунды получится примерно 1.6.

grem ★★★★★ ()

Если всё упёрлось в производительность, то попробуйте собрать проектик с помощью Open Watcom, он одно время имел славу самого скорострельного из компиляторов.

Infra_HDC ★★★★★ ()
Ответ на: комментарий от grem

start /affinity 2 a.exe

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

pon4ik ★★★★★ ()

У меня Qt проект собранный с использованием MSYS2 был в разы медленнее сборки со стандартными либами из установщика Qt.

Времени/желания разбираться не было, хз что не так.

RazrFalcon ★★★★★ ()
Ответ на: комментарий от Norgat

берёте asm выхлоп и смотрите. чего гадать в стиле бабок у подъезда.

dzidzitop ★★ ()
Ответ на: комментарий от dzidzitop

Мне заняться нечем? Я ему предложил возможный вариант, смотрит пусть сам.

Norgat ★★★★★ ()
Ответ на: комментарий от Norgat

Угу. Я больше к ТСу и обращаюсь.

А вообще callgrind есть. С -g3 должен показать всё что нужно.

dzidzitop ★★ ()
Последнее исправление: dzidzitop (всего исправлений: 1)
Ответ на: комментарий от grem

Есть подозрение, что это из-за менеджера памяти.

Скорее всего. И вам еще повезло, я когда собирал в VS код, то он на винде работал в 12 раз медленее чем в линуксе. Он даже под вайном работал быстрее.
Если память не изменяет, то натив под линуксом отрабатывал за 50мс, натив под виндой за 600мс, виндовый под вайном за 150мс

SR_team ★★★★ ()
Ответ на: комментарий от alexanius

Муйня полная, на иви бридже ещё и более высокочастотном и на серверной платформе медленнее кор2, пхаха. У эльбруса такая же кривая методика теста, не сомневаюсь.

anonymous ()

Спасибо всем ответившим.

shielcody, спасибо, попробую выравнивание, может чуть улучшит ситуацию. Но, скорее всего, на этом придётся остановиться :( Я что-то начал припоминать, как мне говорили, что для таких больших N подобные прямые методы решения СЛАУ обычно не используют и преимущественно начинают пользоваться итерационными методами, которые сами по себе работают намного быстрее. Так что с таким большим N я, видимо, погорячился. Но в Linux в данном случае время даже при таких N практически пропорционально (N^3), что и должно быть. Про выравнивание будет полезно узнать, когда до него доберусь.

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

pon4ik, это да. Поотрубал энергосбережение, HT и загрузился в безопасном режиме я на всякий случай. Попытался в PowerShell согнать все процессы (которые админом получилось согнать) на определённые ядра, но после этого (по крайней мере из cmd) не получилось запустить процесс на чём-то отличном от уже указанных для остальных процессов, хотя новый процесс на тот момент не существовал даже. Но вряд ли это поможет, а если поможет, то будут просадки при попытке вызывать параллельные расчёты для разных условий.

А у тебя в linux какой-нибудь openmp не подрубается автоматом?

Norgat, Неа, это было бы слишком прекрасно/ужасно (в зависимости от ситуации), если бы он врубался автоматом. К тому же о подобных свойствах gcc я ни разу не слышал. При включении распараллеливания через openmp (здесь я указал параметры с ошибкой, должно быть #pragma omp parallel for private(i, j, C)), то есть так

...
#pragma omp parallel for private(i, j, C)
    for (j = k + 1; j < N; j++ )  {
        C = A[N*(m-1)+ j];
        A[N*(m-1) + j] = A[N*k + j];
        A[N*k + j] = C;
        // if ( C != 0 )  {
            for (int i = k + 1; i < N; i++ )  {
                A[N*i + j] = A[N*i + j] + A[N*i + k]*C;
            }
        // }
    }
...
то в linux, без учёта чтения-записи в-из файла, код выполняется за 1.33 сек, а в windows за 4.35 сек. То есть в обоих случаях получается ускорение в 2 раза, если сравнивать с кодом без «#pragma omp».

если реально этот цикл на одних A[x,y], transpose ради него должен окупиться. еще и автовекторизация должна заработать (кстати -march=native стоит добавлять подобной математике, а то avx например не включён)
если не вариант, можно глянуть в сторону _mm_prefetch против кэш миссов, но это уже низкий уровень

anonymous, спасибо, поиграться с транспонированием меня тоже посещала мысль, может получится переписатать с ним. Об использовании «_mm_prefetch» тоже почитаю, может позже пригодится.

grem ★★★★★ ()
Ответ на: комментарий от grem

спасибо, попробую выравнивание, может чуть улучшит ситуацию. Но, скорее всего, на этом придётся остановиться :( Я что-то начал припоминать, как мне говорили, что для таких больших N подобные прямые методы решения СЛАУ обычно не используют и преимущественно начинают пользоваться итерационными методами, которые сами по себе работают намного быстрее. Так что с таким большим N я, видимо, погорячился. Но в Linux в данном случае время даже при таких N практически пропорционально (N^3), что и должно быть. Про выравнивание будет полезно узнать, когда до него доберусь.

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

Если код циклов индентичен, обращение к памяти идентично, то остаётся только выравнивание, если не учитывать всё то, о чём говорилось выше( разные режимы работы ЦП, планировщика и прочее).

shielcody ()
Ответ на: комментарий от shielcody

Попробовал выровнять так (с указанным выше вариантом, к сожалению, падало почему-то прямо перед «return 0;» или на нём; delete'ы удалил):

A = new double[N*N + 4096];
B = new double[N + 4096]; 
A = (double *)(( ((uintptr_t)A) + 4096ul) & ~(4096ul - 1));
B = (double *)(( ((uintptr_t)B) + 4096ul) & ~(4096ul - 1));

скорость выполнения не изменилась. Попробую прогнать ещё на Linux при N > 1200, мне кажется, что там тоже достаточно скоро должен наступить момент, когда кэш забьётся и время резко начнёт расти.

grem ★★★★★ ()
Ответ на: комментарий от grem

подобные прямые методы решения СЛАУ обычно не используют и преимущественно начинают пользоваться итерационными методами, которые сами по себе работают намного быстрее. Так что с таким большим N я, видимо, погорячился. Но в Linux в данном случае время даже при таких N практически пропорционально (N^3), что и должно быть.

Попробовал разобраться в коде и посмотреть на проблемы. Тут сплошной перебор столбцов. Как конкретно код манипулирует значениями массива я не особо понял - стал искать исходный алгоритм, который у вас реализован.

Быстрый обход ссылок в википедии ничего не дал - после я повглядывался получше и обнаружил, что это очень похоже на «метод гаусса» в котором своп делает «онлайн», а так же каким-то колдунством деление с вычитанием вынесено за цикл. При это колдунство заключается не в выносе, а в смене обхода. В википедии обход по строкам, а тут по столбцам.

Дак вот у меня вопрос - неужели этот алгоритм быстрее того, что написан в википедии, либо он даёт какой-то иной результат? По мне так «из википедии» должен быть быстрее.

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

shielcody ()
Ответ на: комментарий от shielcody

Реализация алгоритма не моя, я её только поковырять решил. Насколько понял, первоначально это была реализация Гаусса с частичным выбором главного элемента.

На самом деле есть, как минимум, метод Гаусса, метод Гаусса с частичным выбором главного элемента и метод Гаусса с выбором главного элемента. Выбор главного элемента делают для повышения точности. Они упоминаются и описываются, например, здесь. Но для больших систем такие методы обычно не используют.

P.S.
Проверил для linux при N > 1200. Значения на кривой времени выполнения стали отличаться больше чем на 20-30% от значения кривой пропорциональной N^3, с которой он до этого более-менее совпадал, после N =1100..1200. В windows этот момент наступил при N >= 700. При этом в linux скорость выполнения растёт не так быстро как в windows и даже при N = 3000 время выполнения отличается не больше чем в 2.5 раза от предполагаемого. В windows при N = 1100 такое отличие уже больше чем в 4 раза. Это для core i7 4790k.

grem ★★★★★ ()
Ответ на: комментарий от grem

На самом деле есть, как минимум, метод Гаусса, метод Гаусса с частичным выбором главного элемента и метод Гаусса с выбором главного элемента. Выбор главного элемента делают для повышения точности. Они упоминаются и описываются, например, здесь. Но для больших систем такие методы обычно не используют.

Хорошо, спасибо - я тогда поиграюсь с псевдокодом отсюда: https://en.wikipedia.org/wiki/Gaussian_elimination

Проверил для linux при N > 1200.

Кстати, я только сейчас увидел что у вас там 1200 и даблы, а это оказывается больше 8метров. А это значит, что у нас буфер состоит из 2тысяч страниц. А хасвелл может в: Data TLB L2 (STLB): 1024 items

В линуксе есть такие фичи, типа:

# cat /proc/meminfo 

DirectMap4k:       18740 kB
DirectMap2M:     2983936 kB
DirectMap1G:    14680064 kB

Т.е. он мог у вас заммапить ваш буфер большими страницами чем нивелировать влияние тлб, а венда наверное этого не может.

Проверьте эти пункты в меминфо - есть они есть, то вполне возможно что причина в этом.

Сейчас я натравил перф и тлб-мисов там вообще не вижу, а они должны быть. Значит линукс 100% там что-то нашаманил. Попробуйте сделать это же под вендой - я не знаю что там, кроме втюна, это умеет.

shielcody ()
Ответ на: комментарий от shielcody

Проверить это так же можно ограничив кол-во данных в венде 4метрами, а лучше 2-3 чтобы наверняка. Если разница уменьшится, то значит оно.

shielcody ()
Ответ на: комментарий от shielcody

Да, при N < 600-700 в последнем случае на разницу можно уже не смотреть. Оно помедленнее, но не так критично.

grem ★★★★★ ()
Последнее исправление: grem (всего исправлений: 1)
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.