| ЦЯЛАТА информация е нужна в случая. Колко пъти още трябва да се повтори за да го схванеш?
Trie-а е най-елементарния възможен.
Все още не казваш какъв вид е трая, най-лесният е да си обикаляш всички низове, трая е за бързо търсене. Разбрах, че цялата се иска, но както ти писах преди това, слагаш си гпу кода за узър функция и sqlite целият код ти е 10-на ред (питон, с, го каквото искаш). Доста по-лесно от какъвто и да е трай, както и не казваш валидация имаш ли?
bvbfan | ЦЯЛАТА информация е нужна в случая. Колко пъти още трябва да се повтори за да го схванеш?
Trie-а е най-елементарния възможен.
Все още не казваш какъв вид е трая, най-лесният е да си обикаляш всички низове, трая е за бързо търсене. Разбрах, че цялата се иска, но както ти писах преди това, слагаш си гпу кода за узър функция и sqlite целият код ти е 10-на ред (питон, с, го каквото искаш). Доста по-лесно от какъвто и да е трай, както и не казваш валидация имаш ли?
Какви видове tries има?
Явно нямаш абсолютно никаква идея как работят GPUs. :)
Задачата просто си се подава на паралелизация, нуждата от синхронизация между нишките е колко....никаква. Затова ще намазва добре от многонишкова имплементация. А още по-добре от гпу такава. Това не е поради нещо толкова странно, гпу-то без много фантазия може да се разглежда като цпу с хиляда, две хиляди и повече там ядра, естествено това е супер опростен поглед, но реално причината да намазва толкова оттова че се изпълнява върху гпу е тази.
gat3way Задачата просто си се подава на паралелизация, нуждата от синхронизация между нишките е колко....никаква. Затова ще намазва добре от многонишкова имплементация. А още по-добре от гпу такава. Това не е поради нещо толкова странно, гпу-то без много фантазия може да се разглежда като цпу с хиляда, две хиляди и повече там ядра, естествено това е супер опростен поглед, но реално причината да намазва толкова оттова че се изпълнява върху гпу е тази.
Аз не бях сигурен дали memory bandwidth ще е достатъчен да "пълни" 256 нишки, но изглеждаше ОК.
То гпуто това би трябвало да му е по-голям проблем и то вероятно не толкова заради шината към паметта че няма да смогне, а заради всичките безумни малоумни индиански ритуали свързани с това, достъпа до паметта там е некаква ужасия подаваща се на сума ти черни магии, там bank, channel конфликти и всекакви такива глупотии.
bvbfan ФейкПрофил Абе това trie колко памет харчи ? Аз се заиграх, но ми заема 2ГБ :(
Харчи (виж prefix/radix trie) също както и непрекъснатото зареждане при всяко пускане на програмата, но Пайп-а не иска да разисква тоя въпрос, защото компенсира със смятането на гпу и неглижира проблема.
Зареждането при всяко пускане не е проблем - trie-то ми го вдига за 1.3 секунди, което не е никак зле за програма, която ще се пуска точно веднъж за даден сет от данни. Единствения проблем е високата консумация на памет, но тук съм си виновен аз, щото ползвах hashmap, а при само 4 възможни букви може да се направи по-ефективно :)
Интересно е също дали може trie-to да се възползва от avx инструкции, защото както се оказа брутфорса може и това там свали времето 10 пъти.
ФейкПрофил bvbfan ФейкПрофил Абе това trie колко памет харчи ? Аз се заиграх, но ми заема 2ГБ :(
Харчи (виж prefix/radix trie) също както и непрекъснатото зареждане при всяко пускане на програмата, но Пайп-а не иска да разисква тоя въпрос, защото компенсира със смятането на гпу и неглижира проблема.
Зареждането при всяко пускане не е проблем - trie-то ми го вдига за 1.3 секунди, което не е никак зле за програма, която ще се пуска точно веднъж за даден сет от данни. Единствения проблем е високата консумация на памет, но тук съм си виновен аз, щото ползвах hashmap, а при само 4 възможни букви може да се направи по-ефективно :)
Интересно е също дали може trie-to да се възползва от avx инструкции, защото както се оказа брутфорса може и това там свали времето 10 пъти.
Според мен най-лесния вариант е ако се направи да търси едновременно N стринга. Векторизирането на търсенето в дървото ми се струва трудно.
| Какви видове tries има?
Явно нямаш абсолютно никаква идея как работят GPUs. :)
Различни видове, ти кой си написал? Видове Аз доколкото разбрах ти ползваш гпу-то за левенщайн трая си в рама. Гпу-то трябва да копира паметта, иначе работи в паралел, като не съм писал нищо, само пробвал да фиксвам.
Обаче sqlite решение все още никой не е споделил :)
bvbfan | Какви видове tries има?
Явно нямаш абсолютно никаква идея как работят GPUs. :)
Различни видове, ти кой си написал? Видове Аз доколкото разбрах ти ползваш гпу-то за левенщайн трая си в рама. Гпу-то трябва да копира паметта, иначе работи в паралел, като не съм писал нищо, само пробвал да фиксвам.
Аз съм написал Trie. Ако сравняваш два стринга с GPU ще е ЗНАЧИТЕЛНО по-бавно от това да ги сравняваш с CPU. Та, как точно ще направиш юзър функция на sqlite, която сравнява стринговете с GPU?
Какво решение очакваш, имаш данни, които са в базата, имаш юзер функция за sqlite и ти трябва заявка като от първа страница.
bvbfan Какво решение очакваш, имаш данни, които са в базата, имаш юзер функция за sqlite и ти трябва заявка като от първа страница.
И какво прави тази юзер функция?
Намира дистанцията между 2 стринга, sqlite ти ги групира / подрежда спрямо заявката. Все още не разбрах какъв е трая, поне кажи какви са ключовете на листата.
bvbfan Намира дистанцията между 2 стринга, sqlite ти ги групира / подрежда спрямо заявката. Все още не разбрах какъв е трая, поне кажи какви са ключовете на листата.
И за колко време си въобразяваш, че GPU-то ще сравни два стринга?
Помисли как ще напишеш трай да прави каквото трябва и ще си отговориш сам на въпроса за ключовете на листата.
ФейкПрофил Обаче sqlite решение все още никой не е споделил :)
Търси се философския камък под формата на магична юзър дифайнд функция :)
Само Гегата опита да защити честта на релационните бази, Джон ужким е в тоя лагер ама рита за отбор асемблер :)
Ебати яката тема, чей зема още пуканки, жалко че интересите ми са по-скоро в областта на програмиране с възможно най-малко церемония което малко се бие с възможно най-ефективния код въпреки че обожавам Цъ без плюсовете
| Помисли как ще напишеш трай да прави каквото трябва и ще си отговориш сам на въпроса за ключовете на листата.
Аз какво да го мисля, ти как си го направил, може да се направи по няколко начина.
Айде някой който разбира от Ц и SQLite да се престраши за да разбием мита че асемблера е най-бърз. Джони може да пише по-добре от компилатор, но дали може по-добре от sqlite ?
bvbfan | Помисли как ще напишеш трай да прави каквото трябва и ще си отговориш сам на въпроса за ключовете на листата.
Аз какво да го мисля, ти как си го направил, може да се направи по няколко начина.
Кои са тези няколко начина?
Какво стана с юзър функциите в sqlite?
Иначе най-интересното от темата е, че в общи линии очевидната имплементация на който и да е език е еднакво бавна. :)
Другото интересно беше сравнителната скорост на различните процесори.
ФейкПрофил Айде някой който разбира от Ц и SQLite да се престраши за да разбием мита че асемблера е най-бърз. Джони може да пише по-добре от компилатор, но дали може по-добре от sqlite ?
За момент ми мина през акъла да напиша руби юзър функция за sqlite която генерира асемблер през FFI.
Требе да се прегледам :)