Why + vs +. but "fake" parametric polymorphism for <

Why + vs +. but "fake" parametric polymorphism for <

[Carlos Pita]

Hi all!

I would like to implement some number crunching inner loops for dsp
stuff with ocaml. I'm a newcomer to the language with strong
scheme/python background and trying to come into terms with type
inference, parametric polymorphism and structural subtyping. One thing
than I'm pretty fond of is the difference between floating point and
integer basic mathematical operators. I guess the compiler is able to
generate specific and more efficient code for each case without further
analysis. But then I found out that comparison operators offer some kind
of adhoc polymorphism in the guise of parametric one:

# (<);;
- : 'a -> 'a -> bool = <fun>

Is there any reason for this apparently inconsistent design? Would the
generality of < be against performance if for example, say, my critical
inner loops check against a top limit value thousands of times per
second? I'm afraid that the implementation of such a generic operator,
which is so different for numerical integer comparison than v.gr for
string lexicographical comparison, would incur into some run time
overhead. But, as I've said at the beginning, I'm just a newbie and most
probably there is a coherent explanation for all this confusion.

Thank you in advance.
Best regards,
Carlos




	
	
		
__________________________________________________
Preguntá. Respondé. Descubrí.
Todo lo que querías saber, y lo que ni imaginabas,
está en Yahoo! Respuestas (Beta).
¡Probalo ya! 
http://www.yahoo.com.ar/respuestas

Re: [Caml-list] Why + vs +. but "fake" parametric polymorphism for <

[Carlos Pita]

Umh, soon after writing my previous post I found out an interesting
chapter in the tutorial giving an exact example of asm code generated by
the compiler for comparison operator <:

# let max a b =
  if a > b then a else b;;
val max : 'a -> 'a -> 'a = <fun>

===>
        [...]
        ; Call the C "greaterthan" function (in the OCaml library).
        pushl   %ebx
        pushl   %eax
        movl    $greaterthan, %eax
        call    caml_c_call
.L102:
        addl    $8, %esp
        ; If the C "greaterthan" function returned 1, jump to .L100
        [...]

Pretty expensive for a simple int comparison I would say. Which is the
way to go? I bet for-loops are optimized for int arithmetic/comparisons,
aren't they?

Thank you again.
Regards,
Carlos

On Thu, 2006-10-12 at 02:19 -0300, Carlos Pita wrote:
> Hi all!
> 
> I would like to implement some number crunching inner loops for dsp
> stuff with ocaml. I'm a newcomer to the language with strong
> scheme/python background and trying to come into terms with type
> inference, parametric polymorphism and structural subtyping. One thing
> than I'm pretty fond of is the difference between floating point and
> integer basic mathematical operators. I guess the compiler is able to
> generate specific and more efficient code for each case without further
> analysis. But then I found out that comparison operators offer some kind
> of adhoc polymorphism in the guise of parametric one:
> 
> # (<);;
> - : 'a -> 'a -> bool = <fun>
> 
> Is there any reason for this apparently inconsistent design? Would the
> generality of < be against performance if for example, say, my critical
> inner loops check against a top limit value thousands of times per
> second? I'm afraid that the implementation of such a generic operator,
> which is so different for numerical integer comparison than v.gr for
> string lexicographical comparison, would incur into some run time
> overhead. But, as I've said at the beginning, I'm just a newbie and most
> probably there is a coherent explanation for all this confusion.
> 
> Thank you in advance.
> Best regards,
> Carlos
> 
> 
> 
> 
> 	
> 	
> 		
> __________________________________________________
> Pregunt. Respond. Descubr.
> Todo lo que queras saber, y lo que ni imaginabas,
> est en Yahoo! Respuestas (Beta).
> Probalo ya! 
> http://www.yahoo.com.ar/respuestas
> 
> _______________________________________________
> 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


	
	
		
__________________________________________________
Preguntá. Respondé. Descubrí.
Todo lo que querías saber, y lo que ni imaginabas,
está en Yahoo! Respuestas (Beta).
¡Probalo ya! 
http://www.yahoo.com.ar/respuestas

Re: [Caml-list] Why + vs +. but "fake" parametric polymorphism for <

[Basile STARYNKEVITCH]

Le Thu, Oct 12, 2006 at 02:41:20AM -0300, Carlos Pita écrivait/wrote:
> Umh, soon after writing my previous post I found out an interesting
> chapter in the tutorial giving an exact example of asm code generated by
> the compiler for comparison operator <:
> 
> # let max a b =
>   if a > b then a else b;;
> val max : 'a -> 'a -> 'a = <fun>
> 
> ===>
>         [...]
>         ; Call the C "greaterthan" function (in the OCaml library).
>         pushl   %ebx
>         pushl   %eax
>         movl    $greaterthan, %eax
>         call    caml_c_call
> .L102:
>         addl    $8, %esp
>         ; If the C "greaterthan" function returned 1, jump to .L100
>         [...]
> 
> Pretty expensive for a simple int comparison I would say.


If you explicitly type it as an integer compare 
   let max (a : int) b = if a > b then a else b;;
you get much more efficient code (AMD64 linux ocaml 3.09.2 Debian/Sid)


        .globl  camlMaxi__max_57
camlMaxi__max_57:
.L101:
        cmpq    %rbx, %rax
        jle     .L100
        ret
        .align  4
.L100:
        movq    %rbx, %rax
        ret
        .text

-- 
Basile STARYNKEVITCH         http://starynkevitch.net/Basile/ 
email: basile<at>starynkevitch<dot>net 
aliases: basile<at>tunes<dot>org = bstarynk<at>nerim<dot>net
8, rue de la Faïencerie, 92340 Bourg La Reine, France

Re: [Caml-list] Why + vs +. but "fake" parametric polymorphism for <

[Jonathan Roewen]

On 10/12/06, Carlos Pita <cpitadev@yahoo.com.ar> wrote:
> Umh, soon after writing my previous post I found out an interesting
> chapter in the tutorial giving an exact example of asm code generated by
> the compiler for comparison operator <:
>
> # let max a b =
>  if a > b then a else b;;
> val max : 'a -> 'a -> 'a = <fun>
>
> ===>
>        [...]
>        ; Call the C "greaterthan" function (in the OCaml library).
>        pushl   %ebx
>        pushl   %eax
>        movl    $greaterthan, %eax
>        call    caml_c_call
> .L102:
>        addl    $8, %esp
>        ; If the C "greaterthan" function returned 1, jump to .L100
>        [...]
>
> Pretty expensive for a simple int comparison I would say.

It is not an int comparison! max here would work on lists and probably
most other non-abstract types in expected ways.

Try:

let int_max a b : int = if a > b then a else b

ocamlopt -S <source> will help you see what it generates for yourself.

e.g.:

camlTest__int_max_57:
.L101:
        cmpl    %ebx, %eax
        jle     .L100
        ret
        .align  16
.L100:
        movl    %ebx, %eax
        ret
        .text
        .align  16

Jonathan

Re: [Caml-list] Why + vs +. but "fake" parametric polymorphism for <

[Carlos Pita]

> > Pretty expensive for a simple int comparison I would say.
> 
> It is not an int comparison! 

Ok, I meant it would put much of a burden on performance in case max was
called with mere unboxed int arguments.

> Try:
> 
> let int_max a b : int = if a > b then a else b

Great! It's crystal clear now. Thank you all!



	
	
		
__________________________________________________
Preguntá. Respondé. Descubrí.
Todo lo que querías saber, y lo que ni imaginabas,
está en Yahoo! Respuestas (Beta).
¡Probalo ya! 
http://www.yahoo.com.ar/respuestas

Why + vs +. but "fake" parametric polymorphism for <

[Carlos Pita]

Hi all!

I would like to implement some number crunching inner loops for dsp
stuff with ocaml. I'm a newcomer to the language with strong
scheme/python background and trying to come into terms with type
inference, parametric polymorphism and structural subtyping. One thing
than I'm pretty fond of is the difference between floating point and
integer basic mathematical operators. I guess the compiler is able to
generate specific and more efficient code for each case without further
analysis. But then I found out that comparison operators offer some kind
of adhoc polymorphism in the guise of parametric one:

# (<);;
- : 'a -> 'a -> bool = <fun>

Is there any reason for this apparently inconsistent design? Would the
generality of < be against performance if for example, say, my critical
inner loops check against a top limit value thousands of times per
second? I'm afraid that the implementation of such a generic operator,
which is so different for numerical integer comparison than v.gr for
string lexicographical comparison, would incur into some run time
overhead. But, as I've said at the beginning, I'm just a newbie and most
probably there is a coherent explanation for all this confusion.

Thank you in advance.
Best regards,
Carlos



	
	
		
__________________________________________________
Preguntá. Respondé. Descubrí.
Todo lo que querías saber, y lo que ni imaginabas,
está en Yahoo! Respuestas (Beta).
¡Probalo ya! 
http://www.yahoo.com.ar/respuestas

Re: [Caml-list] Why + vs +. but "fake" parametric polymorphism for <

[Jacques Garrigue]

From: Carlos Pita <cpitaper@yahoo.com.ar>

> I would like to implement some number crunching inner loops for dsp
> stuff with ocaml. I'm a newcomer to the language with strong
> scheme/python background and trying to come into terms with type
> inference, parametric polymorphism and structural subtyping. One thing
> than I'm pretty fond of is the difference between floating point and
> integer basic mathematical operators. I guess the compiler is able to
> generate specific and more efficient code for each case without further
> analysis. But then I found out that comparison operators offer some kind
> of adhoc polymorphism in the guise of parametric one:
> 
> # (<);;
> - : 'a -> 'a -> bool = <fun>
> 
> Is there any reason for this apparently inconsistent design? Would the
> generality of < be against performance if for example, say, my critical
> inner loops check against a top limit value thousands of times per
> second?

The reason is that this operator comes handy for symbolic
computations, where you may want to compare lists or other data
structures. And contrary to addition, comparison makes sense for
almost any data structure.

Of course there is an overhead. But the compiler is clever enough to
remove this overhead when the types of arguments are statically known.
In particular this is true for floats.
If you're going to do number crunching, you must be careful of
using it only in situation where the types of the arguments are known,
i.e. not inside polymorphic functions. Typical examples of polymorphic
functions that will call the slow version of equality are List.mem and
List.assoc.

Cheers,

Jacques Garrigue

Re: [Caml-list] Why + vs +. but "fake" parametric polymorphism for <

[Carlos Pita]

> Of course there is an overhead. But the compiler is clever enough to
> remove this overhead when the types of arguments are statically known.
> In particular this is true for floats.

Oh, I see, so if I understand you it would be enough if I use an integer
literal somewhere or explicitly declare some variable as int so the
compiler can infer that the particular use of the comparison operator is
being passed integer operands and consequently inline an specific,
optimized-for-int, version of <. Am I wrong?
Cheers,
Carlos


	
	
		
__________________________________________________
Preguntá. Respondé. Descubrí.
Todo lo que querías saber, y lo que ni imaginabas,
está en Yahoo! Respuestas (Beta).
¡Probalo ya! 
http://www.yahoo.com.ar/respuestas

Re: [Caml-list] Why + vs +. but "fake" parametric polymorphism for <

[Jonathan Roewen]

That's correct. As showed, specifying types somewhere (as I did with
the return type, and someone else did for a given parameter), type
inference deduces the types of the parameters and return values,
allowing it optimise.

let f x y : <t> = .... specifies the return type, or to annotate a
parameter, use (x:<t>) -- the parentheses are required, and <t> is a
placeholder for the type expression.

On 10/12/06, Carlos Pita <cpitaper@yahoo.com.ar> wrote:
>
> > Of course there is an overhead. But the compiler is clever enough to
> > remove this overhead when the types of arguments are statically known.
> > In particular this is true for floats.
>
> Oh, I see, so if I understand you it would be enough if I use an integer
> literal somewhere or explicitly declare some variable as int so the
> compiler can infer that the particular use of the comparison operator is
> being passed integer operands and consequently inline an specific,
> optimized-for-int, version of <. Am I wrong?
> Cheers,
> Carlos
>
>
>
>
>
> __________________________________________________
> Preguntá. Respondé. Descubrí.
> Todo lo que querías saber, y lo que ni imaginabas,
> está en Yahoo! Respuestas (Beta).
> ¡Probalo ya!
> http://www.yahoo.com.ar/respuestas
>
> _______________________________________________
> 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] Why + vs +. but "fake" parametric polymorphism for <

[Carlos Pita]

> Well, to reiterate Jacques warning, annotating the arguments and then 
> calling a function which is polymorphic won't magically cause the 
> polymorphic function to use the non-polymorphic comparisons.
> 

let
  max a b = if a > b then a else b
in
  print_int (max 2 3);;

Ok, I understand. By inspection of code generated for the snippet above
one sees that albeit the max function is in fact inlined the compiler
won't optimize the comparison for ints. What is to be concluded here, if
any? Is the moral of the story that when inlining the compiler won't try
further optimizations beyond almost verbatim copy of code for the
inlined fragment, which was once and for all generated in isolation
without attending to specific contexts of use? So, if this is the case,
following the tutorial and your remarks the best bet is to specify types
for the arguments when defining a function so the compiler get the
chance to optimize it locally.

Cheers,
Carlos.


	
	
		
__________________________________________________
Preguntá. Respondé. Descubrí.
Todo lo que querías saber, y lo que ni imaginabas,
está en Yahoo! Respuestas (Beta).
¡Probalo ya! 
http://www.yahoo.com.ar/respuestas

Re: [Caml-list] Why + vs +. but "fake" parametric polymorphism for <

[Diego Olivier FERNANDEZ PONS]

     Bonjour,

Quoting Jonathan Roewen <jonathan.roewen@gmail.com>:
> That's correct. As showed, specifying types somewhere (as I did with
> the return type, and someone else did for a given parameter), type
> inference deduces the types of the parameters and return values,
> allowing it optimise.

As far as I remember it doesn't work when you specify the type in the  
.mli file. And I never understood really why.

         Diego Olivier

Re: [Caml-list] Why + vs +. but "fake" parametric polymorphism for <

[Gerd Stolpmann]

Am Freitag, den 13.10.2006, 13:56 +0200 schrieb Diego Olivier FERNANDEZ
PONS:
>      Bonjour,
> 
> Quoting Jonathan Roewen <jonathan.roewen@gmail.com>:
> > That's correct. As showed, specifying types somewhere (as I did with
> > the return type, and someone else did for a given parameter), type
> > inference deduces the types of the parameters and return values,
> > allowing it optimise.
> 
> As far as I remember it doesn't work when you specify the type in the  
> .mli file. And I never understood really why.

Well, this is quite easy. The .mli file does not influence code
generation. Code is generated when the .ml file is compiled, and it is
only _checked_ afterwards if the types match the .mli file. This is
simply the logic of the .mli.

That an inlined function cannot be specialized afterwards has a similar
reason, because the part of code generation is already over that decides
whether the mono or polymorphic version is generated. This could be
probably be changed (but I don't know the details, so maybe this would
break something else).

Gerd
-- 
------------------------------------------------------------
Gerd Stolpmann * Viktoriastr. 45 * 64293 Darmstadt * Germany 
gerd@gerd-stolpmann.de          http://www.gerd-stolpmann.de
Phone: +49-6151-153855                  Fax: +49-6151-997714
------------------------------------------------------------

Re: [Caml-list] Why + vs +. but "fake" parametric polymorphism for <

[Diego Olivier FERNANDEZ PONS]

     Bonjour,

Quoting Gerd Stolpmann <info@gerd-stolpmann.de>:
> Well, this is quite easy. The .mli file does not influence code
> generation. Code is generated when the .ml file is compiled, and it is
> only _checked_ afterwards if the types match the .mli file. This is
> simply the logic of the .mli.

Very well, but why ?

         Diego Olivier

Re: [Caml-list] Why + vs +. but "fake" parametric polymorphism for <

[Luc Maranget]

>     Bonjour,
> 
> Quoting Gerd Stolpmann <info@gerd-stolpmann.de>:
> >Well, this is quite easy. The .mli file does not influence code
> >generation. Code is generated when the .ml file is compiled, and it is
> >only _checked_ afterwards if the types match the .mli file. This is
> >simply the logic of the .mli.
> 
> Very well, but why ?
> 
>         Diego Olivier

By design, I guess.

-- 
Luc Maranget

Re: [Caml-list] Why + vs +. but "fake" parametric polymorphism for <

[Diego Olivier FERNANDEZ PONS]

     Bonjour,

Quoting Luc Maranget <luc.maranget@inria.fr>:
>>> This is simply the logic of the .mli.
>>
>> Very well, but why ?
>
> By design, I guess.

Oui mais pourquoi ?

Allez... je retombe en enfance.

Quand j'étais petit, j'ai voulu mettre une annotation de type dans mon  
code Caml du genre:
val fib : int -> int
let rec fib = function ...

Et on m'a dit "Ah non mon garçon, ça c'est du Haskell. En Caml on met  
les annotations dans le .mli, c'est d'ailleurs ça le _veritable_  
esprit de l'inférence de types : ne pas avoir besoin d'écrire de types".

Il faut reconnaître que l'on a tout fait pour rendre les annotations  
de type dans le code totalement illisibles - comparativement à Haskell  
par exemple. Et tout fait pour que le .mli soit aisément utilisable  
(Ctrl-C Ctrl-A sous Emacs, outils de documentation, etc.)

Mais après on me dit que si je mets mes annotations de type dans le  
.mli c'est moins bien que si je les mets dans le .ml avec la syntaxe  
illisible car les optimisations ne sont pas faites.

Et l'esprit de l'inférence de types alors ?

         Diego Olivier

Re: [Caml-list] Why + vs +. but "fake" parametric polymorphism for <

[skaller]

On Fri, 2006-10-13 at 15:01 +0200, Luc Maranget wrote:
> >     Bonjour,
> > 
> > Quoting Gerd Stolpmann <info@gerd-stolpmann.de>:
> > >Well, this is quite easy. The .mli file does not influence code
> > >generation. Code is generated when the .ml file is compiled, and it is
> > >only _checked_ afterwards if the types match the .mli file. This is
> > >simply the logic of the .mli.
> > 
> > Very well, but why ?
> > 
> >         Diego Olivier
> 
> By design, I guess.

Well here's a waffly explanation:

Interfaces act as constraints on what a module
exports. These constraints permit eliding some symbols.

They also permit abstracting types, or replacing types
with sub/supertypes (depending on variance) or specialisations.

The public,for example, could permitted to call a polymorphic
function only monomorphically:

let ident x = x 

is polymorphic but the mli file can say:

val ident : int -> int

This particular factor is almost essential working
with polymorphic variants.

I find this constraint mechanism is sometimes annoying BUT
I'd miss it if it were missing!

It's annoying because you tend to get unintuitive
type error diagnostics, and because one is often
forced to duplicate definitions from *.ml files
in *.mli files for no apparent reason (there is,
of course, a reason).


-- 
John Skaller <skaller at users dot sf dot net>
Felix, successor to C++: http://felix.sf.net

Re: [Caml-list] Why + vs +. but "fake" parametric polymorphism for <

[Luc Maranget]

> Interfaces act as constraints on what a module
> exports. These constraints permit eliding some symbols.
> 
> They also permit abstracting types, or replacing types
> with sub/supertypes (depending on variance) or specialisations.
> <SNIP> relevant examples </SNIP>
> ... for no apparent reason (there is,
> of course, a reason).

Thank you Skaller for this neat explanation and clear conclusion.
My answer was much less informative, I admit.


--Luc

Re: [Caml-list] Why + vs +. but "fake" parametric polymorphism for <

[Gerd Stolpmann]

Am Freitag, den 13.10.2006, 14:46 +0200 schrieb Diego Olivier FERNANDEZ
PONS:
>      Bonjour,
> 
> Quoting Gerd Stolpmann <info@gerd-stolpmann.de>:
> > Well, this is quite easy. The .mli file does not influence code
> > generation. Code is generated when the .ml file is compiled, and it is
> > only _checked_ afterwards if the types match the .mli file. This is
> > simply the logic of the .mli.
> 
> Very well, but why ?

I think the answer is that ocaml uses the model of separate compilation.
That means you can compile the top-level modules separately (in a
certain order) and link them later together. Of course, this implies
that the compilation and code generation steps must be applied in a
certain order. Ocaml is already cleverer than most other implementations
of separate compilation because it allows to defer some parts of code
generation (the so-called cross-module inlining feature).

One can imagine different models. For example, you could do code
generation when a function is _used_, not when the function is seen by
the compiler for the first time. That way, you can always specialize the
function in the generated code to what the types allow. Such a model is
seen as quite problematic, however, because it is unclear how to create
pre-compiled libraries. (In the C++ world often a variation of this
model is used, and is an endless source of problems.)

Of course, you may ask why Ocaml's inlining feature isn't clever enough
to do late specialisation, at least of functions that can be inlined. I
don't know.

Gerd
-- 
------------------------------------------------------------
Gerd Stolpmann * Viktoriastr. 45 * 64293 Darmstadt * Germany 
gerd@gerd-stolpmann.de          http://www.gerd-stolpmann.de
Phone: +49-6151-153855                  Fax: +49-6151-997714
------------------------------------------------------------

Re: [Caml-list] Why + vs +. but "fake" parametric polymorphism for <

[Luc Maranget]

> 
> Of course, you may ask why Ocaml's inlining feature isn't clever enough
> to do late specialisation, at least of functions that can be inlined. I
> don't know.
> 
> Gerd
> -- 

Technically, the ocamlc and ocamlopt compilers share a common
front end that performs the specialization (on the so-called
typed syntax, if I remember well).

By design, both compilers have a lot common.

Only the ocamlopt compiler performs inlining, on a later
internal representation of code.

As to re-performing specialisation in ocamlopt back-end,
precise types are lost there, I am afraid. This may be by design.

--Luc