Fastest and most efficient way to get number of records (lines) in a gzip-compressed file

Question

I am trying to do a record count on a 7.6 GB gzip file. I found few approaches using the zcat command.

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

This works but it takes too much time (more than 10 minutes to get the count). I tried a few more approaches like

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

All three of these commands are executing pretty fast but giving an incorrect count of 28173811.

How can I perform a record count in a minimal amount of time?

Answer 1

The sed, perl and awk commands that you mention may be correct, but they all read the compressed data and counts newline characters in that. These newline characters have nothing to do with the newline characters in the uncompressed data.

To count the number of lines in the uncompressed data, there is no way around uncompressing it. Your approach with zcat is the correct approach and since the data is so large, it will take time to uncompress it.

Most utilities that deals with gzip compression and decompression will most likely use the same shared library routines to do so. The only way to speed it up would be to find an implementation of the zlib routines that are somehow faster than the default ones, and rebuild e.g. zcat to use those.

Answer 2

Use unpigz.

Kusalananda's answer is correct, you will need to uncompress that entire file to scan its contents. /bin/gunzip does this as fast as it can, on a single core. Pigz is a parallel implementation of gzip that can use multiple cores.

Sadly, the decompression itself of normal gzip files cannot be parallelized, but pigz does offer an improved version of gunzip, unpigz, that does related work such as reading, writing, and checksumming in a separate thread. In some quick benchmarks, unpigz is almost twice as fast as gunzip on my core i5 machine.

Install pigz with your favourite package manager, and use unpigz instead of gunzip, or unpigz -c instead of zcat. So your command becomes:

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

All this assumes the bottleneck is the CPU, not the disk, of course.

Answer 3

The problem with all the pipelines is that you are essentially doubling the work. No matter how fast the decompression is, the data still need to be shuttled to another process.

Perl has PerlIO::gzip which allows you to read gzipped streams directly. Therefore, it might offer an advantage even if its decompression speed may not match that of 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]': $!";

I tried it with a 13 MB gzip compressed file (decompresses to 1.4 GB) on an old 2010 MacBook Pro with 16 GB RAM and an old ThinkPad T400 with 8 GB RAM with the file already in the cache. On the Mac, the Perl script was significantly faster than using pipelines (5 seconds vs 22 seconds), but on ArchLinux, it lost to unpigz:

$ time -p ./gzlc.pl spy.gz 
1154737
real 4.49
user 4.47
sys 0.01

versus

$ time -p unpigz -c spy.gz | wc -l
1154737
real 3.68
user 4.10
sys 1.46

and

$ time -p zcat spy.gz | wc -l
1154737
real 6.41
user 6.08
sys 0.86

Clearly, using unpigz -c file.gz | wc -l is the winner here both in terms of speed. And, that simple command line surely beats writing a program, however short.

Answer 4

Kusalananda's answer is mostly correct. To count lines you need to search for newlines. However it is theoretically possible to search for newlines without completely uncompressing the file.

gzip uses DEFLATE compression. DEFLATE is a combination of LZ77 and Huffman encoding. There may be a way to figure out just the Huffman symbol node for newline and ignore the rest. There almost certainly is a way to look for newlines encoded using L277, keep a byte count and ignore everything else.

So IMHO its theoretically possible to come up with a solution more efficient than unpigz or zgrep. That being said its certainly not practical (unless someone has already done it).

Answer 5

Can be done using zgrep with -c flag, and $ parameter.

In this case -c instruct the command to output number of matched lines and the regex $ matches end of line so it matches every line or the file.

zgrep -c $ T.csv.gz 

As commented by @StéphaneChazelas - zgrep is only a script around zcat and grep and it should provide similar performance to the original suggestion of zcat | wc -l

Answer 6

I wrote a parallel gzip decoder, rapidgzip (previously "pragzip"), which can speed up this use case. Here is a performance comparison for counting newlines. I also added igzip, part of the isal package, to the comparison because it is the fastest single-core gzip decompressor I know of. And I included pigz because it is often mentioned for parallel gzip handling but that is only for compression while it doesn't actually use all cores for decompression.

Decoder	Lines	Runtime / s	Bandwidth / (MB/s)
rapidgzip --count-lines	55778796	0.879	4886
rapidgzip	55778796	1.309	3281
igzip	55778796	9.113	471
pigz	55778796	13.091	328
gzip	55778796	22.132	194
zgrep	55778797	23.061	186

Tested on a Ryzen 3900X with 64 GB of RAM. Of course, you will either need a fast enough SSD or use an in-memory file system like /dev/shm, or depending on the distribution /tmp, to reach these speeds.

As others have mentioned, further speedups can be reached by specializing the decoder and letting it do the counting internally instead of copying and piping the decoded data to another tool. This is what rapidgzip --count-lines does.

Furthermore, rapidgzip still contains many things that can be further optimized. Note that at this point you will very likely run into I/O problems first because the disk also has to keep up.

Lastly, beware that the result for zgrep as mentioned in the other answer (zgrep -c '$' 4GiB-base64.gz) is off by one because wc -l counts the number of \n while zgrep -c '$' effectively counts every line including the last one even if it does not end with \n!

This is the script I used to benchmark:

sudo apt install pigz isal
python3 -m pip install --user --upgrade rapidgzip
# Create a compressible random file with many newlines
base64 /dev/urandom | head -c $(( 4 * 1024 * 1024 * 1024 )) > 4GiB-base64
gzip -c 4GiB-base64

fileSize=$( stat -L --format=%s 4GiB-base64 )
printf '\n| %7s | %8s | %10s | %18s |\n' Decoder Lines 'Runtime / s' 'Bandwidth / (MB/s)'
printf -- '|---------|----------|-------------|--------------------|\n'
for tool in rapidgzip igzip pigz gzip; do
    lineCount=$( $tool -d -c "4GiB-base64.gz" | wc -l )
    runtime=$( ( time $tool -d -c "4GiB-base64.gz" | wc -l ) 2>&1 | sed -n -E 's|real[ \t]*0m||p' | sed 's|[ \ts]||' )
    bandwidth=$( python3 -c "print( int( round( $fileSize / 1e6 / $runtime ) ) )" )
    printf '| %7s | %8s | %11s | %18s |\n' "$tool" "$lineCount" "$runtime" "$bandwidth"
done

lineCount=$( zgrep -c '$' "4GiB-base64.gz" )
runtime=$( ( time zgrep -c '$' "4GiB-base64.gz" ) 2>&1 | sed -n -E 's|real[ \t]*0m||p' | sed 's|[ \ts]||' )
bandwidth=$( python3 -c "print( int( round( $fileSize / 1e6 / $runtime ) ) )" )
printf '| %7s | %8s | %11s | %18s |\n' "zgrep" "$lineCount" "$runtime" "$bandwidth"

lineCount=$( rapidgzip --count-lines "4GiB-base64.gz" )
runtime=$( ( time rapidgzip --count-lines "4GiB-base64.gz" ) 2>&1 | sed -n -E 's|real[ \t]*0m||p' | sed 's|[ \ts]||' )
bandwidth=$( python3 -c "print( int( round( $fileSize / 1e6 / $runtime ) ) )" )
printf '| %7s | %8s | %11s | %18s |\n' "rapidgzip --count-lines" "$lineCount" "$runtime" "$bandwidth"

Rapidgzip can also be used as a library from Python. Line counting could be done like this:

python3 -m pip install --user rapidgzip

import rapidgzip
result = 0
with rapidgzip.open("silesia.tar.gz") as file:
    while chunk := file.read( 1024*1024 ):
        result += chunk.count(b'\n')
print("Number of newlines:", result)

Note that performance is significantly impacted by the chunk size used for the read call and even Python's count function might be a bottleneck. I have not benchmarked this implementation.

Answer 7

As you can see, most answers tries to optimize what it can: the number of the context switches and inter-process IO. The reason is, this is the only what you can optimize here easily.

Now the problem is that its resource need is nearly negligible to the resource need of the decompression. This is why the optimizations won't really make anything faster.

Where it could be really accelerated, it would be a modified un-gzip (i.e. decompression) algorithm, which leaves out the actual production of the decompressed data stream; rather it only calculates the number of the newlines in the decompressed stream from the compressed one. It would be hard, it would require the deep knowledge of the gzip's algorithm (some combination of the LZW and Huffman compression algorithms). It is quite probable, that the algorithm doesn't make it possible to significantly optimize the decompression time with the lightening, that we only need to know the newline counts. Even if it would be possible, essentially a new gzip decompression library should have been developed (it doesn't exists until know).

The realistic answer to your question is, that no, you can't make it significantly faster.

Maybe you could use some parallelized gzip decompression, if it exists. It could use multiple CPU cores for the decompression. If it doesn't exist, it could be relatively easily developed.

For the xz, there exists a parallel compressor (pxz).