Re: [Caml-list] caml match optimization

[Gabriel Scherer <gabriel.scherer@gmail.com>]

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