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 WAA00280 for caml-red; Tue, 30 May 2000 22:34:22 +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 TAA17943 for ; Tue, 30 May 2000 19:26:49 +0200 (MET DST) Received: from sundown.cs.cornell.edu (SUNDOWN.CS.CORNELL.EDU [128.84.96.20]) by concorde.inria.fr (8.10.0/8.10.0) with ESMTP id e4UHQh515861; Tue, 30 May 2000 19:26:43 +0200 (MET DST) Received: from cs.cornell.edu (DHCP99-226.CS.CORNELL.EDU [128.84.99.226]) by sundown.cs.cornell.edu (8.9.3/8.9.3/R-3.0) with ESMTP id NAA00319; Tue, 30 May 2000 13:26:41 -0400 (EDT) Message-ID: <3933F97C.11CC74D1@cs.cornell.edu> Date: Tue, 30 May 2000 13:25:16 -0400 From: Dan Grossman X-Mailer: Mozilla 4.72 [en] (WinNT; U) X-Accept-Language: en MIME-Version: 1.0 To: Francois.Pottier@inria.fr CC: caml-list@inria.fr Subject: Re: Alternative generic hash function References: <783D93998201D311B0CF00805FEAA07B7E9233@RED-MSG-42> <20000525102414.55340@pauillac.inria.fr> <392ED1F3.A08D283D@cs.cornell.edu> <20000529151357.24569@pauillac.inria.fr> Content-Type: text/plain; charset=iso-8859-1 Content-Transfer-Encoding: 8bit Sender: weis Francois Pottier wrote: > > there are plenty of clever tricks you can put in the runtime system > > that exploit the immutability of objects. > > Would you care to elaborate? I am no compiler expert, but I'm not sure > why it would be so interesting to have this information at runtime, > where it is already too late to do code optimization. That would allow > implementing the `pure' hash function proposed by Manuel Fähndrich, but > with a cost: the user would have to separate the mutable fields into a > sub-object, so as to allow the root object to be tagged as immutable. > Which other tricks do you have in mind? I think the tricks fall into two categories but none of the tricks may apply to the current OCaml system. The first category is optimizing code by dynamically choosing between a version that only works for immutable data and one that does not. The basic idea is that it is not "too late" so long as you have both versions available. The dynamic check is inexpensive, especially if it is hoisted out of a loop. Now with OCaml as your source language, I believe having dynamic checks is worthless because the mutability of an object is always determined for a program point. That is, this information is available statically. But from a sufficiently low-level viewpoint, we could consider this an artifact of the source language. The second category is in the runtime system. Here, most of the code does not know whether the object it is manipulating is mutable. How could we use this information? I could imagine having one nursery (allocation area) for mutable and immutable objects, but then have the minor collector segregate on mutability. Segregation is particularly useful in conjunction with "card marking" which the OCaml system does not use. But it could help the memory system performance of the OCaml major collector as well. Some more radical ideas I have been playing around with involve using runtime value information to optimize data representation. Knowing that some values cannot change (due to the immutability bit) can enable the run-time system to perform some transformations, perhaps during garbage collection. A final idea is that an incremental garbage collector could optimize its treatment of immutable objects. Assuming mutable objects are uncommon, incremental collection costs could decrease significantly. --Dan -- | Dan Grossman www.cs.cornell.edu/home/danieljg H:607 256 0724 | | 5157 Upson Hall danieljg@cs.cornell.edu O:607 255 9834 |