Skip to content

Optimize strstr (and memmem?) #272

@ncruces

Description

@ncruces

Although SQLite doesn't use them (some extensions do though), SIMD optimize musl strstr.

Probably the simplest option that'll be fast in most cases is combining this with Raita's algorithm for strings larger than 16 bytes.

We can have a 256 byte table, and store shifts between 16 and 271 for each character from the pattern (0 means shifting 16 bytes, 255 means shifting 271). We only use the table if the pattern is (e.g.) 24 bytes or longer.

Also use bcmp for the equality loop.
...

Metadata

Metadata

Assignees

Labels

enhancementNew feature or request

Projects

No projects

Milestone

No milestone

Relationships

None yet

Development

No branches or pull requests

Issue actions