ФейкПрофил А с еднакви нива на оптимизация ли ги компилира ? Разликата ми се струва прекалено голяма.
Да, и двете с O6. Clang, разбира се се оплака, че такова ниво няма и го свали на О3.
Задача НЕ за интервю
johnfound Даже не знаех, че FASM има такава грешка...
Тия червените грешки са гадни, никой не ги знае кво що
| ФейкПрофил А с еднакви нива на оптимизация ли ги компилира ? Разликата ми се струва прекалено голяма.
Да, и двете с O6. Clang, разбира се се оплака, че такова ниво няма и го свали на О3.
Като гледам най-голямото е О3 ? Кой знае как се е побъркало ГЦЦто 
ФейкПрофил | ФейкПрофил А с еднакви нива на оптимизация ли ги компилира ? Разликата ми се струва прекалено голяма.
Да, и двете с O6. Clang, разбира се се оплака, че такова ниво няма и го свали на О3.
Като гледам най-голямото е О3 ? Кой знае как се е побъркало ГЦЦто
И с О3 пробвах, никаква разлика.
| 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.22Ubuntu-server 20.04
Ами при мене всичко се компилира:
$ export lib=/work/asmwork/FreshFs/FreshLibDev/freshlib/
$ export TargetOS=Linux
$ fasm -m 300000 ./Levenshtein.asm
flat assembler version 1.73.24 (300000 kilobytes memory, x64)
I18n strings placeholders: $8049EE44
7 passes, 2.0 seconds, 3715 bytes.
Единственото, което ми хрумва в момента е, че използваш някаква грешна версия на FASM несъответстваща на операционната система. Това съобщение за стека е от операционната система - компилатора просто крашва.
Въобще, виж на сайта https://flatassembler.net - За Linux/Unix има 2 версии. Едната е нейтив, а другата с използване на libc (примерно на BSD). Може някоя от тях да се държи по-добре.
johnfound Ами при мене всичко се компилира:
$ export lib=/work/asmwork/FreshFs/FreshLibDev/freshlib/ $ export TargetOS=Linux $ fasm -m 300000 ./Levenshtein.asm flat assembler version 1.73.24 (300000 kilobytes memory, x64) I18n strings placeholders: $8049EE44 7 passes, 2.0 seconds, 3715 bytes.Единственото, което ми хрумва в момента е, че използваш някаква грешна версия на FASM несъответстваща на операционната система. Това съобщение за стека е от операционната система - компилатора просто крашва.
Въобще, виж на сайта https://flatassembler.net - За Linux/Unix има 2 версии. Едната е нейтив, а другата с използване на libc (примерно на BSD). Може някоя от тях да се държи по-добре.
Просто инсталирах пакета който идва с Ubuntu. Ще погледна като имам време...
Какво дава
ulimit -s
300M стек е много, на моята машина дава 8М
ФейкПрофил Какво дава
ulimit -s300M стек е много, на моята машина дава 8М
Не. Това не е стека, а паметта, която да използва компилатора при компилирането. Особеност на самият FASM. Стека не би трябвало да крашва. Няма от какво.
ФейкПрофил Какво дава
ulimit -s300M стек е много, на моята машина дава 8М
Като вдигнах стека се компилира. Но Ubuntu отказва да изпълни 32-бит application. :)
allegro:~/tmp/work/AsmLeven$ file Levenshtein
Levenshtein: ELF 32-bit LSB executable, Intel 80386, version 1 (GNU/Linux), dynamically linked, interpreter ./ld-musl-i386.so, no section header
allegro:~/tmp/work/AsmLeven$ ./Levenshtein
-bash: ./Levenshtein: No such file or directory
johnfound ФейкПрофил Какво дава
ulimit -s300M стек е много, на моята машина дава 8М
Не. Това не е стека, а паметта, която да използва компилатора при компилирането. Особеност на самият FASM. Стека не би трябвало да крашва. Няма от какво.
Сега погледнах в сорсовете - излиза, че това си е грешка на компилатора. Свързана е действително със надвишаване на лимита на стека при вложени всякакви скоби и други вложени конструкции. Но нещо не намирам от какво се определя...
А при мене всичко се компилира. 
| ФейкПрофил Какво дава
ulimit -s300M стек е много, на моята машина дава 8М
Като вдигнах стека се компилира. Но Ubuntu отказва да изпълни 32-бит application. :)
allegro:~/tmp/work/AsmLeven$ file Levenshtein Levenshtein: ELF 32-bit LSB executable, Intel 80386, version 1 (GNU/Linux), dynamically linked, interpreter ./ld-musl-i386.so, no section header allegro:~/tmp/work/AsmLeven$ ./Levenshtein -bash: ./Levenshtein: No such file or directory
Уф, това го забравих. Изкоментирай реда:
LINUX_INTERPRETER equ './ld-musl-i386.so'
Намира се някъде в началото на сорса. Иначе ще имаш нужда от MUSL, което вече съвсем сложно става...
johnfound Уф, това го забравих. Изкоментирай реда:
LINUX_INTERPRETER equ './ld-musl-i386.so'Намира се някъде в началото на сорса. Иначе ще имаш нужда от MUSL, което вече съвсем сложно става...
Всъщност не е чак толкова сложно. Ето ти един bash скрипт за компилиране на MUSL:
#!/bin/sh
rm -rf ./muslsrc/
if [ -f ./ld-musl-i386.so ]; then
echo "The library is already compiled. Delete the binary files for rebuild."
exit 0
fi
if [ ! -f ./musl*.tar.gz ]; then
echo "Downloading MUSL source archive..."
{ wget https://www.musl-libc.org/releases/musl-latest.tar.gz 2> /dev/null; } || { echo >&2 "Error: missing MUSL sources."; exit 1; }
fi
mkdir muslsrc
{ tar --wildcards --strip-components 1 -C ./muslsrc/ -xzf ./musl*.tar.gz 2> /dev/null; } || { echo "Error: Broken MUSL source archive."; exit 2; }
cd muslsrc
echo "Compiling MUSL ..."
./configure --prefix=../musl --host=i386 CC="gcc -m32" CFLAGS="-Os -fno-omit-frame-pointer -mpreferred-stack-boundary=2 -march=x86-64" CROSS_COMPILE="/bin/" > /dev/null 2>&1 || { echo >&2 "Error: Can't configure MUSL."; exit 3; }
make -j 4 > /dev/null 2>&1 || { echo >&2 "Error: Can't compile MUSL."; exit 3; }
make -j 4 install > /dev/null 2>&1 || { echo >&2 "Error: Can't install MUSL to the current directory."; exit 3; }
cd ..
rm -rf ./muslsrc/ &
strip ./ld-musl-i386.so
echo "Building process finished successfully."
Ако решиш така (ако нямаш инсталирана поддръжка за 32 битови приложения, то само така) то нищо не коментирай в сорса, а компилираната библиотека ld-musl-i386.so я сложи при изпълнимия файл и тогава ще тръгне.
А сега малко зарибявка. Последни резултати на Pentium N3540:
0: Dist: 4, Time: 751 ms
1: Dist: 4, Time: 700 ms
2: Dist: 4, Time: 723 ms
3: Dist: 4, Time: 23 ms
4: Dist: 40, Time: 753 ms
5: Dist: 4, Time: 404 ms
6: Dist: 9, Time: 654 ms
7: Dist: 6, Time: 755 ms
8: Dist: 4, Time: 226 ms
9: Dist: 6, Time: 686 ms
Това според мене е по-бързо от варианта с trie на числотрошачката на Пайпа.
Напомням, че това е процесор с пасивно охлаждане на нетбук Acer.
Дали мога да бия и GPU-то?
Това ще работи ли толкоав бързо със всякакъв вид входни данни с тази дължина на стринга ?
Delegate Това ще работи ли толкоав бързо със всякакъв вид входни данни с тази дължина на стринга ?
Да. Може и с други дължини, но алгоритъма си е все О(n^2).
johnfound А сега малко зарибявка.
0: Dist: 4, Time: 751 ms 1: Dist: 4, Time: 700 ms 2: Dist: 4, Time: 723 ms 3: Dist: 4, Time: 23 ms 4: Dist: 40, Time: 753 ms 5: Dist: 4, Time: 404 ms 6: Dist: 9, Time: 654 ms 7: Dist: 6, Time: 755 ms 8: Dist: 4, Time: 226 ms 9: Dist: 6, Time: 686 msТова според мене е по-бързо от варианта с trie на числотрошачката на Пайпа.
Напомням, че това е процесор с пасивно охлаждане на нетбук Acer.
Дали мога да бия и GPU-то?
Doctors HATE him for revealing this secret
Това без векторни инструкции?
johnfound А сега малко зарибявка.
0: Dist: 4, Time: 751 ms 1: Dist: 4, Time: 700 ms 2: Dist: 4, Time: 723 ms 3: Dist: 4, Time: 23 ms 4: Dist: 40, Time: 753 ms 5: Dist: 4, Time: 404 ms 6: Dist: 9, Time: 654 ms 7: Dist: 6, Time: 755 ms 8: Dist: 4, Time: 226 ms 9: Dist: 6, Time: 686 msТова според мене е по-бързо от варианта с trie на числотрошачката на Пайпа.
Напомням, че това е процесор с пасивно охлаждане на нетбук Acer.
Дали мога да бия и GPU-то?
Nice. Ако си спомням правилно средното време с GPU-то беше някъде около 60 ms обаче.
| johnfound А сега малко зарибявка.
0: Dist: 4, Time: 751 ms 1: Dist: 4, Time: 700 ms 2: Dist: 4, Time: 723 ms 3: Dist: 4, Time: 23 ms 4: Dist: 40, Time: 753 ms 5: Dist: 4, Time: 404 ms 6: Dist: 9, Time: 654 ms 7: Dist: 6, Time: 755 ms 8: Dist: 4, Time: 226 ms 9: Dist: 6, Time: 686 msТова според мене е по-бързо от варианта с trie на числотрошачката на Пайпа.
Напомням, че това е процесор с пасивно охлаждане на нетбук Acer.
Дали мога да бия и GPU-то?
Nice. Ако си спомням правилно средното време с GPU-то беше някъде около 60 ms обаче.
Е, на твоята числотрошачка и моята програма ще е по-бърза. А пък на моето "GPU", времето сигурно няма да е 60ms (ако въобще тръгне).
Пък и това, мисля, не е тавана. Имам още някой и друг фокус в ръкава. 