Performance benchmark

[tomas-campodonico]

#Can you please add a section comparing the performance against the alternatives in plain JavaScript??

I made some tests and actually I got better results without the library. Perhaps I'm not using it properly. Here is the code I used:

var Trie = require('mnemonist/trie');
var query = 'rom';

var words = [];
const dictionary = ['category', 'romance'];

for (var i = 0; i < 10000; i++) {
  words.push(dictionary[i % 2] + i);
}

console.time('ES5');
var result = words.filter(function(word) {
  return word.startsWith(query);
});
console.log(result.length);
console.timeEnd('ES5');

console.time('mnemonist');
// Let's create a trie from our words
var trie = Trie.from(words);

// Now let's query our trie
var wordsWithMatchingPrefix = trie.get(query);
console.log(wordsWithMatchingPrefix.length);
console.timeEnd('mnemonist');

[maxiruani]

You should start the timer after creating the Trie

[Yomguithereal]

Hello @tomas-campodonico. Thanks for noticing this performance issue. I spotted an error in the Trie.get method and was able to get better performance (beating the ES5 array). Some things:

1. @maxiruani is right, you should put your timer after creating the Trie.
2. Try pulling the code & use the latest commit or wait for the npm release.
3. Try increasing your number to 100000 (one more zero) and you'll see a better benefit of using the Trie.

So, on the matter of benchmarking, you are right, I should start to make some in the repo to spot those kind of things etc. Usually I use matcha to do so. What do you think?

[Yomguithereal]

v0.10.2 has been released with the related commit.

[noopnik]

Same benchmark with 10000000 will failed on the Trie.from(words) line . v0.10.2, Node 7.4.0 .

[Yomguithereal]

Yes, but this is a memory issue. With 10M items node will run out of memory because the Trie needs to store pointers whereas a flat array is contiguous in memory.

[Yomguithereal]

This said, we can work together, if you want, to create a StaticTrie that could be stored in a flat array so it is more memory-efficient.