Re: [Caml-list] Physical counterpart to Pervasives.compare?
On 2009-08-25, at 20:03, Christophe Raffalli wrote: [...] and the minor heap is at a higher adress than the major heap, That would be very hard to guarantee, given the current OS trend toward address randomization. How much slower is the compacting major GC comparer to the standard one ? First you do the GC, then you compact, so it's pure overhead but that's not the problem. The problem is that compaction is not incremental. -- Damien ___ Caml-list mailing list. Subscription management: http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list Archives: http://caml.inria.fr Beginner's list: http://groups.yahoo.com/group/ocaml_beginners Bug reports: http://caml.inria.fr/bin/caml-bugs
Re: [Caml-list] Physical counterpart to Pervasives.compare?
> > But you should still do the comparison > with a unique C function written for this purpose. > If you tried to use a "convert address to int" function, > you would have a race condition between the conversion > of each address and garbage collection. Or, if all major GCs are compacting and the minor heap is at a higher adress than the major heap, then OCaml's could also preserve the adress order between GC ... How much slower is the compacting major GC comparer to the standard one ? Cheers, Christophe signature.asc Description: OpenPGP digital signature ___ Caml-list mailing list. Subscription management: http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list Archives: http://caml.inria.fr Beginner's list: http://groups.yahoo.com/group/ocaml_beginners Bug reports: http://caml.inria.fr/bin/caml-bugs
Re: [Caml-list] Physical counterpart to Pervasives.compare?
Pascal Cuoq a écrit :
Elnatan Reisner wrote:
Is there something that can complete this analogy:
(=) is to (==) as Pervasives.compare is to ___?
The simple solution is to number at creation the objects that you
want to
physically compare, using an additional field.
Since people are still participating in this topic,
I have a remark. It is more a "what not to do" kind of
remark, but after replying last time, I remembered
that the current algorithm used by OCaml's GC
for compaction does not change the order of blocks
in memory (byterun/compact.c). Therefore, with the
current version, if you make sure in some way
that the values that you want to compare
are allocated directly in the major heap
(there are a couple of ways to do that),
you can theoretically compare their addresses
as unsigned longs: their order will not change
during execution.
But you should still do the comparison
with a unique C function written for this purpose.
If you tried to use a "convert address to int" function,
you would have a race condition between the conversion
of each address and garbage collection.
This is all in very poor taste, even more so than
the usual discussions about == on this list.
Do I get some kind of prize for breaking the record?
Pascal
__
PS: I wrote a "convert address to int" function for
another purpose once. In order to increase my chances
for the prize, I will provide it here. Someone might be
interested in it. Perhaps someone who maintains a small
library for computing the size of an ML value...
external address_of_value: 'a -> int = "address_of_value"
value address_of_value(value v)
{
return (Val_long(((unsigned long)v)/sizeof(long)));
}
___
Caml-list mailing list. Subscription management:
http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list
Archives: http://caml.inria.fr
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
Bug reports: http://caml.inria.fr/bin/caml-bugs
Re: [Caml-list] Physical counterpart to Pervasives.compare?
Pascal Cuoq a écrit : >> Elnatan Reisner wrote: >>> Is there something that can complete this analogy: >>> (=) is to (==) as Pervasives.compare is to ___? >>> > The simple solution is to number at creation the objects that you want to > physically compare, using an additional field. You can do that while hash-consing your values, which has many other benefits than allowing physical comparison, as explained in this paper: http://www.lri.fr/~filliatr/ftp/publis/hash-consing2.pdf Ocaml code for hash-consing can be found on that page: http://www.lri.fr/~filliatr/software.en.html Hope this helps, -- Jean-Christophe ___ Caml-list mailing list. Subscription management: http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list Archives: http://caml.inria.fr Beginner's list: http://groups.yahoo.com/group/ocaml_beginners Bug reports: http://caml.inria.fr/bin/caml-bugs
Re: [Caml-list] Physical counterpart to Pervasives.compare?
Edgar Friendly wrote: Elnatan Reisner wrote: Is there something that can complete this analogy: (=) is to (==) as Pervasives.compare is to ___? That is, is there a polymorphic total ordering with respect to *physical* entities, rather than to their structure? No, but it'd be pretty trivial to implement through the C interface. No, it would not be trivial to implement, because you would not want the order of two values to change each time one is moved from the minor heap to the major heap or when the major heap is compacted. The article linked below is about this kind of topic (among other things), in the context of Haskell. http://research.microsoft.com/en-us/um/people/simonpj/papers/weak.htm The simple solution is to number at creation the objects that you want to physically compare, using an additional field. If you had to stay in the OCaml realm, you might be able to do [let phys_comp (x:'a) (y:'a) = (Obj.magic x) - (Obj.magic y)], but it depends on the exact implementation of (-) on your architecture, as it may produce a value that's not an OCaml int when given non-ints as input. As an additional general remark, it is a bad idea to use "x - y" as an implementation of "compare x y" because of overflows. Pascal ___ Caml-list mailing list. Subscription management: http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list Archives: http://caml.inria.fr Beginner's list: http://groups.yahoo.com/group/ocaml_beginners Bug reports: http://caml.inria.fr/bin/caml-bugs
Re: [Caml-list] Physical counterpart to Pervasives.compare?
On 7/29/2009 3:25 AM, Elnatan Reisner wrote: Is there something that can complete this analogy: (=) is to (==) as Pervasives.compare is to ___? That is, is there a polymorphic total ordering with respect to *physical* entities, rather than to their structure? Not really. The physical location of heap values is not stable (because of the GC), so you cannot use it as a total ordering. It may be useful to know that the generic structural comparison has a physical behavior for OCaml objects (it compares their unique ids). So wrapping your values inside objects can be a good trick to get physical comparison (and hashing), as in: class ['a] physical_reference init = object val mutable current : 'a = init method get = current method set x = current <- x end -- Alain ___ Caml-list mailing list. Subscription management: http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list Archives: http://caml.inria.fr Beginner's list: http://groups.yahoo.com/group/ocaml_beginners Bug reports: http://caml.inria.fr/bin/caml-bugs
Re: [Caml-list] Physical counterpart to Pervasives.compare?
Edgar Friendly wrote: > Elnatan Reisner wrote: >> I'm afraid of getting into trouble with Obj.magic, but what would this do: >> let f (x:'a) (y:'a) = compare (Obj.magic x) (Obj.magic y) >> ? Or would annotations make any difference: >> let f (x:'a) (y:'a) = compare (Obj.magic x : int) (Obj.magic y : int) >> >> -Elnatan > > Nope, Obj.magic and casting only have compile-time effects, the code > given compiles exactly the same as [let f x y = compare x y]. > It looks like I'm wrong on this - there's versions of compare specialized for floats, strings and ints. Maybe you *could* trigger the use of the caml_int_compare by this kind of type system manipulation. It looks quite safe to use on non-ints. Testing on your platform is possible, by trying to find store pointers to ints, so that caml_compare compares the ints, but the tricked caml_int_compare compares the pointers, and gets a different result. E ___ Caml-list mailing list. Subscription management: http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list Archives: http://caml.inria.fr Beginner's list: http://groups.yahoo.com/group/ocaml_beginners Bug reports: http://caml.inria.fr/bin/caml-bugs
Re: [Caml-list] Physical counterpart to Pervasives.compare?
Elnatan Reisner wrote: > Is there something that can complete this analogy: > (=) is to (==) as Pervasives.compare is to ___? > > That is, is there a polymorphic total ordering with respect to *physical* > entities, rather than to their structure? > No, but it'd be pretty trivial to implement through the C interface. > I'm afraid of getting into trouble with Obj.magic, but what would this do: > let f (x:'a) (y:'a) = compare (Obj.magic x) (Obj.magic y) > ? Or would annotations make any difference: > let f (x:'a) (y:'a) = compare (Obj.magic x : int) (Obj.magic y : int) > > -Elnatan Nope, Obj.magic and casting only have compile-time effects, the code given compiles exactly the same as [let f x y = compare x y]. If you had to stay in the OCaml realm, you might be able to do [let phys_comp (x:'a) (y:'a) = (Obj.magic x) - (Obj.magic y)], but it depends on the exact implementation of (-) on your architecture, as it may produce a value that's not an OCaml int when given non-ints as input. E ___ Caml-list mailing list. Subscription management: http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list Archives: http://caml.inria.fr Beginner's list: http://groups.yahoo.com/group/ocaml_beginners Bug reports: http://caml.inria.fr/bin/caml-bugs
