Strange observation on polymorphic '<'

Strange observation on polymorphic '<'

[Ritesh Kumar]

Hi,
I saw this on the site http://merjis.com/developers/ocaml_tutorial/ch11
The author says that even if the types of a function (let max a b = if 
a>b then a else b)which internally uses the '>' operator are known (by 
type inference) and are found to be ints, the ocamlopt compiler still 
calls the generic 'greaterthan' function written in C to compare them. 
This seems rather an over kill when a simple comparison instruction 
could have done the job. Am I missing something here? Let us assume 
that the function which internally uses the '<' operator is used only 
in the context of integers inside the program.

Ritesh
--
What you see is an illusion... well protected, well cherished only by 
you.

Re: [Caml-list] Strange observation on polymorphic '<'

[Damien Doligez]

On 30 Nov 2004, at 21:30, Ritesh Kumar wrote:

> Am I missing something here? Let us assume that the function which
> internally uses the '<' operator is used only in the context of 
> integers
> inside the program.

You are missing this: because of separate compilation the compiler has 
no
way to know whether the function will only be used on integers in your
program.  When it compiles the function, it doesn't know what it will
be used for.

-- Damien

Re: [Caml-list] Strange observation on polymorphic '<'

[Ritesh Kumar]

Oh sure... but I was of the mind that if you had a polymorphic function 
which on certain types have extremely small (one instruction) size (as 
is the case with the '>' operator) then it makes sense to inline that 
function at a point where it is invoked with that type.
For eg. given the code
============
let max a b = if a>b then a else b;;
print_int (max 2 3);;
============
Separate compilation means that the function max should use the C call 
(for the toplevel module). However, the invocation of max 2 3 shouldn't 
use a direct call to the function in the same module as the invocation 
is in the same module (i.e. there is opportunity to optimize it based 
on the known invocation types). Secondly, does separate compilation 
make that strong a sense in case of native compilation for OcaML ... 
most probably not because it anyways generates a standalone executable?

Ritesh
P.S. Sorry Damien for the duplicate...
--
What you see is an illusion... well protected, well cherished only by 
you.

On Dec 1, 2004, at 6:17 PM, Damien Doligez wrote:

> On 30 Nov 2004, at 21:30, Ritesh Kumar wrote:
>
>> Am I missing something here? Let us assume that the function which
>> internally uses the '<' operator is used only in the context of 
>> integers
>> inside the program.
>
> You are missing this: because of separate compilation the compiler has 
> no
> way to know whether the function will only be used on integers in your
> program.  When it compiles the function, it doesn't know what it will
> be used for.
>
> -- 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] Strange observation on polymorphic '<'

[Ville-Pertti Keinonen]

On Fri, 2004-12-03 at 02:24 -0500, Ritesh Kumar wrote:

> let max a b = if a>b then a else b;;
> print_int (max 2 3);;
> ============
> Separate compilation means that the function max should use the C call 
> (for the toplevel module). However, the invocation of max 2 3 shouldn't 
> use a direct call to the function in the same module as the invocation 
> is in the same module (i.e. there is opportunity to optimize it based 

The decision of whether to inline a function is done based on its size.
You can increase the inlining level to allow for larger functions to be
inlined.

However, apparently inlining is currently done after deciding whether to
call the polymorphic function, so it doesn't help in this case, which is
definitely a missed optimization opportunity.

> on the known invocation types). Secondly, does separate compilation 
> make that strong a sense in case of native compilation for OcaML ... 
> most probably not because it anyways generates a standalone executable?

OCaml supports inlining across compilation units, so eliminating
separate compilation probably wouldn't automatically give you any
benefits.

There is at least one compiler for a related language (Standard ML) that
does global analysis by compiling everything at once (MLtoN).  It's
quite a bit more complex compared to OCaml, doesn't generate
significantly faster code for common cases, and supports far fewer
platforms.  MLtoN does have the nice ability to support unboxed,
untagged integers, though.

Missing a function

[Frédéric Gava]

Hi,

I have done a comparaison on three data structures of the stdlib of OCaml (I
do parallel implementation of this data structure) and I find that the
module Map does not contain any function for counting the number of elements
of the data structure:
   Set, cardinal: t -> int
   Hashtbl,  lenght : ('a,'b) t -> int
   Map,    you have to do   "let length the_map = fold (fun _ _ i -> i+1)
the_map 0 "

And Set and Hastbl have also fold...

Is there an explanation (or is it just a missing ;-) ) ?

Cheers,
Frédéric Gava

Re: [Caml-list] Missing a function

[sejourne_kevin]

Frédéric Gava wrote:
> Hi,
> 
> I have done a comparaison on three data structures of the stdlib of OCaml (I
> do parallel implementation of this data structure) and I find that the
> module Map does not contain any function for counting the number of elements
> of the data structure:
>    Set, cardinal: t -> int
>    Hashtbl,  lenght : ('a,'b) t -> int
>    Map,    you have to do   "let length the_map = fold (fun _ _ i -> i+1)
> the_map 0 "
> 
> And Set and Hastbl have also fold...
> 
> Is there an explanation (or is it just a missing ;-) ) ?

There is a 'fold' function in functor Make.
val fold : (key -> 'a -> 'b -> 'b) -> 'a t -> 'b -> 'b

so :

let cardinal e = fold (fun _ _ x -> succ x) e 0;;

Re: [Caml-list] Missing a function

[Frédéric Gava]

> > I have done a comparaison on three data structures of the stdlib of
OCaml (I
> > do parallel implementation of this data structure) and I find that the
> > module Map does not contain any function for counting the number of
elements
> > of the data structure:
> >    Set, cardinal: t -> int
> >    Hashtbl,  lenght : ('a,'b) t -> int
> >    Map,    you have to do   "let length the_map = fold (fun _ _ i ->
i+1)
> > the_map 0 "
> > And Set and Hastbl have also fold...
> > Is there an explanation (or is it just a missing ;-) ) ?
>
> There is a 'fold' function in functor Make.
> val fold : (key -> 'a -> 'b -> 'b) -> 'a t -> 'b -> 'b
> so :
> let cardinal e = fold (fun _ _ x -> succ x) e 0;;

Hi,

> >    Map,    you have to do   "let length the_map = fold (fun _ _ i ->
i+1)
> let cardinal e = fold (fun _ _ x -> succ x) e 0;;

Ok. That is the same things (except the name) that I have written  in  my
mail... but this method is not very efficient because you apply many time
a function without using its arguments. Map are also implemented as balanced
tree (like sets) and therefore, it is easy to add a function of "cardinal".

Cheers,
Frédéric Gava

Re: [Caml-list] Missing a function

[Radu Grigore]

On Sat, 4 Dec 2004 15:13:44 +0100, Frédéric Gava
<frederic.gava@wanadoo.fr> wrote:

> > let cardinal e = fold (fun _ _ x -> succ x) e 0;;
> [...] Map are also implemented as balanced
> tree (like sets) and therefore, it is easy to add a function of "cardinal".

I agree it's strange not to have "cardinal" in Map.Make. The
implementations of Set and Map are likely to be very similar anyway.

I do not have the ocaml sources handy right now but... Set and Map are
probably RB-trees. In this case there are at least 2 pointers for
links (left and right children),  one pointer for key and, for maps,
one pointer for data.  So a set of N elements occupies at least 12xN
bytes, while a map occupies at least 16xN bytes. If an element counter
is added then the sizes would increase to 16xN and 20xN. That doesn't
seem too bad. The advantages would be:

a. O(1) cardinal function. Right now for Map the user can implement a
O(n) one and for Set the complexity isn't specified. It is probably
O(lg n).

b. O(lg n) indexed access.

Such a change implies minimal modification of existing functions:
Set.cardinal becomes faster (if my guess -- lg n -- was correct) and
add/remove will be _slightly_ slower. The advantage would be
Map.cardinal and indexed access.

-- 
regards,
 radu
http://rgrig.idilis.ro/

Re: [Caml-list] Missing a function

[Radu Grigore]

On Sat, 29 Jan 2005 21:34:28 +0200, Radu Grigore <radugrigore@gmail.com> wrote:

> for Set the complexity [of cardinal] isn't specified. It is probably
> O(lg n).

Strike that :( I don't know what went in my mind. I should probably
make a habit of waiting 5min before pressing "send" :(

-- 
regards,
 radu
http://rgrig.idilis.ro/

Re: [Caml-list] Missing a function

[Olivier Andrieu]

 > Radu Grigore [Sat, 29 Jan 2005]:
 > On Sat, 4 Dec 2004 15:13:44 +0100, Frédéric Gava
 > <frederic.gava@wanadoo.fr> wrote:
 > 
 > > > let cardinal e = fold (fun _ _ x -> succ x) e 0;;
 > > [...] Map are also implemented as balanced
 > > tree (like sets) and therefore, it is easy to add a function of "cardinal".
 > 
 > I agree it's strange not to have "cardinal" in Map.Make. The
 > implementations of Set and Map are likely to be very similar anyway.

Another option is to build on top of the stdlib Map functor another
functor that keeps track of the cardinal of a map :

module CMap = functor (Ord : Map.OrderedType) ->
  (struct
    module M = Map.Make (Ord)
	
    type key = M.key
    type 'a t = int * 'a M.t

    let cardinal = fst

    let empty = 0, M.empty

    let add k v (n, m) = (n + 1, M.add k v m)

    let find k (_, m) = M.find k m
	  
	....
   : sig
       include Map.S
       val cardinal : 'a t -> int
     end)

-- 
   Olivier

Re: [Caml-list] Missing a function

[Radu Grigore]

On Sat, 29 Jan 2005 21:34:28 +0200, Radu Grigore <radugrigore@gmail.com> wrote:

> I do not have the ocaml sources handy right now but... Set and Map are
> probably RB-trees.

Map is not a RB-tree but a height balanced tree: HB(2). (haven't looked at Set)

BTW, what does the license say about reusing the code in map.ml?
Please use simple terms for people that don't like to deal with
administrative stuff. The ideal response would be: do it / don't do it
:)

(Now that I have read the code I would probably write it very
similarly even if I would not look at it any more...)

-- 
regards,
 radu
http://rgrig.idilis.ro/

Fw: [Caml-list] Missing a function

[Frédéric Gava]

Hi,
>
> > Another option is to build on top of the stdlib Map functor another
> > functor that keeps track of the cardinal of a map :
> >
> > module CMap = functor (Ord : Map.OrderedType) ->
> >   (struct
> >     module M = Map.Make (Ord)
> >
> >     type key = M.key
> >     type 'a t = int * 'a M.t
> >
> >     let cardinal = fst
> >
> >     let empty = 0, M.empty
> >
> >     let add k v (n, m) = (n + 1, M.add k v m)
> >
> >     let find k (_, m) = M.find k m
> >
> > ....
> >    : sig
> >        include Map.S
> >        val cardinal : 'a t -> int
> >      end)
> >
Hum. To remove an element, you have to test is its exists or not before
decrease n. It could be to much cost expansive...no ?

Regards,
Frédéric Gava

Re: [Caml-list] Missing a function

[Olivier Andrieu]

 > Frédéric Gava [Sun, 30 Jan 2005]:
 > Hi,
 > >
 > > > Another option is to build on top of the stdlib Map functor another
 > > > functor that keeps track of the cardinal of a map :
 > > >
 > > > module CMap = functor (Ord : Map.OrderedType) ->
 > > >   (struct
 > > >     module M = Map.Make (Ord)
 > > >
 > > >     type key = M.key
 > > >     type 'a t = int * 'a M.t
 > > >
 > > >     let cardinal = fst
 > > >
 > > >     let empty = 0, M.empty
 > > >
 > > >     let add k v (n, m) = (n + 1, M.add k v m)
 > > >
 > > >     let find k (_, m) = M.find k m
 > > >
 > > > ....
 > > >    : sig
 > > >        include Map.S
 > > >        val cardinal : 'a t -> int
 > > >      end)
 > > >
 > Hum. To remove an element, you have to test is its exists or not
 > before decrease n. It could be to much cost expansive...no ?

Oh right. And a test is needed for `add' too since the cardinal will
not change if the key is already bound in the map. So, all in all it's
not a very good idea :)

-- 
   Olivier