Fix GlyphNotCached when match is not adjacent to order
Created by: alexheretic
As mentioned in #39 this PR adds a new solution to #52 (closed). I've also added two benchmarks which highlight the issue and server to avoid performance regression / encourage improvement in the future.
As in #39 I decided to simply solve the failure to find a glyph in the cache will worst-case full traversal. However, I went for a middle out style which is quite similar to the original check-adjacent algorithm.
My method starts from the same place according to BTreeMap ordering, but keeps searching outwards until it finds a left and/or right match instead of stopping after the first two. It'll search this way until it finds at least one match or exhausts the entire cache. After that it works on the 0/1/2 matches in exactly the same way as current code.
In summary it fixes the bug and performs the same way as the current algorithm in all the cases the current algorithm actually works. So while it may still not be the perfect algorithm it seems to definitely be an improvement.
| rusttype version | position tolerance | benchmark |
|---|---|---|
| 0.2.1 master | 1.0 | 3,623,762 ns/iter (+/- 49,103) |
| 0.2.1 master | 0.1 | failed |
| PR39-code | 1.0 | 8,378,997 ns/iter (+/- 176,811) |
| PR39-code | 0.1 | 123,299,414 ns/iter (+/- 804,216) |
| this PR | 1.0 | 3,579,136 ns/iter (+/- 54,938) |
| this PR | 0.1 | 63,443,258 ns/iter (+/- 521,366) |
Fixes #52 (closed) This will also address #39, and all current dependency update PRs.
Note: I took the liberty of adding a note about the benchmark to the readme. Feel free to remove if this isn't desired.