A Question About Types and Inlining

A Question About Types and Inlining

[Jim Grundy]

Apologies in advance for a naive question...

I'm working on a SAT solver in OCaml.  The solver has various types, 
like three-valued bools, variables, literals.  I have modules that 
encapsulate these types and the operations on them.

Now, as it turns out, all these types are represented as ints, but the 
other modules that use those types don't need to know that - and as a 
matter of taste I'd rather not expose this.

The signatures of these modules currently contain lines like this:

type variable (* = int *)

If I uncomment all instances of (* = int *) and reveal the 
representation to the compiler then I get a ... 36% performance 
improvement in the SAT solver.

I have two questions:

1/ Is there some way I can reveal this representation to the parts of 
the system that clearly need it for effective optimization, without 
opening this up for general use.

2/ Failing that, has someone got a pleasant method of doing conditional 
compilation so that I can switch these comments on and off with ease?

I'm using version 3.09.2 of ocamlopt.

Thanks in advance

Jim


-- 
Jim Grundy, Research Scientist. Intel Corporation, Strategic CAD Labs
Mail Stop RA2-451, 2501 NW 229th Ave, Hillsboro, OR 97124-5503, USA
Phone: +1 971 214-1709   Fax: +1 971 214-1771
http://www.intel.com/technology/techresearch/people/bios/grundy_j.htm
Key Fingerprint: 5F8B 8EEC 9355 839C D777  4D42 404A 492A AEF6 15E2

Re: [Caml-list] A Question About Types and Inlining

[Philippe Wang]

Hi.

Ok I misread a line...

I saw once that there were a lot of optimizations based on types 
informations, especially on basic types... So hidding some type 
information would lead to prevent the compiler from some optimization...

Well, I wonder about how to hide the information from the users without 
hiding it to the type checker...

Typically the function compare (or other comparison operators) have to 
check the kinds of their arguments, except when the compiler knows that 
their types are basic types...

Well, I guess you use a lot the function compare ?

Have you tried to force the polymorphic functions' types that are only 
used with integers with the type int ?
(to take back the performance, you will have to tell explicitely the 
compiler to optimise them... or change the compiler code... I guess.)

Cheers,

   Philippe Wang.

Jim Grundy a écrit :
> Hi Philippe
> 
> Thanks for the mail.  That's not quite what I'm looking for:
> 
> I have some module Foo, that implements a type, lets call it abs, that I 
> would like to keep abstract as far as the other modules are concerned.
> 
> In foo.mli I have
> 
>   type abs
> 
> and in foo.ml I have
> 
>   type abs = int
> 
> (which is the set up you were recommending, right)
> 
> But... if I change foo.mli to reveal the type to other modules, that is 
> if foo.mli also says
> 
>   type abs = int
> 
> then the program runs 36% faster.
> 
> I suspect that hiding the type is either preventing inlining of calls 
> from other modules to functions in the foo module, or that hiding the 
> type is forcing the other modules to use a boxed representation rather 
> than an unboxed representation.
> 
> All the best
> 
> Jim
> 
> Philippe Wang wrote:
>> Hi.
>>
>> If I have understood what you meant :
>>
>> Create a .mli file where you put
>> type variable
>>
>> and in the .ml file, put
>> type variable = int
>>
>>
>> It should do what you want (i.e. tell the compiler that the actual 
>> type is int and not allow unifying int type with variable type elsewhere)
>>
>> Note : ocamlopt -i yourmlfile.ml prints the default .mli
>> So you can generate the default .mli easily (at least on unix or cygwin)
>>
>> Cheers,
>> Philippe Wang
>>   mail@philippewang.info
>>
>>
>>
>> Jim Grundy a écrit :
>>> Apologies in advance for a naive question...
>>>
>>> I'm working on a SAT solver in OCaml.  The solver has various types, 
>>> like three-valued bools, variables, literals.  I have modules that 
>>> encapsulate these types and the operations on them.
>>>
>>> Now, as it turns out, all these types are represented as ints, but 
>>> the other modules that use those types don't need to know that - and 
>>> as a matter of taste I'd rather not expose this.
>>>
>>> The signatures of these modules currently contain lines like this:
>>>
>>> type variable (* = int *)
>>>
>>> If I uncomment all instances of (* = int *) and reveal the 
>>> representation to the compiler then I get a ... 36% performance 
>>> improvement in the SAT solver.
>>>
>>> I have two questions:
>>>
>>> 1/ Is there some way I can reveal this representation to the parts of 
>>> the system that clearly need it for effective optimization, without 
>>> opening this up for general use.
>>>
>>> 2/ Failing that, has someone got a pleasant method of doing 
>>> conditional compilation so that I can switch these comments on and 
>>> off with ease?
>>>
>>> I'm using version 3.09.2 of ocamlopt.
>>>
>>> Thanks in advance
>>>
>>> Jim
>>>
>>>
> 

Re: [Caml-list] A Question About Types and Inlining

[Eric Cooper]

On Fri, Dec 08, 2006 at 03:13:40PM -0800, Jim Grundy wrote:
> [...] 
> The signatures of these modules currently contain lines like this:
> type variable (* = int *)
> [...]
> 1/ Is there some way I can reveal this representation to the parts of 
> the system that clearly need it for effective optimization, without 
> opening this up for general use.

You can use
  type variable = Variable of int
  etc.
in your signatures.

This makes the representation visible for optimization purposes,
incurs no representation overhead, but will catch most typing
mistakes.

-- 
Eric Cooper             e c c @ c m u . e d u

Re: [Caml-list] A Question About Types and Inlining

[Philippe Wang]

Eric Cooper a écrit :
> You can use
>   type variable = Variable of int
>   etc.
> in your signatures.
> 
> This makes the representation visible for optimization purposes,
> incurs no representation overhead, but will catch most typing
> mistakes.

I don't get it... Can you tell how adding some boxing/unboxing matter 
can help having better performance ?


I tried this with ocamlopt -inline 4

type v = V of int
let v = V 42 ;;
let _ = match v with V x -> print_int x ;;
print_newline();;
let _ = print_int (Obj.magic v);;
print_newline();;
let _ = print_int (!(Obj.magic v));;
print_newline();;

So whether the Obj.magic "tells" the compiler not to optimise the values 
of type v, whether I really don't get what you meant...

Cheers,
--
Philippe Wang

Re: [Caml-list] A Question About Types and Inlining

[Eric Cooper]

On Sat, Dec 09, 2006 at 02:16:16AM +0100, Philippe Wang wrote:
> I don't get it... Can you tell how adding some boxing/unboxing matter 
> can help having better performance ?

You're right, I completely forgot about the boxing and unboxing, which
will hurt performance.  The exposed representation should still allow
some more optimizations, but I don't know whether it will be enough
for a net gain.

-- 
Eric Cooper             e c c @ c m u . e d u

Re: [Caml-list] A Question About Types and Inlining

[Jon Harrop]

On Saturday 09 December 2006 00:55, Eric Cooper wrote:
> You can use
>   type variable = Variable of int
>   etc.
> in your signatures.
>
> This makes the representation visible for optimization purposes,
> incurs no representation overhead,

In OCaml, that imposes a huge representation overhead.

-- 
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
Objective CAML for Scientists
http://www.ffconsultancy.com/products/ocaml_for_scientists

Re: [Caml-list] A Question About Types and Inlining

[Andrej Bauer]

You can use multiple signatures and modules to combine things just the 
way you want them. For example, you could have modules and signatures 
organized as follows (I made up some types which don't really make sense 
for SAT):

(** The SAT module as seen from the outside. *)
module type SAT =
sig
   module Solver :
   sig
     type variable (* abstract *)
     type problem  (* abstract *)
     type solution = (variable * bool) list
     val solve : problem -> solution
   end

   module SomethingUseful : sig ... end
end

module Sat : SAT =
struct
   (* inside SAT all types are concrete *)

   type variable = int
   type problem = (variable * variable * variable) array
   type solution = (variable * bool) list

   module SatHelper =
   struct
     (* here is a helper module which is not even seen from outside *)
     (* it can rely on internal representation *)
     let internal_solve = ...
   end

   (* The module Solver is exported, we put in it exactly what we want
       the user to see. *)
   module Solver =
   struct
     type variable = variable
     type problem = problem
     type solution = solution
     let solve = SatHelper.internal_solve
   end

   module SomethingUseful = struct ... end
end

My point is that by nesting modules and exposing just the right amount 
of their interfaces through several different signatures, you can 
control precisely what is seen from where. There is no need to always 
realy on the simplistic view

   module    = .ml file
   signature = .mli file

which is just a convenient shortcut that works in simple examples.

Best regards,

Andrej

P.S. The example above makes it look as if you have to stick everything 
inside one huge file. That's not true, as you can use "include", as well 
as type sharing constraints ("with type1 = type2") to expose certain 
types between modules.

Re: [Caml-list] A Question About Types and Inlining

[Nicolas Pouillard]

Hi Jim,

On 12/9/06, Jim Grundy <jim_grundy@ichips.intel.com> wrote:
> Apologies in advance for a naive question...
>
> I'm working on a SAT solver in OCaml.  The solver has various types,
> like three-valued bools, variables, literals.  I have modules that
> encapsulate these types and the operations on them.
>
> Now, as it turns out, all these types are represented as ints, but the
> other modules that use those types don't need to know that - and as a
> matter of taste I'd rather not expose this.
>
> The signatures of these modules currently contain lines like this:
>
> type variable (* = int *)
>
> If I uncomment all instances of (* = int *) and reveal the
> representation to the compiler then I get a ... 36% performance
> improvement in the SAT solver.
>
> I have two questions:
>
> 1/ Is there some way I can reveal this representation to the parts of
> the system that clearly need it for effective optimization, without
> opening this up for general use.
>
> 2/ Failing that, has someone got a pleasant method of doing conditional
> compilation so that I can switch these comments on and off with ease?

I take the second part of your question since the obvious answer is camlp4:

There is an extension called pa_macro that provides conditional compilation.

Alas this extension doesn't work with signatures so the following
example is not (yet) supported:

(* foo.mli *)
IFDEF ABSTRACT THEN
type t
ELSE
type t = int
ENDIF

To address that shortcoming you can write an extension syntax dealing
with some semi-opaque types. Such an extension can allow us to write
that:

(* foo.mli *)
type t = semi opaque int

And have compilation option to set:

# For an abstract version
$ ocamlc -c -pp "camlp4o ./pa_opaque.cmo -abstract" foo.mli

# For a concrete version
$ ocamlc -c -pp "camlp4o ./pa_opaque.cmo -concrete" foo.mli

With this extension:

-----------8<-------------------------------------------------------------------------
(* pa_opaque.ml *)
open Pcaml;;
let abstract = ref true;;
EXTEND
ctyp: [[ LIDENT "semi"; LIDENT "opaque"; t = SELF ->
  if !abstract then <:ctyp< 'abstract >> else t
]];
END;;

Pcaml.add_option "-abstract" (Arg.Set abstract)
  "Use abstract types for semi opaque ones";;
Pcaml.add_option "-concrete" (Arg.Clear abstract)
  "Use concrete types for semi opaque ones";;
-----------8<-------------------------------------------------------------------------


Compiled that way:

$ ocamlc -c -I +camlp4 -pp "camlp4o pa_extend.cmo q_MLast.cmo" pa_opaque.ml

Best regards,

>
> I'm using version 3.09.2 of ocamlopt.
>
> Thanks in advance
>
> Jim
>
>
> --
> Jim Grundy, Research Scientist. Intel Corporation, Strategic CAD Labs
> Mail Stop RA2-451, 2501 NW 229th Ave, Hillsboro, OR 97124-5503, USA
> Phone: +1 971 214-1709   Fax: +1 971 214-1771
> http://www.intel.com/technology/techresearch/people/bios/grundy_j.htm
> Key Fingerprint: 5F8B 8EEC 9355 839C D777  4D42 404A 492A AEF6 15E2
>

-- 
Nicolas Pouillard

Re: [Caml-list] A Question About Types and Inlining

[Christian Stork]

On Fri, Dec 08, 2006 at 03:13:40PM -0800, Jim Grundy wrote:
...
> 1/ Is there some way I can reveal this representation to the parts of 
> the system that clearly need it for effective optimization, without 
> opening this up for general use.

http://martin.jambon.free.fr/opaque/Opaque.html seem to be what you're
looking for in the particular case of ints.

-- 
Chris Stork   <>  Support eff.org!  <>   http://www.ics.uci.edu/~cstork/
OpenPGP fingerprint:  B08B 602C C806 C492 D069  021E 41F3 8C8D 50F9 CA2F