nodejs
address bad usage of TST
This relates to performance of parseHeaders
Rationale
Inserting keys to TST in order yields the worst performance of this data structure. It is similar to inserting keys to a binary search tree in order makes it degenerate to a link list.
Randomize the insertion order simply works, but we do not want any potential instable performance, so I take a snapshot of one randomized insertion order that works well
Changes
Randomize the insertion order of the well known header keys
Features
N/A
Bug Fixes
N/A
Breaking Changes and Deprecations
N/A
Status
- [x] I have read and agreed to the Developer's Certificate of Origin
- [x] Tested
- [x] Benchmarked (optional)
- [S] Documented
- [ ] Review ready
- [ ] In review
- [ ] Merge ready
If not properly shuffled to balance the left and right sides, it will cause a bad case and further degrade performance. This is similar to the problem with binary trees.
If not properly shuffled to balance the left and right sides, it will cause a bad case and further degrade performance. This is similar to the problem with binary trees.
Given the array is sorted, randomly retrieving item from it and inserting to a TST/Binary search tree should yield a balanced tree. And the bottom line is that we definitely don't want to insert items to a TST in order because this is the worst case of this data structure.
Maybe I can print out the TST and do a comparison? I did a non formal one before and it turned out that when searching for Via we actually saved a lot of node traversing
However I would prefer if:
- a script to generate a "working well" snapshot would be placed in
scripts - a test that verifies that the snapshots contains all keys is added
