head: head_lines(): memchr() instead of manual byte-by-byte work - #347

Benchmark environment:

• Gentoo Linux (Hardened), x86_64 bare metal, gcc 15.3.0, glibc 2.43
• head_lines_orig() from coreutils git 9e4b429 (2026-09-08)
• nftw() on the sourcecode of Linux 7.2.4 (1.6 GiB, 94756 files, no .git/) in ramdisk:
  • 92771 files with >=5 lines
  • 90269 files with >=10 lines
  • 54837 files with >=100 lines
  • 9569 files with >=1000 lines
  • 222 files with >=10000 lines
• command output >/dev/null
• average of 10 benchmark runs (runs 3-12, first 2 runs discarded), deviation negligible
• gcc -march=x86-64 -mtune=generic -O2 -D_FORTIFY_SOURCE=3 -std=gnu17 -D_GNU_SOURCE -DNDEBUG

Benchmark sourcecode:

#include <unistd.h>
#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <assert.h>
#include <string.h>
#include <fcntl.h>
#include <stdbool.h>
#include <time.h>
#include <ftw.h>

void xwrite_stdout(char const *buffer, size_t n_bytes)
{
  if (n_bytes > 0 && fwrite (buffer, 1, n_bytes, stdout) < n_bytes) abort();
}

bool head_lines(const char *const filename, const int fd, uintmax_t lines_to_write) {
    (void)filename;
    char buffer[BUFSIZ & 0xffff];
    const char *p, *end;
    int_fast32_t bytes_read;

    if (! lines_to_write) return true;

    while ((bytes_read = read(fd, buffer, sizeof(buffer)))) {
        if (bytes_read < 0) return false;
        end = buffer + bytes_read;

        for (p=memchr(buffer, '\n', bytes_read); p; p=memchr(p, '\n', end-p)) {
            ++p;
            if (! --lines_to_write) {
                //fprintf(stderr, "%d\n", (int)(-(end - p)));
                xwrite_stdout(buffer, p-buffer);
                return true;
            }
        }

        assert(lines_to_write);
        xwrite_stdout(buffer, bytes_read);
    }

    return true;
}

bool head_lines_orig(char const *filename, int fd, uintmax_t lines_to_write)
{
  (void)filename;
  char buffer[BUFSIZ];

  while (lines_to_write)
    {
      ssize_t bytes_read = read (fd, buffer, BUFSIZ);
      size_t bytes_to_write = 0;

      if (bytes_read < 0) return false;
      if (bytes_read == 0) break;
      while (bytes_to_write < (size_t)bytes_read)
        if (buffer[bytes_to_write++] == '\n' && --lines_to_write == 0) {
            //fprintf(stderr, "%d\n", (int)((ssize_t)bytes_to_write-bytes_read));
            break;
        }
      xwrite_stdout(buffer, bytes_to_write);
    }

  return true;
}

int cb(const char *path, const struct stat *meta, int flags, struct FTW *info) {
    (void)meta; (void)info;

    if (flags == FTW_NS) return 1;
    if (flags == FTW_F) {
        int fd = open(path, O_RDONLY);
        if (fd < 0) abort();
        head_lines(path, fd, 5);
        close(fd);
    }

    return 0;
}

int main() {
    struct timespec ts1, ts2;
    if (clock_gettime(CLOCK_MONOTONIC, &ts1)) abort();
    if (nftw("/tmp/linux-7.2.4", cb, 1024, FTW_PHYS)) abort();
    if (clock_gettime(CLOCK_MONOTONIC, &ts2)) abort();
    if (ts2.tv_nsec >= ts1.tv_nsec)
        fprintf(stderr, "%d s %ld ns\n", (int)(ts2.tv_sec-ts1.tv_sec), ts2.tv_nsec-ts1.tv_nsec);
    else fprintf(stderr, "%d s %ld ns\n", (int)(ts2.tv_sec-ts1.tv_sec-1), ts2.tv_nsec+(1000000000-ts1.tv_nsec));

    return 0;
}

I have read the Copyright assignment section in /HACKING and I've viewed https://www.gnu.org/software/gnulib/Copyright/request-assign.changes. I refuse to exchange physical mail. If that really is an issue, I should be able to split the PR into several smaller ones, each below the ~10-line threshold for a Copyright assignment.

Interesting. We'll have a look at this next week after the imminent release.
BTW there is hardware accelerated \n matching in wc
which I've wondered might be usable technique in head etc.

I have read the Copyright assignment section in /HACKING and I've viewed https://www.gnu.org/software/gnulib/Copyright/request-assign.changes. I refuse to exchange physical mail. If that really is an issue, I should be able to split the PR into several smaller ones, each below the ~10-line threshold for a Copyright assignment.

Splitting commits doesn't get around assignment,
but this may be small enough that it doesn't warrant assignment.

Note assignment can be done electronically.

BTW there is hardware accelerated \n matching in wc which I've wondered might be usable technique in head etc.

glibc carries ISA-optimized string functions itself. I imagine they are meticulously optimized. I wonder how wc would fare with memchr.

EDIT: Oh, wc does use rawmemchr(). Never mind.

@pixelb Regarding wc, @Larhzu sent me some generic code that LLVM and GCC vectorize well.

It sort of makes the inline assembly unnecessary as long as you compile with architecture-specific options, which distributions typically don't do. But it should be helpful for architectures without inline assembly implementations.

I can adjust it to fit in coreutils post-release for your reference.

BTW there is hardware accelerated \n matching in wc which I've wondered might be usable technique in head etc.

glibc carries ISA-optimized string functions itself. I imagine they are meticulously optimized. I wonder how wc would fare with memchr.

EDIT: Oh, wc does use rawmemchr(). Never mind.

glibc memchr is pretty well optimized, but it isn't ideal for wc because it makes a function call per newline. That can be very slow for a large file of only newline characters, for example.

To avoid that, GNU wc will only use rawmemchr if it has seen that the average line length is long (in relative terms). Basically, we assume that if the average line length is long, that will continue for the rest of the file. Not always true, of course, but probably more often than not.

The faster way to do it is just to count how many newlines are in the buffer, which is what the inline assembly versions do. Here was the generic, non-assembly version that @Larhzu wrote, which I mentioned earlier: linecount3.c. Assuming you compile with a recent GCC or Clang version and use the correct architecture options, it should perform as well as or better than the inline assembly versions.

It will need some experimenting to see if that can be applied to head, since we need to print the contents of each line instead of just counting. But Lasse and I figured it was worth sharing in case you (or others) want to experiment. No obligation of course, thanks for investigating this so far. :)

glibc memchr is pretty well optimized, but it isn't ideal for wc because it makes a function call per newline. That can be very slow for a large file of only newline characters, for example.

I remember seeing an algorithm resembling your linecount3.c in glibc's implementation. So the function calling itself makes it that much slower? Interesting, I wouldn't expect that. When I started writing the patch, I assumed gcc had a builtin for memchr(). Guess not.

To avoid that, GNU wc will only use rawmemchr if it has seen that the average line length is long (in relative terms). Basically, we assume that if the average line length is long, that will continue for the rest of the file. Not always true, of course, but probably more often than not.

It's to avoid checking individual bytes in a loop, not memchr(). But it's probably still beneficial to choose rawmemchr() over of memchr(). I'm not going to delve into the implementations in glibc, but I clearly remember rawmemchr() advertised as the faster alternative to memchr() (probably because it doesn't have to keep track of its position in the buffer). It might make head_lines() faster. I'll try and find the time to test that. I'm used to writing portable, so I didn't think of it.

The faster way to do it is just to count how many newlines are in the buffer, which is what the inline assembly versions do. Here was the generic, non-assembly version that @Larhzu wrote, which I mentioned earlier: linecount3.c. Assuming you compile with a recent GCC or Clang version and use the correct architecture options, it should perform as well as or better than the inline assembly versions.

It is fast (also Zen 5), just a smidge slower than the AVX512 version of wc.

It will need some experimenting to see if that can be applied to head, since we need to print the contents of each line instead of just counting. But Lasse and I figured it was worth sharing in case you (or others) want to experiment. No obligation of course, thanks for investigating this so far. :)

That's not an obstacle: head_lines() reads up, scans through the whole buffer counting EOLs, then outputs. It seldom has to read much data, though. Still, I see no reason why an ISA-optimized search wouldn't be faster.

EDIT: Ah, now I see it, the ISA-optimized routine is a separated function with reading, there's no inlining.

I remember seeing an algorithm resembling your linecount3.c in glibc's implementation.

The basic idea is ancient, so I assume there are many implementations with the same idea. For me the main news was how amazingly compilers vectorize such code nowadays. :-)

With rawmemchr, one is counting the newlines one by one. For each newline, there is a conditional branch from which rawmemchr returns. Parallel counting and avoiding mispredicted branches can help.

For testing, I commented out AVX-512 and AVX2 from wc_lines in src/wc.c in coreutils 9.11 to have a version of wc -l that always uses the generic code.

I also ran wc -l with the environment varibable GLIBC_TUNABLES=glibc.cpu.hwcaps=-AVX512F,-AVX2 which disables those instructions in glibc. This makes rawmemchr slower (glibc uses SSE2 version).

I built linecount3.c three times:

# Zen 5, GCC emits AVX-512 instructions
gcc -march=znver5 -O2 -D_FORTIFY_SOURCE=3 linecount3.c

# x86-64 baseline only, including SSE2
gcc -march=x86-64 -O2 -D_FORTIFY_SOURCE=3 linecount3.c

# x86-64 without any SIMD
gcc -march=x86-64 -mno-sse -O2 -D_FORTIFY_SOURCE=3 linecount3.c

The test input was all files from a Linux source tree duplicated five times: 8203 million bytes, 219 million newlines (2.7 %). The branch_miss_rate column is from perf stat.

The performance of the second and third wc -l commands depend on the input data. The other versions don't. I created another test file with head -c 10000000000 /dev/zero. It should be ideal input for the generic code:

Every rawmemchr call will scan the whole input buffer, and the processor has easy time predicting the branches. linecount3.c updates the count of newlines, which adds overhead compared to long-running rawmemchr calls.

So the function calling itself makes it that much slower?

With short lines, the function call and the startup overhead of rawmemchr is significant.

I further modified wc.c so that it always calls rawmemchr by replacing if (! long_lines) with if (false). Testing it with a file from yes | head -n 5000000000 shows that it's terribly slow, around 15 seconds while the generic wc -l takes two seconds.

I tested this file with your benchmark too. As expected from the previous paragraph, head_lines_orig is much faster: 0.07 s vs. 0.51 s when outputting the first hundred million lines from one file. That is, currently this PR would make head dramatically slower when the file contains extremely short lines.

I haven't thought much what head should do. Perhaps it could use a fast counting method until it's close to (or even past) the requested number of lines, then use another method to find the exact byte where to stop. On the other hand, I don't know if it is worth the extra complexity. For me, the speed of head hasn't been a problem, so simpler code with predictable performance sounds good enough. I'm not a coreutils developer, so don't give my opinion too much value.

Turns out that memchr() and rawmemchr() are equally fast. Sometimes one was faster in the original benchmark, sometimes the other, always by < 3 ms. The rawmemchr() variant was:

bool head_lines_rawmemchr(const char filename[const static 1], const int fd, uintmax_t lines_to_write) {
    (void)filename;
    assert(fd >= 0);
    char buffer[(BUFSIZ&0xffff)+1], *end;
    const char *p;
    int_fast32_t bytes_read;

    if (! lines_to_write) return true;

    while ((bytes_read = read(fd, buffer, sizeof(buffer)-1))) {
        if (bytes_read < 0) return false;
        end = buffer + bytes_read;
        *end = '\n';

        p = rawmemchr(buffer, '\n');
        while (p != end) {
            ++p;
            if (! --lines_to_write) {
                //fprintf(stderr, "%d\n", (int)(-(end - p)));
                xwrite_stdout(buffer, p-buffer);
                return true;
            }
            p = rawmemchr(p, '\n');
        }

        assert(lines_to_write);
        xwrite_stdout(buffer, bytes_read);
    }

    return true;
}

I used the line length guessing method from wc.c and benchmarked this (the same setup):

bool head_lines_memchr_mixed(const char filename[const static 1], const int fd, uintmax_t lines_to_write) {
    (void)filename;
    assert(fd >= 0);
    char buffer[BUFSIZ & 0xffff];
    const char *p, *end;
    int_fast32_t bytes_read;
    uintmax_t lines_to_write_last;
    #define long_line_threshold 4
    // 36 = avg line length in the distribution of linux-7.2.4
    bool long_lines = 36 >= long_line_threshold;

    if (! lines_to_write) return true;

    while ((bytes_read = read(fd, buffer, sizeof(buffer)))) {
        if (bytes_read < 0) return false;
        p = buffer;
        end = buffer + bytes_read;
        lines_to_write_last = lines_to_write;

        if (long_lines) {
            while ((p = memchr(p, '\n', end-p))) {
                ++p;
                if (! --lines_to_write) break;
            }
        }
        else while ((*p++ != '\n' || --lines_to_write) && p < end) ;

        if (! lines_to_write) {
            //fprintf(stderr, "%d\n", (int)(-(end - p)));
            assert(p);
            xwrite_stdout(buffer, p-buffer);
            return true;
        }
        xwrite_stdout(buffer, bytes_read);
        long_lines = bytes_read/(uintmax_t)long_line_threshold >= lines_to_write_last-lines_to_write;
        if (long_lines) ++nr_ll; else ++nr_sl;
    }

    return true;
}

As compared with head_lines() ("equal" = difference < 10 ms):

• long_line_threshold = 4
  • 10 lines: equal, nr_ll=4537, nr_sl=0
  • 500 lines: equal, nr_ll=111675, nr_sl=11
  • 1000 lines: equal, nr_ll=148912, nr_sl=16
  • 10000 lines: equal, nr_ll=213846, nr_sl=21
• long_line_threshold = 10
  • 500 lines: equal, nr_ll=111568, nr_sl=118
  • 1000 lines: equal, nr_ll=148781, nr_sl=147
  • 10000 lines: equal, nr_ll=213693, nr_sl=174
• long_line_threshold = 20
  • 500 lines: equal, nr_ll=102410, nr_sl=9276
  • 1000 lines: equal, nr_ll=138567, nr_sl=10361
  • 10000 lines: equal, nr_ll=202381, nr_sl=11486
• long_line_threshold = 36
  • 10 lines: equal, nr_ll=1169, nr_sl=3368
  • 500 lines: mixed() is 7% slower, nr_ll=20451, nr_sl=91235
  • 1000 lines: mixed() is 12% slower, nr_ll=27277, nr_sl=121651
  • 10000 lines: mixed() is 20% slower, nr_ll=52725, nr_sl=161142

Instead of the kernel sources, a single file with 300000000 lines, each 10 chars long:

• long_line_threshold = 20
  • 300000000 lines: mixed() is 27% faster, nr_ll=0, nr_sl=402832

A single file with 300000000 lines, each 15 chars long:

• long_line_threshold = 1
  • 300000000 lines: equal, nr_ll=585937, nr_sl=0
• long_line_threshold = 100
  • 300000000 lines: equal, nr_ll=0, nr_sl=585937

A single file with 300000000 lines, each 20 chars long:

• long_line_threshold = 100
  • 300000000 lines: mixed() is 147% slower, nr_ll=0, nr_sl=769042

Conclusion: wc.c's got it about right, except the initial guess should be long_lines = true. I'll push soon.

By the way, this goes against my findings.

For testing, I commented out AVX-512 and AVX2 from wc_lines in src/wc.c in coreutils 9.11 to have a version of wc -l that always uses the generic code.

I also ran wc -l with the environment varibable GLIBC_TUNABLES=glibc.cpu.hwcaps=-AVX512F,-AVX2 which disables those instructions in glibc. This makes rawmemchr slower (glibc uses SSE2 version).

The test input was all files from a Linux source tree duplicated five times: 8203 million bytes, 219 million newlines (2.7 %). The branch_miss_rate column is from perf stat.

Command Time branch_miss_rate
wc -l (AVX-512) 0.37 s 0.1 %
wc -l (generic) 1.6 s 7.0 %

I built coreutils with no custom CFLAGS, just ./configure && make. Once with wc_avx512.c enabled, then with all wc_*.c disabled. No manipulation with tunables. Zen 5, Linux sources (1.5 GiB, 41 mil. lines), avg of 78 runs. That should correspond to the first two lines in your table. I got 313 ms for AVX512, 487 ms for generic. With long_lines = false as default.

FYTI note coreutils honors GLIBC_TUNABLES

By the way, this goes against my findings.
[...]
I got 313 ms for AVX512, 487 ms for generic.

I used a single big file to test because then the file I/O overhead is much smaller. If I use a command like the following, then I get results that are comparable to yours.

time find -name .git -prune -o -type f -exec cat '{}' + | wc -l

# Test the overhead:
time find -name .git -prune -o -type f -exec cat '{}' + > /dev/null

With one big file, the syscall overhead is still significant. For me, cat takes 70 % less time than wc -c:

time cat big.txt | cat > /dev/null
time cat big.txt | wc -c > /dev/null

It's because cat uses splice while wc -c uses read with a 256 KiB buffer. The seemingly useless cat above is to prevent wc -c from using stat to determine the file size. (I sometimes use wc -c with large inputs from a pipe.)

The AVX-512 version of wc -l is barely slower than wc -c. That's because AVX-512 line counting is very fast. 80-90 % of wc -l time is spent in syscalls.

I created a version based on linecount3.c that counts newlines 128 bytes at a time, and once enough newlines have been found, it does the final search with a byte-by-byte method:

bool head_lines_masking128(
        const char filename[const static 1], const int fd,
        uintmax_t lines_to_write) {
    union {
        uint8_t u8[BUFSIZ & ~7U];
        uint64_t u64[(BUFSIZ & ~7U) / 8];
    } buf;

    (void)filename;
    assert(fd >= 0);

    if (lines_to_write == 0)
        return true;

    while (true) {
        const ssize_t read_size = read(fd, buf.u8, sizeof(buf));
        if (read_size == 0)
            return false;

        const size_t buf_size = read_size;

        const size_t CHUNK_SIZE = 128;
        const size_t limit = buf_size & ~(CHUNK_SIZE - 1);
        const size_t limit8 = limit / 8;

        for (size_t i = 0; i < limit8; i += CHUNK_SIZE / 8) {
            const uint64_t NEWLINES8 = 0x0A0A0A0A0A0A0A0A;
            const uint64_t HIGH_MASK = 0x8080808080808080;
            const uint64_t LOW_MASK  = 0x0101010101010101;

            size_t count0 = 0;
            size_t count1 = 0;

            for (size_t k = 0; k < CHUNK_SIZE / 8; k += 2) {
                uint64_t a = buf.u64[i + k] ^ NEWLINES8;
                uint64_t b = buf.u64[i + k + 1] ^ NEWLINES8;

                count0 += ((((a | HIGH_MASK) - LOW_MASK) | a) & HIGH_MASK) >> 7;
                count1 += ((((b | HIGH_MASK) - LOW_MASK) | b) & HIGH_MASK) >> 7;
            }

            count0 += count1;
            count0 = CHUNK_SIZE - ((count0 * LOW_MASK) >> 56);

            if (count0 >= lines_to_write) {
                i *= 8;

                do {
                    lines_to_write -= buf.u8[i++] == 0x0A;
                } while (lines_to_write > 0);

                xwrite_stdout((const char *)buf.u8, i);
                return true;
            }

            lines_to_write -= count0;
        }

        for (size_t i = limit; i < buf_size; ) {
            lines_to_write -= buf.u8[i++] == 0x0A;
            if (lines_to_write == 0) {
                xwrite_stdout((const char *)buf.u8, i);
                return true;
            }
        }

        xwrite_stdout((const char *)buf.u8, buf_size);
    }

    return true;
}

With -march=x86-64 -O2, Linux source tree:

Single file tests:

• Linux source files concatenated
• head -c 5000000000 /dev/zero
• head -c 5000000000 /dev/zero | tr '\0' '\n'
• yes "$(printf '%90s' x)" | head -n 70000000

Printing the first 100,000,000 lines (or the whole file):

With long lines, memchr_mixed is the fastest. Allowing AVX2 (but not AVX-512) with -march=x86-64-v3 makes masking128 do better, but with long enough lines it would still lose to memchr_mixed (not shown in the table).

With typical line lengths, masking128 seems the best on x86-64. It likely won't do so well on 32-bit processors, at least in its current form. Other 64-bit archs I didn't test. Without such testing, memchr_mixed might be a less risky choice. I don't have a clear opinion now, but hopefully others can figure out something from these results.

FYTI note coreutils honors GLIBC_TUNABLES

Thanks! It wasn't enough in this case though. I wanted to check the speed of generic wc -l code with the fastest available rawmemchr version from glibc. This was only possible by modifying wc.c.

This likely isn't important, but I was curious about the worst case performance of the generic version currently in src/wc.c.

I tested with 4 GiB inputs. The first file makes the heuristics in the generic code always pick the wrong method for the next block:

for I in $(seq 8192)
do
    head -c 262144 /dev/zero
    head -c 262144 /dev/zero | tr '\0' '\n'
done > testfile

Note that SSE2 rawmemchr (hwcaps disabled) was faster in the worst case test.

It's an extreme test case, and I'm not suggesting any code changes due to this result.