Implement an efficient `Nonspacing Mark` Normalizer about charabia HOT 2 CLOSED

Hey @crudiedo.

I tried your repo and here are my results:

Naive                   time:   [58.785 ms 58.823 ms 58.860 ms]

BTreeSet                time:   [13.723 ms 13.728 ms 13.733 ms]

RoaringBitmap           time:   [13.142 ms 13.148 ms 13.154 ms]

HashSet                 time:   [10.567 ms 10.578 ms 10.591 ms]

it's funny that the Naive approach has a lower performance than on your computer. 🤯

I think that using a HashSet is a good idea too, nice job! 👍

You can create a PR by replacing the current Hebrew normalizer, it is a good base to introduce your work, therefore, nonspacing marks include the Hebrew diacritics.

from charabia.

Hi everyone,

I’ve got the implementation prepared for the PR, but first wanted to agree on the data structure we’re going to use.

As proposed, I’ve made a sample app and did some benchmarking - you can find it there:

https://github.com/crudiedo/nonspacing-bench

The results are quite interesting - it looks like the built-in HashSet structure performs better than roaring bitmap (at least on my machine and using the 1.5MB sample text):

Naive                time:   [22.296 ms 22.378 ms 22.461 ms]  

BTreeSet             time:   [14.278 ms 14.335 ms 14.394 ms] 

RoaringBitmap        time:   [15.217 ms 15.274 ms 15.333 ms] 

HashSet              time:   [9.5395 ms 9.5683 ms 9.5972 ms]   

Of course there's still a memory difference matter, but I believe the speed is the priority especially since there are only 1281 marks to store.

I'm still not sure how to properly measure data structure size in Rust (besides 4 bytes for u32 * 1281 lol), so I used jemalloc and it's 328480 bytes allocated for a sample using hashset vs 289632 for roaring one.

So I believe we should be good with HashSet (or BTreeSet if I'm missing something about HashSet), and there's no need to use RoaringBitmap.

Thanks, let me know your thoughts and I'll move forward with submitting PR (:

from charabia.