Skip to content

Consider a hybrid SIMD+table lookup #22

Open
@brson

Description

@brson

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

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions