To co? Bawimy się? :D

[mariotti]

Bez przesady, te standardowe narzędzia są uniwersalne i naprawdę szybkie. To są poprostu zupełnie inne narzędzia.

Przykładowo minised ma 5% możliwości seda. Tylko czasem potrzebujemy tylko tych 2% możliwości, a dużo ważniejsza jest szybkość przy przetworzenie terabajtów danych.

Rozumiem, lepsza wydajność za mniejszą funkcjonalność.

Cgrep to akurat unikalny programik. Tylko znowu ma pewne cechy których nie posiada GNU grep, ale również brakuje mu kilku opcji grepa.
Powstał nie byle gdzie, bo w Bell Labs, a tam pracowali naprawdę łebscy goście. Twórcy UNIXA, języka C, C++, R. Bodajże 7 pracowników tego laboratorium "talentów" zostało nagrodzonych Noblem.

Czytałem kiedyś że twórcy Perla szydzili z grepa... ale chyba zaczynam za bardzo odbiegać :)

Wracając do tematu. Jakbym jednak sam chciał/musiał rzeźbić w C++ programik do optymalizacji WU,
to niby wiem jak to zrobić, ale niepokoi mnie pewien szczegół: Są małe rekordy binarnych danych, mają
rozmiar w okolicach 50 - 100 bajtów. Są one zapisane w ogromnym pliku na dysku talerzowym. Odczytujemy
te rekordy sekwencyjnie w pętli, np. tak:

Kod [Zaznacz] Rozwiń


while( not_end_of_file( file , rekord ) ) {
}


W pętli robimy analizę danych i z dużym prawdopodobieństwem odczytany rekord
trzeba zmodyfikować i zapisać:

Kod [Zaznacz] Rozwiń


while( not_end_of_file( file , rekord ) ) {
  if( analiza( rekord ) ) { // prawdopodobieństwo że warunek prawdziwy: 95-99%
    modyfikuj( rekord );
    cofnij_wskaznik_pliku( file , size(rekord) );
    zapisz( file , rekord );
  }
}


I teraz moje pytanie: czy powyższy kod jest wydajny? Czy takie ciągłe cofanie o jeden rekord jest szybkie?
Czy może lepiej przeanalizować w porcjach po 10k rekordów, cofnąć wskaźnik pliku o rozmiar całej
porcji i zapisać całą porcję?


Pozdrawiam

[buninek]

W temacie programowania zupełnie nie pomogę. Przy tego typu "prostych" programach potrzebna jest duża wiedza. Nawet mając duże doświadczenie w programowaniu, może okazać się ono niewystarczające.

Spójrz na to,  szybka wersja sort | uniq -c | sort -n[r] w C++.
https://gist.github.com/alisaifee/2983201

To jakiś wiekowy kod, bo g++-4.7.3, g++-4.4.4, g++-4.3.4 wywala błąd. Dopiero z g++-4.2.4 powiodła się kompilacja.
Wcale nie taka szybka, tylko 3 razy wolniejsza.

[mariotti]

W temacie programowania zupełnie nie pomogę. Przy tego typu "prostych" programach potrzebna jest duża wiedza.
Nawet mając duże doświadczenie w programowaniu, może okazać się ono niewystarczające.

Trzeba długo tuningować takie programiki w różnych warunkach, w różnym sprzęcie - a to
jest katorżnicza robota. W końcu można dobrać zadowalające parametry danego
narzędzia. Pewnie będę musiał sprawdzić w praktyce czy cofanie wskaźnika o jeden
rekord mocno spowalnia.

Spójrz na to,  szybka wersja sort | uniq -c | sort -n[r] w C++.
https://gist.github.com/alisaifee/2983201

Widać, że ktoś wszędzie gdzie się dało wykorzystał STL.
Na pierwszy rzut oka zgrabny programik.

To jakiś wiekowy kod, bo g++-4.7.3, g++-4.4.4, g++-4.3.4 wywala błąd. Dopiero z g++-4.2.4 powiodła się kompilacja.
Wcale nie taka szybka, tylko 3 razy wolniejsza.

Yyyy to działa wolniej niż shellowe? :D Nie przeanalizuję na szybko, bo używam na co
dzień innej biblioteki, nie mam wprawy w STLu.

Eksperyment zrobiony na kolanie, też nie starałem się optymalizować.
Wynik: bash: 74 sekundy; specjalistyczny algorytm: 8 sekund - 9 razy szybciej.

Na samym dole listingu kod w C++.

Kod [Zaznacz] Rozwiń


ls -l
razem 2148
-rwx------ 1 x x      52 2013-06-19 01:40 go1.sh
-rwx------ 1 x x      36 2013-06-19 01:40 go2.sh
-rwx------ 1 x x      54 2013-06-19 01:41 go.sh
-rw-rw-r-- 1 x x    1081 2013-06-19 01:39 main.cpp
-rwxrwxr-x 1 x x 2140238 2013-06-19 01:15 perft4
-rwxrwxr-x 1 x x   19042 2013-06-19 01:39 suniq
-rw-rw-r-- 1 x x     289 2013-06-19 00:47 suniq.pro
-rw-rw-r-- 1 x x   15264 2013-06-19 01:19 suniq.pro.user
x@biglaptop:~/Dokumenty/c/suniq$ cat go.sh
(
echo printLeafs 5
echo quit
) | ./perft4 > data.txt
x@biglaptop:~/Dokumenty/c/suniq$ ./go.sh
x@biglaptop:~/Dokumenty/c/suniq$ ls -l
razem 285324
-rw-rw-r-- 1 x x 289969208 2013-06-19 01:42 data.txt
-rwx------ 1 x x        52 2013-06-19 01:40 go1.sh
-rwx------ 1 x x        36 2013-06-19 01:40 go2.sh
-rwx------ 1 x x        54 2013-06-19 01:41 go.sh
-rw-rw-r-- 1 x x      1081 2013-06-19 01:39 main.cpp
-rwxrwxr-x 1 x x   2140238 2013-06-19 01:15 perft4
-rwxrwxr-x 1 x x     19042 2013-06-19 01:39 suniq
-rw-rw-r-- 1 x x       289 2013-06-19 00:47 suniq.pro
-rw-rw-r-- 1 x x     15264 2013-06-19 01:19 suniq.pro.user
x@biglaptop:~/Dokumenty/c/suniq$ cat go1.sh
cat data.txt | sort | uniq -c | sort -nr > out1.txt
x@biglaptop:~/Dokumenty/c/suniq$ time ./go1.sh

real    1m14.931s
user    1m16.465s
sys     0m1.880s
x@biglaptop:~/Dokumenty/c/suniq$ cat go2.sh
cat data.txt | ./suniq r > out2.txt
x@biglaptop:~/Dokumenty/c/suniq$ time ./go2.sh

real    0m8.541s
user    0m8.053s
sys     0m0.800s
x@biglaptop:~/Dokumenty/c/suniq$ ls -l
razem 393324
-rw-rw-r-- 1 x x 289969208 2013-06-19 01:42 data.txt
-rwx------ 1 x x        52 2013-06-19 01:40 go1.sh
-rwx------ 1 x x        36 2013-06-19 01:40 go2.sh
-rwx------ 1 x x        54 2013-06-19 01:41 go.sh
-rw-rw-r-- 1 x x      1081 2013-06-19 01:39 main.cpp
-rw-rw-r-- 1 x x  55292061 2013-06-19 01:44 out1.txt
-rw-rw-r-- 1 x x  55292061 2013-06-19 01:44 out2.txt
-rwxrwxr-x 1 x x   2140238 2013-06-19 01:15 perft4
-rwxrwxr-x 1 x x     19042 2013-06-19 01:39 suniq
-rw-rw-r-- 1 x x       289 2013-06-19 00:47 suniq.pro
-rw-rw-r-- 1 x x     15264 2013-06-19 01:19 suniq.pro.user
x@biglaptop:~/Dokumenty/c/suniq$ head out1.txt
     87 rnbqkbnr/pppppppp/8/8/8/4P3/PPPP1PPP/RNBQKBNR b qkQK -
     87 rnbqkbnr/pppppppp/8/8/4P3/8/PPPP1PPP/RNBQKBNR b qkQK -
     79 rnbqkbnr/pppppppp/8/8/3P4/8/PPP1PPPP/RNBQKBNR b qkQK -
     75 rnbqkbnr/pppppppp/8/8/8/3P4/PPP1PPPP/RNBQKBNR b qkQK -
     56 rnbqkbnr/pppppppp/8/8/8/6P1/PPPPPP1P/RNBQKBNR b qkQK -
     56 rnbqkbnr/pppppppp/8/8/8/1P6/P1PPPPPP/RNBQKBNR b qkQK -
     56 rnbqkbnr/pppppppp/8/8/6P1/8/PPPPPP1P/RNBQKBNR b qkQK -
     56 rnbqkbnr/pppppppp/8/8/2P5/8/PP1PPPPP/RNBQKBNR b qkQK -
     56 rnbqkbnr/pppppppp/8/8/1P6/8/P1PPPPPP/RNBQKBNR b qkQK -
     52 rnbqkbnr/pppppppp/8/8/8/5N2/PPPPPPPP/RNBQKB1R b qkQK -
x@biglaptop:~/Dokumenty/c/suniq$ head out2.txt
     87 rnbqkbnr/pppppppp/8/8/8/4P3/PPPP1PPP/RNBQKBNR b qkQK -
     87 rnbqkbnr/pppppppp/8/8/4P3/8/PPPP1PPP/RNBQKBNR b qkQK -
     79 rnbqkbnr/pppppppp/8/8/3P4/8/PPP1PPPP/RNBQKBNR b qkQK -
     75 rnbqkbnr/pppppppp/8/8/8/3P4/PPP1PPPP/RNBQKBNR b qkQK -
     56 rnbqkbnr/pppppppp/8/8/2P5/8/PP1PPPPP/RNBQKBNR b qkQK -
     56 rnbqkbnr/pppppppp/8/8/8/6P1/PPPPPP1P/RNBQKBNR b qkQK -
     56 rnbqkbnr/pppppppp/8/8/6P1/8/PPPPPP1P/RNBQKBNR b qkQK -
     56 rnbqkbnr/pppppppp/8/8/8/1P6/P1PPPPPP/RNBQKBNR b qkQK -
     56 rnbqkbnr/pppppppp/8/8/1P6/8/P1PPPPPP/RNBQKBNR b qkQK -
     52 rnbqkbnr/pppppppp/8/8/8/2N5/PPPPPPPP/R1BQKBNR b qkQK -
x@biglaptop:~/Dokumenty/c/suniq$ cat main.cpp
//Listing całego programu:
#include <cstdio>
#include <cstring>
#include <QHash>
#include <QVector>
#include <QtAlgorithms>

#define MAX_ROW (1024*1024)

struct TData {
        QString str;
        int  cnt;
};


bool lessThatA( const TData &a , const TData &b ) {
        return a.cnt > b.cnt;
}
bool lessThatB( const TData &a , const TData &b ) {
        return b.cnt < a.cnt;
}


int main( int argc, char *argv[] ) {
        QHash<QString,int> hash;
        QVector<TData>   data;

        FILE *f = stdin; // TODO if_exists(argv,file) ? fopen(file) : stdin;

        char *buf = new char[MAX_ROW];
        while( fgets( buf , MAX_ROW , f ) ) {
                QString s(buf);
                if( hash.contains(s) ) {
                        data[ hash[s] ].cnt ++ ;
                } else {
                        hash.insert( s , data.size() );
                        TData tmp;
                        tmp.str = s;
                        tmp.cnt = 1;
                        data.append( tmp );
                }
        }

        qSort( data.begin() , data.end() , argc > 1 && strstr( argv[1] , "r" ) ? lessThatA : lessThatB );

        for( int i=0 ; i<data.size() ; i++ )
                printf("%7d %s" , data[i].cnt , qPrintable(data[i].str) );



//      delete[] buf;
//      for( int i=0 ; i<data.size() ; i++ )
//              free( data[i].str );

        if( f != stdin ) fclose(f);
        return 0;
}



Pozdrawiam

[buninek]

Pięknie, skompilowałem, a teraz test.
Bez dodatkowych okrążeń na UTF-8 dla  sorta i uniq, tylko uczciwie, na tych samych zasadach, ograniczmy się do kodu Ascii. Skoro twoja wersja suniq nie obsługuje.

LC_ALL=C sort |LC_ALL=C  uniq -c | LC_ALL=C sort -nr > out1.txt

U mnie nadal sort, uniq jest ponad dwukrotnie szybszy.

[mariotti]

Pięknie, skompilowałem, a teraz test.
Bez dodatkowych okrążeń na UTF-8 dla  sorta i uniq, tylko uczciwie, na tych samych zasadach, ograniczmy się do kodu Ascii. Skoro twoja wersja suniq nie obsługuje.

LC_ALL=C sort |LC_ALL=C  uniq -c | LC_ALL=C sort -nr > out1.txt

U mnie nadal sort, uniq jest ponad dwukrotnie szybszy.

Ja też nic nie optymalizowałem, obliczenia były na utf-16.
Żeby konwertował z utf-8 na utf-16 i potem z powrotem, to
trzeba dodać małą poprawkę:

Kod [Zaznacz] Rozwiń


#include <QHash>
#include <QVector>
#include <QtAlgorithms>
#include <QTextStream>

struct TData {
QString str;
int  cnt;
};

bool lessThatA( const TData &a , const TData &b ) {
return a.cnt > b.cnt;
}
bool lessThatB( const TData &a , const TData &b ) {
return b.cnt < a.cnt;
}

int main( int argc, char *argv[] ) {
QHash<QString,int> hash;
QVector<TData>   data;

QString s;
QTextStream in(stdin);
in.setCodec("UTF-8");
while( ! (s = in.readLine()).isNull() ) {
if( hash.contains(s) ) {
data[ hash[s] ].cnt ++ ;
} else {
hash.insert( s , data.size() );
TData tmp;
tmp.str = s;
tmp.cnt = 1;
data.append( tmp );
}
}

qSort( data.begin() , data.end() , argc > 1 && strstr( argv[1] , "r" ) ? lessThatA : lessThatB );

QTextStream out(stdout);
out.setCodec("UTF-8");
for( int i=0 ; i<data.size() ; i++ ) {
out<<qSetFieldWidth(7)<<data[i].cnt<<qSetFieldWidth(0)<<" "<<data[i].str<<"\n";
}

return 0;
}


U mnie nadal 7-8 razy szybciej niż:

Kod [Zaznacz] Rozwiń


cat data.txt | sort -S2000000 | uniq -c | sort -S2000000 -nr > out1.txt


Może mam starą wersję sort, uniq i cat...

Kod [Zaznacz] Rozwiń


sort --version
sort (GNU coreutils) 8.5
Copyright (C) 2010 Free Software Foundation, Inc.
Licencja GPLv3+: GNU GPL wersja 3 albo późniejsza http://gnu.org/licenses/gpl.html
To jest wolne oprogramowanie: masz prawo je zmieniać i rozpowszechniać.
Autorzy nie dają ŻADNYCH GWARANCJI w granicach dozwolonych prawem.

Autorzy: Mike Haertel i Paul Eggert.


Pozdrawiam

[Szopler]

...
I teraz moje pytanie: czy powyższy kod jest wydajny? Czy takie ciągłe cofanie o jeden rekord jest szybkie?
Czy może lepiej przeanalizować w porcjach po 10k rekordów, cofnąć wskaźnik pliku o rozmiar całej
porcji i zapisać całą porcję?

Na pewno szybciej będzie wczytać porcję danych do pamięci obrobić i zapisać niż pojedynczo linia po linii.
Odpada ileś-set razy czas dostępu do danych na dysku co w rezultacie może się przełożyć na -naście/-dziesiąt sekund.

[mariotti]

Rozwiązanie na bazie skryptu powłoki Linux działa bardzo wydajnie. Dla depth=7
obliczenia trwały zaledwie 412minut. Przy depth=7 trzeba dwa razy posortować
aż 3.2mld wierszy, więc czas rewelacyjny. Niestety ilość unikalnych wierszy zupełnie
nie zgadza się z ilością oczekiwaną. Gdzieś jest błąd, prawdopodobnie w programie perft4.

Program perft4 był dobrze przetestowany, więc błąd jest jakiś dziwny. Niemniej mam
pomysł na napisanie testu, który powinien dokładnie wskazać miejsca, w których
ten dziwny błąd się uaktywnia. Więc pomimo kolejnego potknięcia, jestem nadal
dobrej myśli :)

Pozdrawiam

[buninek]

/usr/bin/file input
input: ASCII text

Doprawdy nie ma sensu zmuszać sorta do pracy na pełnym zakresie UTF-8, aby udowodnić, że wtedy działa 7-8x wolniej.

/usr/bin/file input-utf
input-utf: UTF-8 Unicode English text                                           

W tym przypadku takie działanie jest wręcz konieczne. Wyniki testów są bardzo różne w zależności od danych wejściowych. Bez wątpienia sort nie jest najszybszym programem nie mam do tego żadnych wątpliwości. Jego pole działania i możliwości są zupełnie inne.

Twoja wersja jest bardzo stara, ale wątpię aby nowszy sort (GNU coreutils) 8.20 był odrobinę szybszy.

Niestety ilość unikalnych wierszy zupełnie
nie zgadza się z ilością oczekiwaną. Gdzieś jest błąd, prawdopodobnie w programie perft4.

Jeśli numeracja wieszy jest niepełna wtedy zmienia się zakres sortowania.

[mariotti]

/usr/bin/file input
input: ASCII text

Doprawdy nie ma sensu zmuszać sorta do pracy na pełnym zakresie UTF-8, aby udowodnić, że wtedy działa 7-8x wolniej.

/usr/bin/file input-utf
input-utf: UTF-8 Unicode English text                                           

W tym przypadku takie działanie jest wręcz konieczne. Wyniki testów są bardzo różne w zależności od danych wejściowych. Bez wątpienia sort nie jest najszybszym programem nie mam do tego żadnych wątpliwości. Jego pole działania i możliwości są zupełnie inne.

W ogóle nie chcę udowodnić że sort jest wolnym programem, tylko
chcę pokazać, że specjalistyczny program musi zadziałać szybciej.
Dlatego tak bardzo się zdziwiłem, że tamten program działał 3 razy
wolniej.  Chodzi o to, że wyciąganie unikalnych wierszy można
zrealizować zupełnie innym algorytmem niż sortowanie i dlatego ten
inny zadziała szybciej niż sort.

Moja implementacja jest bardzo niechlujna, można w niej jeszcze
wiele poprawić:
a) przejście z utf na ascii
b) usunięcie zdublowanych danych, teraz są dwie kopie wierszy,
c) przydział pamięci dużymi blokami

A pomimo tego, na moim kompie jest 7-8 razy szybsza. Gdy daję
przed shellowym sort i uniq C_ALL=C to na moim kompie działa jakby
jeszcze o kilka sekund wolniej. Nie wiem dlaczego.

Twoja wersja jest bardzo stara, ale wątpię aby nowszy sort (GNU coreutils) 8.20 był odrobinę szybszy.

Jeśli numeracja wieszy jest niepełna wtedy zmienia się zakres sortowania.

Używam takiego skryptu:

Kod [Zaznacz] Rozwiń


depth=$1
(
echo printLeafs $depth
echo quit
) | ./perft4 | nl | LC_ALL=C sort -t$'\t' -k2 -T'./tmp' -S1000000 | uniq -c -f1 | LC_ALL=C sort -n -k2 -T'./tmp' -S1000000 > out.txt
wc -l out.txt

To jest pełna numeracja czy nie?

Pozdrawiam

[buninek]

Twoja wersja suniq jest szybsza od tej STL-owej i na moim kompie wolniejsza od sort-uniq w zakresie ASCII. Różnica między ASCII a UTF-8.

file input
input: ASCII text

env | grep LANG
LANG=pl_PL.UTF-8

time sort input | uniq -c | sort -nr > out
0m53.61s real     0m52.64s user     0m0.76s system
time LC_ALL=C sort input | LC_ALL=C uniq -c | LC_ALL=C sort -nr > out
0m6.21s real     0m5.29s user     0m0.88s system

W zakresie UTF-8 jest szybsza ok 1.7x, ale sposób prezentacji jej wyników jest mało użyteczny, wręcz nieprzydatny . Ostateczny wynik posortowany jest numerycznie tylko po pierwszym polu, drugie pole jest całkowicie nieuporządkowane.

Numeracji linii nie sprawdzałem, pisałem kilka wątków wcześniej jak w miarę szybko sprawdzić. Choć przy systemie x86_64 nie powinno być niespodzianek.
cat -n jest chyba szybszy od nl.
time seq 1 119060324 | nl > /dev/null
time seq 1 119060324 | cat -n > /dev/null

Edit:
Wcześniejsze moje uwagi dotyczyły wersji sort, uniq z coreutils-8.10, okazuje się że jest jednak ogromna różnica z wersją coreutils-8.20.
- w nowszym sortowanie w zakresie UTF-8 jest szybsze ok 3x,
- automatycznie dobierany jest optymalny zakres, nie trzeba zmieniać zmiennych lokalizacyjnych, typu LC_ALL=C

[mariotti]

Twoja wersja suniq jest szybsza od tej STL-owej i na moim kompie wolniejsza od sort-uniq w zakresie ASCII. Różnica między ASCII a UTF-8.

Zabrnęliśmy w straszny szczegół :) Szybkość mojego suniq zależy od
wielu czynników:
1) wersja biblioteki qt
2) od tego czy użyto qt w wersji debug czy release
3) od tego jakim kompilatorem była skompilowana biblioteka qt
4) od sposobu kompilacji samego programu
5) od ilości wierszy - mój suniq jest niechlujnie napisany (ma tzw duży
    narzut liniowy); ktoś kto pisał sort na pewno włożył wiele dni pracy w
    zmniejszenie narzutu liniowego, ja suniq pisałem może 30 minut.
Na moim kompie suniq na ascii działa 13 razy szybciej:

Kod [Zaznacz] Rozwiń


cat go1.sh
cat data.txt | C_ALL=C sort -S2000000 | C_ALL=C uniq -c | C_ALL=C sort -S2000000 -nr > out1.txt
time ./go1.sh
real    1m18.829s user    1m18.565s sys     0m1.392s
cat ./go2.sh
cat data.txt | ./suniq r > out2.txt
./go2.sh
time ./go2.sh
real    0m6.060s user    0m5.696s sys     0m0.792s
ls -l
-rw-rw-r-- 1 x x 289969208 2013-06-19 01:42 data.txt
-rwx------ 1 x x        96 2013-06-19 15:00 go1.sh
-rwx------ 1 x x        36 2013-06-19 01:40 go2.sh
-rw-rw-r-- 1 x x  55292061 2013-06-19 22:53 out1.txt
-rw-rw-r-- 1 x x  55292061 2013-06-19 22:54 out2.txt


Źródło wersji na ascii, można w nim jeszcze dużo ulepszyć, to
jest cały czas taki program na kolanie :)

Kod [Zaznacz] Rozwiń


#include <cstring>
#include <cstdio>
#include <QHash>
#include <QVector>
#include <QtAlgorithms>
#include <QTextStream>

struct TData {
        char* str;
        int   cnt;
};

bool operator==( const TData &a , const TData &b ) {
        return strcmp(a.str,b.str)==0;
}


bool lessThatA( const TData *a , const TData *b ) {
        return a->cnt > b->cnt;
}
bool lessThatB( const TData *a , const TData *b ) {
        return b->cnt < a->cnt;
}

uint qHash( const TData &d ) {
const static         uint keys[] = {1144700546,221718428,3154688750,371537357,2204050889,1370979008,3321622132,2725480991,3840323144,3287424469,2776693720,4189889840,2357009355,182334614,1137760547,2900706147,3348220913,3247080425,2942765694,2091459760,3590858303,1290645046,1554428098,463533191,3969044147,1250249148,2989244349,1456428351,3857024942,4147237429,173332611,2149971405,2137831619,3217748225,1903294001,4207362380,4259294664,66392448,3071101674,54014783,3967985131,3366669718,2419662148,663421279,790981550,1731337085,2753511525,1588025203,2471176956,3160209272,1951241493,1184684183,3245719876,1093248988,1541818600,2629471904,825230777,317558013,3112647458,1459626771,3256448485,84165149,711060106,851909497,509867808,2788249988,2690693260,3254214876,4085518806,3740895315,3959970419,2518601845,1270121159,1626531539,2063618718,2285762738,1568456969,3158013257,1185432784,3705456404,489197897,377297527,529628780,2175258231,3655214223,1788156313,1907375709,1313704965,2506847518,4239124880,3743104360,2606809867,2171879399,3068856920,1294506824,1184593192,2094794731,1501071601,3510146245,1080924504,834790104,887598572,1921060681,1907957125,384668965,3832505886,1404479738,429073217,4048180485,1277571586,3351160641,3929569221,721495309,2249158795,1507443992,4017319401,3319905986,839976944,1962528687,1398747462,3799998551,3916009169,1044595540,1932375984,1714949749,3315091734,1614450969,448043715,3439145978,397764290,1532361130,651068336,2827749266,1785537617,2043390134,1033076546,1946784178,2727133176,1778246073,4153396324,631184595,4136570176,4168112821,2352350170,2365669525,3106901503,3559075183,3452679161,267545551,772178552,3072751325,256138618,2644329885,1129762003,4095244794,4240565036,3339433038,334828086,80419977,370347897,699707733,2020346493,2976679044,3064802920,427669986,1428976588,156891279,1545628935,2626081822,1679094495,3742728311,2442576814,1219105916,396285832,3609262031,2201174116,4095719957,609760429,1661234868,2935331633,955752368,1162843510,4061950093,3329577137,3099235594,2128352201,3001147777,744609404,3966064758,2066920942,3597487909,2879251104,1097029495,3971956586,2644484385,4006215800,1205546841,180489701,4242616412,2326232595,1103825622,1798146890,2752105516,647156941,3916328196,3639882107,1960105313,721386580,3530279815,2185140566,858146661,559528220,2718615335,1518010104,684609492,1414712780,3995516568,3161547863,3387987884,2028620113,169538833,3362100723,2985309157,2567324161,1485319169,1041627537,3792110993,1616573006,3681252839,4037267467,94540548,3617564886,1731143893,3013952545,2559946057,2281304224,2145511259,616739264,3889211381,1538154866,1679636709,4094920003,3916479913,1052735971,566141280,1212514386,2586777127,1593236856,1505891350,1146017434,1999486611,2578902328,3787093134,472449269,2411157526,2911776849};
        uint x = 123;
        for( uint i=0 ; d.str[i] ; i++ )
                x ^= keys[ ((uint)d.str[i]+i) % 256 ] ;
        return x;
}

int main( int argc, char *argv[] ) {
        QHash<TData,TData*> hash;
        QVector<TData*>   data;

        char *buf = new char[1024*1024];

        TData tmp;
        tmp.str = buf;
        tmp.cnt = 0;

        while( fgets( buf , 1024*1024 , stdin ) ) {

                if( hash.contains( tmp ) ) {
                        hash[tmp]->cnt ++ ;
                } else {
                        TData *tmp = new TData;
                        tmp->str = strdup(buf);
                        tmp->cnt = 1;
                        hash[*tmp] = tmp;
                        data.append( tmp );
                }
        }

        qSort( data.begin() , data.end() , argc > 1 && strstr( argv[1] , "r" ) ? lessThatA : lessThatB );

        for( int i=0 ; i<data.size() ; i++ ) {
                printf("%7d %s" , data[i]->cnt , data[i]->str );
                free( data[i]->str );
                delete data[i];
        }

        return 0;
}


time sort input | uniq -c | sort -nr > out
0m53.61s real     0m52.64s user     0m0.76s system

Czyli wersja shell-unicode 53s

time LC_ALL=C sort input | LC_ALL=C uniq -c | LC_ALL=C sort -nr > out
0m6.21s real     0m5.29s user     0m0.88s system

Wersja shell-ascii ponad 6 sekund. Ciekawe dlaczego na moim
komputerze wersja ascii działa tak samo szybko jak unicode. Na
Twoim różnica jest ogromna.

W zakresie UTF-8 jest szybsza ok 1.7x, ale sposób prezentacji jej wyników jest mało użyteczny, wręcz nieprzydatny . Ostateczny wynik posortowany jest numerycznie tylko po pierwszym polu, drugie pole jest całkowicie nieuporządkowane.

Nie było w treści zadania że ma być posortowane po obu polach. Chyba systemowe sort
też ma prawo podać nieuporządkowane po drugim polu. Trzeba
użyć opcji --stable żeby została zachowana kolejność z pierwszego sortowania.
Ale... coś mnie jeszcze tknęło, sprawdziłem i widzę, że systemowe sort pracuje
na wszystkich rdzeniach, jest wielowątkowe! Czyli na moim kompie, na
dużej ilości wierszy, mój niechlujny(!) suniq działa 12-13 razy szybciej na
jednym wątku, niż rozwiązanie shellowe na 2 + 2hyper!

No ale jeszcze wersja z sortowaniem wielokryterialnym:

Kod [Zaznacz] Rozwiń


#include <cstring>
#include <cstdio>
#include <QHash>
#include <QVector>
#include <QtAlgorithms>


struct TData {
char* str;
int   cnt;
};

bool operator==( const TData &a , const TData &b ) {
return strcmp(a.str,b.str)==0;
}


bool lessThatA( const TData *a , const TData *b ) {
if( a->cnt != b->cnt )
return a->cnt > b->cnt;
return strcmp( a->str , b->str ) > 0;
}
bool lessThatB( const TData *a , const TData *b ) {
if( a->cnt != b->cnt )
return a->cnt < b->cnt;
return strcmp( a->str , b->str ) < 0;
}


uint qHash( const TData &d ) {
const static uint keys[] = {1144700546,221718428,3154688750,371537357,2204050889,1370979008,3321622132,2725480991,3840323144,3287424469,2776693720,4189889840,2357009355,182334614,1137760547,2900706147,3348220913,3247080425,2942765694,2091459760,3590858303,1290645046,1554428098,463533191,3969044147,1250249148,2989244349,1456428351,3857024942,4147237429,173332611,2149971405,2137831619,3217748225,1903294001,4207362380,4259294664,66392448,3071101674,54014783,3967985131,3366669718,2419662148,663421279,790981550,1731337085,2753511525,1588025203,2471176956,3160209272,1951241493,1184684183,3245719876,1093248988,1541818600,2629471904,825230777,317558013,3112647458,1459626771,3256448485,84165149,711060106,851909497,509867808,2788249988,2690693260,3254214876,4085518806,3740895315,3959970419,2518601845,1270121159,1626531539,2063618718,2285762738,1568456969,3158013257,1185432784,3705456404,489197897,377297527,529628780,2175258231,3655214223,1788156313,1907375709,1313704965,2506847518,4239124880,3743104360,2606809867,2171879399,3068856920,1294506824,1184593192,2094794731,1501071601,3510146245,1080924504,834790104,887598572,1921060681,1907957125,384668965,3832505886,1404479738,429073217,4048180485,1277571586,3351160641,3929569221,721495309,2249158795,1507443992,4017319401,3319905986,839976944,1962528687,1398747462,3799998551,3916009169,1044595540,1932375984,1714949749,3315091734,1614450969,448043715,3439145978,397764290,1532361130,651068336,2827749266,1785537617,2043390134,1033076546,1946784178,2727133176,1778246073,4153396324,631184595,4136570176,4168112821,2352350170,2365669525,3106901503,3559075183,3452679161,267545551,772178552,3072751325,256138618,2644329885,1129762003,4095244794,4240565036,3339433038,334828086,80419977,370347897,699707733,2020346493,2976679044,3064802920,427669986,1428976588,156891279,1545628935,2626081822,1679094495,3742728311,2442576814,1219105916,396285832,3609262031,2201174116,4095719957,609760429,1661234868,2935331633,955752368,1162843510,4061950093,3329577137,3099235594,2128352201,3001147777,744609404,3966064758,2066920942,3597487909,2879251104,1097029495,3971956586,2644484385,4006215800,1205546841,180489701,4242616412,2326232595,1103825622,1798146890,2752105516,647156941,3916328196,3639882107,1960105313,721386580,3530279815,2185140566,858146661,559528220,2718615335,1518010104,684609492,1414712780,3995516568,3161547863,3387987884,2028620113,169538833,3362100723,2985309157,2567324161,1485319169,1041627537,3792110993,1616573006,3681252839,4037267467,94540548,3617564886,1731143893,3013952545,2559946057,2281304224,2145511259,616739264,3889211381,1538154866,1679636709,4094920003,3916479913,1052735971,566141280,1212514386,2586777127,1593236856,1505891350,1146017434,1999486611,2578902328,3787093134,472449269,2411157526,2911776849};
uint x = 123;
for( uint i=0 ; d.str[i] ; i++ )
x ^= keys[ ((uint)d.str[i]+i) % 256 ] ;
return x;
}

int main( int argc, char *argv[] ) {
QHash<TData,TData*> hash;
QVector<TData*>   data;

char *buf = new char[1024*1024];

TData tmp;
tmp.str = buf;
tmp.cnt = 0;

while( fgets( buf , 1024*1024 , stdin ) ) {

if( hash.contains( tmp ) ) {
hash[tmp]->cnt ++ ;
} else {
TData *tmp = new TData;
tmp->str = strdup(buf);
tmp->cnt = 1;
hash[*tmp] = tmp;
data.append( tmp );
}
}

qSort( data.begin() , data.end() , argc > 1 && strstr( argv[1] , "r" ) ? lessThatA : lessThatB );

delete[] buf;
for( int i=0 ; i<data.size() ; i++ ) {
printf("%7d %s" , data[i]->cnt , data[i]->str );
free( data[i]->str );
delete data[i];
}

return 0;
}

Spowolnienie w granicach błędu pomiaru.

Numeracji linii nie sprawdzałem, pisałem kilka wątków wcześniej jak w miarę szybko sprawdzić. Choć przy systemie x86_64 nie powinno być niespodzianek.
cat -n jest chyba szybszy od nl.
time seq 1 119060324 | nl > /dev/null
time seq 1 119060324 | cat -n > /dev/null

Ja jestem ciekawy jak szybko zadziała pełna wersja programu do
optymalizacji work-units. Przy niej trochę się pomęczę, gdyż będzie
wiele razy potrzebna. Optymalizacja suniq też jest ciekawym zadaniem, ale
chyba taki program nie jest nikomu potrzebny.


Pozdrawiam

[buninek]

Cóż to za zmienna

C_ALL=C

i w jakim celu ją dodajesz przed sortem  XD?

Polecam zaktualizować coreutils do wersji 8.20.
Jak widać trudno o miarodajny test. U mnie twoja wersja obecnie przegrywa ponad 2x z sortem z coreutils-8.20 na procesorze jednordzeniowym.

Qt w wersji 4.8.4 kompilowane z pomocą g++-4.7.0, NODEBUG.
Qt w systemie ma tylko w sumie dla Qt-webkita.

[mariotti]

Cóż to za zmienna

C_ALL=C

i w jakim celu ją dodajesz przed sortem  XD?

Miałem błąd. Po poprawieniu moja wersja jest tylko dwa razy szybsza.

Polecam zaktualizować coreutils do wersji 8.20.

dałem apt-get install coreutils i krzyczy że jest już w najnowszej wersji.

Jak widać trudno o miarodajny test. U mnie twoja wersja obecnie przegrywa ponad 2x z sortem z coreutils-8.20.

Ale można wykonać miarodajną analizę. Wersja shell dwa razy sortuje i raz przegląda całość, aby
odrzucić powtórki. Przed odrzuceniem jest N wierszy, po odrzuceniu jest M. Czyli mamy
N*LogN + N + M*LogM. Moja wersja dodaje do hash-table i raz sortuje unikalne, czyli
M*LogM + N. Widać gołym okiem która wersja jest lepsza, nie trzeba nic testować. Dla
specyficznych danych, np. gdy M=N, albo gdy N jest małe, różnica będzie pomijalnie
mała. Ale podstaw do wzoru gdy N=100kk, a M=1kk.

Poza tym istnieje jeszcze jeden specjalistyczny algorytm dla tego zadania, żeruje on na
wiedzy o tym, że w ilość powtórzeń różnych wierszy jest podobna, np. wiersze powtarzają się
tylko 10, 15 albo 30 razy. Niestety ten algorytm, tak jak każdy specjalistyczny algorytm,
zadziała wolniej w ogólnym przypadku.
To wersja na kolanie tego programu:

Kod [Zaznacz] Rozwiń


#include <cstring>
#include <cstdio>
#include <QHash>
#include <QVector>
#include <QtAlgorithms>

struct TData {
char* str;
int   cnt;
};

bool operator==( const TData &a , const TData &b ) {
return strcmp(a.str,b.str)==0;
}

uint qHash( const TData &d ) {
const static uint keys[] = {1144700546,221718428,3154688750,371537357,2204050889,1370979008,3321622132,2725480991,3840323144,3287424469,2776693720,4189889840,2357009355,182334614,1137760547,2900706147,3348220913,3247080425,2942765694,2091459760,3590858303,1290645046,1554428098,463533191,3969044147,1250249148,2989244349,1456428351,3857024942,4147237429,173332611,2149971405,2137831619,3217748225,1903294001,4207362380,4259294664,66392448,3071101674,54014783,3967985131,3366669718,2419662148,663421279,790981550,1731337085,2753511525,1588025203,2471176956,3160209272,1951241493,1184684183,3245719876,1093248988,1541818600,2629471904,825230777,317558013,3112647458,1459626771,3256448485,84165149,711060106,851909497,509867808,2788249988,2690693260,3254214876,4085518806,3740895315,3959970419,2518601845,1270121159,1626531539,2063618718,2285762738,1568456969,3158013257,1185432784,3705456404,489197897,377297527,529628780,2175258231,3655214223,1788156313,1907375709,1313704965,2506847518,4239124880,3743104360,2606809867,2171879399,3068856920,1294506824,1184593192,2094794731,1501071601,3510146245,1080924504,834790104,887598572,1921060681,1907957125,384668965,3832505886,1404479738,429073217,4048180485,1277571586,3351160641,3929569221,721495309,2249158795,1507443992,4017319401,3319905986,839976944,1962528687,1398747462,3799998551,3916009169,1044595540,1932375984,1714949749,3315091734,1614450969,448043715,3439145978,397764290,1532361130,651068336,2827749266,1785537617,2043390134,1033076546,1946784178,2727133176,1778246073,4153396324,631184595,4136570176,4168112821,2352350170,2365669525,3106901503,3559075183,3452679161,267545551,772178552,3072751325,256138618,2644329885,1129762003,4095244794,4240565036,3339433038,334828086,80419977,370347897,699707733,2020346493,2976679044,3064802920,427669986,1428976588,156891279,1545628935,2626081822,1679094495,3742728311,2442576814,1219105916,396285832,3609262031,2201174116,4095719957,609760429,1661234868,2935331633,955752368,1162843510,4061950093,3329577137,3099235594,2128352201,3001147777,744609404,3966064758,2066920942,3597487909,2879251104,1097029495,3971956586,2644484385,4006215800,1205546841,180489701,4242616412,2326232595,1103825622,1798146890,2752105516,647156941,3916328196,3639882107,1960105313,721386580,3530279815,2185140566,858146661,559528220,2718615335,1518010104,684609492,1414712780,3995516568,3161547863,3387987884,2028620113,169538833,3362100723,2985309157,2567324161,1485319169,1041627537,3792110993,1616573006,3681252839,4037267467,94540548,3617564886,1731143893,3013952545,2559946057,2281304224,2145511259,616739264,3889211381,1538154866,1679636709,4094920003,3916479913,1052735971,566141280,1212514386,2586777127,1593236856,1505891350,1146017434,1999486611,2578902328,3787093134,472449269,2411157526,2911776849};
uint x = 123;
for( uint i=0 ; d.str[i] ; i++ )
x ^= keys[ ((uint)d.str[i]+i) % 256 ] ;
return x;
}

int main( int argc, char *argv[] ) {
QHash<TData,TData*> hash;
QHash<int,TData*>   hash2;
QVector<TData*>   data;

char *buf = new char[1024*1024];

TData tmp;
tmp.str = buf;
tmp.cnt = 0;

while( fgets( buf , 1024*1024 , stdin ) ) {
if( hash.contains( tmp ) ) {
hash[tmp]->cnt ++ ;
} else {
TData *tmp = new TData;
tmp->str = strdup(buf);
tmp->cnt = 1;
hash[*tmp] = tmp;
data.append( tmp );
}
}

for( int i=0 ; i<data.size() ; i++ ) {
hash2.insertMulti(data[i]->cnt , data[i] );
}

QList<int> keys = hash2.uniqueKeys();
if( argc > 1 && strstr( argv[1] , "r" ) )
qSort( keys.begin() , keys.end() , qGreater<int>() );
else
qSort( keys.begin() , keys.end() , qLess<int>() );


for( int i=0 ; i<keys.size() ; i++ ) {
QList<TData*> vals = hash2.values( keys[i] );
for( int j=0 ; j<vals.size() ; j++ )
printf("%7d %s" , vals[j]->cnt , vals[j]->str );
}


return 0;
}



A jeszcze co do testów, to warto zwrócić uwagę, że moja wersja powstała w 30 minut, a
narzędzia coreutils są udoskonalane od nastu lat. Jak sądzisz, który algorytm będzie
szybszy, jeśli w obu przypadkach włoży się tyle samo pracy? Ten który raz sortuje, czy
ten który dwa razy sortuje?

Pozdrawiam

[mariotti]

Qt w wersji 4.8.4 kompilowane z pomocą g++-4.7.0, NODEBUG.
Qt w systemie ma tylko w sumie dla Qt-webkita.

A opcje z serii -O3, no_frame_pointers były ustawione?
A narzędzia z serii PGO były użyte?
A march było ustawione?
A wykorzystanie szerokich rejestrów i wstawki asemblerowe moja wersja ma?
W systemowym sort prawdopodobnie ktoś o to wszystko zadbał. Na dłuższą
metę moja wersja wygra zawsze bo sortuje jeden raz a nie  dwa razy.

Pozdrawiam

[buninek]

Tobie się nie chce sprofilować sorta w najnowszej wersji tylko używasz jakiegoś zabytku, a mnie się dopytujesz czy ja mam QT odpowiednio zbudowane.
Debian i profilowanie. Pewnie jakiś antyk, typu lenny. Żadna dystrybucja tego nie robi.

Profilować można pod konkretny model procesora na przykład dystrybucję pod Raspberry Pi, wydanie Androida pod konkretny model telefonu.

Wiele programów, bibliotek tego potrzebujących możesz zawsze sobie zbudować na własną modłę z pełnym profilowaniem pod swój procesor.

Trzy minuty
cd /tmp

Kod [Zaznacz] Rozwiń


cd /tmp
wget ftp://ftp.gnu.org/gnu/coreutils/coreutils-8.21.tar.xz
tar xJf coreutils-8.21.tar.xz
cd coreutils-8.21
ustaw swoje CFLAGS

Kod [Zaznacz] Rozwiń

export CFLAGS=""
./configure --prefix=$HOME/test/coreutils --libexecdir=$HOME/test/coreutils/lib
make
make RUN_EXPENSIVE_TESTS=yes check
make DESTDIR=/tmp/coreutils-8.21-install install


[mariotti]

Tobie się nie chce sprofilować sorta w najnowszej wersji tylko używasz jakiegoś zabytku, a mnie się dopytujesz czy ja mam QT odpowiednio zbudowane.
Debian i profilowanie. Pewnie jakiś antyk, typu lenny. Żadna dystrybucja tego nie robi.

Nie dopytuję się po to, abyś instalował, czy zadał sobie jeszcze większy trud optymalizacji
programu, ale po to żebyś spróbował przez chwilę mojego toku rozumowania. Naprawdę
uprawiamy bezsensowną rozmowę od kilku postów, nic z niej nie wyniknie dobrego dla żadnego
z nas. W tej chwili robimy coś takiego: jeden z nas mówi:
- mercedes jest lepszy od syrenki
- syrenka jest lepsza - przeczy drugi
- dlaczego syrenka jest lepsza?
- bo syrenka mniej waży.
Jeśli chcesz powiedzieć że sort jest wydajnym narzędziem, to ja nigdy temu nie przeczyłem,
więc nie ma sensu abyś mi to udowadniał. Ja tylko twierdzę że sortowanie jednokrotne
jest szybsze niż dwukrotne. A program który napisałem to potwierdza, bo pomimo tego
iż napisałem go na kolanie, wygrywa, albo prawie wygrywa z potokiem: sort | uniq | sort.

Ta dyskusja nie ma sensu z jeszcze jednego powodu: już wiemy, że dla depth=7 rozwiązanie
na coreutils jest zadowalające. Jeśli jest zadowalające, to szkoda naszego czasu na
ulepszenia. Z kolei dla depth=8 rozwiązanie na coreutils jest niedopuszczalne, bo będzie potrzebowało
8-10TB danych - a mi na początkowym etapie tego projektu szkoda pieniędzy na zakup macierzy.
Więc jeśli będę chciał zrobić work-units dla depth=8, to i tak i tak będę musiał posłużyć
się specjalistycznym programem.

Profilować można pod konkretny model procesora na przykład dystrybucję pod Raspberry Pi,
wydanie Androida pod konkretny model telefonu.
Wiele programów, bibliotek tego potrzebujących możesz zawsze sobie zbudować na własną modłę z pełnym profilowaniem pod swój procesor.

Można. Ale teraz będę potrzebował profilowania operacji dyskowych na dyskach
talerzowych - o tym rozmawiajmy. Wiem na ten temat tylko tyle, że nastawianie
głowicy powinno być wykonywane możliwie rzadko. Nie wiem chociażby czy cofanie
wskaźnika pliku o małą ilość bajtów (np. o 100 bajtów) wymusza fizyczne
naprowadzanie głowicy.

Trzy minuty
cd /tmp

Kod [Zaznacz] Rozwiń


cd /tmp
wget ftp://ftp.gnu.org/gnu/coreutils/coreutils-8.21.tar.xz
tar xJf coreutils-8.21.tar.xz
cd coreutils-8.21
ustaw swoje CFLAGS

Kod [Zaznacz] Rozwiń

export CFLAGS=""
./configure --prefix=$HOME/test/coreutils --libexecdir=$HOME/test/coreutils/lib
make
make RUN_EXPENSIVE_TESTS=yes check
make DESTDIR=/tmp/coreutils-8.21-install install


Dzięki za instrukcję, przyda się, bo jestem noga z administracji systemów :)


Pozdrawiam

[krzyszp]

Muszé powiedzieć, że obróbka tego tekstu z zapisem do bazy za jednym zamachem mija sié z celem...
kod:

Kod [Zaznacz] Rozwiń

Open "W:\all_rows.txt" For Input As #1
    Do While Not EOF(1)
        Line Input #1, strTemp
        sSQL = "SELECT * FROM dane WHERE Line = '" & strTemp & "'"
        rsS.OpenRs sSQL, cnM, adOpenDynamic, adLockPessimistic
        If rsS.RecordCount = 0 Then
            sSQL = "insert into dane(Line, Rep) Values('" & strTemp & "',0)"
            cnM.Execute sSQL
        Else
            rsS.Fields("Rep") = CInt(rsS.Fields("Rep")) + 1
            rsS.Update
        End If
        rsS.CloseRecordset
        DoEvents
        rsS.CloseRecordset
    Loop
Close #1

Przy odpaleniu w IDE wykonuje na moim sprzécie 30-32 zapytania (średnio) na sekundé. Pomyślałem, że kompilacja powinna przyśpieszyć znacznie... Błád, wynik sié nie zmienił...

Jak widać, w tym przypadku wáskim gardłem jest serwer MySQL, a dokładniej (tak mi sié wydaje) operacja indeksowania tabeli po każdym insercie... (index na Line).

[mariotti]

Muszé powiedzieć, że obróbka tego tekstu z zapisem do bazy za jednym zamachem mija sié z celem...
kod:

Nom, takie same były rokowania.

Przy odpaleniu w IDE wykonuje na moim sprzécie 30-32 zapytania (średnio) na sekundé. Pomyślałem, że kompilacja powinna przyśpieszyć znacznie... Błád, wynik sié nie zmienił...

Wąskim gardłem są operacje na bazie. Optymalizacja innych fragmentów niż wąskie
gardło, przynosi tylko nieznaczną poprawę.

Jak widać, w tym przypadku wáskim gardłem jest serwer MySQL, a dokładniej (tak mi sié wydaje) operacja indeksowania tabeli po każdym insercie... (index na Line).

Zarówno indeks jaki i dane nie mieszczą się w buforach ram. Algorytm
nie wykorzystuje zalet sekwencyjnych operacji, głowica dysku jest
naprowadzana zarówno w przypadku dostępu do danych jak i
do indeksu. Więc wąskim gardłem są obie operacje: na danych i na indeksie.

Pozdrawiam

P.S.
Moim zdaniem to by miało sens na dyskach SSD. Na dyskach SSD też
jest jakiś czas dostępu do danych, ale nie ma głowicy mechanicznej, więc
jest, w zależności do jakości dysku, 5-200 razy szybszy.

[Karlik]

Jak już korzystasz z MySQL to wykorzystuj go optymalnie ;)

Kod [Zaznacz] Rozwiń

http://dev.mysql.com/doc/refman/5.0/en/insert-on-duplicate.html
Chociaż jak dla mnie pomysł zaprzęgania do takiego zadania serwera bazodanowego jest lekko poroniony. Jak mamy dość pamięci dyskowej to już lepiej by było zrobić dużego swapa i wszystko wrzucać do jakiegoś drzewka (może być samodzielnie napisane albo set STLowy). W sumie to aż sam jestem ciekawy jak takie rozwiązanie by sobie poradziło :D

[krzyszp]

Jak już korzystasz z MySQL to wykorzystuj go optymalnie ;)

Kod [Zaznacz] Rozwiń

http://dev.mysql.com/doc/refman/5.0/en/insert-on-duplicate.html
Chociaż jak dla mnie pomysł zaprzęgania do takiego zadania serwera bazodanowego jest lekko poroniony. Jak mamy dość pamięci dyskowej to już lepiej by było zrobić dużego swapa i wszystko wrzucać do jakiegoś drzewka (może być samodzielnie napisane albo set STLowy). W sumie to aż sam jestem ciekawy jak takie rozwiązanie by sobie poradziło :D

INSERT ON DUPLICATE spowodował spadek ilości zapytań na sekundé o 1/3 (ale nie sprawdziłem samej ilości insertów w tym czasie). Ciekawe, jak sié zachowa dalej.

Wiem, że z punktu widzenia optymalizacji nie ma sensu zrzucenie tego na db (od poczátku było to wiadomo), ale chciałem sie przekonać, jakie jest praktyczne spowolnienie oraz czy samo skompilowanie kodu przyniesie zysk w operacji.

[Karlik]

INSERT ON DUPLICATE spowodował spadek ilości zapytań na sekundé o 1/3

Czy ogólnie dostałeś przyspieszenie ;)
Za każdym razem w poprzedniej sytuacji miałeś 2 zapytania (select i insert lub update), teraz masz zawsze jedno.
Ze zgrubnych obliczeń:
miałeś x zapytań na sekundę, na każde dodanie wykorzystywałeś 2 zapytania (select i insert lub update): x/2 dodań na sekundę
masz 2/3x zapytań na sekundę, na każde dodanie wykorzystujesz 1 zapytanie (sam insert): 2/3*x dodań na sekundę
Na każdej sekundzie nowym sposobem zyskujesz (2/3 - 1/2)*x dodań

[mariotti]

Jak już korzystasz z MySQL to wykorzystuj go optymalnie ;)

Kod [Zaznacz] Rozwiń

http://dev.mysql.com/doc/refman/5.0/en/insert-on-duplicate.html
Chociaż jak dla mnie pomysł zaprzęgania do takiego zadania serwera bazodanowego jest lekko poroniony.

A może jednak nie aż taki poroniony? Zależy jaki sprzęt, jak skonfigurowana baza i
jaka baza. Zależy też od tego, jak posłużymy się bazą. A jakby zrobić tabelę w RAM? Dużą tabelę tak
żeby zajęła 50-75% dostępnej pamięci. Następnie dodajemy unikalne lub zliczamy powtórzenia w tej tabeli
w RAM. Gdy osiągniemy ilość wierszy na założone 50-75%, to przerzucamy do tabeli na dysku. Będzie masa
odrzuceń w RAM, a tam to działa szybko. Więc ilość operacji dyskowych będzie zminimalizowana. Oczywiście
bazę danych trzeba tak skonfigurować, żeby pozostałe 25-50% pamięci ram było na bufor tabeli dyskowej.
Oczywiście jeszcze ważne są transakcje, trzeba przynajmniej 10K operacji wstawiania obejmować
begin i commit, a na tabeli RAM może w ogóle wyłączyć transakcje. Trzeba też sprawdzić czy indeks
dla tabeli w RAM się opłaca. Aha, i jeszcze jedno, w obu tabelach indeks typu hash będzie szybszy niż btree.

Pozdrawiam

[edit]

Ponadto kolejna baaardzo ważna technika. Możemy wywalić indeks z tej tabeli dyskowej. Musimy się
upewnić w jakiej kolejności są zapisywane rekordy w tej tabeli dyskowej. Prawdopodobnie są zapisywane
tak jak narasta id=autoinc. Więc mamy pole do popisu dla sekwencyjnego odczytu. Zamiast zrzucać z tabeli w
RAM do tabeli dyskowej, możemy zrobić odwrotnie. Gdy zapełni się tabela w RAM, to odczytujemy z tabeli dyskowej
wszystkie rekordy po kolejnych ID. Jeśli rekord jest w tabeli RAM, to uaktualniamy sumę na dysku:
sum_dysk = sum_dysk + sum_ram
Następnie wyrzucamy go z tabeli w RAM. Gdy dojdziemy do końca tabeli dyskowej, to wszystkie nieusunięte
rekordy z tabeli RAM, przerzucamy na tabelę dyskowa - szybko bo bez sprawdzania czy są powtórzenia i bez
zabawy z indeksami.

Może się okazać, że na id=autoinc w tabeli dyskowej, będzie trzeba założyć clustered-index - ale nie wiem,
trzeba się upewnić.

Pozdrawiam

[mariotti]

Jak mamy dość pamięci dyskowej to już lepiej by było zrobić dużego swapa i wszystko wrzucać do jakiegoś drzewka (może być samodzielnie napisane albo set STLowy). W sumie to aż sam jestem ciekawy jak takie rozwiązanie by sobie poradziło :D

Odpisałem dokładnie na powyższe, ale znowu wcięło tekst. W skrócie: zadziała wolno. Każdy dostęp
do drzewka będzie wymagał nastawienia głowicy i wczytania/zapisania 4kb danych na dysku. Może
być lepiej gdy się swap ustawi na dysku ssd.
Pozdrawiam

[Karlik]

W skrócie: zadziała wolno. Każdy dostęp do drzewka będzie wymagał nastawienia głowicy i wczytania/zapisania 4kb danych na dysku.

Właśnie nie jest to takie pewne. Ogólnie dużo zależałoby od samej konstrukcji drzewa (kolejności napływających danych). Węzły drzewa często wykorzystywane (blisko korzenia) byłyby cały czas w pamięci operacyjnej - prawdopodobnie w ogóle nie byłyby zrzucane na swapa. Pytanie tylko jak mocno rozrzucone są dane napływające, jeśli byłyby długie sekwencje podobnych (w sensie wspólnej ścieżki w drzewie) danych to mogłoby być całkiem nieźle.

[Rysiu]

Dyski SSD raczej nie nadają się do serwerów baz danych. W profesjonalnych sprzętach stosuje się SAS i SCSI.

Dysk SSD przy takiej bazie o której tutaj mówimy najprawdopodobniej za długo by nie przetrwał (przecież tutaj mamy maksymalny io wait). Takich twardzieli właśnie z takich względów nie ustawia się na swap - przy normalnej eksploatacji komputera po pół roku sprzęt idzie na szrot. Pół roku przy normalnej eksploatacji to nie wiem ile by wyszło dla maksymalnego io wait - miesiąc?

Może i SSD są i coraz lepsze ale tutaj potrzeba jakiejś profesjonalnej macierzy. Ktoś oszacował ile ta baza będzie zajmowała? Jeżeli jest to rząd wielkości mierzony w TB to nie wiem czy warto kombinować, bo może okazać się, że zapytania będą szły zbyt wolno aby zgrać to w jakiś realny skrypt. Zależy co tam będzie robione.

Jestem sceptycznie nastawiony ale myślę, że mogę pomóc ale musisz mariotti oszacować jakiego sprzętu potrzebujesz (jaka pojemność, jaka prędkość odczytu/zapisu) i na jak długo.

[mariotti]

Właśnie nie jest to takie pewne. Ogólnie dużo zależałoby od samej konstrukcji drzewa (kolejności napływających danych). Węzły drzewa często wykorzystywane (blisko korzenia) byłyby cały czas w pamięci operacyjnej - prawdopodobnie w ogóle nie byłyby zrzucane na swapa. Pytanie tylko jak mocno rozrzucone są dane napływające, jeśli byłyby długie sekwencje podobnych (w sensie wspólnej ścieżki w drzewie) danych to mogłoby być całkiem nieźle.

W bazach danych są drzewa b-tree i nie zadziałało zbyt dobrze. Drzewa AVL, Red-Black, itd
gorzej sprawują się na dyskach niż b-tree. Ale cóż... skłamałbym, jakbym powiedział, że jestem
pewny na 100% :)
Pozdrawiam

[mariotti]

Dyski SSD raczej nie nadają się do serwerów baz danych. W profesjonalnych sprzętach stosuje się SAS i SCSI.

Dysk SSD przy takiej bazie o której tutaj mówimy najprawdopodobniej za długo by nie przetrwał (przecież tutaj mamy maksymalny io wait). Takich twardzieli właśnie z takich względów nie ustawia się na swap - przy normalnej eksploatacji komputera po pół roku sprzęt idzie na szrot. Pół roku przy normalnej eksploatacji to nie wiem ile by wyszło dla maksymalnego io wait - miesiąc?

Może i SSD są i coraz lepsze ale tutaj potrzeba jakiejś profesjonalnej macierzy. Ktoś oszacował ile ta baza będzie zajmowała? Jeżeli jest to rząd wielkości mierzony w TB to nie wiem czy warto kombinować, bo może okazać się, że zapytania będą szły zbyt wolno aby
zgrać to w jakiś realny skrypt. Zależy co tam będzie robione.

Nie jestem ekspertem od dysków SSD, zwłaszcza od tych najdroższych. Takie mam
zasłyszane informacje, ze one bardzo dobrze sprawują się w losowym odczycie/zapisie.
Podobno te nowe i drogie są wielokrotnie bardziej żywotne od talerzowych. Ale koszt
jednego dysku to 10tys usd i więcej.

Jestem sceptycznie nastawiony ale myślę, że mogę pomóc ale musisz mariotti oszacować jakiego sprzętu potrzebujesz (jaka pojemność, jaka prędkość odczytu/zapisu) i na jak długo.

Jeszcze trochę powalczę na swoim sprzęcie, a nóż się uda. Jak się nie uda, to
wielkiego problemu nie będzie, po prostu work-units będą mniej zoptymalizowane.
Teraz nie potrafię powiedzieć jakie wymagania są potrzebne co do ram i pojemności
dysków - każdy algorytm ma inne. Za jakiś czas dokładnie zastanowimy się czy warto
szukać macierzy dyskowej na to zadanie.


Pozdrawiam

[mariotti]

Problem optymalizacji work-units rozwiązany. Opisany kilka postów wyżej
algorytm ( ten z jednym zbiorem w RAM i drugim na dysku) jest bardzo szybki.
Dla depth=7 generuje w niecałe dwie godziny na tanim dysku zewnętrznym
na usb 2. Jeśli ktoś jest zainteresowany kodem źródłowym, to udostępnię. 

Szkoda że rozwiązanie tego zadania nie oznacza w ogóle końca kłopotów.
Pojawiły się następne problemy - no ale to zwykła praktyka tworzenia
systemów. Muszę przeznaczyć następne dwa-trzy dni w całości na inny
projekt, a potem wracam do dalszych prac i testów.

Pozdrawiam.

[mariotti]

Dotarłem do zdumiewającego etapu :D

Jest sobie ten program perft w kilku wersjach, a wersje czasami są jeszcze w kilku
odmianach.  Generalnie wersje dzielą się na dwie grupy. Jedna grupa to
siłowe zliczanie/przeszukiwanie. Do drugiej grupy należą wersje zapamiętujące częściowe
wyniki. Wersje z obu grup były długo testowane. Testy polegały na ustawieniu
tysiąca pozycji początkowych i przeszukaniu tych pozycji na głębokość 4-6 ruchów. Wyniki były
porównywane pomiędzy wersjami, a także były porównywane z innymi,
całkowicie niezależnymi programami. Wszystkie testy zakończyły się pozytywnie.
Jak było testowane przeszukiwanie z pozycji początkowej to najlepiej sami
wiecie, bo sami testowaliście - wyniki na głębokość 9-10 ruchów były zawsze
dokładne.

Na bazie tak przetestowanej wersji napisałem program, który nie tylko
przeszukuje, ale także wyrzuca układy na standardowe wyjście.
Ilość wszystkich wyrzuconych układów jest poprawna. Natomiast ilość
unikalnych jest poprawna tylko do głębokości 5 ruchów. Przy głębokości 6
ruchów, ilość unikalnych układów jest o 2 za duża.

Mało tego, mam napisany drugi program do zliczania unikalnych układów.
Ten drugi też podaje o 2 więcej niż wynika z dostępnych
materiałów. Zasada działania drugiego programu jest zupełnie inna, gdyż zlicza
on tylko wartości funkcji skrótu. Może warto podkreślić, że jakby błąd był w funkcji
skrótu, to z powodu kolizji byłoby za mało układów - a jest o te 2 układy za dużo.

To jeszcze nie koniec. Obecnie program napisany jest tak, że generuje sobie
sam pod-zadania. Gdy ma przeszukać na głębokość np. 10 ruchów, to
najpierw przeszukuje na 3-4 ruchy. Zapamiętuje unikalne układy z tych
3-4 ruchów. Następnie po kolei ustawia kolejne układy i przeszukuje każdy
układ na 7-6 ruchów, tak aby łączna głębokość wynosiła założone 10 ruchów.
Przez chwilę pomyślałem, że błąd jest właśnie w generowaniu/formatowaniu
układów. No ale nie może tam być błędu, bo generowanie jest wykorzystywane
także w zwykłym przeszukiwaniu, a więc było też przetestowane.

Patrzyłem dziś w różne miejsca kodu i nie wiem co się dzieje. Wygląda to tak,
jakby jeden i ten sam element raz działał, a drugi raz nie. W dodatku
dwa różne algorytmy dają taki sam błąd. Wszelka logika zawodzi. 
Może jakiś element programu nie był tak dokładnie przetestowany jak mi się
wydaje, ale to raczej bym wiedział. 

Zastanawiam się czy może być błąd w materiałach jakie znalazłem, ale taką
możliwość chyba też trzeba odrzucić. Zakładam że jak ktoś przygotowywał
takie czy inne materiały, to jakoś zweryfikował wyniki.


W trakcie pisania tego posta, naszło mnie pewne spostrzeżenie. Program perft4
ma problem z wygenerowaniem unikalnych układów na głębokości równej sześć.
Nie jestem dobrym szachistą, interesuję się tylko szachami komputerowymi, a
samemu nie gram, ale jeśli się nie mylę, to na tej samej głębokości zaczynają
mieć znaczenie "przyzwolenia" do roszad. Przykład widać na pozycji 1 poniżej:
białe i czarne wyjeżdżają skoczkiem i laufrem i mogą wykonać małe roszady:
pozycja 1
Pojawia się w tym kontekście pewna ciekawostka. W sześciu ruchach można także
dojść do takiego układu:
pozycja 2
Białe nie wykonały żadnego ruchu ani królem, ani wieżą, jest wolna przestrzeń
pomiędzy królem i wieżą, więc mają "przyzwolenie" do roszady. Jednak roszady
wykonać w siódmy ruchu nie mogą, bo jest atakowane pole na drodze króla.


Z punktu widzenia programu do zliczania wszystkich pozycji powyższy niuans
nie ma znaczenia, gdyż program i tak i tak nie wykona roszady wbrew zasadom gry, a
więc pozycji po jej wykonaniu nie uwzględni w zliczaniu. Natomiast w przypadku
zliczania unikalnych pozycji mamy dwuznaczność. Gdy zignorujemy "przyzwolenia", to
jest wszystko w porządku, bo i tak i tak nie możemy roszady wykonać. Gdy nie zignorujemy,
to też jest wszystko w porządku - po prostu mamy dodatkową informację o tym, że król i
wieża nie była do tej pory ruszana. Przyzwolenia będą ważne w ruchach następnych, ale w tej
pozycji równie dobrze możemy o nich pamiętać jak i nie.

Czyżby powyższe spostrzeżenie prowadziło do wniosku, że w materiałach jakie mam, ktoś
robiący badania uznał, że w takich pozycjach należy usunąć informację o przyzwoleniach, bowiem
i tak i tak nie można wykonać roszady, a ponadto takie pozycje pojawiają się raptem dwie wśród 12milionów
pozycji, a więc w wynikach ma o te dwie pozycje mniej niż ja?  :boing: Brzmi nieprawdopodobnie, dosłownie
nie mogę uwierzyć, ale na tę chwilę nie mam lepszego wyjaśnienia.

Pewne natomiast jest to, że ja nie mogę z work-units usunąć informacji o przyzwoleniach, bo będzie ona
potrzebna w dalszym przeszukiwaniu drzewa gry, konkretnie w tym przeszukiwaniu jakie będą wykonywały aplikacje
klienckie.

Jakby ktoś coś dorzucił do moich rozważań, to za wszelkie inspirację będę wdzięczny.
Pozdrawiam

[krzyszp]

Czyżby powyższe spostrzeżenie prowadziło do wniosku, że w materiałach jakie mam, ktoś
robiący badania uznał, że w takich pozycjach należy usunąć informację o przyzwoleniach, bowiem
i tak i tak nie można wykonać roszady, a ponadto takie pozycje pojawiają się raptem dwie wśród 12milionów

Ciężko ocenić, nie znając materiałów na których się opierasz (być może informacja o tym jest w tekście)...

[mariotti]

Czyżby powyższe spostrzeżenie prowadziło do wniosku, że w materiałach jakie mam, ktoś
robiący badania uznał, że w takich pozycjach należy usunąć informację o przyzwoleniach, bowiem
i tak i tak nie można wykonać roszady, a ponadto takie pozycje pojawiają się raptem dwie wśród 12milionów

Ciężko ocenić, nie znając materiałów na których się opierasz (być może informacja o tym jest w tekście)...

Pogrzebałem jeszcze trochę w sieci.
Tutaj jest z trójką na końcu (9417683) .
A tutaj z jedynką (9417681)
Piszą, że różnica wynika z tego, iż bicie w przelocie jest (czasami) nielegalne. Przyczyna
różnicy jest podobna jak opisałem powyżej, jednak myliłem się że względem roszady. Nielegalność
oznacza, że po wykonaniu bicia w przelocie król (król strony wykonującej to bicie) będzie
szachowany. Skoro to nielegalny ruch, to można informację o nim usunąć. Jeśli się usunie, to
układów będzie mniej. Trochę dziwne, że przy przeszukiwaniu na głębokość sześciu
ruchów, są tylko dwie takie sytuacje, ale widocznie tak jest.

Program z tą "usterką" zadziałałby poprawnie, po prostu dwa układy brałby za różne, gdy
można je wziąć za takie same. Jednak widzę sens wprowadzenia zmiany do programu.
Po zmianie będzie można sprawdzić, czy ilość unikalnych układów zgadza się z podaną
ilością w tamtych wynikach. Program szybciej będzie przetestowany, odpadnie wiele testów z
poziomu serwera boinc.

Pozdrawiam

P.S.
Tam chyba pełny test perft do depth <= 13
perft <= 13

[mariotti]

Mam wielką prośbę do Was o przeprowadzenie pewnego testu. Na stacjonarnym komputerze
mam losowe wyniki, nie wiem czy ja narobiłem błędów, czy coś źle ze sprzętem lub systemem.
Cały program perft jest wielki, więc napisałem mały substytut o nazwie test_csuniq.
Substytut generuje wiersze, w tym pewną ilość unikalnych wierszy. Jeśli test się nie powiedzie,
to będziemy mieli 100% pewności, że jest błąd w jednym z członów:
1) błąd w programie test_csuniq
2) błąd sprzętu
3) błąd systemu operacyjnego w szczególności narzędzi systemowych
4) błąd kompilatora, bibliotek dostarczonych z kompilatorem
Zrobiłem na laptopie około 10 testów i zakończyły się powodzeniem. Na stacjonarnym 50% kończy
się błędem.

Jak uruchomić program? Można przykładową komendą:

Kod [Zaznacz] Rozwiń


./test_csuniq len_min=5 len_max=20 rows=30 uniq=5 seed=0

Tak uruchomiony program wygeneruje 30 wierszy (rows=30), w
tym 5 unikalnych (unq=5), o długości z przedziału od 5 do 20 znaków.
Wiersze będą zawierały (prawie) losowe znaki ascii. Sposób losowania
można kontrolować nadając parametrowi seed wartości powyżej zero.

Test polega na przekierowaniu programu do sort, uniq i wc, aby sprawdzić czy
ilość unikalnych wierszy jest taka jak wartość parametru uniq. Poniższe
uruchomienie powinno dać w wyniku wartość 50tys.

Kod [Zaznacz] Rozwiń


./test_csuniq len_min=7 len_max=70 rows=200000 uniq=50000 seed=0 | sort | uniq | wc -l


Jak ktoś nie chce wnikać w szczegóły, to najlepiej pobrać źródło programu i
zapisać je jako plik 'main.cpp' w jakimś katalogu:

Kod [Zaznacz] Rozwiń


#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <ctime>

typedef int ityp;
typedef const int cityp;
typedef unsigned int utyp;
typedef const utyp cutyp;


static void help() {
printf("using:test_csuniq len_min=uint len_max=uint rows=uint uniq=uint seed=uint\n");
abort();
}


struct Args {
utyp len_min;
utyp len_max;
utyp rows;
utyp uniq;
utyp seed;
};


static void parseArgs(int argc, char *argv[], Args &args) {
memset( &args , 0 , sizeof(args) );
args.seed = 0;
for( int i=1 ; i<argc ; i++ ) {
if( strncmp( "len_min=" , argv[i] , 8 ) == 0 ) {args.len_min = (utyp)atol( argv[i]+8 ); }
if( strncmp( "len_max=" , argv[i] , 8 ) == 0 ) {args.len_max = (utyp)atol( argv[i]+8 ); }
if( strncmp( "rows="    , argv[i] , 5 ) == 0 ) {args.rows    = (utyp)atol( argv[i]+5 ); }
if( strncmp( "uniq="    , argv[i] , 5 ) == 0 ) {args.uniq    = (utyp)atol( argv[i]+5 ); }
if( strncmp( "seed="    , argv[i] , 5 ) == 0 ) {args.seed    = (utyp)atol( argv[i]+5 ); }
}
if( args.len_max < args.len_min ) help();
if( args.rows < args.uniq ) help();
if( args.len_min == 0 ) help();
if( args.len_max == 0 ) help();
if( args.rows == 0 ) help();
if( args.uniq == 0 ) help();
if( args.seed == 0 ) args.seed = time(NULL);
}


char rndChar() {
const static char rndc[] = "-=!@#$%^&*()_+qqweertyuiop[[]]]\\QWERTYUIOP{}|asdfghjkl;'ASDFGHJKL:\"zxcvbnm,./ZXCVBNM<>?`~";
return rndc[ rand() % (sizeof(rndc)-1) ];
}

void rndString( cutyp len_min, cutyp len_max , char string[] , utyp nr ) {
utyp len = rand() % ( len_max - len_min + 1 ) + len_min;
string[len] = 0;
while( len && nr ) {
string[--len] = '0' + (nr%10);
nr /= 10;
}
while( len )
string[--len] = rndChar();
}

int main(int argc, char *argv[]) {
Args args;
parseArgs( argc , argv , args );
srand(args.seed);

char **strings = new char*[args.uniq];
utyp *counts = new utyp[args.uniq];
char *string = new char[args.len_max+1];

for( utyp i=0 ; i<args.uniq ; i++ ) {
rndString( args.len_min , args.len_max , string , i+1 );
strings[i] = strdup( string );
counts[i] = 1;
}


utyp r = rand();
for( utyp i=0 ; i<args.rows-args.uniq ; i++ ) {
r = (r + rand())%args.uniq;
counts[r] ++ ;
}

{
utyp uniq = args.uniq;
while( uniq ) {
r = (r + rand()) % uniq;
printf("%s\n",strings[r]);
if( --counts[r] == 0 ) {
free( strings[r] );
strings[r] = strings[uniq-1];
counts[r] = counts[uniq-1];
uniq--;
}
}
}



delete[] string;
delete[] counts;
delete[] strings;

return 0;
}



Następnie w tym samym katalogu trzeba zapisać skrypt powłoki:

Kod [Zaznacz] Rozwiń


g++ -O3 -omit-frame-pointers -march=native -o test_csuniq main.cpp
mkdir -p tmp
RAM=$1

./test_csuniq len_min=10  len_max=20  rows=20000    uniq=5000    seed=0  | sort -T'./tmp' -S$RAM | uniq | wc -l
./test_csuniq len_min=50  len_max=100  rows=20000    uniq=5000    seed=0  | sort -T'./tmp' -S$RAM | uniq | wc -l
./test_csuniq len_min=500  len_max=1000  rows=20000    uniq=5000    seed=0  | sort -T'./tmp' -S$RAM | uniq | wc -l
./test_csuniq len_min=10  len_max=20  rows=20000    uniq=5000    seed=0  | sort -T'./tmp' -S$RAM --compress-program=gzip | uniq | wc -l
./test_csuniq len_min=50  len_max=100  rows=20000    uniq=5000    seed=0  | sort -T'./tmp' -S$RAM --compress-program=gzip | uniq | wc -l
./test_csuniq len_min=500  len_max=1000  rows=20000    uniq=5000    seed=0  | sort -T'./tmp' -S$RAM --compress-program=gzip | uniq | wc -l


./test_csuniq len_min=10  len_max=20  rows=200000   uniq=50000   seed=0  | sort -T'./tmp' -S$RAM | uniq | wc -l
./test_csuniq len_min=50  len_max=100  rows=200000   uniq=50000   seed=0  | sort -T'./tmp' -S$RAM | uniq | wc -l
./test_csuniq len_min=500  len_max=1000  rows=200000   uniq=50000   seed=0  | sort -T'./tmp' -S$RAM | uniq | wc -l
./test_csuniq len_min=10  len_max=20  rows=200000   uniq=50000   seed=0  | sort -T'./tmp' -S$RAM --compress-program=gzip | uniq | wc -l
./test_csuniq len_min=50  len_max=100  rows=200000   uniq=50000   seed=0  | sort -T'./tmp' -S$RAM --compress-program=gzip | uniq | wc -l
./test_csuniq len_min=500  len_max=1000  rows=200000   uniq=50000   seed=0  | sort -T'./tmp' -S$RAM --compress-program=gzip | uniq | wc -l


./test_csuniq len_min=10  len_max=20  rows=2000000  uniq=500000  seed=0  | sort -T'./tmp' -S$RAM | uniq | wc -l
./test_csuniq len_min=50  len_max=100  rows=2000000  uniq=500000  seed=0  | sort -T'./tmp' -S$RAM | uniq | wc -l
./test_csuniq len_min=500  len_max=1000  rows=2000000  uniq=500000  seed=0  | sort -T'./tmp' -S$RAM | uniq | wc -l
./test_csuniq len_min=10  len_max=20  rows=2000000  uniq=500000  seed=0  | sort -T'./tmp' -S$RAM --compress-program=gzip | uniq | wc -l
./test_csuniq len_min=50  len_max=100  rows=2000000  uniq=500000  seed=0  | sort -T'./tmp' -S$RAM --compress-program=gzip | uniq | wc -l
./test_csuniq len_min=500  len_max=1000  rows=2000000  uniq=500000  seed=0  | sort -T'./tmp' -S$RAM --compress-program=gzip | uniq | wc -l


./test_csuniq len_min=10  len_max=20  rows=20000000 uniq=5000000 seed=0  | sort -T'./tmp' -S$RAM | uniq | wc -l
./test_csuniq len_min=50  len_max=100  rows=20000000 uniq=5000000 seed=0  | sort -T'./tmp' -S$RAM | uniq | wc -l
./test_csuniq len_min=500  len_max=1000  rows=20000000 uniq=5000000 seed=0  | sort -T'./tmp' -S$RAM | uniq | wc -l
./test_csuniq len_min=10  len_max=20  rows=20000000 uniq=5000000 seed=0  | sort -T'./tmp' -S$RAM --compress-program=gzip | uniq | wc -l
./test_csuniq len_min=50  len_max=100  rows=20000000 uniq=5000000 seed=0  | sort -T'./tmp' -S$RAM --compress-program=gzip | uniq | wc -l
./test_csuniq len_min=500  len_max=1000  rows=20000000 uniq=5000000 seed=0  | sort -T'./tmp' -S$RAM --compress-program=gzip | uniq | wc -l


Skrypt sam:
- skompiluje program
- założy katalog tymczasowy dla polecenia sort
- no i przeprowadzi testy.

Jako parametr skryptu podajemy ilość pamięci w kilobajtach. Gdy skrypt zapisaliśmy
jako plik 'go.sh', to uruchomienie dla 3GB RAM wygląda tak:

Kod [Zaznacz] Rozwiń


./go.sh 3000000


Jeśli test przebiegnie pomyślnie, to program wyświetli  6 razy: 5tys, 50tys, 500tys i 5mln, czyli
razem 24 liczby. Ostatnie testy zajmują dużo czasu i wymagają dużo miejsca na dysku, więc
jak ktoś straci cierpliwość, to po wyświetleniu 20 początkowych liczb można program ubić.

Program losuje sobie zarodek liczb losowych z czasu systemowego, więc każde uruchomienie to
trochę inny test, można program uruchomić kilka razy.

Pozdrawiam

[AXm77]

[krzyszp]

Robi się, aktualnie mam drugi raz 500k na ekranie.

[mariotti]

Robi się, aktualnie mam drugi raz 500k na ekranie.

Dziękuję wszystkim. To jest prosty program, ale wpadam w paranoję, że narobiłem
jakiś błędów, bo sytuacja jest dziwna. Dziwność jej polega na tym, że
jakbym miał błędy na dysku przenośnym, to by też na laptopie nie działało.
Jakbym miał uszkodzoną pamięć RAM, to by nie działał Linux, a już
na pewno by nie działał tam program perft, który korzysta z hash-table o
rozmiarze 6GB RAM. Jednak to wszystko działa i wiele innych programów
też działa. Błąd kompilatora też nie wchodzi w grę, bo jak przenoszę
program skompilowany na laptopie, to na PC nadal nie działa. Jak
długo chodzę po tej planecie, czegoś takiego nie widziałem. No chyba
że jednak znajdziecie błąd w tym prostym programie :)

Pozdrawiam

[krzyszp]

Spokojnie, nie takie rzeczy widzialem...

Wierz mi, że kompilatory potrafią cuda narobić, a zwłaszcza w sytuacji, gdy nieświadomie, podczas ich instalacji np. włączysz optymalizację dla którejś wersji sse...

Osobny temat (rzeka) to .net w tym względzie...

Koniec off-topa... Jak długo program powinien się wykonywać?

[mariotti]

Spokojnie, nie takie rzeczy widzialem...
Wierz mi, że kompilatory potrafią cuda narobić, a zwłaszcza w sytuacji, gdy nieświadomie, podczas ich instalacji np. włączysz optymalizację dla którejś wersji sse...

Wierzę, ale dlaczego reszta programów działa?

Osobny temat (rzeka) to .net w tym względzie...
Koniec off-topa... Jak długo program powinien się wykonywać?

Dwadzieścia pierwszych testów powinno w kilka minut wyskoczyć. Pozostałe mogą trwać bardzo
długo. Jak wyświetlił wyniki z 20 testów, to już jest miarodajne i można ubić przez ctrl+c.

Pozdrawiam

[sknd]

Koniec off-topa... Jak długo program powinien się wykonywać?

o właśnie, też mnie interesuje odpowiedź, bo nie wiem czy jest sens to dzisiaj zapuszczać

[mariotti]

Koniec off-topa... Jak długo program powinien się wykonywać?

o właśnie, też mnie interesuje odpowiedź, bo nie wiem czy jest sens to dzisiaj zapuszczać

Program można zabić po wyczerpaniu cierpliwości, np. po 5-15 minutach :)
Pozdrawiam

[sknd]

po dwudziestu kilku minutach zrobiło mi się szkoda dysku;)

Kod [Zaznacz] Rozwiń

[ja@komp tlo]$ chmod +x go.sh
[ja@komp tlo]$ ./go.sh 8000000
5000
5000
5000
5000
5000
5000
50000
50000
50000
50000
50000
50000
500000
500000
500000
500000
500000
500000
5000000
5000000