по-интересното е с какъв компилатор :)
Задача НЕ за интервю
Golden Gega Накрая да вземе някой да сумира резултатите че станах разноглед - платформи, машини, оптимизиран/неоптимизиран и т.н.
Някой да напише с думи прости - МРЕТЕ СЕЛЯНИ ПРОСТИ, ASM РУЛИРА! или С-то си е С, дядките с асемблера в recycle-bin-а!
Според мен изводите са: а) езика за програмиране няма особено значение; б) структурите данни ИМАТ значение; в) Ако имаш embarassingly parallel проблем, използвай GPU. :)
Все пак ще имплементирам чист брутфорс на Го да видя колко време ще отнеме (защото този, който използвам е твърде абстрактен).
ФейкПрофил по-интересното е с какъв компилатор :)
Аз ли? Apple clang version 12.0.0 (clang-1200.0.32.2)
| ФейкПрофил по-интересното е с какъв компилатор :)
Аз ли? Apple clang version 12.0.0 (clang-1200.0.32.2)
ръста е още на LLVM 10 :)
| Golden Gega Накрая да вземе някой да сумира резултатите че станах разноглед - платформи, машини, оптимизиран/неоптимизиран и т.н.
Някой да напише с думи прости - МРЕТЕ СЕЛЯНИ ПРОСТИ, ASM РУЛИРА! или С-то си е С, дядките с асемблера в recycle-bin-а!
Според мен изводите са: а) езика за програмиране няма особено значение; б) структурите данни ИМАТ значение; в) Ако имаш embarassingly parallel проблем, използвай GPU. :)
Все пак ще имплементирам чист брутфорс на Го да видя колко време ще отнеме (защото този, който използвам е твърде абстрактен).
Мерси, ще ми е интересно да видя крайните резултати.
ФейкПрофил За ред с номер 3 пак имаш невероятно малко време - 30 пъти по-бързо от ред 0.
Ред 0 е един от най-тежките за смятане. Особеност на подреждането на данните в Dataset.csv. При друго подреждане и времената са други.
По-надолу в редицата има и други подобни случаи, даже и по-малки времена от ред 3. Но резултата е правилен. Сигурно във програмите на HLL нещо не правите както трябва.
Golden Gega Мерси, ще ми е интересно да видя крайните резултати.
Редактирах мнението с резултатите и го добавих. Надявам се да не съм направил някоя идиотщина, защото още не съм си изпил сутрeшното кафе. :)
| Golden Gega Мерси, ще ми е интересно да видя крайните резултати.
Редактирах мнението с резултатите и го добавих. Надявам се да не съм направил някоя идиотщина, защото още не съм си изпил сутрeшното кафе. :)
Мерси, сега да разбирам че при теб няма как да пуснем и на Джони нещата, т.е. да сравним неговото решение с твоите?
Golden Gega | Golden Gega Мерси, ще ми е интересно да видя крайните резултати.
Редактирах мнението с резултатите и го добавих. Надявам се да не съм направил някоя идиотщина, защото още не съм си изпил сутрeшното кафе. :)
Мерси, сега да разбирам че при теб няма как да пуснем и на Джони нещата, т.е. да сравним неговото решение с твоите?
Executable което съм свалил от форум в Интернет няма как да пусна. Това ми е принцип и няма значение дали вярвам на пусналия го или не.
| Golden Gega | Golden Gega Мерси, ще ми е интересно да видя крайните резултати.
Редактирах мнението с резултатите и го добавих. Надявам се да не съм направил някоя идиотщина, защото още не съм си изпил сутрeшното кафе. :)
Мерси, сега да разбирам че при теб няма как да пуснем и на Джони нещата, т.е. да сравним неговото решение с твоите?
Executable което съм свалил от форум в Интернет няма как да пусна. Това ми е принцип и няма значение дали вярвам на пусналия го или не.
Няма грижи
| Executable което съм свалил от форум в Интернет няма как да пусна. Това ми е принцип и няма значение дали вярвам на пусналия го или не.
Въобще, сорсовете са вече достъпни: https://asm32.info/fossil/BioData
Компилира се така:
fossil clone https://fresh.flatassembler.net/fossil/repo/fresh MY_REPOS/fresh.fossil
mkdir /WORK/FreshLibDev
cd /WORK/FreshLibDev
fossil open MY_REPOS/fresh.fossil FreshLibDev
После:
fossil clone https://asm32.info/fossil/BioData MY_REPOS/BioData.fossil
mkdir /WORK/AsmLeven
cd /WORK/AsmLeven
fossil open MY_REPOS/BioData.fossil
После сетваш променливите:
TargetOS=Linux # Win32 - за Windows версията.
lib=/WORK/FreshLibDev/freshlib
После компилираш така:
cd /WORK/AsmLeven
fasm -m 300000 ./Levenshtein.asm
Трябва да се появи или Linux или Windоws изпълним файл, в зависимост от променливата TargetOS.
Браво! Много добра оптимизация - не би ми хрумнало, че може да намерим общ префикс в О(н) време и да спестим от левенщайн :)
Старата ми версия (без проверка за обя префикс): Elapsed: 222600мс
С проверка: Elapsed: 138315мс
Свали ~80 секунди върху целия сет.
johnfound | Executable което съм свалил от форум в Интернет няма как да пусна. Това ми е принцип и няма значение дали вярвам на пусналия го или не.
Въобще, сорсовете са вече достъпни: https://asm32.info/fossil/BioData
Thanks, ще пробвам. Но ще трябва да ги пусна всичките на друга машина, защото не поддържаш macOS. :)
johnfound В кода,
proc Levensteinе предишната имплементация с MMX и опит за паралелна обработка (не много ефективна при Левенщейн), а сегашният фаворит еproc Levenstein2.Следващата стъпка ще е по аналогия - ако по-малкият код се изпълнява по-бързо, следва да се приеме, че и по-малките данни ще се изпълняват по-бързо. Следователно си струва да се опита с пакетирани данни - по 2 бита на символ. (Защото това са данни за ДНК, а при тях символите са само 4).
Според мен асемблера ще блести най-много ако използваш avx(512) и смяташ разстоянията на повече (64?) стринга едновременно.
Трябва в един момент най-после да науча OpenMP и да видя колко добре ще се справи с векторизиране на С код.
johnfound | Executable което съм свалил от форум в Интернет няма как да пусна. Това ми е принцип и няма значение дали вярвам на пусналия го или не.
Въобще, сорсовете са вече достъпни: https://asm32.info/fossil/BioData
Компилира се така:
fossil clone https://fresh.flatassembler.net/fossil/repo/fresh MY_REPOS/fresh.fossil mkdir /WORK/FreshLibDev cd /WORK/FreshLibDev fossil open MY_REPOS/fresh.fossil FreshLibDevПосле:
fossil clone https://asm32.info/fossil/BioData MY_REPOS/BioData.fossil mkdir /WORK/AsmLeven cd /WORK/AsmLeven fossil open MY_REPOS/BioData.fossilПосле сетваш променливите:
TargetOS=Linux # Win32 - за Windows версията. lib=/WORK/FreshLibDev/freshlibПосле компилираш така:
cd /WORK/AsmLeven fasm -m 300000 ./Levenshtein.asmТрябва да се появи или Linux или Windоws изпълним файл, в зависимост от променливата
TargetOS.
~/tmp/work/AsmLeven$ fasm -m 300000 ./Levenshtein.asm
flat assembler version 1.73.22 (300000 kilobytes memory)
error: out of stack space.
ФейкПрофил ръста е още на LLVM 10 :)
Това вероятно има значение. Ето резултатите компилирано с gcc и clang на машина с AMD EPYC 7742.
# GCC
0: 4 6962.730499 ms
1: 4 5661.941457 ms
2: 4 5847.619775 ms
3: 4 1527.305740 ms
4: 40 5923.693092 ms
5: 4 3892.952103 ms
6: 9 4221.266831 ms
7: 6 5516.135584 ms
8: 4 2777.935761 ms
9: 6 4492.822948 ms
10: 58 7285.167814 ms
#CLANG
0: 4 3644.049879 ms
1: 4 2519.609612 ms
2: 4 2596.144889 ms
3: 4 710.885451 ms
4: 40 2639.906794 ms
5: 4 2388.691301 ms
6: 9 2232.470938 ms
7: 6 2458.542905 ms
8: 4 1260.388534 ms
9: 6 2006.592793 ms
10: 58 3208.214118 ms
Къде е оня експерт по компилаторите bvbfan да обясни колко е добро GCC. :)
P.S. Хмм, при това e инсталиран clang 10. Сега ще компилирам най-новия. :)
| Според мен асемблера ще блести най-много ако използваш avx(512) и смяташ разстоянията на повече (64?) стринга едновременно.
Това също го мислех, но искам първо да изследвам класическото решение за един стринг. Не за друго, но така или иначе отдавна се каня да пиша нещо като diff, но така и не бях се занимавал със подобни алгоритми.
| ~/tmp/work/AsmLeven$ fasm -m 300000 ./Levenshtein.asm flat assembler version 1.73.22 (300000 kilobytes memory) error: out of stack space.
Даже не знаех, че FASM има такава грешка... Или това е грешка на операционната система?
Това FASM за каква OS e?
А с еднакви нива на оптимизация ли ги компилира ? Разликата ми се струва прекалено голяма.
johnfound | ~/tmp/work/AsmLeven$ fasm -m 300000 ./Levenshtein.asm flat assembler version 1.73.22 (300000 kilobytes memory) error: out of stack space.Даже не знаех, че FASM има такава грешка... Или това е грешка на операционната система?
Това FASM за каква OS e?
allegro:~$ fasm -v
flat assembler version 1.73.22
Ubuntu-server 20.04