servo / unicode-bidi

Implementation of the Unicode Bidirection Algorithm in Rust
Other
74 stars 34 forks source link

Optimize handling of purely-LTR paragraphs #97

Closed jfkthame closed 1 year ago

jfkthame commented 1 year ago

This aims to boost performance for paragraphs that do not contain any strongly-RTL characters.

Typical results of cargo bench -F bench_it --bench udhr with current master:

test bench_1_bidi_info_new_for_ltr_texts  ... bench:     891,763 ns/iter (+/- 43,823)
test bench_2_bidi_info_new_for_bidi_texts ... bench:   1,002,740 ns/iter (+/- 173,182)
test bench_3_reorder_line_for_ltr_texts   ... bench:     155,455 ns/iter (+/- 17,878)
test bench_4_reorder_line_for_bidi_texts  ... bench:     330,877 ns/iter (+/- 39,449)

And the same test after applying this patch:

test bench_1_bidi_info_new_for_ltr_texts  ... bench:     875,862 ns/iter (+/- 99,252)
test bench_2_bidi_info_new_for_bidi_texts ... bench:   1,005,841 ns/iter (+/- 179,152)
test bench_3_reorder_line_for_ltr_texts   ... bench:         894 ns/iter (+/- 57)
test bench_4_reorder_line_for_bidi_texts  ... bench:     243,300 ns/iter (+/- 16,616)
bors-servo commented 1 year ago

:umbrella: The latest upstream changes (presumably #105) made this pull request unmergeable. Please resolve the merge conflicts.

jfkthame commented 1 year ago

I've updated this to take a different approach that (AFAICS) should not break any public API. @Manishearth PTAL and see if this is a workable way forward.

Current results on my local machine for cargo bench -F bench_it --bench udhr with master:

test bench_1_bidi_info_new_for_ltr_texts  ... bench:     672,764 ns/iter (+/- 94,785)
test bench_2_bidi_info_new_for_bidi_texts ... bench:     778,742 ns/iter (+/- 172,804)
test bench_3_reorder_line_for_ltr_texts   ... bench:     110,351 ns/iter (+/- 6,317)
test bench_4_reorder_line_for_bidi_texts  ... bench:     255,082 ns/iter (+/- 25,808)

Same test with this patch:

test bench_1_bidi_info_new_for_ltr_texts  ... bench:     215,393 ns/iter (+/- 23,973)
test bench_2_bidi_info_new_for_bidi_texts ... bench:     725,057 ns/iter (+/- 55,314)
test bench_3_reorder_line_for_ltr_texts   ... bench:       8,326 ns/iter (+/- 1,408)
test bench_4_reorder_line_for_bidi_texts  ... bench:     193,079 ns/iter (+/- 14,852)

So we get a pretty big improvement on the ltr_texts tests, and also a slight improvement on the bidi_texts ones (presumably the "bidi" texts do have a smattering of LTR-only paragraphs in them).

Manishearth commented 1 year ago

Needs rustfmt, you can ignore the failure on 1.36 (I should fix that CI job)

Manishearth commented 1 year ago

I'll just merge and fix in post.

Manishearth commented 1 year ago

Thanks!!