Najszybszy i najbardziej wydajny sposób na uzyskanie liczby rekordów (wierszy) w pliku skompresowanym gzip

16

Próbuję wykonać rejestr rekordów dla pliku gzip o wielkości 7,6 GB. Znalazłem kilka podejść przy użyciu zcatpolecenia.

$ zcat T.csv.gz | wc -l
423668947

To działa, ale zajmuje zbyt dużo czasu (więcej niż 10 minut, aby uzyskać licznik). Próbowałem jeszcze kilku takich podejść

$ sed -n '$=' T.csv.gz
28173811
$ perl -lne 'END { print $. }' < T.csv.gz
28173811
$ awk 'END {print NR}' T.csv.gz
28173811

Wszystkie trzy te polecenia działają dość szybko, ale dają niepoprawną liczbę 28173811.

Jak mogę wykonać rekord w minimalnym czasie?

Rahul
źródło
5
Dlaczego musisz liczyć liczbę rekordów? Jeśli próbujesz je policzyć przed przetworzeniem, oznacza to, że musisz dwukrotnie rozpakować plik.
Andrew Henle,
3
Pomocne byłoby więcej informacji o tym, dlaczego to robisz. Jeśli coś jest w toku - to znaczy regularnie kompresujesz kilka plików, a później musisz znać liczbę rekordów - dlaczego nie policzyć ich jako skompresowanych i osadzić liczbę w nazwie pliku?
jamesqf
3
Odczytywanie pliku 9,7 GB z dysku mechanicznego jest z natury wolniejsze. Zapisz plik na dysku SSD i sprawdź, o ile szybciej działa gunzip / zcat. Ale jak mówi @jamesqf, zapisz numer linii w nazwie pliku lub w pliku w tgz, a rozpakowanie tego pliku będzie znacznie szybsze.
ChuckCottrill
2
Istnieją dobre teoretyczne powody, dla których nie można uniknąć tej pracy. Format kompresji, który pozwala określić jakąś użyteczną właściwość danych „bez dekompresji”, z definicji nie jest tak dobrym formatem kompresji, jak mógłby być :)
hobbs

Odpowiedzi:

28

Te sed, perli awkpolecenia, które można wymienić poprawne, ale wszystko przeczytać skompresowane dane i liczby znaków nowego wiersza w tym. Te znaki nowej linii nie mają nic wspólnego ze znakami nowej linii w nieskompresowanych danych.

Aby policzyć liczbę wierszy w nieskompresowanych danych, nie ma sposobu na ich rozpakowanie. Twoje podejście zcatjest prawidłowe, a ponieważ dane są tak duże, ich rozpakowanie zajmie trochę czasu.

Większość narzędzi zajmujących się gzipkompresją i dekompresją najprawdopodobniej wykorzysta do tego te same procedury bibliotek współdzielonych. Jedynym sposobem na jego przyspieszenie byłoby znalezienie implementacji zlibprocedur, które są w jakiś sposób szybsze od domyślnych, i przebudowanie np. Ich zcatużycie.

Kusalananda
źródło
11
Byłoby to nietrywialne ćwiczenie programistyczne, ale wykonalne. Chodzi o to, aby nie odbudowywać zcat. Znaczna część pracy zcatpolega na generowaniu rzeczywistej produkcji. Ale jeśli liczysz tylko \npostacie, nie jest to konieczne. gzipkompresja działa zasadniczo poprzez zastąpienie zwykłych długich łańcuchów krótszymi łańcuchami. Musisz więc dbać tylko o długie ciągi w słowniku, które zawierają \n, i policz (ważone) ich wystąpienie. Np. Z powodu angielskich zasad .\njest to wspólny ciąg 16 bitów.
MSalters
19

Użyj unpigz.

Odpowiedź Kusalananda jest poprawna, to będzie trzeba rozpakować, że cały plik do skanowania jego zawartość. /bin/gunziprobi to tak szybko, jak to możliwe, na jednym rdzeniu. Pigz to równoległa implementacja, gzipktóra może wykorzystywać wiele rdzeni.

Niestety, dekompresja sama od zwykłych plików gzip nie można parallelized, ale pigznie oferują ulepszoną wersję gunzip, unpigz, że robi prac związanych, takich jak czytanie, pisanie, i sum kontrolnych w osobnym wątku. W niektórych szybkich testach porównawczych unpigzjest prawie dwa razy szybszy niż gunzipna moim podstawowym komputerze i5.

Zainstaluj pigzz ulubionym menedżerem pakietów i używaj unpigzzamiast gunziplub unpigz -czamiast zcat. Twoje polecenie staje się:

$ unpigz -c T.csv.gz | wc -l

Wszystko to zakłada, że ​​wąskim gardłem jest procesor, a nie dysk.

marcelm
źródło
4
Moja pigzstrona podręcznika stwierdza, że dekompresji nie można zrównoleglać, przynajmniej nie bez specjalnie przygotowanych do tego celu strumieni deflacji. W rezultacie pigz używa pojedynczego wątku (głównego wątku) do dekompresji, ale utworzy trzy inne wątki do czytania, pisania i sprawdzania obliczeń, co w niektórych okolicznościach może przyspieszyć dekompresję . Mimo to, podobnie jak ty, uważam, że jest co najmniej dwa razy szybszy niż gzip, jeśli nie z powodu równoległości
Stéphane Chazelas
@ StéphaneChazelas Dobra uwaga! To tłumaczy nieco rozczarowujące przyspieszenie dekompresji. Zredagowałem swój post, aby lepiej odzwierciedlić te informacje.
marcelm
5

Problem ze wszystkimi rurociągami polega na tym, że zasadniczo podwajasz pracę. Bez względu na to, jak szybka jest dekompresja, dane nadal muszą zostać przeniesione do innego procesu.

Perl ma PerlIO :: gzip, który pozwala bezpośrednio czytać strumienie gzip. Dlatego może oferować przewagę, nawet jeśli jego prędkość dekompresyjna może nie odpowiadać unpigz:

#!/usr/bin/env perl

use strict;
use warnings;

use autouse Carp => 'croak';
use PerlIO::gzip;

@ARGV or croak "Need filename\n";

open my $in, '<:gzip', $ARGV[0]
    or croak "Failed to open '$ARGV[0]': $!";

1 while <$in>;

print "$.\n";

close $in or croak "Failed to close '$ARGV[0]': $!";

Próbowałem go z 13 MB skompresowanym plikiem gzip (dekompresuje się do 1,4 GB) na starym MacBooku Pro 2010 z 16 GB pamięci RAM i starym ThinkPad T400 z 8 GB pamięci RAM z plikiem już w pamięci podręcznej. Na Macu skrypt Perla był znacznie szybszy niż przy użyciu potoków (5 sekund vs 22 sekund), ale na ArchLinux stracił rozpakowanie:

$ time -p ./gzlc.pl spy.gz 
1154737
prawdziwe 4,49
użytkownik 4.47
sys 0,01

przeciw

$ time -p unpigz -c spy.gz | wc -l
1154737
prawdziwy 3.68
użytkownik 4.10
sys 1.46

i

$ time -p zcat spy.gz | wc -l
1154737
prawdziwe 6,41
użytkownik 6.08
sys 0,86

Oczywiste jest, że używanie unpigz -c file.gz | wc -ljest tutaj zwycięzcą zarówno pod względem szybkości. I ta prosta linia poleceń z pewnością przewyższa pisanie programu, nawet najkrótszego.

Sinan Ünür
źródło
1
Myślę, że znacznie przeceniasz zasoby wymagane do przenoszenia danych między dwoma procesami, w porównaniu do obliczeń dekompresyjnych. Spróbujcie
porównać
2
@ SinanÜnür W moim systemie Linux x86_64 (także stary sprzęt) gzip | wcma taką samą prędkość jak skrypt w perlu. I pigz | wcjest dwukrotnie szybszy. gzipdziała z tą samą prędkością, niezależnie od tego, czy wypiszę dane wyjściowe do / dev / null lub potok do. wcUważam, że „biblioteka gzip” używana przez perla jest szybsza niż narzędzie wiersza poleceń gzip. Być może istnieje inny specyficzny problem Mac / Darwin z rurami. To wciąż niesamowite, że ta wersja perla jest w ogóle konkurencyjna.
rudimeier
1
W mojej instalacji Linuksa x86_64 wydaje się, że działa lepiej niż zcati gorzej niż unpigz. Dziwi mnie, jak szybszy jest potok w systemie Linux w porównaniu z komputerem Mac. Nie spodziewałem się tego, chociaż powinienem, jak kiedyś zauważyłem, ten sam program działał szybciej na Linux VM z ograniczoną mocą procesora na tym samym komputerze Mac niż na gołym metalu.
Sinan Ünür
1
To interesujące; w moim systemie (Debian 8.8 amd64, quad core i5), skrypt perla jest nieco wolniejszy ... Plik 109g .gz dekompresuje się do 1,1G tekstu, konsekwentnie zajmuje 5,4 sekundy zcat | wc -l, a twój skrypt perla 5,5 sekundy. Szczerze mówiąc, jestem zdumiony różnorodnością, którą zgłaszają ludzie, szczególnie między Linuksem a MacOS X!
marcelm
Nie wiem, czy mogę uogólnić to, co widzę na komputerze Mac, dzieje się coś dziwnego. Z dekompresowanym plikiem 1,4 GB wc -lzajmuje 2,5 sekundy. gzcat compressed.gz > /dev/nullzajmuje 2,7 sekundy. Rurociąg trwa jednak 22 sekundy. Jeśli spróbuję GNU wc, zajmuje to tylko pół sekundy na zdekompresowanym pliku, ale 22 sekundy w potoku. Wykonanie GNU zcatzajmuje dwa razy więcej czasu zcat compressed.gz > /dev/null. To jest na Mavericks, stary procesor Core 2 Duo, 16 GB pamięci RAM, Crucial MX100 SSD.
Sinan Ünür
4

Odpowiedź Kusalanandy jest w większości poprawna. Aby policzyć linie, musisz wyszukać nowe linie. Jednak teoretycznie możliwe jest wyszukiwanie nowych linii bez całkowitego rozpakowywania pliku.

gzip używa kompresji DEFLATE. DEFLATE to kombinacja kodowania LZ77 i Huffmana. Może istnieć sposób, aby odkryć tylko węzeł symbolu Huffmana dla nowej linii i zignorować resztę. Prawie na pewno istnieje sposób na wyszukiwanie nowych linii zakodowanych za pomocą L277, utrzymywanie liczby bajtów i ignorowanie wszystkiego innego.

Więc IMHO teoretycznie możliwe jest znalezienie rozwiązania bardziej wydajnego niż unpigz czy zgrep. To powiedziawszy, z pewnością nie jest praktyczne (chyba że ktoś już to zrobił).

IAmBarry
źródło
7
Głównym problemem związanym z tym pomysłem jest to, że symbole Huffmana używane przez DEFLATE odpowiadają sekwencjom bitów po kompresji LZ77, więc może nie być prostej relacji między nimi a znakami U + 000A w nieskompresowanym pliku. Na przykład, może jeden symbol Huffmana oznacza ostatnie pięć bitów „.” po których następują pierwsze trzy bity „\ n”, a inny symbol oznacza ostatnie pięć bitów „\ n”, po których następują wszystkie osiem bitów „T”.
zwolnienie
@zwol Nie, część LZ77 algorytmu Deflate kompresuje sekwencje bajtów, a nie sekwencje bitów. en.wikipedia.org/wiki/DEFLATE#Duplicate_string_elimination
Ross Ridge
1
@RossRidge Huh, nie wiedziałem o tym, ale nie sądzę, aby unieważniało to, co powiedziałem. W Huffman symbole mogą, wydaje mi się, na podstawie następnym akapicie tego odniesienia, każde rozszerzenie do zmiennej liczby bitów, nie mają produkować całą liczbę bajtów.
zwolnienie
1
@zwol Pewnie, musisz wyszukać pasujące sekwencje bitów kodu Huffmana w strumieniu bitów, ale ta odpowiedź nie sugeruje inaczej. Problem z tą odpowiedzią polega na tym, że ustalenie, które kody Huffmana ostatecznie generują lub więcej znaków nowej linii, nie jest proste. Kody LZ77, które generują nowe linie, zmieniają się stale w miarę przesuwania okna przesuwnego, co oznacza, że ​​zmieniają się również kody Huffmana. Będziesz musiał zaimplementować cały algorytm dekompresyjny oprócz części wyjściowej i być może części przesuwanego okna, ponieważ interesują Cię tylko nowe linie.
Ross Ridge
1

Można to zrobić za zgreppomocą -cflagi i $parametru.

W takim przypadku -c poinstruuj komendę, aby wypisała liczbę dopasowanych linii, a regex $ dopasowuje koniec linii, aby pasował do każdej linii lub pliku.

zgrep -c $ T.csv.gz 

Jak komentował @ StéphaneChazelas - zgrepto tylko skrypt wokół zcati greppowinny zapewniać podobną wydajność do oryginalnego sugestięzcat | wc -l

Yaron
źródło
2
Cześć Yaron, dziękuję za odpowiedź, nawet zgrep zajmuje tyle czasu, ile Zcat. Potrzebuję znaleźć inne podejście, które myślę
Rahul
8
zgrepjest ogólnie skryptem, który wywołuje zcat(tak samo jak gzip -dcq), aby rozpakować dane i nakarmić je grep, więc nie pomoże.
Stéphane Chazelas
1
@ StéphaneChazelas - dziękuję za komentarz, zaktualizuj moją odpowiedź, aby ją odzwierciedlić.
Yaron
0

Jak widać, większość odpowiedzi próbuje zoptymalizować to, co potrafi: liczbę przełączników kontekstu i międzyoperacyjne operacje wejścia / wyjścia. Powodem jest to, że jest to jedyne, co można tutaj łatwo zoptymalizować.

Problem polega na tym, że zapotrzebowanie na zasoby jest prawie nieistotne w stosunku do zapotrzebowania na zasoby podczas dekompresji. Właśnie dlatego optymalizacje nie przyspieszają niczego.

Tam, gdzie można to naprawdę przyspieszyć, byłby to zmodyfikowany algorytm rozpakowywania (tj. Dekompresji), który pomija faktyczną produkcję rozpakowanego strumienia danych; raczej oblicza tylko liczbę nowych linii w zdekompresowanym strumieniu ze skompresowanego . Byłoby ciężko, wymagałaby głębokiej znajomości algorytmu gzip (pewnej kombinacji algorytmów kompresji LZW i Huffmana ). Jest całkiem prawdopodobne, że algorytm nie pozwala znacząco zoptymalizować czasu dekompresji przy oświetleniu, że musimy tylko znać liczbę nowych linii. Nawet jeśli byłoby to możliwe, zasadniczo powinna zostać opracowana nowa biblioteka dekompresyjna gzip (nie istnieje, dopóki się nie dowie).

Realistyczna odpowiedź na twoje pytanie brzmi: nie, nie możesz uczynić go znacznie szybszym.

Być może przydałaby Ci się równoległa dekompresja gzip, jeśli istnieje. Może używać wielu rdzeni procesora do dekompresji. Jeśli nie istnieje, można go stosunkowo łatwo opracować.

Dla xz istnieje równoległy kompresor (pxz).

peterh - Przywróć Monikę
źródło