keymanapp / keymanapp/keyman

feat(web): Improve performance of predictive text search algorithm

Open
#10,414 2 comments 0 reactions 1 assignee Claimed by @jahorton View on GitHub
feat web/ web/predictive-text/
Dominant language
Pascal
Stars
534
Forks
143
Avg merge
2d 10h
Merged PRs (30d)
113

Description

> After the other things already noted... the last thing I can presently see is that certain properties of search nodes that _could_ be computed based on previous nodes... aren't - they're rebuilt from scratch instead. Yes, the arrays are typically small... but as word size grows, a word of M letters needs O(M^2) time for the properties to build across all steps taken to reach it - O(M) time to build, M times. Dropping this to O(M) is feasible - O(1) to build, M times. This "O(M^2)" cost likely only surfaces as a 'larger coefficient' on the true runtime complexity of each correction-search step. Reducing this "coefficient" could still be a decent improvement, though.
>
> This is in reference to the following `SearchNode` properties:
> - `knownCost`, `inputSamplingCost` (and their sum `currentCost`)
> - `mapKey` (used to prevent re-running nodes that were already reached via different path)
>
> The proportion of code affected is a bit hard to discern on the surface of things; the impact is somewhat scattered. For a loose estimate, I believe that this affects no more than 1/5 of the current correction-algorithm runtime. The 1/5 figure gives us an absolute maximum speedup of 25% if we could completely eliminate such sections (1 / 0.8, as per Amdahl's law)... and only a 11.1% speedup if we merely halve their runtime. Quartering the runtime: 1 / .85 => 17.6% speedup, and I'd be quite surprised if we could do better than that. It's certainly not _nothing_, but I'm pretty sure we're entering the realm of limited ROI for further optimization pursuits.

_Originally posted by @jahorton in https://github.com/keymanapp/keyman/issues/10127#issuecomment-1880586159_

Reference this and other comments in #10127 for more details.

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.