search

shepmaster / jetscii

A tiny library to efficiently search strings for sets of ASCII characters and byte slices for sets of bytes.
Apache License 2.0
113 stars 21 forks source link

Consider a hybrid SIMD+table lookup #22

Open brson opened 6 years ago

brson commented 6 years ago

I'm sorry this is such a half-baked idea, but in comrak there is a search of many sigils that seems perfect for jetscii; and in a comrak-downstream project I'm working on (that isn't presently open) I have an even more perfect case for jetscii.

In both cases though we've found that in practice jetscii does not beat a fairly naive table lookup - that is, a 256-byte array containing bools for the bytes being searched, coupled with a loop over the search bytes. (You can see this in the comrak link, though the logic is a bit obscured by other domain-specific stuff).

This was a surprise in both cases, and I really wanted jetscii to win this contest.

I have some idea that the problem may be in the SIMD setup overhead compared to the length of the input buffers, as both of our cases are often searching rather small buffers (I don't have a firm number, but a few bytes to a few hundred).

On that assumption I have it in the back of my mind to write a hybrid table+jetscii search that knows how long a buffer must be to make the jetscii machine code "prologue" worth the expense.

Ah, sorry for the rambling - I was just commenting on another jetscii bug and it reminded me of this idea.

Love your work @shepmaster <3 <3 cc @kivikakk

Ygg01 commented 2 years ago

Hi. Just wondering. Shouldn't that be a 256 bit table?

So like two u128 or [u8; 32]?

Most XML parsers make it so different bit of 256 byte array are for different applications.

Otherwise sounds exciting.