From mboxrd@z Thu Jan 1 00:00:00 1970 Received: (from weis@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id UAA26052 for caml-red; Fri, 26 May 2000 20:52:01 +0200 (MET DST) Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id TAA26441 for ; Thu, 25 May 2000 19:08:54 +0200 (MET DST) Received: from mail3.microsoft.com (mail3.microsoft.com [131.107.3.123]) by concorde.inria.fr (8.10.0/8.10.0) with SMTP id e4PH8n910305 for ; Thu, 25 May 2000 19:08:53 +0200 (MET DST) Received: from 157.54.9.100 by mail3.microsoft.com (InterScan E-Mail VirusWall NT); Thu, 25 May 2000 10:08:47 -0700 (Pacific Daylight Time) Received: by INET-IMC-03 with Internet Mail Service (5.5.2651.58) id ; Thu, 25 May 2000 10:08:47 -0700 Message-ID: <783D93998201D311B0CF00805FEAA07B7E9234@RED-MSG-42> From: Manuel Fahndrich To: "'dsl@tepkom.ru'" , caml-list@pauillac.inria.fr Subject: RE: Alternative generic hash function Date: Thu, 25 May 2000 10:08:38 -0700 X-Mailer: Internet Mail Service (5.5.2651.58) Sender: weis Thanks for all the answers. Yes, one clearly would need information about mutable data fields at runtime in order to implement hash_pure. Dmitri's suggestion on using block length and tag for computing the hash is essentially the 0th approximation of hash_pure, since we know that the length and tag of a block are immutable. Noone has made any comments about the managing of explicit id's in order to get around the problem I sketched. I've written a lot of code with such id generation and it is not an ideal solution. First, there needs to be an id generator, which introduces a global variable into your program. Second, what happens if you wrap around in the id space (e.g. ints). I can speak from experience that wrap around happens, namely when generating structures with id's repeatedly, where most of them are garbage collected away. At any point, there are only few structures live, but whenever we create a new one, we still need a fresh id. In general, one would have to be able to reuse id's, and thus connect with the garbage collector through weak pointers etc... It gets pretty complicated. My point is that the memory address of an object is an ideal id for equality comparisons. The space of addresses is already managed by the language, such that reusable id's can be generated cheaply. With copying garbage collection, id's change over time, which is not a problem for equality testing, but breaks hashing on them. The only reliable part of a datastructure to use in computing a hash is the immutable part. -Manuel BTW, the same problem arises with the polymorphic comparison functions: Objective Caml version 3.00 # let x = ref 1;; val x : int ref = {contents=1} # let y = ref 5;; val y : int ref = {contents=5} # x < y;; - : bool = true # x := 10;; - : unit = () # x < y;; - : bool = false Of course, using an analogous pure comparison operator would result in a preorder, not a total order. -----Original Message----- From: Dmitri Lomov [mailto:dsl@tepkom.ru] Sent: Thursday, May 25, 2000 12:38 AM To: caml-list@pauillac.inria.fr Cc: Manuel Fahndrich Subject: Re: Alternative generic hash function AFA I understand, Hastable.hash_pure will be hard to implement in run-time, as now at run-time it is not known whether given data structure, or given data structure field is mutable or not. Such information is not propagated to run-time by ocaml compiler. Possibly your option here is to divide your data structure into mutable and immutable parts, and than use Hashtable.hash on immutable part. Then all will work well. This, however, does not cover the example you present. But actually the nature of hashing assumes the hashed object has some immutable part. For example, when hashing strings you do not assume to get the same hash value for mutable string if you change some character of it. In your example everything in an object changes - it does not have any immutable properties/elements/fields to "hook" hash to. By the way, a rough hashing function for all O'Caml objects can be based on block length and/or tag (they are accesible via Obj module). Such hash function will tend to be very biased, due to biased distribution of lengths and tags, but in very bad situations it may help. I use such function in my (forthcoming :-)) dynamic code generation library for O'Caml to keep external references from code block. Regards, Dmitri Manuel Fahndrich wrote: > > The generic hash function Hashtbl.hash traverses into mutable data > structures. So I get different hash values depending on updates of the data > structure. > > # let x = ref None;; > val x : '_a option ref = {contents=None} > # Hashtbl.hash x;; > - : int = 0 > # x := Some 5;; > - : unit = () > # Hashtbl.hash x;; > - : int = 5 > > As was pointed out times before on this list, Hashtbl.hash is thus > unsuitable for hashing on data structures that contain mutable data. > > I'm wondering what the design rational is for this choice. I'd rather have a > generic hash function (Hashtbl.hash_pure) that never looks into mutable > structures (skips refs and mutable fields of records and classes). > The reason being that if I want to hash on data that contains references, > I'm more likely to want to find the structure independent of the contents of > any mutable subparts. > > So yes, a hashtable containing int refs would pointless, because it maps > them all to the same bucket. But I frequently use hashing with equality > being ==. Whenever I do this, I need to actually add some unique identifier > to the data structure just for the hashing operation. Having an alternate > hash function (Hashtbl.hash_pure) would make such id's (and their managment) > unnecessary. > > I see how the current working of Hashtbl.hash is useful for data structures > that contain mutable parts in the case where such structures don't change > between the time they are stored and later looked up in the hash table. But > I'm wondering how often this actually arises. > > Furthermore, using Hashtbl.hash_pure in place of Hashtbl.hash would not > break any old code (except for performance), since all it does is make the > equivalence classes bigger. On the other hand, using Hashtbl.hash with the > misconception that it acts as Hashtbl.hash_pure breaks lots of code. > > I rest my case. > > Manuel Fahndrich _________________________________________________________________ Dmitri S. Lomov mailto:dsl@tepkom.ru ICQ#: 20524819 (Rusty) http://users.tepkom.ru/dsl, http://young.tepkom.ru ftp://young.tepkom.ru +7 (812) 428-46-57 (b) +7 (812) 295-94-15 (h)