[Caml-list] Hash consed Patricia trees

["Neuhaeusser, Martin" <martin.neuhaeusser@siemens.com>]

Dear all,

during some experiments with integer set implementations, I came across a discussion on that list that proposed to use Patricia trees and hash consing on the tree nodes' constructors to achieve maximal sharing:
http://caml.inria.fr/pub/ml-archives/caml-list/2008/03/5be97d51e2e8aab16b9e7e369a5a5533.en.html

Is anyone aware of a corresponding implementation that also has a performance benefit (or, at least, no negative performance impact) compared to standard sets or to non-hash consed Patricia trees? Or is anyone aware of a paper on that matter? 

Sadly, in all my experiments, the combination of Patricia trees with hash consing applied to the terms representing the tree has a horrible impact on performance (a slowdown by an order of magnitude). After spending some thoughts, this seems to be reasonable given the structure of a Patricia tree. In particular, we found no way to make significand use of the reflexivity properties obtained by hash consing in set operations like subset or union. In our benchmarks, the time for constructing hash-consed subtrees during set operations outweighs any gains obtained by the "physical equality = set equality" property. Or is the whole point in the earlier discussion the possibility to use hash consing tags for memoization of set operations? 

Any hints and comments are highly appreciated. It would really be great if some of the participants from the 2008 discussion could perhaps share their experience.

Best regards,
Martin