[Caml-list] caml match optimization

[Caml-list] caml match optimization

[William]

Hello,
I have this code sample :

let apply_foo         = apply_all_elements foo foo_struct
let apply_bar         = apply_all_elements bar bar_struct
let apply_baz         = apply_all_elements baz baz_struct
[...]
let apply_biz         = apply_all_elements biz biz_struct



If I make a function such as :

let apply2 = function
| `Foo -> apply_all_elements foo foo_struct
| `Bar -> apply_all_elements bar bar_struct
| `Baz -> apply_all_elements baz baz_struct
[...]
| `Biz -> apply_all_elements biz biz_struct


How much is "apply2" inefficient ?
does caml tests for 20 elements if `Biz is number 21 ?
Or does ocaml try to convert the list of elements in a tree internally ? 
(to optimise access) or something else ?

Regards,
William

Re: [Caml-list] caml match optimization

[Gabriel Kerneis]

On Tue, Oct 16, 2012 at 11:54:13PM +0200, William wrote:
> let apply2 = function
> | `Foo -> apply_all_elements foo foo_struct
> | `Bar -> apply_all_elements bar bar_struct
> | `Baz -> apply_all_elements baz baz_struct
> [...]
> | `Biz -> apply_all_elements biz biz_struct
> 
> 
> How much is "apply2" inefficient ?

Efficiency notwithstanding (and I wouldn't expect much of the OCaml compiler in
this area), I'd find the code cleaner with a Map m from `Foo to (foo,
foo_struct), `Bar to (bar, bar_struct), etc., then:
let apply2 x = let (f,s) = Map.find x m in apply_all_elements f s

Best,
-- 
Gabriel

Re: [Caml-list] caml match optimization

[Gabriel Scherer]

You can just test the current behavior of the compiler.

% cat test.ml
let apply2 apply_all_elements foo bar baz biz = function
| `Foo -> apply_all_elements foo foo
| `Bar -> apply_all_elements bar bar
| `Baz -> apply_all_elements baz baz
| `Biz -> apply_all_elements biz biz

% ocamlopt -dlambda -c test.ml
(seq
  (let
    (apply2/1030
       (function apply_all_elements/1031 foo/1032 bar/1033 baz/1034 biz/1035
         param/1037
         (if (>= param/1037 3305651)
           (if (>= param/1037 3505894)
             (apply apply_all_elements/1031 foo/1032 foo/1032)
             (apply apply_all_elements/1031 biz/1035 biz/1035))
           (if (>= param/1037 3303867)
             (apply apply_all_elements/1031 baz/1034 baz/1034)
             (apply apply_all_elements/1031 bar/1033 bar/1033)))))
    (setfield_imm 0 (global Test!) apply2/1030))
  0a)


Note that using regular variants instead of polymorphic variants gives
you a rather more efficient dispatch (because the variant tags are
represented as continguous small integers rather than integers
resulting from a hashing process):

% cat test2.ml
type tag = Foo | Bar | Baz | Biz

let apply2 apply_all_elements foo bar baz biz = function
| Foo -> apply_all_elements foo foo
| Bar -> apply_all_elements bar bar
| Baz -> apply_all_elements baz baz
| Biz -> apply_all_elements biz biz

% ocamlopt -dlambda -c test2.ml
(seq
  (let
    (apply2/1039
       (function apply_all_elements/1040 foo/1041 bar/1042 baz/1043 biz/1044
         param/1051
         (switch* param/1051
          case int 0: (apply apply_all_elements/1040 foo/1041 foo/1041)
          case int 1: (apply apply_all_elements/1040 bar/1042 bar/1042)
          case int 2: (apply apply_all_elements/1040 baz/1043 baz/1043)
          case int 3: (apply apply_all_elements/1040 biz/1044 biz/1044))))
    (setfield_imm 0 (global Test2!) apply2/1039))
  0a)


On Tue, Oct 16, 2012 at 11:54 PM, William <r.3@libertysurf.fr> wrote:
> Hello,
> I have this code sample :
>
> let apply_foo         = apply_all_elements foo foo_struct
> let apply_bar         = apply_all_elements bar bar_struct
> let apply_baz         = apply_all_elements baz baz_struct
> [...]
> let apply_biz         = apply_all_elements biz biz_struct
>
>
>
> If I make a function such as :
>
> let apply2 = function
> | `Foo -> apply_all_elements foo foo_struct
> | `Bar -> apply_all_elements bar bar_struct
> | `Baz -> apply_all_elements baz baz_struct
> [...]
> | `Biz -> apply_all_elements biz biz_struct
>
>
> How much is "apply2" inefficient ?
> does caml tests for 20 elements if `Biz is number 21 ?
> Or does ocaml try to convert the list of elements in a tree internally ? (to
> optimise access) or something else ?
>
> Regards,
> William
>
> --
> Caml-list mailing list.  Subscription management and archives:
> https://sympa.inria.fr/sympa/arc/caml-list
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs