From: David Allsopp <dra-news@metastack.com>
To: Yaron Minsky <yminsky@janestreet.com>,
Gerd Stolpmann <info@gerd-stolpmann.de>
Cc: "caml-list@inria.fr" <caml-list@inria.fr>
Subject: RE: [Caml-list] Hashtbl and security
Date: Fri, 30 Dec 2011 19:01:33 +0000 [thread overview]
Message-ID: <E51C5B015DBD1348A1D85763337FB6D9C25F6345@Remus.metastack.local> (raw)
In-Reply-To: <CACLX4jQwBZndqwq6AQiaE74Za7wvKumT_PERj6_h0-gLONOEow@mail.gmail.com>
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
next prev parent reply other threads:[~2011-12-30 19:01 UTC|newest]
Thread overview: 34+ messages / expand[flat|nested] mbox.gz Atom feed top
2011-12-30 16:44 Gerd Stolpmann
2011-12-30 16:48 ` Yaron Minsky
2011-12-30 19:01 ` David Allsopp [this message]
2011-12-30 20:52 ` Yaron Minsky
2011-12-30 21:54 ` Gerd Stolpmann
2011-12-30 17:06 ` Xavier Leroy
2011-12-30 21:16 ` Gerd Stolpmann
2011-12-31 0:57 ` oliver
2011-12-31 0:59 ` oliver
2012-01-01 12:52 ` Richard W.M. Jones
2012-01-01 17:29 ` Xavier Leroy
2012-01-01 21:04 ` Gerd Stolpmann
2012-01-01 23:24 ` oliver
2012-01-01 23:58 ` Gerd Stolpmann
2012-01-02 1:43 ` oliver
2012-01-04 17:56 ` Damien Doligez
2012-01-04 21:52 ` oliver
2012-01-02 9:34 ` David MENTRE
2012-01-30 10:54 ` Goswin von Brederlow
2011-12-30 17:40 ` rixed
2011-12-30 17:52 ` Edgar Friendly
2011-12-31 1:02 ` oliver
2011-12-31 0:33 ` oliver
2012-01-02 0:21 ` Shawn Wagner
2012-01-02 14:52 ` Gerd Stolpmann
2012-01-30 10:51 ` Goswin von Brederlow
2012-01-31 14:16 ` Gerd Stolpmann
2012-02-08 9:41 ` Goswin von Brederlow
2012-02-08 10:43 ` Philippe Wang
2012-02-08 10:46 ` AUGER Cédric
2012-02-09 13:22 ` Goswin von Brederlow
2012-02-09 14:48 ` Gerd Stolpmann
2012-02-08 11:12 ` Gerd Stolpmann
2012-02-09 13:11 ` Goswin von Brederlow
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=E51C5B015DBD1348A1D85763337FB6D9C25F6345@Remus.metastack.local \
--to=dra-news@metastack.com \
--cc=caml-list@inria.fr \
--cc=info@gerd-stolpmann.de \
--cc=yminsky@janestreet.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).