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 E05447F91C for ; Mon, 23 May 2016 16:49:46 +0200 (CEST) IronPort-PHdr: 9a23:GBgiAh2GDhlDhAgUsmDT+DRfVm0co7zxezQtwd8ZsekWKPad9pjvdHbS+e9qxAeQG96LurQf2qGJ7OjJYi8p39WoiDg6aptCVhsI2409vjcLJ4q7M3D9N+PgdCcgHc5PBxdP9nC/NlVJSo6lPwWB6kO74TNaIBjjLw09fr2zQd6DyZ/mnL/ts7ToICx2xxOFKYtoKxu3qQiD/uI3uqBFbpgL9x3Sv3FTcP5Xz247bXianhL7+9vitMU7q3cYk7sb+sVBSaT3ebgjBfwdVWx+cjN92Mq+/z/OUAuG62YHSWgM1lJtChLZ7RewFsP0uzHmt+w73iSHPcT7UKsvVC6K9KZmTRLuk2EMMDtvo0/Njcklt6NepxTpjAZiyojZe8nBL/t7eaWbdskHTGxMRYALD3QeKobgf80IFeVXbrUQlJX0u1Zb9Uj2PgKrHu66j2YQ3nI= Authentication-Results: mail3-smtp-sop.national.inria.fr; spf=Neutral smtp.pra=simon.cruanes.2007@m4x.org; spf=Pass smtp.mailfrom=SRS0=CqG+=RQ=m4x.org=simon.cruanes.2007@bounces.m4x.org; spf=Pass smtp.helo=postmaster@mx1.polytechnique.org Received-SPF: Neutral (mail3-smtp-sop.national.inria.fr: domain of simon.cruanes.2007@m4x.org does not assert whether or not 129.104.30.34 is permitted sender) identity=pra; client-ip=129.104.30.34; receiver=mail3-smtp-sop.national.inria.fr; envelope-from="SRS0=CqG+=RQ=m4x.org=simon.cruanes.2007@bounces.m4x.org"; x-sender="simon.cruanes.2007@m4x.org"; x-conformance=sidf_compatible; x-record-type="spf2.0" Received-SPF: Pass (mail3-smtp-sop.national.inria.fr: domain of SRS0=CqG+=RQ=m4x.org=simon.cruanes.2007@bounces.m4x.org designates 129.104.30.34 as permitted sender) identity=mailfrom; client-ip=129.104.30.34; receiver=mail3-smtp-sop.national.inria.fr; envelope-from="SRS0=CqG+=RQ=m4x.org=simon.cruanes.2007@bounces.m4x.org"; x-sender="SRS0=CqG+=RQ=m4x.org=simon.cruanes.2007@bounces.m4x.org"; x-conformance=sidf_compatible; x-record-type="spf2.0" Received-SPF: Pass (mail3-smtp-sop.national.inria.fr: domain of postmaster@mx1.polytechnique.org designates 129.104.30.34 as permitted sender) identity=helo; client-ip=129.104.30.34; receiver=mail3-smtp-sop.national.inria.fr; envelope-from="SRS0=CqG+=RQ=m4x.org=simon.cruanes.2007@bounces.m4x.org"; x-sender="postmaster@mx1.polytechnique.org"; x-conformance=sidf_compatible; x-record-type="v=spf1" X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: A0DfAQBFF0NXgCIeaIFchA19skGHTYIbhTOBazoSAQEBAQEBAQERAQELCwkJIS+CLYIWAQUjSQ0QCyEhAgIPBUmIQgUJsyKRPSMOinSCYIRgglkFkzeEdggBAYYAgniFHoFzTocthTiPTCYBgkAdgU1sAQGJTwEBAQ X-IPAS-Result: A0DfAQBFF0NXgCIeaIFchA19skGHTYIbhTOBazoSAQEBAQEBAQERAQELCwkJIS+CLYIWAQUjSQ0QCyEhAgIPBUmIQgUJsyKRPSMOinSCYIRgglkFkzeEdggBAYYAgniFHoFzTocthTiPTCYBgkAdgU1sAQGJTwEBAQ X-IronPort-AV: E=Sophos;i="5.26,356,1459807200"; d="asc'?scan'208";a="178716476" Received: from mx1.polytechnique.org ([129.104.30.34]) by mail3-smtp-sop.national.inria.fr with ESMTP/TLS/DHE-RSA-AES256-GCM-SHA384; 23 May 2016 16:49:45 +0200 Received: from nunchakus.loria.fr (nunchakus.loria.fr [152.81.10.98]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ssl.polytechnique.org (Postfix) with ESMTPSA id 1A1B9564A07; Mon, 23 May 2016 16:49:45 +0200 (CEST) Date: Mon, 23 May 2016 16:49:44 +0200 From: Simon Cruanes To: "Neuhaeusser, Martin" Cc: "caml-list@inria.fr" Message-ID: <20160523144943.GV25494@nunchakus.loria.fr> References: <965631B03C670145ABB9F693E51622530D1279D7@DENBGAT9EK5MSX.ww902.siemens.net> MIME-Version: 1.0 Content-Type: multipart/signed; micalg=pgp-sha256; protocol="application/pgp-signature"; boundary="Q0Mu3I7vbdq4WOv6" Content-Disposition: inline In-Reply-To: <965631B03C670145ABB9F693E51622530D1279D7@DENBGAT9EK5MSX.ww902.siemens.net> User-Agent: Mutt/1.5.23.1 (2014-03-12) X-AV-Checked: ClamAV using ClamSMTP at svoboda.polytechnique.org (Mon May 23 16:49:45 2016 +0200 (CEST)) X-Spam-Flag: No, tests=bogofilter, spamicity=0.000055, queueID=44F37564A08 X-Org-Mail: simon.cruanes.2007@polytechnique.org Subject: Re: [Caml-list] Hash consed Patricia trees --Q0Mu3I7vbdq4WOv6 Content-Type: text/plain; charset=utf-8 Content-Disposition: inline Content-Transfer-Encoding: quoted-printable 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/CCHashconse= dSet.mli https://github.com/c-cube/ocaml-containers/blob/master/src/data/CCHashconse= dSet.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 =C3=A9crit : > Dear all, >=20 > during some experiments with integer set implementations, I came across a= discussion on that list that proposed to use Patricia trees and hash consi= ng on the tree nodes' constructors to achieve maximal sharing: > http://caml.inria.fr/pub/ml-archives/caml-list/2008/03/5be97d51e2e8aab16b= 9e7e369a5a5533.en.html >=20 > Is anyone aware of a corresponding implementation that also has a perform= ance benefit (or, at least, no negative performance impact) compared to sta= ndard sets or to non-hash consed Patricia trees? Or is anyone aware of a pa= per on that matter?=20 >=20 > Sadly, in all my experiments, the combination of Patricia trees with hash= consing applied to the terms representing the tree has a horrible impact o= n performance (a slowdown by an order of magnitude). After spending some th= oughts, 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 s= et operations outweighs any gains obtained by the "physical equality =3D se= t equality" property. Or is the whole point in the earlier discussion the p= ossibility to use hash consing tags for memoization of set operations?=20 >=20 > Any hints and comments are highly appreciated. It would really be great i= f some of the participants from the 2008 discussion could perhaps share the= ir experience. --=20 Simon Cruanes http://weusepgp.info/ key 49AA62B6, fingerprint 949F EB87 8F06 59C6 D7D3 7D8D 4AC0 1D08 49AA 62B6 --Q0Mu3I7vbdq4WOv6 Content-Type: application/pgp-signature; name="signature.asc" -----BEGIN PGP SIGNATURE----- Version: GnuPG v2 iQIcBAEBCAAGBQJXQxiHAAoJEErAHQhJqmK2eBkP/R2AqxjQskvT9CvYiOoh9kmF XRqwS8H/DQ5JXc7cbt3WuJGmscOAHytw3awAQMvSmflCJzR3+och4YTdktnBDJlF 8DqajbHXMlk2gxsGFzqwVgWwZAk6FwGGwsy4duXbjaMIbcHzRWu+Kxkmvm/oAEAe qzIwVrarMXR2yfwhl+YVyuMzaEXwLnOlwWocj/L6EDpcTvPd6x+x4S4TAde4CvbD 5d/Ufn2K0RtNFO88MzvUq9ItJdtWr+UX7FUInycdS5enp9YrXXeCcGU0jzldTXxC vgs+LqlByEHIKk15fXM1qIG1ydvPC6DeLuMSgs2vA5Z9FKTRnS7DPrRgonjiOQOZ HpRNTVN7VV3bW41QvgmdzPZdkpZFq0GKRMNXBnaPlo1v1HfA8Ol06kTNrCk3kB8G RUu+zBFUEutu+aufOUYDQZOp/wGhpQWjLJ4505grT8SV0Y9GsDOqED/3DG1QJhL9 OHsk8sA/Iebu50jFAqUwDBgQDiRDHzxXxu9UA9YZoaKxKSgo1mTkOhAGB9gGVN1T tfSoJbS8cQER3vnga+D0EovvMq4NJ1D71tlxGXdpbn2YrO7uGqk/uIFsNQy2rnpm uG4CA0GkcIMJrARs76QjtPDmULyVWERCbD1tKjzMqj65g+Jk5B8uPvv6r0DYp0+3 Pinbg+Kae4X5Ge7heens =YH9W -----END PGP SIGNATURE----- --Q0Mu3I7vbdq4WOv6--