[Caml-list] Functor Performace Question

[Jim Grundy]

I have a functor related performance issue.

I have the following collection of modules and types that we are using
in the implementation of a SAT solver:

module type Map = sig .. end

module Nat_map: Map with type key = int

module type PriorityQueue = sig .. end

module Make_priority_queue:
functor (M : Map) -> PriorityQueue with type elt = M.key

module Nat_priority_queue: PriorityQueue with type elt = int

If we implement Nat_priority_queue in the "right" way as

module Nat_priority_queue = Make_priority_queue (Nat_map)

Then I pay about a 3% performance penalty over instantiating the functor
by hand...

module Nat_priority_queue = struct
module M = Nat_map
(* same code as the body of Make_priority_queue *)
end

Is there some compiler switch or future version in the works that will
save me from this?

Thanks

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

_______________________________________________
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

[Till Varoquaux]

Functors are computed at run time... defunctorisation has been studied
for Ocaml before [1], however the current implementation of reccursive
modules relies on these modules not being defunctorised (The process
is being made in a lazy like way at runtime since fix point cannot
always be reached during compilation).

Like monorphisation defunctorisation is a whole program optimization
technique that relies on the existence of a finite number of cases.
However ocaml is not about whole program optimizations nor are we
dealing with finite universes (in the general case, although more than
90% of the ocaml programs don't uses these corner cases). I doubt we
will see these in a caml compiler any time soon.

Till

P.S.: You should take my answer with a grain of salt: I'm not
affiliated in anyways with ocaml development team.

[1]http://www.lri.fr/~signoles/publis/signoles06defun.ps.gz

[Xavier Leroy]

> I have a functor related performance issue.
> I have the following collection of modules and types that we are using
> in the implementation of a SAT solver:

> If we implement Nat_priority_queue in the "right" way as
> module Nat_priority_queue = Make_priority_queue (Nat_map)
> Then I pay about a 3% performance penalty over instantiating the functor
> by hand...

> Is there some compiler switch or future version in the works that will
> save me from this?

Basically, no. There is indeed a small performance penalty associated
with functors, owing to the fact that the functor body is compiled
only once without knowledge of its arguments. Late specialization of
functors would be nice in the absolute, but would require a major
rework of the OCaml compiler. This said, a 3% speed penalty is not
too bad --- to me, it's lost in the noise of performance measurement.

Regards,

- Xavier Leroy