16

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?

  • 5
    Why do you need to count the number of records? If you're trying to count them before processing them, that means you have to uncompress the file twice. – Andrew Henle May 8 '17 at 10:25
  • 3
    More info on why you're doing this would be helpful. If it's something ongoing - that is, you regularly compress a bunch of files, and at some later time need to know the number of records - why not count them as they're compressed, and embed the number in the file name? – jamesqf May 8 '17 at 18:35
  • 3
    Reading a 9.7GB file from a mechanical disk is inherently slower. Store the file on an SSD, and see how much faster the gunzip/zcat runs. But as @jamesqf says, store the linecount in the filename, or in a file in the tgz, and extracting that file will be much faster. – ChuckCottrill May 8 '17 at 22:16
  • 2
    There are good theoretical reasons why you can't avoid this work. A compression format that lets you determine some useful property of the data "without decompressing it" is pretty much by definition not as good a compression format as it could be :) – hobbs May 8 '17 at 23:43
28

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.

  • 11
    It would be a non-trivial programming exercise, but doable. The whole point is to not rebuild zcat. A significant part of the work of zcat is generating the actual output. But if you're only counting \n characters, that is not necessary. gzip compression essentially works by replacing common long strings by shorter strings. So you only need to care about the long strings in the dictionary that contain a \n, and count the (weighted) occurrence of those. E.g. due to English rules, .\n is a common 16 bits string. – MSalters May 8 '17 at 14:31
19

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.

  • 4
    My pigz man page states that Decompression can't be parallelized, at least not without specially prepared deflate streams for that purpose. As a result, pigz uses a single thread (the main thread) for decompression, but will create three other threads for reading, writing, and check calculation, which can speed up decompression under some circumstances. Still, like you I find it's at least twice as faster than gzip, if not because of the parallelism – Stéphane Chazelas May 8 '17 at 13:05
  • @StéphaneChazelas Good point! That explains the mildly disappointing speedup for decompression. I edited my post to reflect this information better. – marcelm May 8 '17 at 13:23
5

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.

  • 1
    I think you're greatly overestimating the resources required to move the data between two processes, compared to the decompression calculations. Try benchmarking the various approaches ;) – marcelm May 8 '17 at 16:15
  • 2
    @SinanÜnür On my x86_64 Linux system (also old hardware) gzip | wc has the same speed than your perl script. And pigz | wcis double as fast. gzip runs with the same speed, regardless if I write the output to /dev/null or pipe into wc What I believe is that the "gzip library" used by perl is faster than the gzip command line tool. Maybe there is another Mac/Darwin specific problem with pipes. It's still amazing that this perl version is competitive at all. – rudimeier May 8 '17 at 18:02
  • 1
    On my x86_64 Linux install, it seems to do better than zcat and worse than unpigz. I am amazed at how much faster the pipeline is on the Linux system compared to the Mac. I was not expecting that, even though I should have as I once observed the same program ran faster on a CPU limited Linux VM on that same Mac than on bare metal. – Sinan Ünür May 8 '17 at 18:48
  • 1
    That's interesting; on my system (Debian 8.8 amd64, quad core i5), the perl script is slightly slower... 109M .gz file decompressing to 1.1G of text, consistently takes 5.4 secs for zcat | wc -l, and 5.5 secs for your perl script. Honestly, I'm amazed at the variation people are reporting here, especially between Linux and MacOS X! – marcelm May 9 '17 at 9:22
  • I don't know if I can generalize what I am seeing on my Mac, something odd is going on. With the decompressed 1.4 GB file, wc -l takes 2.5 seconds. gzcat compressed.gz > /dev/null takes 2.7 seconds. Yet, the pipeline takes 22 seconds. If I try GNU wc, it takes only half a second on the decompressed file, but 22 seconds in the pipeline. GNU zcat takes twice as long to execute zcat compressed.gz > /dev/null. This is on Mavericks, old Core 2 Duo CPU, 16 GB RAM, Crucial MX100 SSD. – Sinan Ünür May 9 '17 at 10:39
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).

  • 7
    A major problem with this idea is, the Huffman symbols used by DEFLATE correspond to bit sequences after LZ77 compression, so there may be no simple relationship between them and U+000A characters in the uncompressed file. For instance, maybe one Huffman symbol means the last five bits of "." followed by the first three bits of "\n", and another symbol means the last five bits of "\n" followed by all eight bits of "T". – zwol May 8 '17 at 14:01
  • @zwol No, the LZ77 portion of the Deflate algorithm compresses byte sequences, not bit sequences. en.wikipedia.org/wiki/DEFLATE#Duplicate_string_elimination – Ross Ridge May 8 '17 at 21:29
  • 1
    @RossRidge Huh, I didn't know that, but I don't think it invalidates what I said. The Huffman symbols can, it appears to me based on the next paragraph of that reference, each expand to a variable number of bits, they don't have to produce a whole number of bytes. – zwol May 8 '17 at 21:32
  • 1
    @zwol Sure, you have to search for matching Huffman code bit sequences in the bit stream but this answer doesn't suggest otherwise. The problem with this answer is that determining which Huffman codes ultimately generate or more newline characters isn't simple. The LZ77 codes that generate newlines are constantly changing as the sliding window moves, which means that the Huffman codes are changing as well. You'd have to implement the entire decompression algorithm except the output part, and maybe some part of the sliding window since you're only interested in the newlines. – Ross Ridge May 8 '17 at 22:01
1

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

  • 2
    Hi Yaron thanks for the answer even the zgrep is taking as much time as zcat i need find some other approach i think – Rahul May 8 '17 at 8:23
  • 8
    zgrep is generally a script that invokes zcat (same as gzip -dcq) to uncompress the data and feed it to grep, so is not going to help. – Stéphane Chazelas May 8 '17 at 13:00
  • 1
    @StéphaneChazelas - thanks for the comment, update my answer to reflect it. – Yaron May 8 '17 at 13:05
0

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).

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.