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=0.0 required=5.0 tests=none autolearn=disabled version=3.1.3 Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by yquem.inria.fr (Postfix) with ESMTP id 33936BC68 for ; Sat, 11 Nov 2006 21:31:56 +0100 (CET) Received: from deckard.concept-micro.com ([82.228.75.25]) by concorde.inria.fr (8.13.6/8.13.6) with ESMTP id kABKVpTe028304 for ; Sat, 11 Nov 2006 21:31:55 +0100 X-Envelope-From: petchema@concept-micro.com X-Envelope-To: Received: from polo.concept-micro.com (root@localhost [127.0.0.1]) by deckard.concept-micro.com (8.13.8/8.13.8/Pierre Etchemaite - 20/05/03) with SMTP id kABKVTm9020729 for ; Sat, 11 Nov 2006 21:31:30 +0100 Date: Sat, 11 Nov 2006 21:31:29 +0100 From: Pierre =?UTF-8?B?RXRjaGVtYcOvdMOp?= To: caml-list@yquem.inria.fr Subject: Importance of weak hash tables initial size ? Message-Id: <20061111213129.5855c21b.petchema@concept-micro.com> Organization: Concept Micro 33 SARL X-Mailer: Sylpheed version 2.2.6 (GTK+ 2.6.4; i386-pc-linux-gnu) X-Face: #eTSL0BRng*(!i1R^[)oey6`SJHR{3Sf4dc;"=af8%%;d"%\#"Hh0#lYfJBcm28zu3r^/H ^ d6!9/eElH'p0'*,L3jz_UHGw"+[c1~ceJxAr(^+{(}|DTZ"],r[jSnwQz$/K&@MT^?J#p"n[J>^O[ \ "%*lo](u?0p=T:P9g(ta[hH@uvv X-TRP: honey@concept-micro.com Mime-Version: 1.0 Content-Type: text/plain; charset=US-ASCII Content-Transfer-Encoding: 7bit X-Miltered: at concorde with ID 45563337.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Spam: no; 0.00; hash:01 hash:01 hashtbl:01 short:01 pierre:02 pierre:02 weak:04 weak:04 size:95 size:95 table:93 table:93 uses:06 rationale:08 constant:08 Hi all, I noticed that while the initial size of regular hash tables does not matter too much for performance (beside the cost of additional resizes and elements rehashing to reach the final size), creating weak hash tables with a small initial size leads to a weak hash table with a much higher load factor than the same program with a larger initial hash table size. For short, large weak hash tables have a significantly worse access time performance when created with a small initial size. Specifically, what is the rationale behind the t.limit <- t.limit + 2 in weak.ml ? It may be ok to use a higher load factor than Hashtbl (who uses a constant limit of 2), since there's some overallocation going on in each bucket of weak hash tables, but I fail to understand why the load factor limit should also be raised with each resizing... Best regards, Pierre.