From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from mail4-relais-sop.national.inria.fr (mail4-relais-sop.national.inria.fr [192.134.164.105]) by walapai.inria.fr (8.13.6/8.13.6) with ESMTP id pBUJ1lcx028534 for ; Fri, 30 Dec 2011 20:01:47 +0100 X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AhcCAJAI/k5RZ90xgmdsb2JhbABDrE8iAQELCwkHFgMigXIBAQEEeRACAQgOCgokMiUCBAENDYd0tVqLLGMEiASMfpI0 X-IronPort-AV: E=Sophos;i="4.71,433,1320620400"; d="scan'208";a="125095411" Received: from mtaout03-winn.ispmail.ntl.com ([81.103.221.49]) by mail4-smtp-sop.national.inria.fr with ESMTP; 30 Dec 2011 20:01:42 +0100 Received: from aamtaout02-winn.ispmail.ntl.com ([81.103.221.35]) by mtaout03-winn.ispmail.ntl.com (InterMail vM.7.08.04.00 201-2186-134-20080326) with ESMTP id <20111230190141.WIYM21018.mtaout03-winn.ispmail.ntl.com@aamtaout02-winn.ispmail.ntl.com>; Fri, 30 Dec 2011 19:01:41 +0000 Received: from romulus.metastack.com ([81.102.132.77]) by aamtaout02-winn.ispmail.ntl.com (InterMail vG.3.00.04.00 201-2196-133-20080908) with ESMTP id <20111230190141.XLWD5924.aamtaout02-winn.ispmail.ntl.com@romulus.metastack.com>; Fri, 30 Dec 2011 19:01:41 +0000 Received: from remus.metastack.local ([172.16.0.1]) by romulus.metastack.com (8.14.2/8.14.2) with ESMTP id pBUJ1a3n011928 (version=TLSv1/SSLv3 cipher=AES128-SHA bits=128 verify=FAIL); Fri, 30 Dec 2011 19:01:37 GMT Received: from Remus.metastack.local ([fe80::547c:3c42:e1da:eda2]) by Remus.metastack.local ([fe80::547c:3c42:e1da:eda2%10]) with mapi id 14.01.0355.002; Fri, 30 Dec 2011 19:01:35 +0000 From: David Allsopp To: Yaron Minsky , Gerd Stolpmann CC: "caml-list@inria.fr" Thread-Topic: [Caml-list] Hashtbl and security Thread-Index: AQHMxxJPHvxoftPPtU+H+444ZhfPs5X0l3eAgAAinoA= Date: Fri, 30 Dec 2011 19:01:33 +0000 Message-ID: References: <1325263446.5036.104.camel@samsung> In-Reply-To: Accept-Language: en-GB, en-US Content-Language: en-US X-MS-Has-Attach: X-MS-TNEF-Correlator: x-originating-ip: [172.16.0.7] Content-Type: text/plain; charset="iso-8859-1" MIME-Version: 1.0 Organization: MetaStack Solutions Ltd. X-Scanned-By: MIMEDefang 2.65 on 81.102.132.77 X-Cloudmark-Analysis: v=1.1 cv=JvdXmxIgLJv2/GthKqHpGJEEHukvLcvELVXUanXFreg= c=1 sm=0 a=40hZHaDki8MA:10 a=5U82IvIxVIkA:10 a=cTs9vV391PwA:10 a=8nJEP1OIZ-IA:10 a=xqWC_Br6kY4A:10 a=CQu0B7GFCcew38HD_ngA:9 a=wPNLvfGTeEIA:10 a=HpAAvcLHHh0Zw7uRqdWCyQ==:117 Content-Transfer-Encoding: 8bit X-MIME-Autoconverted: from quoted-printable to 8bit by walapai.inria.fr id pBUJ1lcx028534 Subject: RE: [Caml-list] Hashtbl and security Yaron Minsky wrote: > For just this reason, the hashtables in Core have been reimplemented to use an > AVL tree in the buckets.  That way, even when you have pathological collisions, > you degrade gracefully to O(log n) per operation, instead of O(n), where n is > the number of keys in the hashtable. I'm resisting the temptation to hack-it-and-see: does your implementation do anything clever to maintain Hashtbl's O(1) insertion time (e.g. Hashtbl.add updates a list and then the first call to Hashtbl.find or Hashtbl.mem "moves" any items from the list to the AVL). Or does doing that impact "general" performance too much? In the POST web scenario (or processing HTTP request headers), for example, "degrading" Hashtbl.add from O(1) to O(log n) is only acceptable if you know that you'll query all the fields in the POST (which isn't necessarily true). David