Re: [Caml-list] Hash consed Patricia trees

[Simon Cruanes <simon.cruanes.2007@m4x.org>]

[-- Attachment #1: Type: text/plain, Size: 2501 bytes --]

Hi,

I toyed with an example of that some time ago, implementing a set of
integers with hashconsing of every sub-tree:
https://github.com/c-cube/ocaml-containers/blob/master/src/data/CCHashconsedSet.mli
https://github.com/c-cube/ocaml-containers/blob/master/src/data/CCHashconsedSet.ml
(there are some tests, but for serious use it might be nice to have more
tests).

As far as I can tell after years spent using hashconsed terms,
hashconsing is only useful for quite specific cases. You need to "read"
(typically, use the unique integer, physically compare, etc.) a LOT more
than you "write" (create new structures); or you might want the
reduction in memory if many similar objects are built. In this
particular case, I think it would be worth it if set comparison was
extremely frequent.

Cheers!

Le Mon, 23 May 2016, Neuhaeusser, Martin a écrit :
> 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.


-- 
Simon Cruanes

http://weusepgp.info/
key 49AA62B6, fingerprint 949F EB87 8F06 59C6 D7D3  7D8D 4AC0 1D08 49AA 62B6

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 819 bytes --]