digitalmars.D - Small collections optimizations
- bearophile (9/19) May 20 2012 A stackoverflow site question:...
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
May 20 2012