Re: ocaml sefault in bytecode: unanswered questions

Re: ocaml sefault in bytecode: unanswered questions

[ivan chollet]

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

Yes it was a freebsd 6.4 with ocaml 3.10.2

I'll run the program on linux later and see how it goes.

 

Thanks for your advices regarding debugging. I pretty much tried all of
these though. the thing is my error is not an ocaml error at runtime but an
error of the ocaml runtime. And to analyze a core dump of ocamlrun, I just
thought my best bet was gdb. Whatever.

 

OK I'll try to provide you with a minimal ocaml code that produce an
ocamlrun error. Might take a little while as I'm not free.

In the meantime, I've got a newbie question regarding ocaml garbage
collector and the same List.iter stuff:

Say you do a "List.iter myfun !myref", where !myref is a list (hehe.), and
where myfun is a function that does reallocations of myref (that is
affectations like myref := [some new or old objects]). The pointers myref
that are generated through this process are destroyed each time a new
reallocation of myref is done. Of course the underlying linked lists that
are not referenced anymore shouldn't be collected by the GC before the end
of the main "List.iter", otherwise it's iterating through a linked list that
has been garbage collected.

My question is: does the GC know that it cannot collect the unreferenced
myref pointers before the end of the List.iter? 

Sorry, I just wanted to ask this question to rule it out.

 

Thanks again.

 

 

 

 

On 07-08-2009, ivan chollet <ivan.chollet@free.fr> wrote:

> 

> This GDB was configured as "i386-marcel-freebsd"...(no debugging symbols

> found)...

> 

> Not very informative. So here are my questions:

 

I suppose you are running freebsd ? Which version of freebsd, of ocaml ? 

 

> 

>  

> 

> -          What is the best way to produce and analyze core dumps in
ocaml?

> Should I compile in bytecode or native? Is there any special gdb "trick"

> that gives you more information? Is there any special "trick" while

> compiling the ocaml runtime to make it throw more information?

> 

 

gdb is not the perfect tool to debug ocaml program. You should give a

try to ocamldebug which is a better option for bytecode (see below for

options). Bytecode is more informative when coming to reporting

backtrace (at least with old version of ocaml). 

 

Compile every program with "-g" option (just like gcc). 

 

If you have compiled everything with "-g" option, you can also use the

environment variable OCAMLRUNPARAM="b" to get a backtrace for your

exception, at runtime.

 

> -          Then, my main question is actually: in bytecode, what can
produce

> segfaults? My ocaml code is completely standard, excepted that I use the

> Marshal module. So my question is rather: outside the Marshal module, what

> can cause segfault?

 

Some part of the bytecode are just standard C, everything can cause a

segfault just as C. These errors are not very common but it is possible

that some case are not well handled on freebsd. Most probably a porting

issue.

 

Marshal module can easily trigger a segfault when you map the loaded data

to a type which doesn't match the dumped data.

 

Example: 

List.length (Marshal.from_string (Marshal.to_string 1234 []) 0);;

 

Here the integer value is marshalled and then unmarshalled as a list ->

segfault.

 

> 

> -          Slightly unrelated question: I have been able to generate

> segfaults by running ocaml code that: 1) iterates recursively through a
list

> reference 2) changes the reference while still iterating on it. For
example,

> you just do a "List.iter myfun !myref", and within the function myfun, you

> do stuff like "myref := List.filter somefilterfunction !myref". It is not

> good to program like this, but for some reason I thought ocaml would not

> segfault on that. Is this expected behavior? If it's not, I'll be happy to

> provide some simple source code that illustrates it. (nevermind I have

> actually cleaned all my code base from these dirty uses of references)

> 

 

Could you provide a minimal example code for this error ? I don't think

this should generate a segfault.

 

 

Regards

Sylvain Le Gall

 


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

RE: [Caml-list] Re: ocaml sefault in bytecode: unanswered questions

[David Allsopp]

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

When you pass a value to a function, you create a pointer to that value in
the OCaml runtime - the GC can't collect the old value until List.iter
completes because the value is still live (internally, it's part of a local
root but, in practice, as List.iter is implemented in OCaml directly it's
because an OCaml function parameter references the value). Note that in this
example:

 

let a = [1; 2; 3]

and b = [4; 5; 6]

and c = [7; 8; 9] in

let myref = ref a in

(* No allocations are done after here *)

  myref := a;

  myref := b;

  myref := c;;

 

the assignments to [myref] do not result in any memory being allocated at
all (my point is that action of assigning to a reference does not implicitly
result in an allocation).

 

 

David

 

From: caml-list-bounces@yquem.inria.fr
[mailto:caml-list-bounces@yquem.inria.fr] On Behalf Of ivan chollet
Sent: 08 August 2009 18:10
To: ivan.chollet@free.fr
Cc: caml-list@yquem.inria.fr
Subject: [Caml-list] Re: ocaml sefault in bytecode: unanswered questions

 

Yes it was a freebsd 6.4 with ocaml 3.10.2

I'll run the program on linux later and see how it goes.

 

Thanks for your advices regarding debugging. I pretty much tried all of
these though. the thing is my error is not an ocaml error at runtime but an
error of the ocaml runtime. And to analyze a core dump of ocamlrun, I just
thought my best bet was gdb. Whatever.

 

OK I'll try to provide you with a minimal ocaml code that produce an
ocamlrun error. Might take a little while as I'm not free.

In the meantime, I've got a newbie question regarding ocaml garbage
collector and the same List.iter stuff:

Say you do a "List.iter myfun !myref", where !myref is a list (hehe.), and
where myfun is a function that does reallocations of myref (that is
affectations like myref := [some new or old objects]). The pointers myref
that are generated through this process are destroyed each time a new
reallocation of myref is done. Of course the underlying linked lists that
are not referenced anymore shouldn't be collected by the GC before the end
of the main "List.iter", otherwise it's iterating through a linked list that
has been garbage collected.

My question is: does the GC know that it cannot collect the unreferenced
myref pointers before the end of the List.iter? 

Sorry, I just wanted to ask this question to rule it out.

 

Thanks again.

 

 

 

 

On 07-08-2009, ivan chollet <ivan.chollet@free.fr> wrote:

> 

> This GDB was configured as "i386-marcel-freebsd"...(no debugging symbols

> found)...

> 

> Not very informative. So here are my questions:

 

I suppose you are running freebsd ? Which version of freebsd, of ocaml ? 

 

> 

>  

> 

> -          What is the best way to produce and analyze core dumps in
ocaml?

> Should I compile in bytecode or native? Is there any special gdb "trick"

> that gives you more information? Is there any special "trick" while

> compiling the ocaml runtime to make it throw more information?

> 

 

gdb is not the perfect tool to debug ocaml program. You should give a

try to ocamldebug which is a better option for bytecode (see below for

options). Bytecode is more informative when coming to reporting

backtrace (at least with old version of ocaml). 

 

Compile every program with "-g" option (just like gcc). 

 

If you have compiled everything with "-g" option, you can also use the

environment variable OCAMLRUNPARAM="b" to get a backtrace for your

exception, at runtime.

 

> -          Then, my main question is actually: in bytecode, what can
produce

> segfaults? My ocaml code is completely standard, excepted that I use the

> Marshal module. So my question is rather: outside the Marshal module, what

> can cause segfault?

 

Some part of the bytecode are just standard C, everything can cause a

segfault just as C. These errors are not very common but it is possible

that some case are not well handled on freebsd. Most probably a porting

issue.

 

Marshal module can easily trigger a segfault when you map the loaded data

to a type which doesn't match the dumped data.

 

Example: 

List.length (Marshal.from_string (Marshal.to_string 1234 []) 0);;

 

Here the integer value is marshalled and then unmarshalled as a list ->

segfault.

 

> 

> -          Slightly unrelated question: I have been able to generate

> segfaults by running ocaml code that: 1) iterates recursively through a
list

> reference 2) changes the reference while still iterating on it. For
example,

> you just do a "List.iter myfun !myref", and within the function myfun, you

> do stuff like "myref := List.filter somefilterfunction !myref". It is not

> good to program like this, but for some reason I thought ocaml would not

> segfault on that. Is this expected behavior? If it's not, I'll be happy to

> provide some simple source code that illustrates it. (nevermind I have

> actually cleaned all my code base from these dirty uses of references)

> 

 

Could you provide a minimal example code for this error ? I don't think

this should generate a segfault.

 

 

Regards

Sylvain Le Gall

 


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

RE: [Caml-list] Re: ocaml sefault in bytecode: unanswered questions

[ivan chollet]

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

Definitely.

Actually I had my real-world case in mind, so let me explain further with
the following snippet:

 

let myfun = doSomeWork (); myref := List.filter somefilterfunction !myref in

List.iter myfun !myref

 

In this case, a new linked list is created in each iteration of the
List.filter. (that is, a new list allocation)

Then, if doSomeWork () does a lot of work and lots of allocations, the GC
will be called on a regular basis while in function myfun. 

Then List.iter is tail-recursive, so it doesn’t push its successive
arguments on the stack. So the successively created myref become unreachable
while still iterating on them.

So my question is, how does the GC know whether all these myref created
throughout the iteration are collectable or not? I’m curious about how these
myref are tagged/untagged by the garbage collector. Maybe pointing me the
relevant portions of the ocamlrun source code would be nice.

 

Anyway no worries, once I get a bit more free I’ll just try to read about
this topic by myself. Also I’ll try to send you some source code for that.
All this will take me a little while, so see you next time!

 

 

 

From: David Allsopp [mailto:dra-news@metastack.com] 
Sent: samedi 8 août 2009 19:25
To: 'ivan chollet'
Cc: caml-list@yquem.inria.fr
Subject: RE: [Caml-list] Re: ocaml sefault in bytecode: unanswered questions

 

When you pass a value to a function, you create a pointer to that value in
the OCaml runtime – the GC can’t collect the old value until List.iter
completes because the value is still live (internally, it’s part of a local
root but, in practice, as List.iter is implemented in OCaml directly it’s
because an OCaml function parameter references the value). Note that in this
example:

 

let a = [1; 2; 3]

and b = [4; 5; 6]

and c = [7; 8; 9] in

let myref = ref a in

(* No allocations are done after here *)

  myref := a;

  myref := b;

  myref := c;;

 

the assignments to [myref] do not result in any memory being allocated at
all (my point is that action of assigning to a reference does not implicitly
result in an allocation).

 

 

David

 

From: caml-list-bounces@yquem.inria.fr
[mailto:caml-list-bounces@yquem.inria.fr] On Behalf Of ivan chollet
Sent: 08 August 2009 18:10
To: ivan.chollet@free.fr
Cc: caml-list@yquem.inria.fr
Subject: [Caml-list] Re: ocaml sefault in bytecode: unanswered questions

 

Yes it was a freebsd 6.4 with ocaml 3.10.2

I’ll run the program on linux later and see how it goes.

 

Thanks for your advices regarding debugging. I pretty much tried all of
these though… the thing is my error is not an ocaml error at runtime but an
error of the ocaml runtime. And to analyze a core dump of ocamlrun, I just
thought my best bet was gdb. Whatever.

 

OK I’ll try to provide you with a minimal ocaml code that produce an
ocamlrun error. Might take a little while as I’m not free.

In the meantime, I’ve got a newbie question regarding ocaml garbage
collector and the same List.iter stuff:

Say you do a “List.iter myfun !myref”, where !myref is a list (hehe…), and
where myfun is a function that does reallocations of myref (that is
affectations like myref := [some new or old objects]). The pointers myref
that are generated through this process are destroyed each time a new
reallocation of myref is done. Of course the underlying linked lists that
are not referenced anymore shouldn’t be collected by the GC before the end
of the main “List.iter”, otherwise it’s iterating through a linked list that
has been garbage collected.

My question is: does the GC know that it cannot collect the unreferenced
myref pointers before the end of the List.iter? 

Sorry, I just wanted to ask this question to rule it out.

 

Thanks again.

 

 

 

 

On 07-08-2009, ivan chollet <ivan.chollet@free.fr> wrote:

> 

> This GDB was configured as "i386-marcel-freebsd"...(no debugging symbols

> found)...

> 

> Not very informative. So here are my questions:

 

I suppose you are running freebsd ? Which version of freebsd, of ocaml ? 

 

> 

>  

> 

> -          What is the best way to produce and analyze core dumps in
ocaml?

> Should I compile in bytecode or native? Is there any special gdb "trick"

> that gives you more information? Is there any special "trick" while

> compiling the ocaml runtime to make it throw more information?

> 

 

gdb is not the perfect tool to debug ocaml program. You should give a

try to ocamldebug which is a better option for bytecode (see below for

options). Bytecode is more informative when coming to reporting

backtrace (at least with old version of ocaml). 

 

Compile every program with "-g" option (just like gcc). 

 

If you have compiled everything with "-g" option, you can also use the

environment variable OCAMLRUNPARAM="b" to get a backtrace for your

exception, at runtime.

 

> -          Then, my main question is actually: in bytecode, what can
produce

> segfaults? My ocaml code is completely standard, excepted that I use the

> Marshal module. So my question is rather: outside the Marshal module, what

> can cause segfault?

 

Some part of the bytecode are just standard C, everything can cause a

segfault just as C. These errors are not very common but it is possible

that some case are not well handled on freebsd. Most probably a porting

issue.

 

Marshal module can easily trigger a segfault when you map the loaded data

to a type which doesn't match the dumped data.

 

Example: 

List.length (Marshal.from_string (Marshal.to_string 1234 []) 0);;

 

Here the integer value is marshalled and then unmarshalled as a list ->

segfault.

 

> 

> -          Slightly unrelated question: I have been able to generate

> segfaults by running ocaml code that: 1) iterates recursively through a
list

> reference 2) changes the reference while still iterating on it. For
example,

> you just do a "List.iter myfun !myref", and within the function myfun, you

> do stuff like "myref := List.filter somefilterfunction !myref". It is not

> good to program like this, but for some reason I thought ocaml would not

> segfault on that. Is this expected behavior? If it's not, I'll be happy to

> provide some simple source code that illustrates it. (nevermind I have

> actually cleaned all my code base from these dirty uses of references)

> 

 

Could you provide a minimal example code for this error ? I don't think

this should generate a segfault.

 

 

Regards

Sylvain Le Gall

 


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

Re: [Caml-list] Re: ocaml sefault in bytecode: unanswered questions

[Michel Mauny]

ivan chollet écrit/writes [09/08/2009 08:58] :
> So my question is rather: outside the Marshal module, what
> can cause segfault?

The Obj module and your own C code --if any-- are also unsafe.

Note that the OS itself can kill you when your process goes beyond limits. Try playing with ulimit (for bash) before running your program.

Best,

-- Michel Mauny

RE: [Caml-list] Re: ocaml sefault in bytecode: unanswered questions

[ivan chollet]

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

Thanks for your help Sylvain, David & Michel for all these explanations.
These insightful comments have enlightened my vision of the ocaml runtime.

It all makes sense so I’ll follow your advice and stop worrying about the
GC.

Let’s come back to my problem. I played with ocaml interpreter a bit, and
there is a behavior that I cannot understand. This behavior actually creates
a fairly large range of problems all over my code base. See the following
snippet:

 

# let q = Queue.create () in

  Queue.push 0 q;

  q == q;;

- : bool = true

 

Standard behavior.

Now let see this:

 

# let q = Queue.create () in

  Queue.push 0 q;

q = q;;

 

which hangs for ever…

I would have thought physical equality implies structural equality, but it
doesn’t seem like it.

Can you please explain to me what’s wrong there?

 

Thanks again for your help!

 

 

From: David Allsopp [mailto:dra-news@metastack.com] 
Sent: dimanche 9 août 2009 10:39
To: 'ivan chollet'
Subject: RE: [Caml-list] Re: ocaml sefault in bytecode: unanswered questions

 

Chapter 18.2 of the manual is what you need – it explains the value type
used internally for the heap. In hyper-simplistic terms, when the garbage
collector runs it just assumes that anything could be a pointer and applies
a colouring to the heap to determine reachable values (the memory bit
required for this colouring is why integer values are only 31 or 63 bits in
OCaml – you get the performance of their being unboxed, but the hit of
losing a bit for the colouring). 

 

Personally, I wouldn’t spend so much time worrying about the Garbage
Collector – it just works! To answer part of your original question: using
only the standard library, the only way that you can segfault a program
(other than by abusing Marshal) is to abuse the Obj module (Obj.magic in
particular allows you to circumvent the type system).  However, the
documentation for Obj says it all – “Operations on internal representations
of values. Not for the casual user.”

 

If you’ve seen an example in the past which segfaulted the bytecode runtime,
then it was a bug in the compiler... if you can still produce a repro case
then raise a bug in mantis. However, the Garbage Collector received a lot of
attention in both 3.10 (big overhaul of lazy values) and 3.11 (change the
way the memory tables are implemented) so if it was with an older version of
OCaml that you saw it then the error may have disappeared. Similarly, the
semantics of the bytecode runtime and native runtime are supposed to be the
same – but there are a few instances where the native runtime intentionally
segfaults (for performance) where the bytecode runtime would raise an
exception (stack overflow is the principal one). 

 

Best,

 

 

D

 

 

From: ivan chollet [mailto:ivan.chollet@free.fr] 
Sent: 09 August 2009 08:59
To: 'David Allsopp'
Cc: caml-list@yquem.inria.fr; 'Edgar Friendly'
Subject: RE: [Caml-list] Re: ocaml sefault in bytecode: unanswered questions

 

Definitely.

Actually I had my real-world case in mind, so let me explain further with
the following snippet:

 

let myfun = doSomeWork (); myref := List.filter somefilterfunction !myref in

List.iter myfun !myref

 

In this case, a new linked list is created in each iteration of the
List.filter. (that is, a new list allocation)

Then, if doSomeWork () does a lot of work and lots of allocations, the GC
will be called on a regular basis while in function myfun. 

Then List.iter is tail-recursive, so it doesn’t push its successive
arguments on the stack. So the successively created myref become unreachable
while still iterating on them.

So my question is, how does the GC know whether all these myref created
throughout the iteration are collectable or not? I’m curious about how these
myref are tagged/untagged by the garbage collector. Maybe pointing me the
relevant portions of the ocamlrun source code would be nice.

 

Anyway no worries, once I get a bit more free I’ll just try to read about
this topic by myself. Also I’ll try to send you some source code for that.
All this will take me a little while, so see you next time!

 

 

 

From: David Allsopp [mailto:dra-news@metastack.com] 
Sent: samedi 8 août 2009 19:25
To: 'ivan chollet'
Cc: caml-list@yquem.inria.fr
Subject: RE: [Caml-list] Re: ocaml sefault in bytecode: unanswered questions

 

When you pass a value to a function, you create a pointer to that value in
the OCaml runtime – the GC can’t collect the old value until List.iter
completes because the value is still live (internally, it’s part of a local
root but, in practice, as List.iter is implemented in OCaml directly it’s
because an OCaml function parameter references the value). Note that in this
example:

 

let a = [1; 2; 3]

and b = [4; 5; 6]

and c = [7; 8; 9] in

let myref = ref a in

(* No allocations are done after here *)

  myref := a;

  myref := b;

  myref := c;;

 

the assignments to [myref] do not result in any memory being allocated at
all (my point is that action of assigning to a reference does not implicitly
result in an allocation).

 

 

David

 

From: caml-list-bounces@yquem.inria.fr
[mailto:caml-list-bounces@yquem.inria.fr] On Behalf Of ivan chollet
Sent: 08 August 2009 18:10
To: ivan.chollet@free.fr
Cc: caml-list@yquem.inria.fr
Subject: [Caml-list] Re: ocaml sefault in bytecode: unanswered questions

 

Yes it was a freebsd 6.4 with ocaml 3.10.2

I’ll run the program on linux later and see how it goes.

 

Thanks for your advices regarding debugging. I pretty much tried all of
these though… the thing is my error is not an ocaml error at runtime but an
error of the ocaml runtime. And to analyze a core dump of ocamlrun, I just
thought my best bet was gdb. Whatever.

 

OK I’ll try to provide you with a minimal ocaml code that produce an
ocamlrun error. Might take a little while as I’m not free.

In the meantime, I’ve got a newbie question regarding ocaml garbage
collector and the same List.iter stuff:

Say you do a “List.iter myfun !myref”, where !myref is a list (hehe…), and
where myfun is a function that does reallocations of myref (that is
affectations like myref := [some new or old objects]). The pointers myref
that are generated through this process are destroyed each time a new
reallocation of myref is done. Of course the underlying linked lists that
are not referenced anymore shouldn’t be collected by the GC before the end
of the main “List.iter”, otherwise it’s iterating through a linked list that
has been garbage collected.

My question is: does the GC know that it cannot collect the unreferenced
myref pointers before the end of the List.iter? 

Sorry, I just wanted to ask this question to rule it out.

 

Thanks again.

 

 

 

 

On 07-08-2009, ivan chollet <ivan.chollet@free.fr> wrote:

> 

> This GDB was configured as "i386-marcel-freebsd"...(no debugging symbols

> found)...

> 

> Not very informative. So here are my questions:

 

I suppose you are running freebsd ? Which version of freebsd, of ocaml ? 

 

> 

>  

> 

> -          What is the best way to produce and analyze core dumps in
ocaml?

> Should I compile in bytecode or native? Is there any special gdb "trick"

> that gives you more information? Is there any special "trick" while

> compiling the ocaml runtime to make it throw more information?

> 

 

gdb is not the perfect tool to debug ocaml program. You should give a

try to ocamldebug which is a better option for bytecode (see below for

options). Bytecode is more informative when coming to reporting

backtrace (at least with old version of ocaml). 

 

Compile every program with "-g" option (just like gcc). 

 

If you have compiled everything with "-g" option, you can also use the

environment variable OCAMLRUNPARAM="b" to get a backtrace for your

exception, at runtime.

 

> -          Then, my main question is actually: in bytecode, what can
produce

> segfaults? My ocaml code is completely standard, excepted that I use the

> Marshal module. So my question is rather: outside the Marshal module, what

> can cause segfault?

 

Some part of the bytecode are just standard C, everything can cause a

segfault just as C. These errors are not very common but it is possible

that some case are not well handled on freebsd. Most probably a porting

issue.

 

Marshal module can easily trigger a segfault when you map the loaded data

to a type which doesn't match the dumped data.

 

Example: 

List.length (Marshal.from_string (Marshal.to_string 1234 []) 0);;

 

Here the integer value is marshalled and then unmarshalled as a list ->

segfault.

 

> 

> -          Slightly unrelated question: I have been able to generate

> segfaults by running ocaml code that: 1) iterates recursively through a
list

> reference 2) changes the reference while still iterating on it. For
example,

> you just do a "List.iter myfun !myref", and within the function myfun, you

> do stuff like "myref := List.filter somefilterfunction !myref". It is not

> good to program like this, but for some reason I thought ocaml would not

> segfault on that. Is this expected behavior? If it's not, I'll be happy to

> provide some simple source code that illustrates it. (nevermind I have

> actually cleaned all my code base from these dirty uses of references)

> 

 

Could you provide a minimal example code for this error ? I don't think

this should generate a segfault.

 

 

Regards

Sylvain Le Gall

 


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

RE: [Caml-list] Re: ocaml sefault in bytecode: unanswered questions

[David Allsopp]

Ivan Chollet wrote:
> See the following snippet:
>
> # let q = Queue.create () in
>  Queue.push 0 q;
>  q == q;;
> - : bool = true
>
> Standard behavior.
> Now let see this:
>
> # let q = Queue.create () in
>  Queue.push 0 q;
>  q = q;;
>  
>  which hangs for ever...

Internally, Queues are a cyclic data structure (see stdlib/queue.ml in the
sources). The documentation for Pervasives.(=) notes "Equality between
cyclic data structures may not terminate". If you want to compare two queues
for structural equality you'd have to fold the two Queues to a list and then
compare those. Perhaps a Queue isn't the most appropriate data structure for
what you're doing, therefore (functional queues wouldn't suffer from this
problem but note that their performance characteristic is subtly different
from an imperative queue)? Alternatively, if Queue.compare would be a handy
function, you could try raising a feature-request for it in Mantis.

> I would have thought physical equality implies structural equality, but it
doesn't seem like it.
> Can you please explain to me what’s wrong there?

"It does" - but only with the given caveat that comparison of cyclic
structures may not terminate. Pervasives.compare has a similar restriction,
although note that [compare q q] in your example does return 0 (which is
lucky or it would be a bug as the docs for Pervasives.(==) state that [x ==
y] => [compare x y = 0]).

The notes in http://caml.inria.fr/mantis/view.php?id=3322 may be of interest
too...
 


David

Re: [Caml-list] Re: ocaml sefault in bytecode: unanswered questions

[Alain Frisch]

On 8/9/2009 2:06 PM, ivan chollet wrote:
> I would have thought physical equality implies structural equality, but
> it doesn’t seem like it.
>
> Can you please explain to me what’s wrong there?

There are two modes for the generic comparison. The total mode 
(Pervasives.compare) creates a total ordering between values (except for 
functional values and custom blocks with no comparison function) and 
uses physical equality as a shortcut to cut the recursive traversal of 
sub-values. The non-total mode (used by the operators = < > <= >=) has a 
different behavior for NaN values ([nan <= x], [x <= nan], and [nan = x] 
all return false, including when x is nan) and does not use the physical 
equality shortcut (so that [let x = (nan, nan) in x = x] returns false).

-- Alain

RE: [Caml-list] Re: ocaml sefault in bytecode: unanswered questions

[ivan chollet]

Cool, thanks for that, for some reason this wasn't obvious to me reading the
documentation.


-----Original Message-----
From: Alain Frisch [mailto:alain@frisch.fr] 
Sent: dimanche 9 août 2009 15:55
To: ivan chollet
Cc: caml-list@yquem.inria.fr
Subject: Re: [Caml-list] Re: ocaml sefault in bytecode: unanswered questions

On 8/9/2009 2:06 PM, ivan chollet wrote:
> I would have thought physical equality implies structural equality, but
> it doesn’t seem like it.
>
> Can you please explain to me what’s wrong there?

There are two modes for the generic comparison. The total mode 
(Pervasives.compare) creates a total ordering between values (except for 
functional values and custom blocks with no comparison function) and 
uses physical equality as a shortcut to cut the recursive traversal of 
sub-values. The non-total mode (used by the operators = < > <= >=) has a 
different behavior for NaN values ([nan <= x], [x <= nan], and [nan = x] 
all return false, including when x is nan) and does not use the physical 
equality shortcut (so that [let x = (nan, nan) in x = x] returns false).

-- Alain

Re: [Caml-list] Re: ocaml sefault in bytecode: unanswered questions

[Elnatan Reisner]

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

Continuing this conversation about equality...

On Aug 9, 2009, at 9:20 AM, David Allsopp wrote:

> Ivan Chollet wrote:
>
>> I would have thought physical equality implies structural equality,  
>> but it
>> doesn't seem like it.
>> Can you please explain to me what’s wrong there?
>
> "It does" - but only with the given caveat that comparison of cyclic
> structures may not terminate. Pervasives.compare has a similar  
> restriction,
> although note that [compare q q] in your example does return 0  
> (which is
> lucky or it would be a bug as the docs for Pervasives.(==) state  
> that [x ==
> y] => [compare x y = 0]).

Let me start with a few pedantic comments about the documentation of  
(==):

First, what David says isn't *quite* what the documentation says. The  
documentation only says this is [x==y] implies [compare x y = 0]  for  
non-mutable structures. And in fact, what the documentation says is  
surprisingly weak: an implementation could define (==) as *always  
false* for non-mutable structures and yet satisfy the documentation.  
I'm not sure of the right way to reword it, but this loophole in the  
specification seems undesirable.

My other issue is that the description of (==) for mutable structures  
doesn't specify that it is symmetric; reading the documentation  
literally only implies that e1 is a substructure of e2. Even just  
adding 'and vice versa' might clean this up:
e1 == e2 is true if and only if physical modification of e1 also  
affects e2 and vice versa

Okay, now for more substantive questions:

> The notes in http://caml.inria.fr/mantis/view.php?id=3322 may be of  
> interest
> too...

I hadn't paid attention to the distinction drawn between 'may not  
terminate' and 'does not terminate' until I read the discussion at  
that link, but it's relevant to my question below...

On Aug 9, 2009, at 9:55 AM, Alain Frisch wrote:

> On 8/9/2009 2:06 PM, ivan chollet wrote:
>
>> I would have thought physical equality implies structural equality,  
>> but
>> it doesn’t seem like it.
>>
>> Can you please explain to me what’s wrong there?
>
> There are two modes for the generic comparison. The total mode  
> (Pervasives.compare) creates a total ordering between values (except  
> for functional values and custom blocks with no comparison function)  
> and uses physical equality as a shortcut to cut the recursive  
> traversal of sub-values. The non-total mode (used by the operators =  
> < > <= >=) has a different behavior for NaN values ([nan <= x], [x  
> <= nan], and [nan = x] all return false, including when x is nan)  
> and does not use the physical equality shortcut (so that [let x =  
> (nan, nan) in x = x] returns false).

In terms of 'may not' versus 'does not' terminate, I just noticed that  
the current documentation for (=) says 'may not terminate' while the  
documentation for (>=) says 'does not terminate'. However, the example  
cited in the link above:
type t = { a : t };;
let rec x = { a = x } in x = x
doesn't terminate in OCaml 3.11. This seems to be about as simple a  
cyclic structure as there is, so shouldn't (=)'s documentation say  
'Equality between cyclic structures does not terminate.'?

Also, the documentation for Pervasives.compare says 'may not  
terminate'. Is this supposed to imply that it uses the shortcut Alain  
mentions (because if it did not use physical equality as a shortcut  
then it would say 'does not terminate')? Or is this shortcutting meant  
to be undocumented?

And is there any reason, aside from NaN values, that (=) does *not*  
use physical equality as a shortcut? The only other reason I can think  
of is that, in cases where things are in fact *not* physically equal,  
checking physical equality would introduce a small overhead.

In any case, if I have a data structure which I know does not contain  
any NaNs (for example, maybe it doesn't contain any floats  
whatsoever), is there ever a reason I should prefer (=) to (compare x  
y = 0)? It sounds to me like compare is preferable because of its  
shortcutting behavior.

-Elnatan

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

Re: [Caml-list] Re: ocaml sefault in bytecode: unanswered questions

[Alain Frisch]

On 8/9/2009 8:56 PM, Elnatan Reisner wrote:
> My other issue is that the description of (==) for mutable structures
> doesn't specify that it is symmetric; reading the documentation
> literally only implies that e1 is a substructure of e2. Even just adding
> 'and vice versa' might clean this up:
> |e1 == e2| is true if and only if physical modification of |e1| also
> affects |e2 and vice versa|

It depends on what 'physical modification' and 'affect' mean. Clearly, 
the documentation means toplevel modifications of the values (i.e. 
modifying fields for record values, or elements for arrays or strings). 
If one includes deep modifications, then your extended criterion does 
not work either (think about two mutually recursive records).

> In terms of 'may not' versus 'does not' terminate, I just noticed that
> the current documentation for (=) says 'may not terminate' while the
> documentation for (>=) says 'does not terminate'. However, the example
> cited in the link above:
> type t = { a : t };;
> let rec x = { a = x } in x = x
> doesn't terminate in OCaml 3.11. This seems to be about as simple a
> cyclic structure as there is, so shouldn't (=)'s documentation say
> 'Equality between cyclic structures does not terminate.'?

Note that (=) sometimes terminates for cylic values.

# type t = A of t | B of t;;
type t = A of t | B of t
# (let rec x = A x in x) = (let rec x = B x in x);;
- : bool = false


> And is there any reason, aside from NaN values, that (=) does *not* use
> physical equality as a shortcut?

I think a custom comparison function for custom blocks can also specify 
that a value is not equal to itself.

> In any case, if I have a data structure which I know does not contain
> any NaNs (for example, maybe it doesn't contain any floats whatsoever),
> is there ever a reason I should prefer (=) to (compare x y = 0)?

No, I don't see any reason.


-- Alain

Re: [Caml-list] Re: ocaml sefault in bytecode: unanswered questions

[Elnatan Reisner]

On Sun, 2009-08-09 at 21:09 +0200, Alain Frisch wrote:
> On 8/9/2009 8:56 PM, Elnatan Reisner wrote:
> > My other issue is that the description of (==) for mutable structures
> > doesn't specify that it is symmetric; reading the documentation
> > literally only implies that e1 is a substructure of e2. Even just adding
> > 'and vice versa' might clean this up:
> > |e1 == e2| is true if and only if physical modification of |e1| also
> > affects |e2 and vice versa|
> 
> It depends on what 'physical modification' and 'affect' mean. Clearly, 
> the documentation means toplevel modifications of the values (i.e. 
> modifying fields for record values, or elements for arrays or strings). 
> If one includes deep modifications, then your extended criterion does 
> not work either (think about two mutually recursive records).

You're right; thanks for pointing this out. But what does this mean for
physical equality? What does it really mean? Does [e1 == e2] mean e1 and
e2 are the same entity in memory---i.e., they are equal as C pointers?

> Note that (=) sometimes terminates for cylic values.
> 
> # type t = A of t | B of t;;
> type t = A of t | B of t
> # (let rec x = A x in x) = (let rec x = B x in x);;
> - : bool = false

Again, thanks for pointing this out. But can (=) ever evaluate to true
on cyclic structures?

-Elnatan

Re: [Caml-list] Re: ocaml sefault in bytecode: unanswered questions

[Martin Jambon]

Elnatan Reisner wrote:
> On Sun, 2009-08-09 at 21:09 +0200, Alain Frisch wrote:
>> On 8/9/2009 8:56 PM, Elnatan Reisner wrote:
>>> My other issue is that the description of (==) for mutable structures
>>> doesn't specify that it is symmetric; reading the documentation
>>> literally only implies that e1 is a substructure of e2. Even just adding
>>> 'and vice versa' might clean this up:
>>> |e1 == e2| is true if and only if physical modification of |e1| also
>>> affects |e2 and vice versa|
>> It depends on what 'physical modification' and 'affect' mean. Clearly, 
>> the documentation means toplevel modifications of the values (i.e. 
>> modifying fields for record values, or elements for arrays or strings). 
>> If one includes deep modifications, then your extended criterion does 
>> not work either (think about two mutually recursive records).
> 
> You're right; thanks for pointing this out. But what does this mean for
> physical equality? What does it really mean? Does [e1 == e2] mean e1 and
> e2 are the same entity in memory---i.e., they are equal as C pointers?
> 
>> Note that (=) sometimes terminates for cylic values.
>>
>> # type t = A of t | B of t;;
>> type t = A of t | B of t
>> # (let rec x = A x in x) = (let rec x = B x in x);;
>> - : bool = false
> 
> Again, thanks for pointing this out. But can (=) ever evaluate to true
> on cyclic structures?

Yes:

let rec x = `A x;;
let o = object val x = x end;;
o = o;;

-> true


Martin

-- 
http://mjambon.com/

Re: [Caml-list] Re: ocaml sefault in bytecode: unanswered questions

[Elnatan Reisner]

On Mon, 2009-08-10 at 15:36 +0200, Martin Jambon wrote:
> Elnatan Reisner wrote:
> > On Sun, 2009-08-09 at 21:09 +0200, Alain Frisch wrote:
> >> Note that (=) sometimes terminates for cylic values.
> >>
> >> # type t = A of t | B of t;;
> >> type t = A of t | B of t
> >> # (let rec x = A x in x) = (let rec x = B x in x);;
> >> - : bool = false
> > 
> > Again, thanks for pointing this out. But can (=) ever evaluate to true
> > on cyclic structures?
> 
> Yes:
> 
> let rec x = `A x;;
> let o = object val x = x end;;
> o = o;;
> 
> -> true

Okay, give me one more try: Can (=) evaluate to true on cyclic
structures that are not objects? (My understanding is that objects are
compared---by both Pervasives.compare and by (=)---using only their
object ids, so [obj1 = obj2] is always just an comparison of two ints,
regardless of the contents of the objects. Is this correct?)

Also, I just tested out (>=), which the documentation says 'does not
terminate on cyclic structures':
# (let rec x = `A x in x) >= (let rec x = `B x in x);;
- : bool = false
So maybe my question went the wrong way: apparently the documentation of
(>=) should say 'may not terminate'.

Also, if I may, let me add two additional questions:
- Do (=), (<>), (<), (>), (<=), and (>=) all terminate on exactly the
same operands?
- Does Pervasives.compare terminate strictly more often, or are there
cases when the comparisons terminate but [compare x y] does not?

-Elnatan

Re: [Caml-list] Re: ocaml sefault in bytecode: unanswered questions

[Goswin von Brederlow]

"ivan chollet" <ivan.chollet@free.fr> writes:

> :v="urn:schemas-microsoft-com:vml"
> xmlns:o="urn:schemas-microsoft-com:office:office"
> xmlns:w="urn:schemas-microsoft-com:office:word"
> xmlns:m="http://schemas.microsoft.com/office/2004/12/omml"
> xmlns="http://www.w3.org/TR/REC-html40">
>
> Definitely.:p>
>
> Actually I had my real-world case in mind, so let me explain further with the
> following snippet::p>
>
> :p> 
>
> let myfun = doSomeWork (); myref := List.filter somefilterfunction !myref
> in:p>
>
> List.iter myfun !myref:p>
>
> :p> 
>
> In this case, a new linked list is created in each iteration of the
> List.filter. (that is, a new list allocation):p>
>
> Then, if doSomeWork () does a lot of work and lots of allocations, the GC will
> be called on a regular basis while in function myfun. :p>
>
> Then List.iter is tail-recursive, so it doesn't push its successive arguments
> on the stack. So the successively created myref become unreachable while still
> iterating on them.:p>
>
> So my question is, how does the GC know whether all these myref created
> throughout the iteration are collectable or not? I'm curious about how these
> myref are tagged/untagged by the garbage collector. Maybe pointing me the
> relevant portions of the ocamlrun source code would be nice.:p>

The current value of each binding is on the stack and the GC knows
about that. In the tail-recursion the value on the stack is
successively replaced by newer ones while the old ones are forgotten.
The GC then marks everything known (reachable) as still being needed
and everything it can't reach recursively from the known values your
code can't reach either and the GC can free it.

But that isn't even what happens in your case. Your myref is not on
the stack and you do not create a new myref on every iteration. You
only change its value. The GC knows about the myref and it will be one
of the known (reachable) things the GC starts from.

MfG
        Goswin

RE: [Caml-list] Re: ocaml sefault in bytecode: unanswered questions

[ivan chollet]

Hi Goswin, 

Sorry there was a typo, I wanted to say new !myref (ie a new linked list)
are created each time you do the List.filter, so I thought the first list on
which you iterate wasn't referenced anymore but actually I misunderstood how
the GC scans the heap. I got it now!

Thanks again


-----Original Message-----
From: goswin-v-b@web.de [mailto:goswin-v-b@web.de] 
Sent: dimanche 9 août 2009 18:14
To: ivan chollet
Cc: 'David Allsopp'; caml-list@yquem.inria.fr
Subject: Re: [Caml-list] Re: ocaml sefault in bytecode: unanswered questions

"ivan chollet" <ivan.chollet@free.fr> writes:

> :v="urn:schemas-microsoft-com:vml"
> xmlns:o="urn:schemas-microsoft-com:office:office"
> xmlns:w="urn:schemas-microsoft-com:office:word"
> xmlns:m="http://schemas.microsoft.com/office/2004/12/omml"
> xmlns="http://www.w3.org/TR/REC-html40">
>
> Definitely.:p>
>
> Actually I had my real-world case in mind, so let me explain further with
the
> following snippet::p>
>
> :p> 
>
> let myfun = doSomeWork (); myref := List.filter somefilterfunction !myref
> in:p>
>
> List.iter myfun !myref:p>
>
> :p> 
>
> In this case, a new linked list is created in each iteration of the
> List.filter. (that is, a new list allocation):p>
>
> Then, if doSomeWork () does a lot of work and lots of allocations, the GC
will
> be called on a regular basis while in function myfun. :p>
>
> Then List.iter is tail-recursive, so it doesn't push its successive
arguments
> on the stack. So the successively created myref become unreachable while
still
> iterating on them.:p>
>
> So my question is, how does the GC know whether all these myref created
> throughout the iteration are collectable or not? I'm curious about how
these
> myref are tagged/untagged by the garbage collector. Maybe pointing me the
> relevant portions of the ocamlrun source code would be nice.:p>

The current value of each binding is on the stack and the GC knows
about that. In the tail-recursion the value on the stack is
successively replaced by newer ones while the old ones are forgotten.
The GC then marks everything known (reachable) as still being needed
and everything it can't reach recursively from the known values your
code can't reach either and the GC can free it.

But that isn't even what happens in your case. Your myref is not on
the stack and you do not create a new myref on every iteration. You
only change its value. The GC knows about the myref and it will be one
of the known (reachable) things the GC starts from.

MfG
        Goswin