|

Кои са тези няколко начина?

Какво стана с юзър функциите в sqlite?

Prefix trie всяко листо се разклонява на общ префикс, Radix trie имаш power of 2 листа, Ternary Search - ляв, равен и десен и т.н.

Какво да стане с функцията, тя е левенщайн, приемаш 2 стринга и връщаш близостта.

bvbfan

|

Кои са тези няколко начина?

Какво стана с юзър функциите в sqlite?

Prefix trie всяко листо се разклонява на общ префикс, Radix trie имаш power of 2 листа, Ternary Search - ляв, равен и десен и т.н.

Prefix trie. Казах ти, най-простото.

bvbfan

Какво да стане с функцията, тя е левенщайн, приемаш 2 стринга и връщаш близостта.

Kak ще я направиш бърза на GPU?

db.define("LEVENSTEIN", [](std::string_view s1, std::string_view s2) -> int {
    const auto m = s1.size();
    const auto n = s2.size();

    if(m == 0) return n;
    if(n == 0) return m;

    std::vector<size_t> costs;
    costs.resize(n + 1);
    for (auto i = 0u; i < n + 1; ++i)
        costs[i] = i + 1;

    for (auto i = 0u; i < m; ++i) {
        costs[0] = i + 1;
        std::size_t corner = i;
        for (auto j = 0u; j < n; ++j) {
            auto upper = costs[j + 1];
            if(s1[i] == s2[j]) {
                costs[j + 1] = corner;
            } else {
                auto t = std::min(upper, corner);
                costs[j + 1] = std::min(costs[j], t) + 1;
            }
            corner = upper;
        }
    }
    return costs[n];
});

auto levenstein = db << "SELECT r.word as rw, MIN(LEVENSTEIN(?, r.word)) FROM right r";
db << "SELECT l.word FROM left l ORDER BY l.word"
   >> [&](std::string_view v) {
          levenstein << v >> [v](std::string_view s1, int leve) {
          std::cout << v << " : " << s1 << " : " << leve << '\n';
      };
      levenstein++;
  };

db << "SELECT l.word, r.word, MIN(LEVENSTEIN(l.word, r.word)) as l "
      "FROM left l JOIN right r GROUP BY l.word HAVING l < 60"
   >> [&](std::string_view s1, std::string_view s2, int leve) {
       std::cout << s1 << " : " << s2 << " : " << leve << '\n';
   };

Разбито на заявки е по-бързо от една заявка, някой по-добър да обясни?

g++ -Wall -std=c++17 -O3 -march=native main.cpp -o leve -lsqlite3

Може да се добави sqlite amalgamation за да се компилира и той с - O3, че стандартните са с - O2.

bvbfan

....

Може да се добави sqlite amalgamation за да се компилира и той с - O3, че стандартните са с - O2.

....

Интересно решение. При мене работи не много бързо, но не свръх бавно: примерно 10 секунди на ред.

Две забележки - добре е да качиш и базата данни с тестовите данни, защото не е ясно кое е left и кое right на пръв поглед. (В left отиват редовете от файла t2.csv, а в right от Dataset.csv).

Също добре е да извеждаш rowid-то на left защото резултатите излизат разбъркани и е трудно да се следят за коректност. Обратно - самите стрингове с данни можеш да не ги извеждаш, защото са много малко информативни.

Освен това имаш грешка в този ред:

        db << "CREATE TABLE IF NOT EXISTS right (word BLOB NOT NULL PRIMARI KEY);";

Но ако сложиш и създадената база в архива, то тези редове можеш и въобще да ги махнеш.

Най-накрая успях да фиксна Windows версията, така че прикачам файл с компилираните програми с използване на SSE2, ако някой иска да тества на Windows с последната версия.

Проблема се оказа в това, че HeapAlloc на Windows алокира паметта подравнена на 8 байта, а аз си мислех, че е на 16. (Но WINE версията подравнява на 16, което прави програмата да работи във WINE, но не и във Windows! )

В резултат се наложи да се модифицира FreshLib слоя за Win32 - защото програмите трябва да се държат еднакво при прекомпилиране на различните операционни системи.

Така че, който иска да компилира от сорс, ще трябва да си ъпдейтне и версията на FreshLibDev от репозиторито.

johnfound

Най-накрая успях да фиксна Windows версията, така че прикачам файл с компилираните програми с използване на SSE2, ако някой иска да тества на Windows с последната версия.

Проблема се оказа в това, че HeapAlloc на Windows алокира паметта подравнена на 8 байта, а аз си мислех, че е на 16. (Но WINE версията подравнява на 16, което прави програмата да работи във WINE, но не и във Windows! )

В резултат се наложи да се модифицира FreshLib слоя за Win32 - защото програмите трябва да се държат еднакво при прекомпилиране на различните операционни системи.

Така че, който иска да компилира от сорс, ще трябва да си ъпдейтне и версията на FreshLibDev от репозиторито.

We are beating a dead horse here

johnfound

bvbfan

....

Може да се добави sqlite amalgamation за да се компилира и той с - O3, че стандартните са с - O2.

....

Интересно решение. При мене работи не много бързо, но не свръх бавно: примерно 10 секунди на ред.

Две забележки - добре е да качиш и базата данни с тестовите данни, защото не е ясно кое е left и кое right на пръв поглед. (В left отиват редовете от файла t2.csv, а в right от Dataset.csv).

Също добре е да извеждаш rowid-то на left защото резултатите излизат разбъркани и е трудно да се следят за коректност. Обратно - самите стрингове с данни можеш да не ги извеждаш, защото са много малко информативни.

Освен това имаш грешка в този ред:

        db << "CREATE TABLE IF NOT EXISTS right (word BLOB NOT NULL PRIMARI KEY);";

Но ако сложиш и създадената база в архива, то тези редове можеш и въобще да ги махнеш.

Чакай сега, нали sqlite щеше да е по-бързо от моят C код, понеже го бил писал някакъв C гуру? :)

gat3way

Това с векторизацията на теслата доста вероятно ще доведе до противоречив, вероятно по-лош резултат. Аз дори съм учуден че има вектори в кудата, в опенцл-а има защото е за различна железария - от процесори през FPGA до видеокарти, там някои платформи си имат реално хардуерни SIMD регистри отдолу. Нвидията няма (АМД имаха в по-старите архитектури, ма ги махнаха). Тоест от векторни операции няма да намажеш абсолютно нищо, просто защото компилатора ще ги сведе до n на броя скаларни, които ще подкара една след друга. Обаче в един частен случай има файда от това дори при това положение - при достъпването на памет. Това е защото хардуера позволява наведнъж да се чете повече памет, сега колко точно не помня, но определено е повече от един int на workitem. И тогава, от четенето от векторен буфер във векторна променлива има файда. От друга страна, това ще ти вдигне бройката регистри, които ползва кернела и съответно ще имаш по-ниско occupancy. Та като цяло дали ще намажеш или не е въпрос на експерименти.

Да, векторизацията доведе до по-лош резултат. Да не говорим, че кода стана доста по-неразбираем и сложен.

И аз да се включа с avx2 решение на асемблер. 61мс средно на низ дава при мен. Това как се дебъгва под wine не е истина.

BIGBUGEX

Това как се дебъгва под wine не е истина.

Ами да, малко странен стил на кода - засукан. А защо трябваше да е за Windows?

За съжаление не работи на Pentium P3540 – няма AVX. Ще го пробвам на AMD-то по-късно днес.

johnfound

BIGBUGEX

Това как се дебъгва под wine не е истина.

Ами да, малко странен стил на кода - засукан. А защо трябваше да е за Windows?

За съжаление не работи на Pentium P3540 – няма AVX. Ще го пробвам на AMD-то по-късно днес.

Windows има по-добрата конвенция на извикване в 64 битов режим.

johnfound

Интересно решение. При мене работи не много бързо, но не свръх бавно: примерно 10 секунди на ред.

Две забележки - добре е да качиш и базата данни с тестовите данни, защото не е ясно кое е left и кое right на пръв поглед. (В left отиват редовете от файла t2.csv, а в right от Dataset.csv).

При мен, разбито на заявки е под 3 сек. на ред, с една заявка поне 2 пъти по-бавно. left е t2.csv (сета от думи, на които се търсят най-близките в дясно), right e Dataset.csv (по-големият сет, в който се търсят съвпаденията).

По подразбиране в повечето дистрибуции не се прилагат големи оптимизации при компилиранe и линкване, има и изключения - Open Mandriva използват - O3 и LTO, което е достатъчно оптимизирано. Освен това, статичното линкване и O3 ще ти даде нужното ускорение, все пак за нас е критично да имаме бързодействие, O2 съвсем не дава това.

|

Чакай сега, нали sqlite щеше да е по-бързо от моят C код, понеже го бил писал някакъв C гуру? :)

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

BIGBUGEX

Windows има по-добрата конвенция на извикване в 64 битов режим.

М-м-м-м, много спорно. Още повече пък относно точно тази програма. Конвенциите за викане касаят само системните функции, които тука не играят никаква роля. А в твоя код можеш да си правиш каквото си искаш на която и да е операционна система.

За съжаление AVX2 не се поддържа и на AMD процесора ми.

Програмата гърми със illegal instruction на адрес 4010f9h.

Компилирането със clang и - O3 на sqlite бутна времето с още секунда надолу, около 2 сек. на ред.

gcc version 9.3.0
clang version 10.0.1

bvbfan

Компилирането със clang и - O3 на sqlite бутна времето с още секунда надолу, около 2 сек. на ред.

gcc version 9.3.0
clang version 10.0.1

По този повод, може да си поиграеш и със PRAGMA threads - Не съм много сигурен как точно SQLite използва допълнителни нишки (документацията е много лаконична в това отношение), но някои от операциите в базата и индексите по принцип могат да се паралелят добре. По подразбиране това е изключено въобще.

Няма келепир от нишки, аз в момента отварям базата без мутекс-и, прекалено синхронно се случват нещата.

SELECT l.word FROM left l WHERE l.ROWID < 50 ORDER BY l.word
SELECT l.word FROM left l WHERE l.ROWID >= 50 ORDER BY l.word

Реално като захване едната нишка - работи само тя, по някоя време захваща другата т.е. напълно синхронно и реално не работят една върху друга.

bvbfan

Няма келепир от нишки, аз в момента отварям базата без мутекс-и, прекалено синхронно се случват нещата.

SELECT l.word FROM left l WHERE l.ROWID < 50 ORDER BY l.word
SELECT l.word FROM left l WHERE l.ROWID >= 50 ORDER BY l.word

Реално като захване едната нишка - работи само тя, по някоя време захваща другата т.е. напълно синхронно и реално не работят една върху друга.

Аз имах предвид вътрешната заявка:

SELECT r.word as rw, MIN(LEVENSTEIN(?, r.word)) FROM right r

Агрегатните функции като MIN() вероятно могат да се ускоряват с паралелна обработка.

BIGBUGEX

61мс средно на низ дава при мен.

BIGBUGEX, ако обичаш, можеш ли да тестваш това в атачмънта колко е бързо на AMD процесор?

Сега направих една промяна, която ускори програмата 3 пъти (!) на моят А4-1200, но само с 10% на интелски процесор. Интересно дали на други АМД процесори ще се получи такова ускорение...

В архива има два изпълними файла за Линукс: LevenshteinOld и LevenshteinNew - съответно без промяната и със промяната.

Времената на А4-1200 изглеждат така:

; Преди:
0: Dist: 4, Time: 1894 ms
1: Dist: 4, Time: 1776 ms
2: Dist: 4, Time: 1844 ms
3: Dist: 4, Time: 60 ms
4: Dist: 40, Time: 1888 ms
5: Dist: 4, Time: 1032 ms
6: Dist: 9, Time: 1598 ms
7: Dist: 6, Time: 1895 ms
8: Dist: 4, Time: 574 ms
9: Dist: 6, Time: 1697 ms

; Сега:
0: Dist: 4, Time: 665 ms
1: Dist: 4, Time: 622 ms
2: Dist: 4, Time: 647 ms
3: Dist: 4, Time: 26 ms
4: Dist: 40, Time: 660 ms
5: Dist: 4, Time: 365 ms
6: Dist: 9, Time: 562 ms
7: Dist: 6, Time: 670 ms
8: Dist: 4, Time: 206 ms
9: Dist: 6, Time: 598 ms