Prior to this change table search would have to do a binary search over about 1000 entries which resulted in around 10 memory loads on average. In this commit we reduce the search space by doing a pre-lookup in a generated table to get a smaller (often zero-length) slice of the full sorted range list. On average this gives us just one entry of the range list to perform binary search on, which reduces the average number of memory loads to 2.

Copy link

ContributorAuthor

indutny commentedJan 28, 2023•
edited
Loading

With the help of#113 this gives:

Between 0% and 15% improvement on grapheme benchmark (depending on language)
Between 22% and 40% improvement on word benchmarks (depending on language)

Full Report:https://gist.github.com/indutny/9f5f623c52d6e935225edfe09857ef99

Copy link

ContributorAuthor

indutny commentedJan 30, 2023

Rebased over the latest master, but it looks like nothing changed in this PR.

indutny force-pushed thefeature/lookup-and-search branch from0b2442c toa2f1b04Compare

January 30, 2023 17:45

Manishearth reviewed

Jan 30, 2023

View reviewed changes

src/tables.rs Outdated

		@@ -387,9 +387,81 @@ pub mod grapheme {
		}

		pub fn grapheme_category(c: char) -> (u32, u32, GraphemeCat) {
		bsearch_range_value_table(c, grapheme_cat_table)
		let idx = c as usize / 0x80;

Copy link

Member

ManishearthJan 30, 2023

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others.Learn more.

please add/generate comments into the code that explains what's going on here

also on the const

Copy link

ContributorAuthor

indutnyJan 30, 2023

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others.Learn more.

Sounds good! Force pushed with comments!

indutny force-pushed thefeature/lookup-and-search branch 4 times, most recently fromf52636c tobb6b82aCompare

January 30, 2023 22:04

Copy link

indutny-signal commentedJan 30, 2023

Let me run benchmarks on this first, it looks like I might have regressed with my latest refactor.

Improve table search speed through lookups

b4c9ce1

Prior to this change table search would have to do a binary search overabout 1000 entries which resulted in around 10 memory loads on average.In this commit we reduce the search space by doing a pre-lookup in agenerated table to get a smaller (often zero-length) slice of the fullsorted range list. On average this gives us just one entry of the rangelist to perform binary search on, which reduces the average number ofmemory loads to 2.

indutny force-pushed thefeature/lookup-and-search branch frombb6b82a tob4c9ce1Compare

January 30, 2023 22:49

Copy link

Member

Manishearth commentedJan 30, 2023

Alright, let me know when I should look at this!

Copy link

ContributorAuthor

indutny commentedJan 30, 2023

@Manishearth Should be good now, sorry for the back and forth! I made some simplifications and benchmarks looks even better than before:https://gist.github.com/indutny/c8d29a00680bfbaf19d22d02a7175c0d ( with up to 51% improvement on some word bounds benches).

Manishearth approved these changes

Jan 30, 2023

View reviewed changes

Manishearth merged commite94d2fe intounicode-rs:master

Jan 30, 2023

Copy link

Member

Manishearth commentedJan 30, 2023

Thanks!

indutny deleted the feature/lookup-and-search branch

January 30, 2023 23:12

Copy link

ContributorAuthor

indutny commentedJan 30, 2023

Wow! Thankyou for merging it!

Not to impose, but I was wondering when you planned to release a new version of the library?

Copy link

Member

Manishearth commentedJan 30, 2023

I'd happily merge a PR bumping the library to 1.10.1.

Copy link

ContributorAuthor

indutny commentedJan 30, 2023

You got it!

Copy link

jrose-signal commentedJan 30, 2023•
edited
Loading

Wait, I have one more optimization for you. :-) (EDIT: I'm@indutny's coworker, we've been loosely collaborating and independently looking at optimization opportunities in a few of the unicode-rs crates.)