Statistical performance of purely functional maps and sets

Question

Given a data structure specification such as a purely functional map with known complexity bounds, one has to pick between several implementations. There is some folklore on how to pick the right one, for example Red-Black trees are considered to be generally faster, but AVL trees have better performance on work loads with many lookups.

1. Is there a systematic presentation (published paper) of this knowledge (as relates to sets/maps)? Ideally I would like to see statistical analysis performed on actual software. It might conclude, for example, that there are N typical kinds of map usage, and list the input probability distribution for each.

2. Are there systematic benchmarks that test map and set performance on different distributions of inputs?

3. Are there implementations that use adaptive algorithms to change representation depending on actual usage?

Answer 1

These are basically research topics, and the results are generally given in the form of conclusions, while the statistical data is hidden. One can have statistical analysis on their own data though.

For the benchmarks, better go through the implementation details.

The 3rd part of the question is a very subjective matter, and the actual intentions may never be known at the time of implementation. However, languages like perl do their best to implement highly optimized solutions to every operation.

Following might be of help: Purely Functional Data Structures by Chris Okasaki http://www.cs.cmu.edu/~rwh/theses/okasaki.pdf