Implement simple B-Tree for faster string comparisons

[Uzlopak]

Prerequisites

• I have written a descriptive issue title
• I have searched existing issues to ensure the feature has not already been requested

🚀 Feature Proposal

Implement a B-Tree Class

Motivation

Lets see following lines

fastify/lib/handleRequest.js

Line 30 in 8d66924

if (method === 'POST' || method === 'PUT' || method === 'PATCH' || method === 'TRACE' || method === 'SEARCH' ||

This is run on every request. It means, that the last condition, here method === 'LOCK' is the slowest, as we have to check first 7 other values, before we potentially hit LOCK.

We should implement some simple and understandable b-tree, which only returns true if the element is in the tree and false if not.

Maybe there are other places we can use it.

Maybe using a Map is sufficient? But I think a b-tree would be faster.

Example

const MethodWithBody = new Tree()

MethodWithBody.insert('POST')
MethodWithBody.insert('PATCH')
MethodWithBody.insert('PUT')
MethodWithBody.insert('PROPFIND')

if (MethodWithBody.has(method)) {
}

[gurgunday]

Can you see this? We recently landed it and Set performed a little better, it might already be using something like that under-the-hood:

#5419

[Uzlopak]

I dont think that Set is optimized for this case, as Set also handles Objects and numbers etc.. So Set must have some code to check if the type is the same and stuff like that. I have the feeling that a b-tree will be significantly faster.

[casantosmu]

A switch statement could be more efficient as it allows for direct comparison and may be optimized by the JavaScript engine.

[Uzlopak]

I kind of doubt that switch case is faster.

[RafaelGSS]

Linear search is very often more efficient than Binary search when the number of items is tiny. I would be very surprised if implementing a binary search for this use case would be faster (regardless Big-O notation).

[ismailmmd]

Why don't we use hashing for this,

const methods = new Set(['POST', 'PUT', 'PATCH', 'TRACE', 'SEARCH']);

if (methods.has(method)) {
  // ....
}

I can make a PR, If this is what we are looking for. IMHO Set is way better than linear search.

[dancastillo]

I've explored options above for comparison—linear search, tree, if statement, switch statements, and sets. After conducting ~100 million comparisons, the results points to sets and switch statements as the fastest approaches.

[millette]

Thanks @dancastillo I was about to do the same. Out of curiosity I benchmarked with bun and deno too, here are those results:

Summary
  bun switch.js ran
    1.09 ± 0.17 times faster than deno run set.js
    1.12 ± 0.17 times faster than deno run if.js
    1.12 ± 0.16 times faster than deno run switch.js
    1.16 ± 0.23 times faster than bun if.js
    1.45 ± 0.28 times faster than node set.js
    1.53 ± 0.27 times faster than node switch.js
    1.55 ± 0.29 times faster than node if.js
    1.77 ± 0.33 times faster than bun set.js
   14.25 ± 2.00 times faster than deno run search.js
   18.86 ± 2.64 times faster than node search.js
   41.30 ± 5.79 times faster than deno run tree.js
   43.12 ± 6.04 times faster than bun tree.js
   50.86 ± 7.14 times faster than node tree.js
   54.16 ± 7.61 times faster than bun search.js

[gurgunday]

Maybe switch, but Sets let us centralize supported methods and they are usually as fast as it gets when used with only one type

Why don't we use hashing for this,

const methods = new Set(['POST', 'PUT', 'PATCH', 'TRACE', 'SEARCH']);

if (methods.has(method)) {
  // ....
}

I can make a PR, If this is what we are looking for. IMHO Set is way better than linear search.

This is what we do right now, and like you said, V8 probably creates an efficient hash table anyway

Maybe we could switch to a switch, but I need to see real improvement in a bench that uses Fastify