Re: Alternative generic hash function

From: Dan Grossman (danieljg@cs.cornell.edu)
Date: Tue May 30 2000 - 19:25:16 MET DST

  • Next message: Daniel Ortmann: "Re: Alternative generic hash function"

    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 |
    



    This archive was generated by hypermail 2b29 : Tue May 30 2000 - 22:36:22 MET DST