Performance issues with suggestions in French

[ByteOfBrie]

Spellchecking performance seems especially bad in French (compared to German or English), even after #14

This was also originally found by @new-years-eve, but I did a bit of testing around it.

Some testing data (formatted for clarity):

Spellbook:
en_US correct word: 14.818µs 
fr_FR correct word: 19.015µs 
en_US incorrect word: 12.574µs
fr_FR incorrect word: 360.648µs

en_US impécable suggestions: 130.336522ms
fr_FR impécable suggestions: 1.465016974s

en_US réceptioniste suggestions: 188.750999ms
fr_FR réceptioniste suggestions: 1.662972801s

de_DE frühstrucken suggestions: 370.188776ms

(before #14, impécable took ~30 seconds, I killed my test for réceptioniste after 15 minutes)

Click to expand (Hunspell results)

Hunspell:
en_US correct word: 4.148µs
fr_FR correct word: 38.251µs
en_US incorrect word: 11.712µs
fr_FR incorrect word: 20.358µs

en_US impécable suggestions: 59.585589ms
fr_FR impécable suggestions: 243.439059ms

en_US réceptioniste suggestions: 56.378308ms
fr_FR réceptioniste suggestions: 117.79522ms

de_DE frühstrucken suggestions: 98.131046ms

Click to expand (source code)

use std::time::Instant;

use hunspell_rs::{CheckResult, Hunspell};
use spellbook::Dictionary;

fn test_hunspell() {
    let fr_dict = Hunspell::new(
        "/usr/share/hunspell/fr_FR.aff",
        "/usr/share/hunspell/fr_FR.dic",
    );
    let en_dict = Hunspell::new(
        "/usr/share/hunspell/en_US.aff",
        "/usr/share/hunspell/en_US.dic",
    );
    let de_dict = Hunspell::new(
        "/home/brie/Downloads/de_DE.aff",
        "/home/brie/Downloads/de_DE.dic",
    );

    let dur = Instant::now();
    assert!(en_dict.check("test") == CheckResult::FoundInDictionary);
    println!("en_US correct word: {:?}", dur.elapsed());

    let dur = Instant::now();
    assert!(fr_dict.check("test") == CheckResult::FoundInDictionary);
    println!("fr_FR correct word: {:?}", dur.elapsed());

    let dur = Instant::now();
    assert!(en_dict.check("foobarbaz") != CheckResult::FoundInDictionary);
    println!("en_US incorrect word: {:?}", dur.elapsed());

    let dur = Instant::now();
    assert!(fr_dict.check("foobarbaz") != CheckResult::FoundInDictionary);
    println!("fr_FR incorrect word: {:?}", dur.elapsed());

    let dur = Instant::now();
    let suggestions = en_dict.suggest("impécable");
    println!("en_US impécable suggestions: {:?}", dur.elapsed());
    println!("Suggestions: {suggestions:?}");

    let dur = Instant::now();
    let suggestions = fr_dict.suggest("impécable");
    println!("fr_FR impécable suggestions: {:?}", dur.elapsed());
    println!("Suggestions: {suggestions:?}");

    let dur = Instant::now();
    let suggestions = en_dict.suggest("réceptioniste");
    println!("en_US réceptioniste suggestions: {:?}", dur.elapsed());
    println!("Suggestions: {suggestions:?}");

    let dur = Instant::now();
    let suggestions = fr_dict.suggest("réceptioniste");
    println!("fr_FR réceptioniste suggestions: {:?}", dur.elapsed());
    println!("Suggestions: {suggestions:?}");

    let dur = Instant::now();
    let suggestions = de_dict.suggest("frühstrucken");
    println!("de_DE frühstrucken suggestions: {:?}", dur.elapsed());
    println!("Suggestions: {suggestions:?}");
}

fn test_spellbook() {
    let fr_aff = std::fs::read_to_string("/usr/share/hunspell/fr_FR.aff").unwrap();
    let fr_dic = std::fs::read_to_string("/usr/share/hunspell/fr_FR.dic").unwrap();
    let fr_dict = Dictionary::new(&fr_aff, &fr_dic).unwrap();
    let en_aff = std::fs::read_to_string("/usr/share/hunspell/en_US.aff").unwrap();
    let en_dic = std::fs::read_to_string("/usr/share/hunspell/en_US.dic").unwrap();
    let en_dict = Dictionary::new(&en_aff, &en_dic).unwrap();
    let de_aff = std::fs::read_to_string("/home/brie/Downloads/de_DE.aff").unwrap();
    let de_dic = std::fs::read_to_string("/home/brie/Downloads/de_DE.dic").unwrap();
    let de_dict = Dictionary::new(&de_aff, &de_dic).unwrap();

    let dur = Instant::now();
    assert!(en_dict.check("test"));
    println!("en_US correct word: {:?} ", dur.elapsed());

    let dur = Instant::now();
    assert!(fr_dict.check("test"));
    println!("fr_FR correct word: {:?} ", dur.elapsed());

    let dur = Instant::now();
    assert!(!en_dict.check("foobarbaz"));
    println!("en_US incorrect word: {:?}", dur.elapsed());

    let dur = Instant::now();
    assert!(!fr_dict.check("foobarbaz"));
    println!("fr_FR incorrect word: {:?}", dur.elapsed());

    let mut suggestions = Vec::new();

    let dur = Instant::now();
    en_dict.suggest("impécable", &mut suggestions);
    println!("en_US impécable suggestions: {:?}", dur.elapsed());
    println!("Suggestions: {suggestions:?}");

    let dur = Instant::now();
    fr_dict.suggest("impécable", &mut suggestions);
    println!("fr_FR impécable suggestions: {:?}", dur.elapsed());
    println!("Suggestions: {suggestions:?}");

    let dur = Instant::now();
    en_dict.suggest("réceptioniste", &mut suggestions);
    println!("en_US réceptioniste suggestions: {:?}", dur.elapsed());
    println!("Suggestions: {suggestions:?}");

    let dur = Instant::now();
    fr_dict.suggest("réceptioniste", &mut suggestions);
    println!("fr_FR réceptioniste suggestions: {:?}", dur.elapsed());
    println!("Suggestions: {suggestions:?}");

    let dur = Instant::now();
    de_dict.suggest("frühstrucken", &mut suggestions);
    println!("de_DE frühstrucken suggestions: {:?}", dur.elapsed());
    println!("Suggestions: {suggestions:?}");
}

fn main() {
    println!("Hunspell:");
    test_hunspell();
    println!("----------");
    println!("Spellbook:");
    test_spellbook();
}

I can provide dictionary files to replicate if necessary, but I'm just using French and English from the standard fedora 43 packages (hunspell-en, hunspell-fr). The German package is from Arch Linux, since the Fedora de_DE dictionary uses ISO-8859 instead of UTF-8 (and spellbook cannot handle non-UTF-8)

---

I'm well aware that the README doesn't guarantee that this will work well:

Some dictionaries which use complex compounding directives may work less well.

It seemed like this was (potentially) bad enough to be worth an issue

[blopker]

Hey! Got another report that seems similar over at blopker/codebook#264. @the-mikedavis, would you be open for me to put together some test cases and maybe a fix? Additionally, some kind of clean way to cancel a suggest call could be helpful in case a user wants to put a cap on execution time.

[blopker]

Actually after testing, the fix in #14 brings performance back to a reasonable level. 13 s → 94 ms on my machine for the specific issue on the Danish dictionary. Can I poke you for a release? 😁

[the-mikedavis]

Sorry for the delay, I've been busy at work for the last few weeks/months. Let me make a patch release for #14.

I will try taking a look at this when I get a change as well. Thanks for the nice reproducer!

[the-mikedavis]

Released #14 as v0.4.1: https://github.com/helix-editor/spellbook/releases/tag/v0.4.1

[the-mikedavis]

Ok I spent some time looking into this. The main reason fr_FR was slower in Spellbook is that fr_FR has many more affixes (PFX and SFX rules):

Lang	en_US	fr_FR
PFX groups	7	18
PFX entries	7	197
SFX groups	16	160
SFX entries	43	5224

The checker iterates on matching PFX/SFX rules and the suggester calls the checker often. Iterating on matching affixes (AffixesIter::next) was doing a linear scan through parts of the prefixes/suffixes tables. Nuspell does a binary search (std::equal_range). Hunspell has a tree for that data structure, so it was also sub-linear. I switched AffixesIter::next to use a binary search (partition_point) in 39254f2. There was also an opportunity to add a small fast-lane which cut the check and suggest times even more (Condition::matches, b862d97).

I added fr_FR to the check benchmark and created a suggest benchmark. Overall the improvements with those two commits looks like this:

Benchmark	Baseline	AffixesIter::next opt	Condition::matches opt	Overall improvement
check fr_incorrect_word	9042.5 ns	3270.8 ns	2930.5 ns	3.09x
check fr_in_dictionary_word	699.9 ns	697.5 ns	708.3 ns	~1.0x (noise)
check fr_word_with_suffix	772.4 ns	784.6 ns	715.1 ns	~1.0x (noise)
suggest fr_fr_correct_word	12.84 ms	3.82 ms	3.28 ms	3.92x
suggest fr_fr_receptioniste	112.84 ms	93.81 ms	83.32 ms	1.35x
suggest fr_fr_impecable	131.01 ms	121.42 ms	112.42 ms	1.17x
suggest fr_fr_incorrect_word	152.80 ms	90.70 ms	94.11 ms	1.62x

en_US affix table is tiny so those benchmarks didn't change noticeably.

Raw data...

cargo bench --bench check

baseline

running 13 tests
test breaks                       ... bench:         820.84 ns/iter (+/- 18.10)
test compound_word                ... bench:         792.26 ns/iter (+/- 116.57)
test fr_in_dictionary_word        ... bench:         699.87 ns/iter (+/- 44.81)
test fr_incorrect_word            ... bench:       9,042.52 ns/iter (+/- 458.12)
test fr_word_with_suffix          ... bench:         772.37 ns/iter (+/- 32.40)
test in_dictionary_word           ... bench:          61.85 ns/iter (+/- 16.50)
test incorrect_prefix             ... bench:         458.03 ns/iter (+/- 69.72)
test number                       ... bench:          35.80 ns/iter (+/- 6.16)
test titlecase_in_dictionary_word ... bench:         288.56 ns/iter (+/- 10.64)
test uppercase_in_dictionary_word ... bench:         531.14 ns/iter (+/- 125.07)
test word_with_prefix             ... bench:         203.39 ns/iter (+/- 9.78)
test word_with_prefix_and_suffix  ... bench:         361.53 ns/iter (+/- 38.17)
test word_with_suffix             ... bench:          70.81 ns/iter (+/- 2.33)

AffixesIter::next opt

running 13 tests
test breaks                       ... bench:         875.63 ns/iter (+/- 104.73)
test compound_word                ... bench:         747.23 ns/iter (+/- 99.10)
test fr_in_dictionary_word        ... bench:         697.46 ns/iter (+/- 145.75)
test fr_incorrect_word            ... bench:       3,270.84 ns/iter (+/- 86.94)
test fr_word_with_suffix          ... bench:         784.57 ns/iter (+/- 27.51)
test in_dictionary_word           ... bench:          63.49 ns/iter (+/- 6.80)
test incorrect_prefix             ... bench:         447.63 ns/iter (+/- 14.40)
test number                       ... bench:          33.87 ns/iter (+/- 2.98)
test titlecase_in_dictionary_word ... bench:         314.49 ns/iter (+/- 16.85)
test uppercase_in_dictionary_word ... bench:         531.48 ns/iter (+/- 20.83)
test word_with_prefix             ... bench:         211.77 ns/iter (+/- 28.09)
test word_with_prefix_and_suffix  ... bench:         414.78 ns/iter (+/- 90.82)
test word_with_suffix             ... bench:          68.69 ns/iter (+/- 1.82)

Condition::matches opt

running 13 tests
test breaks                       ... bench:         906.89 ns/iter (+/- 36.93)
test compound_word                ... bench:         752.57 ns/iter (+/- 86.21)
test fr_in_dictionary_word        ... bench:         708.33 ns/iter (+/- 60.46)
test fr_incorrect_word            ... bench:       2,930.47 ns/iter (+/- 444.50)
test fr_word_with_suffix          ... bench:         715.08 ns/iter (+/- 20.07)
test in_dictionary_word           ... bench:          68.32 ns/iter (+/- 4.77)
test incorrect_prefix             ... bench:         467.91 ns/iter (+/- 58.84)
test number                       ... bench:          37.89 ns/iter (+/- 6.91)
test titlecase_in_dictionary_word ... bench:         322.26 ns/iter (+/- 10.87)
test uppercase_in_dictionary_word ... bench:         542.03 ns/iter (+/- 21.80)
test word_with_prefix             ... bench:         194.09 ns/iter (+/- 32.20)
test word_with_prefix_and_suffix  ... bench:         412.55 ns/iter (+/- 40.16)
test word_with_suffix             ... bench:          72.02 ns/iter (+/- 4.93)

---

cargo bench --bench suggest

baseline

running 7 tests
test en_us_edit_suggest           ... bench:  13,666,423.90 ns/iter (+/- 2,559,660.32)
test en_us_ngram_suggest          ... bench:  20,264,291.70 ns/iter (+/- 2,400,239.22)
test en_us_uppercase_suggest      ... bench:      81,988.43 ns/iter (+/- 2,926.50)
test fr_fr_correct_word_suggest   ... bench:  12,835,208.90 ns/iter (+/- 1,593,773.77)
test fr_fr_impecable_suggest      ... bench: 131,007,255.60 ns/iter (+/- 14,262,803.08)
test fr_fr_incorrect_word_suggest ... bench: 152,803,194.10 ns/iter (+/- 16,477,591.86)
test fr_fr_receptioniste_suggest  ... bench: 112,835,599.50 ns/iter (+/- 12,116,497.90)

AffixesIter::next opt

running 7 tests
test en_us_edit_suggest           ... bench:  14,190,488.80 ns/iter (+/- 2,124,976.06)
test en_us_ngram_suggest          ... bench:  20,170,439.90 ns/iter (+/- 2,732,603.77)
test en_us_uppercase_suggest      ... bench:      84,106.78 ns/iter (+/- 4,565.17)
test fr_fr_correct_word_suggest   ... bench:   3,818,302.20 ns/iter (+/- 455,218.15)
test fr_fr_impecable_suggest      ... bench: 121,423,175.60 ns/iter (+/- 14,501,839.70)
test fr_fr_incorrect_word_suggest ... bench:  90,697,099.70 ns/iter (+/- 10,163,934.75)
test fr_fr_receptioniste_suggest  ... bench:  93,814,033.40 ns/iter (+/- 10,500,000.74)

Condition::matches opt

running 7 tests
test en_us_edit_suggest           ... bench:  14,669,992.90 ns/iter (+/- 1,413,600.45)
test en_us_ngram_suggest          ... bench:  18,652,809.40 ns/iter (+/- 1,248,795.02)
test en_us_uppercase_suggest      ... bench:      79,535.97 ns/iter (+/- 1,394.08)
test fr_fr_correct_word_suggest   ... bench:   3,276,677.90 ns/iter (+/- 322,519.54)
test fr_fr_impecable_suggest      ... bench: 112,421,017.80 ns/iter (+/- 7,558,251.48)
test fr_fr_incorrect_word_suggest ... bench:  94,111,789.30 ns/iter (+/- 9,432,798.57)
test fr_fr_receptioniste_suggest  ... bench:  83,318,923.90 ns/iter (+/- 8,503,753.07)

---

There's still some room for improvement for fr_FR. Comparing now with Hunspell & Nuspell:

check (ns/iter)

case	spellbook	hunspell	nuspell
en correct (earth)	56.5	235.6	143.5
en incorrect(foobarbaz)	295.7	1325.1	397.9
fr correct (test)	699.7	264.3	193.0
fr incorrect(foobarbaz)	3166.8	2502.7	2948.8
fr suffix (mangeable)	715.1	390.2	336.4

suggest (ms/iter)

case	spellbook	hunspell	nuspell
en exmaple	14.38	11.90	16.48
fr impécable	120.55	169.61	140.03
fr réceptioniste	81.94	0.247 (*)	106.60
fr foobarbaz	84.06	114.51	98.34

*: Hunspell short-circuits in this case instead of looking at ngram suggestions. Spellbook should probably adopt that strategy too.

Raw data...

cargo bench --bench compare-check

running 15 tests
test en_correct_hunspell    ... bench:         235.60 ns/iter (+/- 15.84)
test en_correct_nuspell     ... bench:         143.50 ns/iter (+/- 10.76)
test en_correct_spellbook   ... bench:          56.54 ns/iter (+/- 0.87)
test en_incorrect_hunspell  ... bench:       1,325.12 ns/iter (+/- 39.38)
test en_incorrect_nuspell   ... bench:         397.93 ns/iter (+/- 39.26)
test en_incorrect_spellbook ... bench:         295.66 ns/iter (+/- 9.29)
test fr_correct_hunspell    ... bench:         264.25 ns/iter (+/- 12.08)
test fr_correct_nuspell     ... bench:         193.04 ns/iter (+/- 13.71)
test fr_correct_spellbook   ... bench:         699.70 ns/iter (+/- 44.25)
test fr_incorrect_hunspell  ... bench:       2,502.69 ns/iter (+/- 108.99)
test fr_incorrect_nuspell   ... bench:       2,948.79 ns/iter (+/- 119.66)
test fr_incorrect_spellbook ... bench:       3,166.81 ns/iter (+/- 147.55)
test fr_suffix_hunspell     ... bench:         390.19 ns/iter (+/- 21.08)
test fr_suffix_nuspell      ... bench:         336.43 ns/iter (+/- 19.66)
test fr_suffix_spellbook    ... bench:         715.07 ns/iter (+/- 22.49)

cargo bench --bench compare-suggest

running 12 tests
test en_exmaple_hunspell        ... bench:  11,898,827.30 ns/iter (+/- 2,530,645.06)
test en_exmaple_nuspell         ... bench:  16,483,186.80 ns/iter (+/- 2,846,422.17)
test en_exmaple_spellbook       ... bench:  14,377,873.10 ns/iter (+/- 1,537,863.88)
test fr_impecable_hunspell      ... bench: 169,608,226.50 ns/iter (+/- 11,522,304.60)
test fr_impecable_nuspell       ... bench: 140,030,524.60 ns/iter (+/- 15,549,164.18)
test fr_impecable_spellbook     ... bench: 120,554,402.20 ns/iter (+/- 13,221,262.96)
test fr_incorrect_hunspell      ... bench: 114,511,038.60 ns/iter (+/- 10,170,402.52)
test fr_incorrect_nuspell       ... bench:  98,342,708.60 ns/iter (+/- 3,453,098.40)
test fr_incorrect_spellbook     ... bench:  84,060,500.90 ns/iter (+/- 3,689,501.40)
test fr_receptioniste_hunspell  ... bench:     247,375.00 ns/iter (+/- 6,974.48)
test fr_receptioniste_nuspell   ... bench: 106,598,964.10 ns/iter (+/- 10,855,160.10)
test fr_receptioniste_spellbook ... bench:  81,944,361.80 ns/iter (+/- 8,947,704.98)

---

Spellbook is faster for checking en_US since it's mainly dominated by hash table lookup and we're using a fancy hashbrown table here. There are some cases where spellbook is loosing out to hunspell or nuspell, especially for checking fr_FR. I'll keep digging into those. We should be able to beat hunspell and nuspell on everything ideally.

[the-mikedavis]

Looks like we lose in the remaining cases because ICONV/OCONV. perf reports it as a very noticeably slice of the remaining work. We can make the conversion table type much smarter, it's pretty naive at the moment.

[the-mikedavis]

I've pushed a few more fixes to master. I'll make a patch release this evening.

perf on check("test") showed ~94% of the time in ICONV/OCONV:

58.18%  [.] core::str::pattern::StrSearcher::new
20.52%  [.] spellbook::aff::ConversionTable::convert
15.02%  [.] __memcmp_avx2_movbe
...
 0.59%  [.] HashBag::get

Checking a correct word should just be a single hash bag lookup and we can see that's a tiny tiny fraction.

fr_FR in particular has 42 ICONV patterns and convert was running a substring search for every pattern on every word. Two improvements:

• Binary searching the table (97551e2). Same story as the affixes: the table is now sorted by pattern, so we binary-search the patterns sharing each position's leading byte instead of scanning all of them. Nuspell (Substr_Replacer) and Hunspell (RepList) both do per-position binary search.
• Fast-lanes (cc9cf22). Skip an empty table (most dictionaries have no ICONV/OCONV). And since every fr_FR pattern is a non-ASCII accent/ligature/decomposed char, skip the whole walk when str::is_ascii is true for the word. str::is_ascii is quick since it's done with SIMD.

check benchmark improvement:

case	before (b862d97)	binary search (97551e2)	fast-lanes (cc9cf22)	overall
fr_in_dictionary_word (test)	708.3 ns	99.1 ns	46.0 ns	15.4x
fr_word_with_suffix (mangeable)	715.1 ns	191.5 ns	48.9 ns	14.6x
fr_incorrect_word (foobarbaz)	2930.5 ns	2554.3 ns	2433.7 ns	1.2x

The binary search also scales with table size on its own. A synthetic ICONV table where the ASCII fast-lane can't fire:

table	linear	binary search
64 patterns	1816 ns	841 ns
1024 patterns	27642 ns	6303 ns

With this, Spellbook now beats both Hunspell and Nuspell on every check benchmark very handily, including the fr_FR cases that were losing before:

check (ns/iter)

case	spellbook	hunspell	nuspell
en correct (earth)	45.4	235.0	120.8
en incorrect (foobarbaz)	289.2	1240.9	367.6
fr correct (test)	46.8	268.8	184.7
fr incorrect (foobarbaz)	2195.5	2518.1	2868.1
fr suffix (mangeable)	46.9	414.7	314.9

suggest is not really affected by this since convert runs once per call and it's drowned out by everything else.

Raw data...

cargo bench --bench compare-check

test en_correct_hunspell    ... bench:         234.95 ns/iter (+/- 37.63)
test en_correct_nuspell     ... bench:         120.76 ns/iter (+/- 3.97)
test en_correct_spellbook   ... bench:          45.42 ns/iter (+/- 3.50)
test en_incorrect_hunspell  ... bench:       1,240.89 ns/iter (+/- 26.43)
test en_incorrect_nuspell   ... bench:         367.61 ns/iter (+/- 11.02)
test en_incorrect_spellbook ... bench:         289.17 ns/iter (+/- 8.44)
test fr_correct_hunspell    ... bench:         268.84 ns/iter (+/- 36.98)
test fr_correct_nuspell     ... bench:         184.69 ns/iter (+/- 27.01)
test fr_correct_spellbook   ... bench:          46.82 ns/iter (+/- 7.39)
test fr_incorrect_hunspell  ... bench:       2,518.07 ns/iter (+/- 52.97)
test fr_incorrect_nuspell   ... bench:       2,868.14 ns/iter (+/- 126.91)
test fr_incorrect_spellbook ... bench:       2,195.49 ns/iter (+/- 574.99)
test fr_suffix_hunspell     ... bench:         414.66 ns/iter (+/- 42.97)
test fr_suffix_nuspell      ... bench:         314.88 ns/iter (+/- 12.32)
test fr_suffix_spellbook    ... bench:          46.87 ns/iter (+/- 1.51)

cargo bench --bench conversion

test iconv_table_64   ... bench:         840.63 ns/iter (+/- 37.51)
test iconv_table_1024 ... bench:       6,303.02 ns/iter (+/- 257.61)

[the-mikedavis]

Ok this is all released now as v0.4.2: https://github.com/helix-editor/spellbook/releases/tag/v0.4.2

It seemed like this was (potentially) bad enough to be worth an issue

The note in the README is a little out of date, I hadn't tested compounding at the time. There's one very specific branch involving compounds that is a stub / unimplemented, but otherwise it should work OK these days. If there are performance or correctness gaps I'd definitely say it's a bug. And I'd rather have the nice problem of too many issues than having stuff like this fly under the radar :)

[ByteOfBrie]

Wow, thanks for the work, the additional benchmarks are excellent.

On 0.4.2 and master (d7ec275), I'm still seeing spellbook suggestions being slower in my "basic" test (from this issue), but the same test in the benchmark seems to be faster (in line with the results you see here).

I'm not sure what's going on there, I might continue to play around with it

[ByteOfBrie]

It isn't a problem with the dictionaries themselves, I see similar performance when using the spellbook vendor dictionaries with the basic test.

My next best guess was that it was because of caching or something in the benchmark, but I'm not sure if that's it.

Source Code

#![feature(test)]
#![allow(unused_variables)]

use std::time::Instant;

extern crate test;

use hunspell_rs::{CheckResult, Hunspell};
use spellbook::Dictionary;

#[cfg(test)]
use test::Bencher;

type RandomState = foldhash::fast::FixedState;

// const EN_DICT_PATH: &str = "/usr/share/hunspell/en_US";
// const FR_DICT_PATH: &str = "/usr/share/hunspell/fr_FR";
const EN_DICT_PATH: &str = "/home/brie/code/spellbook/vendor/en_US/en_US";
const FR_DICT_PATH: &str = "/home/brie/code/spellbook/vendor/fr_FR/fr";
const DE_DICT_PATH: &str = "/usr/share/hunspell/de_DE";

const SHOW_CORRECT_INCORRECT: bool = false;

fn test_hunspell() {
    let fr_dict = Hunspell::new(
        &format!("{FR_DICT_PATH}.aff"),
        &format!("{FR_DICT_PATH}.dic"),
    );
    let en_dict = Hunspell::new(
        &format!("{EN_DICT_PATH}.aff"),
        &format!("{EN_DICT_PATH}.dic"),
    );
    let de_dict = Hunspell::new(
        &format!("{DE_DICT_PATH}.aff"),
        &format!("{DE_DICT_PATH}.dic"),
    );

    if SHOW_CORRECT_INCORRECT {
        let dur = Instant::now();
        assert_eq!(en_dict.check("test"), CheckResult::FoundInDictionary);
        println!("en_US correct word: {:?}", dur.elapsed());

        let dur = Instant::now();
        assert_eq!(fr_dict.check("test"), CheckResult::FoundInDictionary);
        println!("fr_FR correct word: {:?}", dur.elapsed());

        let dur = Instant::now();
        assert_eq!(en_dict.check("foobarbaz"), CheckResult::MissingInDictionary);
        println!("en_US incorrect word: {:?}", dur.elapsed());

        let dur = Instant::now();
        assert_eq!(fr_dict.check("foobarbaz"), CheckResult::MissingInDictionary);
        println!("fr_FR incorrect word: {:?}", dur.elapsed());
    }

    let dur = Instant::now();
    let suggestions = en_dict.suggest("impécable");
    println!("en_US impécable suggestions: {:?}", dur.elapsed());
    // println!("Suggestions: {suggestions:?}");

    let dur = Instant::now();
    let suggestions = fr_dict.suggest("impécable");
    println!("fr_FR impécable suggestions: {:?}", dur.elapsed());
    // println!("Suggestions: {suggestions:?}");

    let dur = Instant::now();
    let suggestions = en_dict.suggest("réceptioniste");
    println!("en_US réceptioniste suggestions: {:?}", dur.elapsed());
    // println!("Suggestions: {suggestions:?}");

    let dur = Instant::now();
    let suggestions = fr_dict.suggest("réceptioniste");
    println!("fr_FR réceptioniste suggestions: {:?}", dur.elapsed());
    // println!("Suggestions: {suggestions:?}");

    let dur = Instant::now();
    for _ in 1..10 {
        let suggestions = fr_dict.suggest("réceptioniste");
    }
    println!(
        "fr_FR réceptioniste 10 loop suggestions: {:?}",
        dur.elapsed()
    );

    let dur = Instant::now();
    for _ in 1..200 {
        let suggestions = fr_dict.suggest("réceptioniste");
    }
    println!(
        "fr_FR réceptioniste 200 loop suggestions: {:?}",
        dur.elapsed()
    );

    let dur = Instant::now();
    let suggestions = de_dict.suggest("frühstrucken");
    println!("de_DE frühstrucken suggestions: {:?}", dur.elapsed());
    // println!("Suggestions: {suggestions:?}");
}

fn test_spellbook() {
    let fr_aff = std::fs::read_to_string(format!("{FR_DICT_PATH}.aff")).unwrap();
    let fr_dic = std::fs::read_to_string(format!("{FR_DICT_PATH}.dic")).unwrap();
    let fr_dict = Dictionary::new(&fr_aff, &fr_dic).unwrap();
    let en_aff = std::fs::read_to_string(format!("{EN_DICT_PATH}.aff")).unwrap();
    let en_dic = std::fs::read_to_string(format!("{EN_DICT_PATH}.dic")).unwrap();
    let en_dict = Dictionary::new(&en_aff, &en_dic).unwrap();
    let de_aff = std::fs::read_to_string(format!("{DE_DICT_PATH}.aff")).unwrap();
    let de_dic = std::fs::read_to_string(format!("{DE_DICT_PATH}.dic")).unwrap();
    let de_dict = Dictionary::new(&de_aff, &de_dic).unwrap();

    if SHOW_CORRECT_INCORRECT {
        let dur = Instant::now();
        assert!(en_dict.check("test"));
        println!("en_US correct word: {:?} ", dur.elapsed());

        let dur = Instant::now();
        assert!(fr_dict.check("test"));
        println!("fr_FR correct word: {:?} ", dur.elapsed());

        let dur = Instant::now();
        assert!(!en_dict.check("foobarbaz"));
        println!("en_US incorrect word: {:?}", dur.elapsed());

        let dur = Instant::now();
        assert!(!fr_dict.check("foobarbaz"));
        println!("fr_FR incorrect word: {:?}", dur.elapsed());
    }

    let mut suggestions = Vec::new();

    let dur = Instant::now();
    en_dict.suggest("impécable", &mut suggestions);
    println!("en_US impécable suggestions: {:?}", dur.elapsed());
    // println!("Suggestions: {suggestions:?}");

    let dur = Instant::now();
    fr_dict.suggest("impécable", &mut suggestions);
    println!("fr_FR impécable suggestions: {:?}", dur.elapsed());
    // println!("Suggestions: {suggestions:?}");

    let dur = Instant::now();
    en_dict.suggest("réceptioniste", &mut suggestions);
    println!("en_US réceptioniste suggestions: {:?}", dur.elapsed());
    // println!("Suggestions: {suggestions:?}");

    let dur = Instant::now();
    fr_dict.suggest("réceptioniste", &mut suggestions);
    println!("fr_FR réceptioniste suggestions: {:?}", dur.elapsed());

    let dur = Instant::now();
    for _ in 1..10 {
        fr_dict.suggest("réceptioniste", &mut suggestions);
    }
    println!(
        "fr_FR réceptioniste 10 loop suggestions: {:?}",
        dur.elapsed()
    );

    let dur = Instant::now();
    for _ in 1..200 {
        fr_dict.suggest("réceptioniste", &mut suggestions);
    }
    println!(
        "fr_FR réceptioniste 200 loop suggestions: {:?}",
        dur.elapsed()
    );
    // println!("Suggestions: {suggestions:?}");

    let dur = Instant::now();
    de_dict.suggest("frühstrucken", &mut suggestions);
    println!("de_DE frühstrucken suggestions: {:?}", dur.elapsed());
    // println!("Suggestions: {suggestions:?}");
}

#[bench]
fn bench_suggest(b: &mut Bencher) {
    let hasher: RandomState = RandomState::with_seed(16553733157538299820);

    let fr_aff = std::fs::read_to_string(format!("{FR_DICT_PATH}.aff")).unwrap();
    let fr_dic = std::fs::read_to_string(format!("{FR_DICT_PATH}.dic")).unwrap();
    let fr_dict = Dictionary::new_with_hasher(&fr_aff, &fr_dic, hasher).unwrap();

    let mut _out = Vec::new();
    b.iter(|| {
        fr_dict.suggest("impécable", &mut _out);
    })
}

#[bench]
fn bench_suggest_hunspell(b: &mut Bencher) {
    let fr_dict = Hunspell::new(
        &format!("{FR_DICT_PATH}.aff"),
        &format!("{FR_DICT_PATH}.dic"),
    );

    b.iter(|| {
        fr_dict.suggest("impécable");
    })
}

fn main() {
    println!("Hunspell:");
    test_hunspell();
    println!("----------");
    println!("Spellbook:");
    test_spellbook();
}

(this test was specifically against spellbook 0.4.2 with the dictionaries from the spellbook source tree, but running against 94e099a doesn't seem to change anything)

cargo run:

Hunspell:
fr_FR réceptioniste suggestions: 105.731656ms
fr_FR réceptioniste 10 loop suggestions: 931.414999ms
fr_FR réceptioniste 200 loop suggestions: 20.99904558s
----------
Spellbook:
fr_FR réceptioniste suggestions: 902.211722ms
fr_FR réceptioniste 10 loop suggestions: 8.354322894s
fr_FR réceptioniste 200 loop suggestions: 182.583686939s

cargo bench:

running 2 tests
test bench_suggest          ... bench:  83,343,381.60 ns/iter (+/- 8,402,902.09)
test bench_suggest_hunspell ... bench: 115,048,377.70 ns/iter (+/- 18,493,471.28)

I have absolutely no idea why the benchmarks show spellbook being faster, but the adhoc benchmark with durations would take longer. This is my first time dealing with cargo bench, so I could easily be missing something there

[the-mikedavis]

Those timings seem pretty long to me. Are you using cargo run --release? Hunspell's C source might be optimized during compilation in a regular dev build but Spellbook's source won't be. If you use hunspell-sys / hunspell-rs, it will reuse your distro hunspell (probably at O2 opt level) by default, if you have one installed. This would explain why your findings in cargo bench agree with mine while cargo run diverges.

[ByteOfBrie]

I can't believe I didn't think of that, it's so obvious now that you said it

cargo run --release:

Hunspell:
fr_FR réceptioniste suggestions: 67.635986ms
fr_FR réceptioniste 10 loop suggestions: 610.749483ms
fr_FR réceptioniste 200 loop suggestions: 13.334107069s
----------
Spellbook:
fr_FR réceptioniste suggestions: 48.955026ms
fr_FR réceptioniste 10 loop suggestions: 421.302749ms
fr_FR réceptioniste 200 loop suggestions: 9.454044786s