From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail4-relais-sop.national.inria.fr (mail4-relais-sop.national.inria.fr [192.134.164.105]) by sympa.inria.fr (Postfix) with ESMTPS id F31537EC41 for ; Wed, 17 Oct 2012 00:18:12 +0200 (CEST) Received-SPF: None (mail4-smtp-sop.national.inria.fr: no sender authenticity information available from domain of gabriel.scherer@gmail.com) identity=pra; client-ip=209.85.223.182; receiver=mail4-smtp-sop.national.inria.fr; envelope-from="gabriel.scherer@gmail.com"; x-sender="gabriel.scherer@gmail.com"; x-conformance=sidf_compatible Received-SPF: Pass (mail4-smtp-sop.national.inria.fr: domain of gabriel.scherer@gmail.com designates 209.85.223.182 as permitted sender) identity=mailfrom; client-ip=209.85.223.182; receiver=mail4-smtp-sop.national.inria.fr; envelope-from="gabriel.scherer@gmail.com"; x-sender="gabriel.scherer@gmail.com"; x-conformance=sidf_compatible; x-record-type="v=spf1" Received-SPF: None (mail4-smtp-sop.national.inria.fr: no sender authenticity information available from domain of postmaster@mail-ie0-f182.google.com) identity=helo; client-ip=209.85.223.182; receiver=mail4-smtp-sop.national.inria.fr; envelope-from="gabriel.scherer@gmail.com"; x-sender="postmaster@mail-ie0-f182.google.com"; x-conformance=sidf_compatible X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: Au4BAAjcfVDRVd+2m2dsb2JhbABFrhmRdggjAQEBAQEICQsJFCeCIAEBAQQSAhMZARsSCwEDDAYFCw0NISIBEQEFAQoSBhMIChCHTwEDDwucSAkDjCiCdoEGhAQKGScDClmIdQEFDItDhkADlWuBFY08FimEAg8 X-IronPort-AV: E=Sophos;i="4.80,595,1344204000"; d="scan'208";a="159272672" Received: from mail-ie0-f182.google.com ([209.85.223.182]) by mail4-smtp-sop.national.inria.fr with ESMTP/TLS/RC4-SHA; 17 Oct 2012 00:18:12 +0200 Received: by mail-ie0-f182.google.com with SMTP id k10so18152204iea.27 for ; Tue, 16 Oct 2012 15:18:11 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:in-reply-to:references:from:date:message-id:subject:to :cc:content-type; bh=2CrIyybNLP+tz4oqosKOcD+VfdmmBN7IPvC6yLdomtU=; b=PTBCSc4z/XC0FSLfIVl5OyWvFTPKbyBb4hqkUe3u2WLAjq/4cXTyNgqyRY/F8szL9V 9bFB/0/+R0lB8tA5yMOjtvgAaortR4PpAmwywWuJx4u6vxsdHKE4TgWl9OAwNPbOE24W KLSR2ZYEVz+1UUnMpIprU4pA9ijXCh+N8MYxnIGUav3NdJWH8ou5Qc02ANMaQCBbrwfT 1D1jrwEqZcLBP39FbZasloy4nAXCi1xCB5tvC4qwykEdM+l4BRv+UuAm8hbSJpo2ydDg SufLJhZNevyEv7zMleWSc36ecXIkVALaL6O8a/L6PNxLxd2d4E3cTGduLx0qbL65GaHH T3Fw== Received: by 10.50.194.169 with SMTP id hx9mr4748714igc.70.1350425889476; Tue, 16 Oct 2012 15:18:09 -0700 (PDT) MIME-Version: 1.0 Received: by 10.50.65.9 with HTTP; Tue, 16 Oct 2012 15:17:29 -0700 (PDT) In-Reply-To: <507DD785.8030300@libertysurf.fr> References: <507DD785.8030300@libertysurf.fr> From: Gabriel Scherer Date: Wed, 17 Oct 2012 00:17:29 +0200 Message-ID: To: William Cc: caml-list@inria.fr Content-Type: text/plain; charset=ISO-8859-1 Subject: Re: [Caml-list] caml match optimization 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 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