>> And/or pick a different algorithm. E.g. Jaro-Winkler, which apparently
>> is used in a lot of "fuzzy matching" implementations out there, it's
>> pretty fast.
>
> That may be useful, but for other purposes. If I understand correctly,
> Jaro-Winkler is for finding the distante between two arbitrary strings,
> where the first in not a subsequence of the second. I bet google uses
> stuff like that when you accitendally transpose characters. Flex just
> gives up. Those other others algos still catch the match (and Google
> than probably NL-scours your most intimate fears and checks with your
> local dictator before showing you typing suggestions)
Meant to write ML as in machine learning, not NL.
I'm not crazy about shuffling completion, but some people did indeed ask
for it. The filtering step has to be more complex, though (you can't
just construct a straightforward regexp to filter with).
I think you calculate the distance using one of these fancy multi-surname algorithms , then do cutoff somewhere.
Same result, indeed. We should note, though, that
completion-pcm--hilit-commonality has some steps that were added
together with the 'flex' style, for it to work.
But nothing algorithmically aberrant, I think.
I did some instrumenting, replacing (completion-pcm--hilit-commonality
pattern all) inside completion-flex-all-completions with
(benchmark-progn (completion-pcm--hilit-commonality pattern all)).
Recompiled between each change (interpreted mode gives very different
numbers).
Unmodified, the call takes ~85ms:
Elapsed time: 0.085520s (0.068406s in 4 GCs)
By the way, I think you should be running benchmarks multiple times to get times in the seconds range, and reduce noise. Multiple levels of CPU cache and other factors like temp thottling may skew results when running just one time.
If I comment everything inside its first lambda except the returned
value (making the function the same as #'identity), the time goes down
to <1ms.
Uncomment the 'copy-sequence' and 'string-match' calls (which one might
suspect of garbage generation):
Elapsed time: 0.006380s
Tried binding gc-cons-threshold to a high value, and even galling
garbage-collect-maybe (or not): that speeds it up, but adds some
unpredictable GC pauses later (though it would be nice to be able to
consolidate the pauses into one collection pass).
Maybe in Elisp that's a good idea, in other lisps and other languages, second-guessing the GC is a bad idea. I hear ours is so basic that indeed it might be reasonable.
Long story short, the patch I just installed, to reuse the match data,
brings the runtime down to
Elapsed time: 0.066388s (0.050087s in 3 GCs)
That's nice! but are you sure you're not seeing noise, too?
Tried other things like moving the update-score-and-face lambda out of
the mapcar loop - that didn't move a needle.
If a lambda is non capturing of stuff inside the loop, only one copy of it is ever made, I think. So it doesn't suprise me.
And a weird part: replacing all repeated (length str) calls with a
reference to an existing local binding makes it *slower* (back to the
original performance).
Might be noise, or you might be thrashing of CPU caches, who knows? If the string length is on the same cache line as the contents of the string you're reading, then evicting that to go read the value of a boxed integer somewhere radically different is slow. Just speculation of course. Might just be noise or something else entirely.
João