Ternary Search Trees

[bearophile]

Robert Fraser:
> Why is the default block size so freaking huge (16kb)?<

If the block is too much small you waste too much time allocating small blocks of memory (about as much time as you waste allocating the single tree nodes).
If the block is too much big you waste empty nodes in the last block, and over a certain size you don't gain much anyway. And too much big chunks don't fit in the data part of the L1 cache anyway (it's 32 KB on many CPUs).
>From experiments I have seen that usually having a block bigger than 64 KB lets you gain very little. And having blocks less than 4-8 KB is a waste of time. 16-32 KB is the faster and on a 2 GB RAM PC it doesn't waste much RAM. If you want to save some RAM you can reduce that value at compile time.

Bye,
bearophile