7

I had to replace all the null bytes in a file with another character (I arbitrarily chose @), and was pretty surprised that tr '\00' '@' was about 1/4 the speed of gzip:

$ pv < lawl | gzip > /dev/null
^C13MiB 0:00:04 [28.5MiB/s] [====>                             ] 17% ETA 0:00:18
$ pv < lawl | tr '\00' '@' > /dev/null
^C58MiB 0:00:08 [7.28MiB/s] [==>                               ]  9% ETA 0:01:20

My real data file is 3GB gzipped and took 50 minutes to tr, and I'll actually need to do this on many such files, so it's not a completely academic problem. Note that reading from disk (a reasonably fast SSD here), or pv, isn't the bottleneck in either case; both gzip and tr are using 100% CPU, and cat is much faster:

$ pv < lawl | cat > /dev/null
 642MiB 0:00:00 [1.01GiB/s] [================================>] 100%

This code:

#include <stdio.h>

int main() {
    int ch;
    while ((ch = getchar()) != EOF) {
        if (ch == '\00') {
            putchar('@');
        } else {
            putchar(ch);
        }
    }
}

compiled with clang -O3 is somewhat faster:

$ pv < lawl | ./stupidtr > /dev/null
^C52MiB 0:00:06 [ 8.5MiB/s] [=>                                ]  8% ETA 0:01:0

Compiling with gcc -O4 -mtune=native -march=native (4.8.4) is comparable, maybe very slightly faster. Adding -march=native to clang (Apple LLVM version 6.1.0 (clang-602.0.53) (based on LLVM 3.6.0svn)) produces an identical binary.

This is presumably just because the generic processing code for replacements in tr is replaced with constants and the checks can be compiled down. The LLVM IR (clang -S -O3 stupidtr.c) looks pretty good.

I guess gzip must be faster because it's doing something SIMD instructions or something. Is it possible to get this up to gzip speeds?

Some specifications, if they're relevant:

  • The file is a CSV; the null byte can only occur in a certain field, but some of the other fields are variable-length, so you can't just seek around arbitrarily. Most lines have a null byte in that field. I suppose this means you could do a Boyer-Moore search for ,\00,, if that'd help. Once you've found a null byte, it's also guaranteed that there can't be another one for a hundred bytes or so.

  • A typical file is about 20 GiB uncompressed, but are bz2 compressed on disk, if that's relevant.

  • You can parallelize if you want, though gzip does this with one so it shouldn't be necessary. I'll be running this either on a quad-core i7 running OSX or a two-vCPU cloud server running Linux.

  • Both machines I might run on have 16GB of RAM.

8
  • You forgot to finish the sentence Is it possible to get just before the specs at the end.
    – xxbbcc
    Jun 10, 2015 at 20:45
  • @xxbbcc Thanks, fixed. Nonlinear writing is hard. :)
    – Danica
    Jun 10, 2015 at 20:46
  • dd if=/dev/zero bs=1M count=20000 | pv | tr '\00' '@' > /dev/null (similar to your second case) proceeds at 322MB/s on my not-that-fancy notebook, fwiw. Jun 10, 2015 at 21:07
  • 1
    @StefanoSanfilippo I get 7 MiB/s (changing to bs=1048576 since OSX's dd doesn't support the 1M syntax). Presumably a buffering difference in the OSes...
    – Danica
    Jun 10, 2015 at 21:12
  • 2
    char ch cannot correctly hold the value EOF: If char is unsigned by default, your code will never stop, otherwise if will mistakenly stop on '\377' also.
    – chqrlie
    Jun 10, 2015 at 21:20

4 Answers 4

4

Combining ideas from the various answers with some extra bithacks, here is an optimized version:

#include <errno.h>
#include <stdint.h>
#include <stdio.h>
#include <string.h>
#include <unistd.h>

#define BUFFER_SIZE  16384
#define REPLACE_CHAR  '@'

int main(void) {
    /* define buffer as uint64_t to force alignment */
    /* make it one slot longer to allow for loop guard */
    uint64_t buffer[BUFFER_SIZE/8 + 1];
    ssize_t size, chunk;
    uint64_t *p, *p_end;
    uint64_t rep8 = (uint8_t)REPLACE_CHAR * 0x0101010101010101ULL;

    while ((size = read(0, buffer, BUFFER_SIZE)) != 0) {
        if (size < 0) {
            if (errno == EINTR) continue;
            fprintf(stderr, "read error: %s\n", strerror(errno));
            return 1;
        }
        p = buffer;
        p_end = p + ((size + 7) >> 3);
        *p_end = 0ULL; /* force a 0 at the end */
        for (;; p++) {
#define LOWBITS   0x0101010101010101ULL
#define HIGHBITS  0x8080808080808080ULL
            uint64_t m = ((*p - LOWBITS) & ~*p & HIGHBITS);
            if (m != 0) {
                if (p >= p_end) break;
                m |= m >> 1;
                m |= m >> 2;
                m |= m >> 4;
                *p |= m & rep8;
            }
        }
        for (unsigned char *pc = (unsigned char *)buffer;
             (chunk = write(1, pc, (size_t)size)) != size;
             pc += chunk, size -= chunk) {
            if (chunk < 0) {
                if (errno == EINTR) continue;
                fprintf(stderr, "write error: %s\n", strerror(errno));
                return 2;
            }
        }
    }
    return 0;
}
8
  • ~900 MiB/s with clang -O3. We've now moved well past the stage where this is the bottleneck. :)
    – Danica
    Jun 10, 2015 at 22:28
  • 1
    @Dougal: 8.5 to 900, that's the kind of multiple I live for ;-)
    – chqrlie
    Jun 10, 2015 at 22:31
  • 1
    Hey! No using sizeof without parentheses! Where I come from, you get shot for doing that :p
    – durka42
    Jun 10, 2015 at 22:37
  • @durka42: I usually recommend always using () even if they are redundant, but I don't shoot programmers for that. For clarity, I should probably not use sizeof here at all.
    – chqrlie
    Jun 10, 2015 at 22:39
  • 1
    @chqrlie: The problem with sizeof x + 1 is that people may not remember that sizeof has higher precedence than +. The problem with sizeof (x)+1 is... guess what... people may not remember that sizeof has higher precedence than +. Only in (sizeof x) + 1 do the parentheses make the parse clear. It's not a matter of removing redundant parentheses, it's a matter of putting them where they do some good.
    – Ben Voigt
    Jun 11, 2015 at 0:16
4

You need to use block reads and writes for speed. (Even with a buffered I/O library like stdio.h, the cost of managing the buffer can be significant.) Something like:

#include <unistd.h>
int main( void )
{
    char buffer[16384];
    int size, i;
    while ((size = read(0, buffer, sizeof buffer)) > 0) {
        for( i = 0; i < size; ++i ) {
            if (buffer[i] == '\0') {
                buffer[i] = '@';
                // optionally, i += 64; since
                // "Once you've found a null byte, it's also guaranteed that there can't
                // be another one for a hundred bytes or so"
            }
        }
        write(1, buffer, size);
    }
}

Naturally, compile with optimizations so that the compiler can transform indexing into pointer arithmetic if helpful.

This version also lends itself well to SIMD optimizations if you still aren't meeting your speed targets (or a smart enough compiler may vectorize the for loop automatically).

Furthermore, this code lacks robust error handling. As @chqrlie mentions in a comment, you should retry when you get -EINTR, and you should handle partial writes.

8
  • 689MiB/s! Really didn't expect stdio's buffering to have so much overhead. Thanks. :)
    – Danica
    Jun 10, 2015 at 21:05
  • This approach is tricky: read can return -1 if it was interrupted by a signal and it should be restarted. write(1, buffer, size); may return a smaller count for various reasons, and -1 for the same reason as read, it should then be restarted. Failing to handle this corner cases will produce hard to find bugs in production, usually at the worst moment... Using the stdio.h functions is much safer and not much slower: use fread and fwrite.
    – chqrlie
    Jun 10, 2015 at 21:06
  • @chqrlie: Already fixed. And I believe that fwrite suffers from the same problems as write. I'll add a note to that effect.
    – Ben Voigt
    Jun 10, 2015 at 21:08
  • 3
    You can combine the 2 tests in the loop by making the buffer one byte larger and setting a '\0' at the end. You then only need to test the position on matches, effectively dividing the number of tests by 2.
    – chqrlie
    Jun 10, 2015 at 21:25
  • 1
    @Andrew Henle: true but give the buffer size, int is large enough.
    – chqrlie
    Jun 10, 2015 at 22:28
3

Your code is incorrect because you do not test for end of file at the right spot. It is a very common mistake in do {} while loops. I recommend to avoid this construct completely (except in macros to convert sequences of statements into a single statement).

Also try and tell the glibc to perform fewer checks on the stream:

#include <stdio.h>

int main() {
    int c;
    while ((c = getchar_unlocked()) != EOF) {
        if (c == '\0')
            c = '@':
        putchar_unlocked(c);
    }
}

You can also play with different buffer sizes, for example try these before the while() loop:

setvbuf(stdin, NULL, _IOFBF, 1024 * 1024);
setvbuf(stdout, NULL, _IOFBF, 1024 * 1024);

It should not have much impact if you use the utility as a filter with pipes, but it may be more efficient if you use files.

If you use files, you can also mmap the file and use memchr to find the '\0' bytes, or even strchr that might be faster and you can ensure there is a `'\0`` at the end of the file (putting it there is a good way).

5
  • Oh, good catch with the check; shouldn't really be relevant to the processing speed, though.
    – Danica
    Jun 10, 2015 at 20:56
  • 2
    Using the _unlocked functions doubles the speed, up to 16.5ish MiB/sec. Halfway there! :)
    – Danica
    Jun 10, 2015 at 20:58
  • @Dougal: Try increasing the buffer size
    – chqrlie
    Jun 10, 2015 at 20:59
  • 1024*1024 didn't help; 10 times that slowed it down slightly.
    – Danica
    Jun 10, 2015 at 21:00
  • As noted in the question, I can't really use a raw file because the input is gzipped, and going to disk first would probably defeat the point.
    – Danica
    Jun 10, 2015 at 21:03
0

First, as others have noted, don't use getchar()/putchar(), or even any of the FILE-based methods such as fopen()/fread()/fwrite(). Use open()/read()/write() instead.

If the file is already uncompressed on disk, do not use pipes. If it is compressed, then you DO want to use a pipe in order remove an entire read/write cycle. If you uncompress from disk back to disk, then replace the NUL characters, the data path is disk->memory/cpu->disk->memory/cpu->disk. If you use a pipe, the path is disk->memory/cpu->disk. If you're disk-limited, that extra read/write cycle will just about double the time it takes to process your gigabytes (or more) of data.

One more thing - given your IO pattern and the amount of data your moving - read an entire multi-GB file, write the entire file - the page cache is only getting in your way. Use direct IO, thusly in C on Linux (headers and robust error checking left off for clarity):

#define CHUNK_SIZE ( 1024UL * 1024UL * 4UL )
#define NEW_CHAR '@'
int main( int argc, char **argv )
{
    /* page-aligned buffer */
    char *buf = valloc( CHUNK_SIZE );
    /* just set "in = 0" to read a stdin pipe */
    int in = open( argv[ 1 ], O_RDONLY | O_DIRECT );
    int out = open( argv[ 2 ], O_WRONLY | O_CREAT | O_TRUNC | O_DIRECT, 0644 );

    for ( ;; )
    {
        ssize_t bytes = read( in, buf, CHUNK_SIZE );
        if ( bytes < 0 )
        {
            if ( errno == EINTR )
            {
                continue;
            }
            break;
        }
        else if ( bytes == 0 )
        {
            break;
        }

        for ( int ii = 0; ii < bytes; ii++ )
        {
            if ( !buf[ ii ] )
            {
                buf[ ii ] = NEW_CHAR;
            }
        }
        write( out, buf, bytes );
    }

    close( in );
    close( out );

    return( 0 );
}

Crank up the compiler optimization as high as it goes. To use this code on real data, you do need to check the results of the write() call - direct IO on Linux is a real finicky beast. I've had to close a file opened with O_DIRECT and reopen a it without direct IO set in order to write the last bytes of a file on Linux when the last bits weren't a multiple of a full page.

If you want to go even faster, you can multithread the process - one thread reads, one thread translates chars, and another thread writes. Use as many buffers, passing them from thread to thread, as necessary to keep the slowest part of the process busy at all times.

If you're really interested in seeing how fast you can move data, multithread the reads/writes, too. And if your filesystem support it, use asynchronous read/write.

11
  • That's a lot of suggestions, but it does not well serve the OPs problem: He uses pipes, so the API is inappropriate and the huge buffer is useless. Error handling is absent (good for clarity, but bad for results), especially trying to write -1 bytes is calling for trouble. Multithreading read, translate and write phases or using asynchronous I/O is not for the faint of heart, it goes well beyond reasonable effort to reduce the bottleneck.
    – chqrlie
    Jun 10, 2015 at 22:38
  • Yet another good illustration of how do {} while loops are mostly broken.
    – chqrlie
    Jun 10, 2015 at 22:46
  • And your experience moving petabytes of data or doing IO on high-performance storage is? Well, it's obviously zero else you would never even think of calling 4 MB "huge" or "useless". Do you really think multithreading and async IO are really "not for the faint of heart"? I guess we just work and code in different worlds. Jun 10, 2015 at 22:57
  • I am stating facts, 4MB is vastly larger than the pipe buffer, it does not help at all, the OP verified it. mmap would be a good way to get closer to the metal, but it is a little tricky for huge files. using a different thread for reading, translating and writing in this particular case is hardly useful and not so trivial. You seem to master the art, give it a try and see what multiple you get. You retaliating on the accepted answer shows little respect for actual results.
    – chqrlie
    Jun 10, 2015 at 23:04
  • The fact that 4MB is vastly larger than the pipe buffer isn't going to hurt performance on read(). And when accessing a fast disk system - which the OPs SSD could very well be - the larger buffer will improve performance. Try it - get a disk system that can sustain reads and writes at a GB/sec or more. The OP's "verification" consisted of changing the buffer used for fopen()/fread()/fwrite(). That does not apply to any performance differences that may arise in read()/write() calls doing direct IO when using a different-sized buffer. ii being a size_t only matters with a >2GB buffer. Jun 10, 2015 at 23:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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