I'm curious how you can speed up finding a single byte? Don't you have to touch all bytes at that point? Leaning heavily on simd instructions?

And I realize newlines is only to track line counts. Am I wrong that that slows things down?

> I'm curious how you can speed up finding a single byte? Don't you have to touch all bytes at that point? Leaning heavily on simd instructions?

Yes. That's what memchr does: https://github.com/BurntSushi/rust-memchr/blob/427fdc384007d...

> And I realize newlines is only to track line counts. Am I wrong that that slows things down?

It does, but only a little if it's implemented using vector instructions. You can try with ripgrep using -N/-n. GNU grep's line counting isn't vectorized IIRC, so you might notice bigger differences there.

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.

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

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

I believe GNU grep just uses memchr for this. But I might be mis-remembering.

For line counting specifically, memchr isn't used, but rather, bytecount is: 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/427fdc384007d...