5 ms·

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

> 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/427fdc384007d0a5b00b190e8313b3c8d3694a67/src/x86/sse2.rs#L18 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.

scottlamb 6y ago
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...

scottlamb 6y ago

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