Small collections optimizations

[bearophile]

A stackoverflow site question: "What are the underlying data 
structures used for Redis?":

An answer:
http://stackoverflow.com/questions/9625246/what-are-the-underlying-data-structures-used-for-redis/9626334#9626334

A part of the answer:
>But when lists, sets, and sorted sets are small in number of 
>items and size of the largest values, a different, much more 
>compact encoding is used. This encoding differs for different 
>types, but has the feature that it is a compact blob of data 
>that often forces an O(N) scan for every operation. Since we use 
>this format only for small objects this is not an issue; 
>scanning a small O(N) blob is cache oblivious so practically 
>speaking it is very fast, and when there are too many elements 
>the encoding is automatically switched to the native encoding 
>(linked list, hash, and so forth).<

It reminds us of the usefulneess of having "small AA" (and small 
set, small linked list) optimizations.

Bye,
bearophile