[Caml-list] equality testing in 3.08

[Caml-list] equality testing in 3.08

[Matt Harren]

Hi,

I recently upgraded to OCaml 3.08, and ran into problems with the
changed implementation of structural equality.  To support NaN, the (=)
operator no longer checks for physical equality or its operands.  This
causes two problems:
  1) Our application runs 9% slower because comparison isn't as
efficient.  When x == y, checking "x = y" takes time proportional to the
size of the structure, instead of constant time.
  2) We've been cheating and using (=) on structures that may be cyclic.
This works fine on earlier versions of ocaml, because the structures
contain a unique identifier as their first field.  But now that
structural equality checks no longer begin with a physical equality
check, we can get an infinite loop.


To work around this, I've been defining
   let (=) x1 x2 : bool =
     (compare x1 x2) = 0
at the start of each file, since the "compare" function still starts
with a physical equality check.  Is there a better way to override a
definition in the Pervasives module?

Also, has there been any discussion of restoring the old meaning of (=)?
I know it breaks NaN, but the performance difference might make this
worthwhile, even if you have no sympathy for those of us who use = on
cyclic structures. :)


Thanks,
Matt


-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] equality testing in 3.08

[Christophe TROESTLER]

On Sun, 1 Aug 2004, "Matt Harren" <matth@cs.berkeley.edu> wrote:
> 
>   1) Our application runs 9% slower because comparison isn't as
> efficient.  When x == y, checking "x = y" takes time proportional to
> the size of the structure, instead of constant time.

I do not know what you are comparing but maybe a custom comparison
function would make things even faster?  As an example,

          min : 'a -> 'a -> 'a
and
          let min' x y = if (x:int) < y then x else y

have (very) different speed characteristics!

>   2) We've been cheating and using (=) on structures that may be cyclic.

Same: why don't you define the meaningful equality?  Sure, you do not
have the convenience of the name "=" but you can use "===", "=^=",
"=~=",...  This probably would also make your software easier to
understand (the "strange" comparison on cyclic structures would be
made explicit).

Regards,
ChriS

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners