From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Original-To: caml-list@sympa.inria.fr Delivered-To: caml-list@sympa.inria.fr Received: from mail3-relais-sop.national.inria.fr (mail3-relais-sop.national.inria.fr [192.134.164.104]) by sympa.inria.fr (Postfix) with ESMTPS id 667307F926 for ; Mon, 23 May 2016 16:33:22 +0200 (CEST) IronPort-PHdr: 9a23:SW3EFR2KSYeVzdVYsmDT+DRfVm0co7zxezQtwd8ZsegRI/ad9pjvdHbS+e9qxAeQG96LurQf2qGJ7+jJYi8p39WoiDg6aptCVhsI2409vjcLJ4q7M3D9N+PgdCcgHc5PBxdP9nC/NlVJSo6lPwWB6kO74TNaIBjjLw09fr2zQd6DyZ/mnL/us7ToICx2xxOFKYtoKxu3qQiD/uI3uqBFbpgL9x3Sv3FTcP5Xz247bXianhL7+9vitMU7q3cY6Lod8JsKWqz/e+E8TKdEJDUgKWE8osPx/1GXRgKK4j4YU34KuhtOGQnMqh/gCMTfqCz/46Bb1TSaNMDrVqs5Q3Dqyq5xVB7uwm9TMjcj7GDRzMp9kaJSrQ+6vBFl65XVbYSYMuE4daTYK4BJDVFdV9pcAnQSSri3aJECWrIM Authentication-Results: mail3-smtp-sop.national.inria.fr; spf=None smtp.pra=martin.neuhaeusser@siemens.com; spf=None smtp.mailfrom=martin.neuhaeusser@siemens.com; spf=None smtp.helo=postmaster@thoth.sbs.de Received-SPF: None (mail3-smtp-sop.national.inria.fr: no sender authenticity information available from domain of martin.neuhaeusser@siemens.com) identity=pra; client-ip=192.35.17.2; receiver=mail3-smtp-sop.national.inria.fr; envelope-from="martin.neuhaeusser@siemens.com"; x-sender="martin.neuhaeusser@siemens.com"; x-conformance=sidf_compatible Received-SPF: None (mail3-smtp-sop.national.inria.fr: no sender authenticity information available from domain of martin.neuhaeusser@siemens.com) identity=mailfrom; client-ip=192.35.17.2; receiver=mail3-smtp-sop.national.inria.fr; envelope-from="martin.neuhaeusser@siemens.com"; x-sender="martin.neuhaeusser@siemens.com"; x-conformance=sidf_compatible Received-SPF: None (mail3-smtp-sop.national.inria.fr: no sender authenticity information available from domain of postmaster@thoth.sbs.de) identity=helo; client-ip=192.35.17.2; receiver=mail3-smtp-sop.national.inria.fr; envelope-from="martin.neuhaeusser@siemens.com"; x-sender="postmaster@thoth.sbs.de"; x-conformance=sidf_compatible X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: A0CpAADZE0NXgAIRI8BchA19Brl6AQ2BdSSFMzoCgS84FAEBAQEBAQEBEQEBCQ0JCSEkC4Itghw6JgwfASoUQiYBBBuIJwUJoy6hToYog0mFRIMqgi4FmDEGAYEuhFGCeIdfhwaFX49MHgEBgXgBCwFCHYFLbgEBiFABfgEBAQ X-IPAS-Result: A0CpAADZE0NXgAIRI8BchA19Brl6AQ2BdSSFMzoCgS84FAEBAQEBAQEBEQEBCQ0JCSEkC4Itghw6JgwfASoUQiYBBBuIJwUJoy6hToYog0mFRIMqgi4FmDEGAYEuhFGCeIdfhwaFX49MHgEBgXgBCwFCHYFLbgEBiFABfgEBAQ X-IronPort-AV: E=Sophos;i="5.26,356,1459807200"; d="scan'208";a="178713252" Received: from thoth.sbs.de ([192.35.17.2]) by mail3-smtp-sop.national.inria.fr with ESMTP/TLS/DHE-RSA-AES256-GCM-SHA384; 23 May 2016 16:33:21 +0200 Received: from mail1.sbs.de (mail1.sbs.de [192.129.41.35]) by thoth.sbs.de (8.15.2/8.15.2) with ESMTPS id u4NEXKvm028633 (version=TLSv1.2 cipher=DHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK) for ; Mon, 23 May 2016 16:33:20 +0200 Received: from DEFTHW99ERMMSX.ww902.siemens.net (defthw99ermmsx.ww902.siemens.net [139.22.70.142]) by mail1.sbs.de (8.15.2/8.15.2) with ESMTPS id u4NEX6SG024614 (version=TLSv1 cipher=AES256-SHA bits=256 verify=FAIL) for ; Mon, 23 May 2016 16:33:20 +0200 Received: from DENBGAT9ERHMSX.ww902.siemens.net (139.22.70.143) by DEFTHW99ERMMSX.ww902.siemens.net (139.22.70.142) with Microsoft SMTP Server (TLS) id 14.3.294.0; Mon, 23 May 2016 16:33:08 +0200 Received: from DENBGAT9EK5MSX.ww902.siemens.net ([169.254.12.98]) by DENBGAT9ERHMSX.ww902.siemens.net ([139.22.70.143]) with mapi id 14.03.0294.000; Mon, 23 May 2016 16:33:07 +0200 From: "Neuhaeusser, Martin" To: "caml-list@inria.fr" Thread-Topic: Hash consed Patricia trees Thread-Index: AdG0/3eivl5jwxsMTR634Jl9JcT5SQ== Date: Mon, 23 May 2016 14:33:07 +0000 Message-ID: <965631B03C670145ABB9F693E51622530D1279D7@DENBGAT9EK5MSX.ww902.siemens.net> Accept-Language: de-DE, en-US Content-Language: de-DE X-MS-Has-Attach: X-MS-TNEF-Correlator: x-originating-ip: [139.22.70.55] Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: quoted-printable MIME-Version: 1.0 Subject: [Caml-list] Hash consed Patricia trees Dear all, during some experiments with integer set implementations, I came across a d= iscussion 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/5be97d51e2e8aab16b9e= 7e369a5a5533.en.html Is anyone aware of a corresponding implementation that also has a performan= ce benefit (or, at least, no negative performance impact) compared to stand= ard sets or to non-hash consed Patricia trees? Or is anyone aware of a pape= r on that matter?=20 Sadly, in all my experiments, the combination of Patricia trees with hash c= onsing applied to the terms representing the tree has a horrible impact on = performance (a slowdown by an order of magnitude). After spending some thou= ghts, this seems to be reasonable given the structure of a Patricia tree. I= n particular, we found no way to make significand use of the reflexivity pr= operties obtained by hash consing in set operations like subset or union. I= n our benchmarks, the time for constructing hash-consed subtrees during set= operations outweighs any gains obtained by the "physical equality =3D set = equality" property. Or is the whole point in the earlier discussion the pos= sibility to use hash consing tags for memoization of set operations?=20 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