sortUniq

Laeeth Isharc via Digitalmars-d digitalmars-d at puremagic.com
Sat Jan 24 07:42:23 PST 2015


> The problem with RedBlackTree is that it's cache-unfriendly due 
> to the
> memory allocation and per-node pointers. One reason quicksort 
> performs
> so well is because it works in-place, and the partition 
> operation
> accesses elements bilinearly (i.e., two linear traversals over 
> the same
> stretch of memory interleaved with each other), so it's very 
> likely that
> most of the accesses will hit the cache (possibly even all, if 
> hardware
> prefetching is present).  Whereas with RedBlackTree, it's 
> jumping all
> over memory, so there will be a higher rate of cache misses and 
> the
> resulting slow RAM fetches. Plus, memory allocation is slooow, 
> and is
> best avoided where possible.

In an interview Stepanov said he would have used b* trees instead 
for this reason if he were writing STL today.

Here is a (dated) benchmark comparison of hash libraries:
https://attractivechaos.wordpress.com/2008/08/28/comparison-of-hash-table-libraries/


More information about the Digitalmars-d mailing list