[Caml-list] Comparing variant types

[Caml-list] Comparing variant types

[Ethan Burns]

Hi,

I have a program that uses variant types as an enumeration.  While
profiling, I noticed that compare_val was being called a bunch.  When
I went to inspect why this was the case, it turns out that it was
being called to compare equality of my variants.  I am a bit confused,
however, because my understanding was that variants that are declared
without an 'of' clause were just represented as integers and therefore
a type containing only these simple elements should be directly
comparable (no compare_val).

While looking further into this, I found a little example where the
compiler seems to produce a simple comparison in one case and not in
another:

type dir = Left | Right | Up | Down | No_op

(* performs a simple comparison *)
let f a = a <> Right

(* calls out to C to do compare_val *)
let g (a:dir) b = a <> b

There is the -dlambda output:

(seq
  (let (f/69 (function a/70 (!= a/70 1a)))
    (setfield_imm 0 (global Test!) f/69))
  (let (g/71 (function a/72 b/73 (caml_notequal a/72 b/73)))
    (setfield_imm 1 (global Test!) g/71))
  0a)

Since both functions know that the types of the elements being compare
is 'dir', which contains only simple elements, why does the g function
still use compare_val?  Does the compiler not perform this particular
optimization?


Best,
Ethan

Re: [Caml-list] Comparing variant types

[Vincent Aravantinos]

Hi,

without entering any details, probably the following links would be  
interesting to you:

http://ocaml.janestreet.com/?q=node/33
http://ocaml.janestreet.com/?q=node/35

V.

Le 28 avr. 11 à 21:16, Ethan Burns a écrit :

> Hi,
>
> I have a program that uses variant types as an enumeration.  While
> profiling, I noticed that compare_val was being called a bunch.  When
> I went to inspect why this was the case, it turns out that it was
> being called to compare equality of my variants.  I am a bit confused,
> however, because my understanding was that variants that are declared
> without an 'of' clause were just represented as integers and therefore
> a type containing only these simple elements should be directly
> comparable (no compare_val).
>
> While looking further into this, I found a little example where the
> compiler seems to produce a simple comparison in one case and not in
> another:
>
> type dir = Left | Right | Up | Down | No_op
>
> (* performs a simple comparison *)
> let f a = a <> Right
>
> (* calls out to C to do compare_val *)
> let g (a:dir) b = a <> b
>
> There is the -dlambda output:
>
> (seq
>  (let (f/69 (function a/70 (!= a/70 1a)))
>    (setfield_imm 0 (global Test!) f/69))
>  (let (g/71 (function a/72 b/73 (caml_notequal a/72 b/73)))
>    (setfield_imm 1 (global Test!) g/71))
>  0a)
>
> Since both functions know that the types of the elements being compare
> is 'dir', which contains only simple elements, why does the g function
> still use compare_val?  Does the compiler not perform this particular
> optimization?
>
>
> Best,
> Ethan
>
> -- 
> Caml-list mailing list.  Subscription management and archives:
> https://sympa-roc.inria.fr/wws/info/caml-list
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs
>

Re: [Caml-list] Comparing variant types

[Ethan Burns]

On Thu, Apr 28, 2011 at 5:07 PM, Vincent Aravantinos
<vincent.aravantinos@gmail.com> wrote:
> Hi,
>
> without entering any details, probably the following links would be
> interesting to you:
>
> http://ocaml.janestreet.com/?q=node/33
> http://ocaml.janestreet.com/?q=node/35

Thanks for the links.  Actually, I think that understand OCaml's
polymorphic comparison and how to get rid of it (for the most part). I
guess that I just found it surprising that the compiler doesn't seem
to optimize it away in this case (a variant type used as an
enumeration with only simple constructors).  I suppose that one
solution would be to just use let-bindings to associate integers with
names "by hand" instead of using the variant type.  I don't really
like that approach too much, however.


Ethan

Re: [Caml-list] Comparing variant types

[Fabrice Le Fessant]

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

On 04/29/2011 12:57 AM, Ethan Burns wrote:
> Thanks for the links.  Actually, I think that understand OCaml's
> polymorphic comparison and how to get rid of it (for the most part). I
> guess that I just found it surprising that the compiler doesn't seem
> to optimize it away in this case (a variant type used as an
> enumeration with only simple constructors).  I suppose that one
> solution would be to just use let-bindings to associate integers with
> names "by hand" instead of using the variant type.  I don't really
> like that approach too much, however.

Indeed, the compiler does not do it... yet. But it's already somewhere
on someone's TODO list ;-)

Fabrice

[-- Attachment #2: fabrice_le_fessant.vcf --]
[-- Type: text/x-vcard, Size: 380 bytes --]

begin:vcard
fn:Fabrice LE FESSANT
n:LE FESSANT;Fabrice
org:INRIA Saclay -- Ile-de-France;P2P & OCaml
adr;quoted-printable:;;Parc Orsay Universit=C3=A9 ;Orsay CEDEX;;91893;France
email;internet:fabrice.le_fessant@inria.fr
title;quoted-printable:Charg=C3=A9 de Recherche
tel;work:+33 1 74 85 42 14
tel;fax:+33 1 74 85 42 49 
url:http://fabrice.lefessant.net/
version:2.1
end:vcard

Re: [Caml-list] Comparing variant types

[Dmitry Bely]

On Thu, Apr 28, 2011 at 11:16 PM, Ethan Burns <burns.ethan@gmail.com> wrote:
> Hi,
>
> I have a program that uses variant types as an enumeration.  While
> profiling, I noticed that compare_val was being called a bunch.  When
> I went to inspect why this was the case, it turns out that it was
> being called to compare equality of my variants.  I am a bit confused,
> however, because my understanding was that variants that are declared
> without an 'of' clause were just represented as integers and therefore
> a type containing only these simple elements should be directly
> comparable (no compare_val).
>
> While looking further into this, I found a little example where the
> compiler seems to produce a simple comparison in one case and not in
> another:
>
> type dir = Left | Right | Up | Down | No_op
>
> (* performs a simple comparison *)
> let f a = a <> Right
>
> (* calls out to C to do compare_val *)
> let g (a:dir) b = a <> b
>
> There is the -dlambda output:
>
> (seq
>  (let (f/69 (function a/70 (!= a/70 1a)))
>    (setfield_imm 0 (global Test!) f/69))
>  (let (g/71 (function a/72 b/73 (caml_notequal a/72 b/73)))
>    (setfield_imm 1 (global Test!) g/71))
>  0a)
>
> Since both functions know that the types of the elements being compare
> is 'dir', which contains only simple elements, why does the g function
> still use compare_val?  Does the compiler not perform this particular
> optimization?

I don't know why structured compare is not optimized, but physical one
(which does the same in your case) is optimized away as expected.

let g (a:dir) b = a != b

- Dmitry Bely

Re: [Caml-list] Comparing variant types

[luc.maranget]

> > (* performs a simple comparison *)
> > let f a = a <> Right
> >
> > (* calls out to C to do compare_val *)
> > let g (a:dir) b = a <> b
> >
...
> 
> let g (a:dir) b = a != b
> 
> - Dmitry Bely
> 

As a general rule, don't do that! :)  (using <> or !=
for writing  'g').


For <>, you'll get hurt by data types with non-unique representation
(such as Set), as already pointed out.
It is ok to use structural equality when it is not the case, but
your programm is not as robust as you may want it to be.

For !=, it is much worse, as soon as you add a non-constant
constructor to your data type, your code is wrong
(cf. [1] != [1])

If you aim at robust  code. A recommended (tiresome) alternative
is to write your own equality function once for all, in
the following style.

type dir = Left | Right | Up | Down | No_op

let dir_equal d1 d2 = match d1,d2 with
| (Left, Left)
| (Right,Right)
| (Up, Up)
| (Down,Down)
| (No_op,No_op)
 -> true
| (Left,(Right|Up|Down|No_op))
| (Right,(Left|Up|Down|No_op))
| (Up,(Left|Right|Down|No_op))
| (Down,(Left|Right|Up|No_op))
| (No_op,(Down|Up|Right|Left))
-> false



let g a b = not (dir_equal a b)

Notice that 'let f a = a != Right' and 'let f a = a <> Right' are
less dangerous, but well...


--Luc

Re: [Caml-list] Comparing variant types

[Andrew]

> type dir = Left | Right | Up | Down | No_op
>
> let dir_equal d1 d2 = match d1,d2 with
> | (Left, Left)
> | (Right,Right)
> | (Up, Up)
> | (Down,Down)
> | (No_op,No_op)
>   ->  true
> | (Left,(Right|Up|Down|No_op))
> | (Right,(Left|Up|Down|No_op))
> | (Up,(Left|Right|Down|No_op))
> | (Down,(Left|Right|Up|No_op))
> | (No_op,(Down|Up|Right|Left))
> ->  false


Why not write directly
	let dir_equal = fun d1 d2 ->
	  | Left Left
	  | Right Right
	  | Up Up
	  | Down Down
	  | No_op No_op ->  true
	  | _ -> false
?

Re: [Caml-list] Comparing variant types

[Dmitry Bely]

On Fri, Apr 29, 2011 at 2:54 PM, Andrew <newsgroups.fr@gmail.com> wrote:
>> type dir = Left | Right | Up | Down | No_op
>>
>> let dir_equal d1 d2 = match d1,d2 with
>> | (Left, Left)
>> | (Right,Right)
>> | (Up, Up)
>> | (Down,Down)
>> | (No_op,No_op)
>>  ->  true
>> | (Left,(Right|Up|Down|No_op))
>> | (Right,(Left|Up|Down|No_op))
>> | (Up,(Left|Right|Down|No_op))
>> | (Down,(Left|Right|Up|No_op))
>> | (No_op,(Down|Up|Right|Left))
>> ->  false
>
>
> Why not write directly
>        let dir_equal = fun d1 d2 ->
>          | Left Left
>          | Right Right
>          | Up Up
>          | Down Down
>          | No_op No_op ->  true
>          | _ -> false

"Directly" means "syntactically incorrect"? :) As for _ clause - you'd
better to avoid it.

- Dmitry Bely

Re: [Caml-list] Comparing variant types

[Dmitry Bely]

On Fri, Apr 29, 2011 at 1:33 PM,  <luc.maranget@inria.fr> wrote:
>> > (* performs a simple comparison *)
>> > let f a = a <> Right
>> >
>> > (* calls out to C to do compare_val *)
>> > let g (a:dir) b = a <> b
>> >
> ...
>>
>> let g (a:dir) b = a != b
>>
>> - Dmitry Bely
>>
>
> As a general rule, don't do that! :)  (using <> or !=
> for writing  'g').
>
>
> For <>, you'll get hurt by data types with non-unique representation
> (such as Set), as already pointed out.
> It is ok to use structural equality when it is not the case, but
> your programm is not as robust as you may want it to be.
>
> For !=, it is much worse, as soon as you add a non-constant
> constructor to your data type, your code is wrong
> (cf. [1] != [1])
>
> If you aim at robust  code. A recommended (tiresome) alternative
> is to write your own equality function once for all, in
> the following style.
>
> type dir = Left | Right | Up | Down | No_op
>
> let dir_equal d1 d2 = match d1,d2 with
> | (Left, Left)
> | (Right,Right)
> | (Up, Up)
> | (Down,Down)
> | (No_op,No_op)
>  -> true
> | (Left,(Right|Up|Down|No_op))
> | (Right,(Left|Up|Down|No_op))
> | (Up,(Left|Right|Down|No_op))
> | (Down,(Left|Right|Up|No_op))
> | (No_op,(Down|Up|Right|Left))
> -> false

Yes, but Ethan's primary concern was efficiency. You dir_equal would
hardly fit (I'm afraid it's even more slow than <> because it's
translated into switch/case block). But generally speaking, of course
robustness is always the first priority.

- Dmitry Bely

RE: [Caml-list] Comparing variant types

[Jon Harrop]

Andrew wrote:
> Why not write directly
> 	let dir_equal = fun d1 d2 ->
> 	  | Left Left
> 	  | Right Right
> 	  | Up Up
> 	  | Down Down
> 	  | No_op No_op ->  true
> 	  | _ -> false

You want to fill out your _ pattern with explicit type constructors
otherwise it is fragile wrt new constructors being added to the type.

Cheers,
Jon.

Re: [Caml-list] Comparing variant types

[craff73]

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

Hello,

You want to avoid code size quadratic in the number of constructors. Which is possible:

let cmp x y = match x, y with
A, A -> true
| A, _ | _, A -> false
| B, B -> true
| B, _ | _, B -> false
...

Cheers
Christophe

-- 
Envoyé de mon téléphone Android avec K-9 Mail. Excusez la brièveté.


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

Re: [Caml-list] Comparing variant types

[Andrew]

On Apr. 29, 2011, Jon Harrop <jon@ffconsultancy.com> wrote:
> Andrew wrote:
>> Why not write directly
>> 	let dir_equal = fun d1 d2 ->
>> 	| Left Left
>> 	  | Right Right
>> 	  | Up Up
>> 	  | Down Down
>> 	  | No_op No_op ->   true
>> 	  | _ ->  false
>
> You want to fill out your _ pattern with explicit type constructors
> otherwise it is fragile wrt new constructors being added to the type.

Oh, ok =)

> Cheers,
> Jon.

Re: [Caml-list] Comparing variant types

[Andrew]

> Hello,
>
> You want to avoid code size quadratic in the number of constructors. Which is possible:
>
> let cmp x y = match x, y with
> A, A -> true
> | A, _ | _, A -> false
> | B, B -> true
> | B, _ | _, B -> false
> ...

Yay! _ strikes back =)

Re: [Caml-list] Comparing variant types

[Gabriel Scherer]

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

>
> You want to avoid code size quadratic in the number of constructors. Which
> is possible:
>


let cmp x y = match x, y with
> A, A -> true
> | A, _ | _, A -> false
> | B, B -> true
> | B, _ | _, B -> false


With one twist though: if done that way for (type foo = A | B), the last (_,
B) pattern is actually redundant. If you want to avoid getting a warning
here, you should comment it out or remove it:

  let cmp x y = match x, y with
  | A, A -> true
  | A, _ | _, A -> false
  | B, B -> true
  | B, _ (*| _, B*) -> false

That's the style I use.

On Sat, Apr 30, 2011 at 3:43 PM, craff73@gmail.com <craff73@gmail.com>wrote:

> Hello,
>
> You want to avoid code size quadratic in the number of constructors. Which
> is possible:
>
> let cmp x y = match x, y with
> A, A -> true
> | A, _ | _, A -> false
> | B, B -> true
> | B, _ | _, B -> false
> ...
>
> Cheers
> Christophe
>
> --
> Envoyé de mon téléphone Android avec K-9 Mail. Excusez la brièveté.
>
>

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

Re: [Caml-list] Comparing variant types

[Yaron Minsky]

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

When I have to do this by hand, my favorite style is this:

type t = A of float | B of string

let compare x y =
   let tag_idx = function  A _ -> 0 | B _ -> 1 in
   match x, y with
   | A a1, A a2 -> Float.compare a1 a2
   | B b1, B b2 -> String.compare b1 b2
   | (B _ | A _), _ -> Int.compare (tag_idx x) (tag_idx y)

You will get the right kind of warnings when the type t changes, and it's
pleasantly explicit about the ordering implied by the tags.

That said, this is unpleasant boilerplate to have to write by hand.  My
expectation is that in the next release of Core, we will include a set of
macros for autogenerating equality, comparison and hash functions, as well
as type-hashes, all driven by the type definitions.

On Sat, Apr 30, 2011 at 4:19 PM, Gabriel Scherer
<gabriel.scherer@gmail.com>wrote:

> You want to avoid code size quadratic in the number of constructors. Which
>> is possible:
>>
>
>
> let cmp x y = match x, y with
>> A, A -> true
>> | A, _ | _, A -> false
>> | B, B -> true
>> | B, _ | _, B -> false
>
>
> With one twist though: if done that way for (type foo = A | B), the last
> (_, B) pattern is actually redundant. If you want to avoid getting a warning
> here, you should comment it out or remove it:
>
>   let cmp x y = match x, y with
>   | A, A -> true
>   | A, _ | _, A -> false
>   | B, B -> true
>   | B, _ (*| _, B*) -> false
>
> That's the style I use.
>
> On Sat, Apr 30, 2011 at 3:43 PM, craff73@gmail.com <craff73@gmail.com>wrote:
>
>> Hello,
>>
>> You want to avoid code size quadratic in the number of constructors. Which
>> is possible:
>>
>> let cmp x y = match x, y with
>> A, A -> true
>> | A, _ | _, A -> false
>> | B, B -> true
>> | B, _ | _, B -> false
>> ...
>>
>> Cheers
>> Christophe
>>
>> --
>> Envoyé de mon téléphone Android avec K-9 Mail. Excusez la brièveté.
>>
>>
>

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

Re: [Caml-list] Comparing variant types

[Ethan Burns]

On Friday, April 29, 2011 5:34:16 AM UTC-4, luc.ma...@inria.fr wrote:
> As a general rule, don't do that! :)  (using <> or !=
> for writing  'g').
> 
> 
> For <>, you'll get hurt by data types with non-unique representation
> (such as Set), as already pointed out.
> It is ok to use structural equality when it is not the case, but
> your programm is not as robust as you may want it to be.

Well, in this case I am actually not really writing the function g and instead this comparison is embedded in another function somewhere.  My feeling was that using <> would be perfectly safe because it would translate to an integer comparison.  The structure of a type containing only simple constructors should be unique (I think they are all just mapped to ints).

> For !=, it is much worse, as soon as you add a non-constant
> constructor to your data type, your code is wrong
> (cf. [1] != [1])
> 
> If you aim at robust  code. A recommended (tiresome) alternative
> is to write your own equality function once for all, in
> the following style.
> 
> type dir = Left | Right | Up | Down | No_op
> 
> let dir_equal d1 d2 = match d1,d2 with
> | (Left, Left)
> | (Right,Right)
> | (Up, Up)
> | (Down,Down)
> | (No_op,No_op)
>  -> true
> | (Left,(Right|Up|Down|No_op))
> | (Right,(Left|Up|Down|No_op))
> | (Up,(Left|Right|Down|No_op))
> | (Down,(Left|Right|Up|No_op))
> | (No_op,(Down|Up|Right|Left))
> -> false

This is tiresome indeed!  Also, I am concerned that it is less efficient than just dropping down to compare_val (although I haven't tried it).  Since the type that I am using will only ever have a unique representation, I would love to avoid something like this.

I think that the solution that I will stick with for now is the one given by Dmitry (although I am typically not a fan of != in general).  Fabrice seemed to imply that optimizing <> in this case was 'in the works.'  I will be pretty happy to see that because I am sure that I have other code lying around somewhere that is assuming <> on a simple 'enum type' is just an integer comparison.


Best,
Ethan