kkawakam / rustyline

Readline Implementation in Rust
https://crates.io/crates/rustyline/
MIT License
1.55k stars 178 forks source link

Use lookup tables instead of linear search with `memchr` #625

Closed lopopolo closed 1 year ago

lopopolo commented 2 years ago

Several places use memchr with a byteset. This commit refactors these code paths to construct a lookup table from u8 -> bool, where an index is set to true if the byte is present in the given slice.

This change removes linear scans that occur in loops, which changes these functions runtime complexity from O(m * n) to O(m + n).

gwenn commented 2 years ago

I guess break_chars_byteset can be evaluated once / statically. Something like https://github.com/sqlite/sqlite/blob/master/src/tokenize.c#L61-L80 but for DEFAULT_BREAK_CHARS and DOUBLE_QUOTES_SPECIAL_CHARS.

lopopolo commented 2 years ago

@gwenn I think so too but I wasn't sure if that change would be accepted since these functions are public APIs that take the byteset as a slice.

I'm not sure how you'd like to make the API breaks.

Do you want to merge this as is or maybe push a PR to my fork?

gwenn commented 1 year ago

See #676

lopopolo commented 1 year ago

Thanks @gwenn!