4 ms·

On a typical input, where there's probably a newline every 30–80 characters on average [1], it seems like many of the bytes are not in that algorithm's happy 64

On a typical input, where there's probably a newline every 30–80 characters on average [1], it seems like many of the bytes are not in that algorithm's happy 64-bytes-at-a-time 16-bytes-aligned main loop because each line would be a separate memchr call which has to redo the unaligned prefix bit, and/or are processed twice because they're in the 64 bytes but after the first newline. Have you ever considered an alternate interface which returns all the newline positions in a single call on a whole buffer? [edit: or next N with N>1.] Is it worth pursuing? [1] bytes/lines on "wc -l *.[ch]" in the ffmpeg/libavformat directory I happened to have open says there's a newline every ~34 bytes. edit: I suppose if ripgrep -N and ripgrep -n aren't that far apart, it's fast enough already. But I have to think it's not getting much mileage out of that 64-bytes-at-a-time loop.

a1369209993 6y ago
> each line would be a separate memchr call which has to redo the unaligned prefix bit I'm not sure what GNU grep/wc does, but assuming you're getting line numbers for relatively rare matches, you probably shouldn't use memchr. Instead, load chunks of bytes into a SIMD/vector register, compare each one for equality to 0A, take the popcnt, and add it to a line number counter. You don't actually care where (most of) the newlines are located, just how many of them there are.
- burntsushi 6y ago
  Yes, that's what ripgrep does, or similarish. In my initial implementation, I did what you suggested on a standard u64. But bytecount adds SIMD to it (which I did not write): https://docs.rs/bytecount https://docs.rs/bytecount I believe GNU grep just uses memchr for this. But I might be mis-remembering.
burntsushi 6y ago
For line counting specifically, memchr isn't used, but rather, bytecount is: https://docs.rs/bytecount/0.6.2/bytecount/ https://docs.rs/bytecount/0.6.2/bytecount/ However, memchr is still used for finding the bounds of a line when a match occurs. memchr still does pretty well on shorter haystacks too. The main loop is indeed quite large, but before that, it does unaligned loads of 32 bytes: https://github.com/BurntSushi/rust-memchr/blob/427fdc384007d0a5b00b190e8313b3c8d3694a67/src/x86/avx.rs#L481 https://github.com/BurntSushi/rust-memchr/blob/427fdc384007d...

a1369209993 6y ago

> each line would be a separate memchr call which has to redo the unaligned prefix bit I'm not sure what GNU grep/wc does, but assuming you're getting line numbers for relatively rare matches, you probably shouldn't use memchr. Instead, load chunks of bytes into a SIMD/vector register, compare each one for equality to 0A, take the popcnt, and add it to a line number counter. You don't actually care where (most of) the newlines are located, just how many of them there are.

burntsushi 6y ago
Yes, that's what ripgrep does, or similarish. In my initial implementation, I did what you suggested on a standard u64. But bytecount adds SIMD to it (which I did not write): https://docs.rs/bytecount https://docs.rs/bytecount I believe GNU grep just uses memchr for this. But I might be mis-remembering.

burntsushi 6y ago

For line counting specifically, memchr isn't used, but rather, bytecount is: https://docs.rs/bytecount/0.6.2/bytecount/ https://docs.rs/bytecount/0.6.2/bytecount/ However, memchr is still used for finding the bounds of a line when a match occurs. memchr still does pretty well on shorter haystacks too. The main loop is indeed quite large, but before that, it does unaligned loads of 32 bytes: https://github.com/BurntSushi/rust-memchr/blob/427fdc384007d0a5b00b190e8313b3c8d3694a67/src/x86/avx.rs#L481 https://github.com/BurntSushi/rust-memchr/blob/427fdc384007d...