Re: [Caml-list] Physical counterpart to Pervasives.compare?

Re: [Caml-list] Physical counterpart to Pervasives.compare?

[Pascal Cuoq]

[-- Attachment #1: Type: text/plain, Size: 1743 bytes --]

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)));
}


[-- Attachment #2: Type: text/html, Size: 3558 bytes --]

Re: [Caml-list] Physical counterpart to Pervasives.compare?

[Christophe Raffalli]

[-- Attachment #1: Type: text/plain, Size: 533 bytes --]

>
> 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



[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 258 bytes --]

Re: [Caml-list] Physical counterpart to Pervasives.compare?

[Damien Doligez]

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

Re: [Caml-list] Physical counterpart to Pervasives.compare?

[Pascal Cuoq]

[-- Attachment #1: Type: text/plain, Size: 1283 bytes --]

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


[-- Attachment #2: Type: text/html, Size: 2087 bytes --]

Re: [Caml-list] Physical counterpart to Pervasives.compare?

[Jean-Christophe Filliâtre]

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

Physical counterpart to Pervasives.compare?

[Elnatan Reisner]

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?

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

Re: [Caml-list] Physical counterpart to Pervasives.compare?

[Edgar Friendly]

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

Re: [Caml-list] Physical counterpart to Pervasives.compare?

[Edgar Friendly]

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

Re: [Caml-list] Physical counterpart to Pervasives.compare?

[Alain Frisch]

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