From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.1.3 (2006-06-01) on yquem.inria.fr X-Spam-Level: * X-Spam-Status: No, score=1.4 required=5.0 tests=AWL,SPF_SOFTFAIL autolearn=disabled version=3.1.3 X-Original-To: caml-list@yquem.inria.fr Delivered-To: caml-list@yquem.inria.fr Received: from mail4-relais-sop.national.inria.fr (mail4-relais-sop.national.inria.fr [192.134.164.105]) by yquem.inria.fr (Postfix) with ESMTP id 6373DBC37 for ; Thu, 17 Sep 2009 11:08:09 +0200 (CEST) X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AvgBABOZsUqEpqxqmWdsb2JhbACbJwEBAQEBCAsKBxOyTwiQEIJACIFQBQ X-IronPort-AV: E=Sophos;i="4.44,402,1249250400"; d="scan'208";a="46750164" Received: from cirse-out.extra.cea.fr ([132.166.172.106]) by mail4-smtp-sop.national.inria.fr with ESMTP/TLS/DHE-RSA-AES256-SHA; 17 Sep 2009 11:08:08 +0200 Received: from pisaure.intra.cea.fr (pisaure.intra.cea.fr [132.166.88.21]) by cirse.extra.cea.fr (8.14.2/8.14.2/CEAnet-Internet-out-2.0) with ESMTP id n8H97v7C006075 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NOT); Thu, 17 Sep 2009 11:07:57 +0200 Received: from muguet1.intra.cea.fr (muguet1.intra.cea.fr [132.166.192.6]) by pisaure.intra.cea.fr (8.14.2/8.14.2) with ESMTP id n8H97v4w016116; Thu, 17 Sep 2009 11:07:57 +0200 (envelope-from Pascal.CUOQ@cea.fr) Received: from levau.intra.cea.fr (levau.intra.cea.fr [132.166.88.52]) by muguet1.intra.cea.fr (8.13.8/8.13.8/CEAnet-Intranet-out-1.1) with ESMTP id n8H97vQG031369; Thu, 17 Sep 2009 11:07:57 +0200 Received: from LAXA.intra.cea.fr ([132.166.64.42]) by levau.intra.cea.fr with Microsoft SMTPSVC(6.0.3790.3959); Thu, 17 Sep 2009 11:07:56 +0200 X-MimeOLE: Produced By Microsoft Exchange V6.5 Content-class: urn:content-classes:message MIME-Version: 1.0 Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: quoted-printable Subject: Re: Sets and home-made ordered types Date: Thu, 17 Sep 2009 11:07:56 +0200 Message-ID: <5EFD4D7AC6265F4D9D3A849CEA9219191AB20E@LAXA.intra.cea.fr> X-MS-Has-Attach: X-MS-TNEF-Correlator: Thread-Topic: Sets and home-made ordered types Thread-Index: Aco3c4ikCI7FEL2JRwqJJ3XKU1g3wAAAWarC References: <20090917030607.927BCBCA9@yquem.inria.fr> <5EFD4D7AC6265F4D9D3A849CEA9219191AB20D@LAXA.intra.cea.fr> <4AB1F740.9020404@cs.unibo.it> From: "CUOQ Pascal" To: "Matthias Puech" Cc: X-OriginalArrivalTime: 17 Sep 2009 09:07:56.0559 (UTC) FILETIME=[589949F0:01CA3776] X-Spam: no; 0.00; home-made:01 cuoq:01 cuoq:01 pointer:01 pointer:01 node:01 pointers:01 subtrees:01 node:01 height:98 cea:01 structures:02 tree:02 dynamic:03 overhead:04 > So what, one pointer more for each association=20 > in the Map? That would be rather acceptable (but still not ideal, = sorry=20 > I'm very demanding). You were already paying the price of "one pointer more" many times over and were not even thinking about it. One more will not make any difference. You have to realize that each node already carries a height, two pointers to subtrees, and take into account the one-word overhead for the block header. We're not doubling the size of each tree node here, we're increasing it from 5 to 6 words. Pascal PS: You make up for the overhead by having dynamic structures that are just the right size, and by taking advantage of sharing, of course.