Jak działa Ksh93 tak szybko?

9

Ogólnie rzecz biorąc, zwykle szukam sedprzetwarzania tekstu - szczególnie w przypadku dużych plików - i zwykle unikam robienia tego rodzaju rzeczy w samej powłoce.

Myślę jednak, że to może się zmienić. Grzebałem man kshi zauważyłem to:

<#pattern     Seeks forward to the beginning of the
              next line containing pattern.

<##pattern    The same as <# except that  the  por
              tion  of  the file that is skipped is
              copied to standard output.

Sceptycznie odnosząc się do użyteczności w świecie rzeczywistym, postanowiłem to wypróbować. Zrobiłem:

seq -s'foo bar
' 1000000 >file

... dla miliona linii danych, które wyglądają jak:

1foo bar
...
999999foo bar
1000000

... i zmierzyli się z sed:

p='^[^0-8]99999.*bar'
for c in "sed '/$p/q'" "ksh -c ':<##@(~(E)$p)'"    
do </tmp/file eval "time ( $c )"
done | wc -l

Tak więc oba polecenia powinny dostać się do paska 999999foo, a ich implementacja dopasowania wzorca musi oceniać co najmniej początek i koniec każdej linii w tym celu. Muszą także zweryfikować pierwszy znak względem zanegowanego wzoru. To prosta sprawa, ale ... Wyniki nie były zgodne z oczekiwaniami:

( sed '/^[^0-8]99999.*bar/q' ) \
    0.40s user 0.01s system 99% cpu 0.419 total
( ksh -c ':<##@(~(E)^[^0-8]99999.*bar)' ) \
    0.02s user 0.01s system 91% cpu 0.033 total
1999997

kshużywa ERE tutaj i sedBRE. kshWcześniej robiłem to samo i wzór powłoki, ale wyniki nie różniły się.

W każdym razie jest to dość znacząca rozbieżność - kshprzewyższa sed10 razy. Czytałem wcześniej, że David Korn napisał własną bibliotekę io i implementuje ją w ksh- być może jest to związane? - ale ja nic o tym nie wiem. Jak to się dzieje, że skorupa robi to tak dobrze?

Jeszcze bardziej zdumiewające jest dla mnie to, że kshnaprawdę pozostawia swoje przesunięcie tam, gdzie o to prosisz. Aby uzyskać (prawie) to samo z (GNU) sed , musisz użyć -u- bardzo wolno .

Oto test grepv ksh:

1000000         #grep + head
( grep -qm1 '^[^0-8]99999.*bar'; head -n1; ) \
    0.02s user 0.00s system 90% cpu 0.026 total
999999foo bar   #ksh + head
( ksh -c ':<#@(~(E)^[^0-8]99999.*bar)'; head -n1; )  \
    0.02s user 0.00s system 73% cpu 0.023 total

kshbije greptutaj - ale nie zawsze - są prawie związane. Mimo to jest to całkiem doskonałe i ksh zapewnia spojrzenie z wyprzedzeniem, zanimhead rozpocznie się mecz.

Wydaje mi się, że to po prostu zbyt piękne, aby mogło być prawdziwe. Co te polecenia robią inaczej pod maską?

Och, i najwyraźniej nie ma tu nawet podpowłoki:

ksh -c 'printf %.5s "${<file;}"'
mikeserv
źródło
Czy patternwyrażenie regularne czy prostszy wzór powłoki?
muru
@muru - Może być albo, ale nie jestem zbyt dobry w zmienianiu tych. W tym przykładzie jest to wzór powłoki - domyślny.
mikeserv
@muru - Dodałem jeden z wyrażeniem regularnym.
mikeserv

Odpowiedzi:

8

Ksh nie tylko korzysta z sfio, ale korzysta z własnego niestandardowego przydziału pamięci.

Niemniej jednak przypuszczam, że sfio robi różnicę w tym przypadku. Właśnie próbowałem uruchomić twój przykład pod kontrolą i widzę, że wywołania ksh odczytują / zapisują ~ 200 razy (bloki 65 KB), a sed robi to ~ 3400 razy (bloki 4 KB). Z sed -u mój laptop prawie się stopił, odczyty są wykonywane na bajt i zapisywane na wiersz. Ksh simple używa lseek. Grep używa odczytu ~ 400 razy (bloki 32 KB).

Miroslav Franc
źródło
Tak - niebuforowany nie jest dla osób o słabym sercu. Zastanawiam się, czy kshsilnik regex jest wydajny jak jego io? W każdym razie dziękuję bardzo za odpowiedź. Przepraszam twojego laptopa. A co z niestandardowym alokatorem pamięci? Czy masz coś więcej na ten temat?
mikeserv
1
Niestety nie. Możesz oczywiście pobrać kod źródłowy ze strony at & t, ale to wszystko. Biblioteka nazywa się AST i zawiera alokator, silnik regex i wiele innych rzeczy. Jest więc całkiem możliwe, że połączenie tych wszystkich rzeczy znacznie przyspiesza działanie Ksh.
Miroslav Franc
Dziękuję - to też wygląda obiecująco: niektóre komponenty dostępne w kolekcji oprogramowania AST to: Polecenia POSIX Większość standardowych poleceń POSIX jest dostępnych w kolekcji AST. Wiele z nich jest zakodowanych jako funkcje biblioteczne, które można dodać do ksh jako wbudowane polecenie, które znacznie poprawia wydajność. - Teraz muszę tylko wymyślić, jak to zbudować,
mikeserv
1
@mikeserv ksh można zbudować tak, aby korzystał z programu vmalloc w programie Phong Vo . Artykuły w czasopismach dostępne pod tym linkiem.
Mark Plotnick,