Cache Fuse.js instances instead of rebuilding on every search#5342
Open
repparw wants to merge 1 commit intotridactyl:masterfrom
Open
Cache Fuse.js instances instead of rebuilding on every search#5342repparw wants to merge 1 commit intotridactyl:masterfrom
repparw wants to merge 1 commit intotridactyl:masterfrom
Conversation
b0b6d4a to
162649d
Compare
- Add getter/setter for options that auto-invalidates Fuse index when options change - Fuse index is now built lazily once when first searched, then reused until options change - Direct _options assignment for internal reordering to avoid index invalidation
162649d to
3bbafc5
Compare
Contributor
Author
Performance BenchmarkTested with synthetic completion data to simulate real-world usage:
Test: 100 iterations × 7 different queries per dataset Benchmark codeconst Fuse = require('fuse.js');
const sizes = [500, 1000, 2000];
const queries = ['opt', 'opt-5', 'desc', 'item', '999', 'option-100', 'xxx'];
for (const size of sizes) {
const options = [];
for (let i = 0; i < size; i++) {
options.push({
value: `option-${i}`,
fuseKeys: [`option-${i}`, `desc-${i}`, `item number ${i}`],
state: "normal"
});
}
const fuseOptions = {
keys: ["fuseKeys"],
shouldSort: true,
includeScore: true,
findAllMatches: true,
ignoreLocation: true,
ignoreFieldNorm: true,
threshold: 0.3,
minMatchCharLength: 1,
};
function searchOld(query) {
const searchThis = options.map((elem, index) => ({ index, fuseKeys: elem.fuseKeys }));
const fuse = new Fuse(searchThis, fuseOptions);
return fuse.search(query);
}
let cachedFuse = undefined;
function searchNew(query) {
if (cachedFuse === undefined) {
const searchThis = options.map((elem, index) => ({ index, fuseKeys: elem.fuseKeys }));
cachedFuse = new Fuse(searchThis, fuseOptions);
}
return cachedFuse.search(query);
}
// Warmup
for (const q of queries) { searchOld(q); searchNew(q); }
// OLD
let start = Date.now();
for (let iter = 0; iter < 100; iter++) {
for (const q of queries) { searchOld(q); }
}
const oldTime = Date.now() - start;
// NEW
cachedFuse = undefined;
start = Date.now();
for (let iter = 0; iter < 100; iter++) {
for (const q of queries) { searchNew(q); }
}
const newTime = Date.now() - start;
console.log(`${size} options: OLD=${oldTime}ms, NEW=${newTime}ms, SPEEDUP=${(oldTime/newTime).toFixed(2)}x`);
} |
Contributor
Author
Performance Testing ResultsI tested this PR using the perf tooling from the Histogram (distribution of search durations)Raw Performance Dump (first few entries)[
{
"name": "tri/BufferCompletionSource/updateOptions:625658:start",
"entryType": "mark",
"startTime": 908,
"duration": 0
},
{
"name": "tri/BufferCompletionSource/updateOptions:625658",
"entryType": "measure",
"startTime": 908,
"duration": 17
},
{
"name": "tri/BufferCompletionSource/updateOptions:210565",
"entryType": "measure",
"startTime": 920,
"duration": 5
},
{
"name": "tri/BufferCompletionSource/updateOptions:217731",
"entryType": "measure",
"startTime": 2332,
"duration": 2
},
{
"name": "tri/BufferCompletionSource/updateOptions:496849",
"entryType": "measure",
"startTime": 2858,
"duration": 1
}
]ConclusionThe optimization is working as expected:
This represents a 3-10x speedup for repeated searches during completion filtering. The Fuse instance is now built once and cached, then reused until the options change. |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Add this suggestion to a batch that can be applied as a single commit.This suggestion is invalid because no changes were made to the code.Suggestions cannot be applied while the pull request is closed.Suggestions cannot be applied while viewing a subset of changes.Only one suggestion per line can be applied in a batch.Add this suggestion to a batch that can be applied as a single commit.Applying suggestions on deleted lines is not supported.You must change the existing code in this line in order to create a valid suggestion.Outdated suggestions cannot be applied.This suggestion has been applied or marked resolved.Suggestions cannot be applied from pending reviews.Suggestions cannot be applied on multi-line comments.Suggestions cannot be applied while the pull request is queued to merge.Suggestion cannot be applied right now. Please check back later.
Summary
optionsthat automatically invalidates Fuse index when options changebuildFuseIndex()method for lazy initialization instead of rebuilding on every searchsetOptionsWithoutInvalidation()for internal reordering without triggering rebuildThis addresses the performance issue noted in the code comments: "PERF: Could be expensive not to cache Fuse() // yeah, it was."
Before: Fuse.js index was rebuilt on every call to
scoredOptions(), which happens on every keystroke during completion search.After: Fuse index is built once when
optionschange, then reused for subsequent searches until options are updated again.Testing