slowness issue

[flammie]

I was demoing the morphology-aware spelling prediction stuff here at the conference and ran into a weird slowness issue I might need help to debug and profile, I have a zhfst and input that works instantaneously in hfst-ospell but takes 20 minutes in divvunspell, I thought first it was in my code, but it seems to happen in without analysis option as well:

$ echo niwa | time hfst-ospell -a crk-neu.zhfst -n 10
...
1.13user 0.02system 0:01.18elapsed 97%CPU (0avgtext+0avgdata 54824maxresident)k
$ echo niwa | time cargo run -- suggest --archive crk-neu.zhfst -S -n 10
...
1146.24user 1.33system 19:08.48elapsed 99%CPU (0avgtext+0avgdata 126788maxresident)k

Perhaps I am doing something simple wrong? I can upload the zhfst after the conference with better network and battery

[bbqsrc]

Can help debug when you're back next week. Pathological cases are fuuuun.

[flammie]

Here's the file, renamed as github is being silly: crk-neu.zhfst.zip. I'll be busy today but free most of the rest of the week.

[flammie]

I was doing debugging / tracing and it seems that the system legit goes through a whole large search space but maybe c++ version has hardcoded timeout just.

I might be off the track but the current code seems to sort and prune the suggestion list every new suggestion found which is probably necessary for keeping the suggestion list data structures in decent sizes and the weight limit that up-to-date but if I pull that out of inner loop I get some same results faster for this experiment? e6e198b

[bbqsrc]

@flammie yes, it's for weight limit and memory weight. When you say faster, how much faster?

[flammie]

@flammie yes, it's for weight limit and memory weight. When you say faster, how much faster?

when I test it now it's more like 10 seconds instead of 20 minutes:

echo niwa | time cargo run -- suggest --archive crk-neu.zhfst -S -n 10 
...
10.21user 0.16system 0:10.39elapsed 99%CPU (0avgtext+0avgdata 124500maxresident)k
0inputs+0outputs (0major+18798minor)pagefaults 0swaps

I mean, it is inner loop and it seems that it probably allocates a bit and does like sosrt algorithm everytime so order of magnitude difference isn't it?

IIRC I think in C++ version we used a self-sorting priority queue which hid some this complexity?

[bbqsrc]

Uh, have you been running the debug version of divvunspell? You need to add --release to cargo run for optimisations to be enabled.

[flammie]

Uh, have you been running the debug version of divvunspell? You need to add --release to cargo run for optimisations to be enabled.

ach, does it have such huge effect too? It seems I need to recompile the world with --release now D:

if the release version handles this zhfst and input just fine then it's just that we'd like to have the attached zhfst perhaps in some dev beta keyboard for demoing...

[bbqsrc]

Yeah if it's just that we can do that. And the impact is massive.

[flammie]

Right, this is the release:

285.75user 2.38system 4:49.46elapsed 99%CPU (0avgtext+0avgdata 123276maxresident)k
0inputs+0outputs (0major+1444099minor)pagefaults 0swaps

it's down to 5 minutes from 20 so quarter time but probably no very useful for spelling corrections yet...

[bbqsrc]

Ooh, 4x faster. Cool, so we have some work to do here.

[aarppe]

Might the next step be to explore whether moving the weights as much to the beginning of the prefix-weighting FST, that is used as the error-model in the *.zhfst setup, would have some positive impact?

[aarppe]

And I'm wondering about other ways to split the weighted morpheme completion FST. Could there be a point in setting the spell-relax component as the error model (without weights), and the rest as the acceptor (with weights)?

[snomos]

@aarppe it would be better to keep the two discussions (slowness and morpheme completion) as separate threads. Could you create a new issue, and move your comments related to morpheme completion there? You can of course reference this issue in the new one :)