From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Original-To: caml-list@sympa.inria.fr Delivered-To: caml-list@sympa.inria.fr Received: from mail2-relais-roc.national.inria.fr (mail2-relais-roc.national.inria.fr [192.134.164.83]) by sympa.inria.fr (Postfix) with ESMTPS id 4A1937F89E for ; Thu, 3 Apr 2014 16:28:28 +0200 (CEST) Received-SPF: None (mail2-smtp-roc.national.inria.fr: no sender authenticity information available from domain of lpw25@cam.ac.uk) identity=pra; client-ip=131.111.8.151; receiver=mail2-smtp-roc.national.inria.fr; envelope-from="lpw25@cam.ac.uk"; x-sender="lpw25@cam.ac.uk"; x-conformance=sidf_compatible Received-SPF: None (mail2-smtp-roc.national.inria.fr: no sender authenticity information available from domain of lpw25@cam.ac.uk) identity=mailfrom; client-ip=131.111.8.151; receiver=mail2-smtp-roc.national.inria.fr; envelope-from="lpw25@cam.ac.uk"; x-sender="lpw25@cam.ac.uk"; x-conformance=sidf_compatible Received-SPF: None (mail2-smtp-roc.national.inria.fr: no sender authenticity information available from domain of postmaster@ppsw-51.csi.cam.ac.uk) identity=helo; client-ip=131.111.8.151; receiver=mail2-smtp-roc.national.inria.fr; envelope-from="lpw25@cam.ac.uk"; x-sender="postmaster@ppsw-51.csi.cam.ac.uk"; x-conformance=sidf_compatible X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: Ah0EAD1vPVODbwiXgWdsb2JhbABYg0GtVpZ3gR8WDgEBFiYogiUBAQEDAScTNAsFCwsHEQkEIQ8BBA0kGBMSh1MDCQgNx04DCleGXxeJRoMRghoHhDgElm6DIYs7iQA X-IPAS-Result: Ah0EAD1vPVODbwiXgWdsb2JhbABYg0GtVpZ3gR8WDgEBFiYogiUBAQEDAScTNAsFCwsHEQkEIQ8BBA0kGBMSh1MDCQgNx04DCleGXxeJRoMRghoHhDgElm6DIYs7iQA X-IronPort-AV: E=Sophos;i="4.97,787,1389740400"; d="scan'208";a="66249519" Received: from ppsw-51.csi.cam.ac.uk ([131.111.8.151]) by mail2-smtp-roc.national.inria.fr with ESMTP/TLS/DHE-RSA-AES256-SHA; 03 Apr 2014 16:28:27 +0200 X-Cam-AntiVirus: no malware found X-Cam-ScannerInfo: http://www.cam.ac.uk/cs/email/scanner/ Received: from kingston.cl.cam.ac.uk ([128.232.64.15]:44415) by ppsw-51.csi.cam.ac.uk (smtp.hermes.cam.ac.uk [131.111.8.159]:587) with esmtpsa (PLAIN:lpw25) (TLSv1.2:DHE-RSA-AES128-SHA:128) id 1WVid0-0003r0-YW (Exim 4.82_3-c0e5623) (return-path ); Thu, 03 Apr 2014 15:28:26 +0100 From: Leo White To: Thomas Braibant Cc: John Whitington , "caml-list\@inria.fr" References: <5332F937.1030303@coherentgraphics.co.uk> <86eh1oacmq.fsf@cam.ac.uk> X-Face: "XWxb[u_Z\PA_Y?9@|IA!!+jTb(/290-*ea/Un$I0B98.$n%eL.;2w*,z]WR#T:,p[ NBd++M7l]#7zj7!{~iw $W-"/=|dVjhT[D{4~gE}gK<2`.6fs!;uqqud]vs2N/3^m7{aS1V, Date: Thu, 03 Apr 2014 15:28:26 +0100 In-Reply-To: (Thomas Braibant's message of "Fri, 28 Mar 2014 08:22:42 +0000") Message-ID: User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/23.4 (gnu/linux) MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Subject: Re: [Caml-list] Wrapping up the Set module in another I'm afraid I don't have any real idea of the runtime cost. The main additional cost would come from calling `Set.Make` in `set_of_list` and creating new modules in `set_of_list` and `insert`. `Set.Make` has to create a lot of closures which capture the `compare` function. I think these closures are all allocated at once, but this still means a lot of assignments. Creating the new modules is a record allocation and assignment of all the record fields. The cost of creating modules could probably be reduced a bit by rewriting it as: module type SetS = sig module Ops : Set.S val s : Ops.t end;; type 'a t = (module SetS with type Ops.elt = 'a) let list_of_set (type elt) ((module S) : elt t) = S.Ops.elements S.s let set_of_list (type elt) (l : elt list) : elt t = (module struct module Ops = Set.Make (struct type t = elt let compare = compare end) let s = List.fold_right Ops.add l Ops.empty end) let member (type elt) (x : elt) ((module S) : elt t) = S.Ops.mem x S.s let insert (type elt) (x : elt) ((module S) : elt t) : elt t = (module struct module Ops = S.Ops let s = add x S.s end) let size (type elt) ((module S) : elt t) = S.Ops.cardinal S.s There would also be a cost in the other functions for the indirection to get to the actual set and the functions. Theoretically it might also be slower than using the result of `Set.Make` directly since that would be easier for the compiler to optimise by calling the functions directly or inlining them, although I'm not sure if the current compiler actually does this. Regards, Leo Thomas Braibant writes: > Hi, > > I really like this trick of wrapping the module and an actual set > together. Do you have any idea of the runtime cost? I remember reading > that functor applications are runtime operations, but I wonder what is > the overhead. > > Best > Thomas > > On Wed, Mar 26, 2014 at 9:11 PM, Leo White wrote: >> It is not at all ideal, and there is almost certainly a better way, but >> you could wrap the set module up with the actual set. I also don't know >> how much the overhead might affect your benchmarks. >> >> # module SetSet : SetType = struct >> module type SetS = sig include Set.S val s : t end;; >> >> type 'a t = (module SetS with type elt = 'a) >> >> let list_of_set (type elt) ((module S) : elt t) = S.elements S.s >> >> let set_of_list (type elt) (l : elt list) : elt t = >> (module struct >> include Set.Make (struct type t = elt let compare = compare end) >> let s = List.fold_right add l empty >> end) >> >> let member (type elt) (x : elt) ((module S) : elt t) = S.mem x S.s >> >> let insert (type elt) (x : elt) ((module S) : elt t) : elt t = >> (module struct >> include S >> let s = add x S.s >> end) >> >> let size (type elt) ((module S) : elt t) = S.cardinal S.s >> >> end;; >> module SetSet : SetType >> >> # let implementations = >> [("Lists", (module SetList : SetType)); >> ("Sets", (module SetSet : SetType))];; >> val implementations : (string * (module SetType)) list = >> [("Lists", ); ("Sets", )] >> >> Regards, >> >> Leo >> >> John Whitington writes: >> >>> Hi, >>> >>> Suppose I want to benchmark various toy set implementations, so I have already written: >>> >>> module type SetType = >>> sig >>> type 'a t >>> val set_of_list : 'a list -> 'a t >>> val list_of_set : 'a t -> 'a list >>> val insert : 'a -> 'a t -> 'a t >>> val size : 'a t -> int >>> val member : 'a -> 'a t -> bool >>> end >>> >>> and then, for example: >>> >>> module SetList : sig include SetType end = >>> struct >>> type 'a t = 'a list >>> >>> let list_of_set x = x >>> >>> let rec set_of_list l = >>> match l with >>> [] -> [] >>> | h::t -> >>> if List.mem h t then set_of_list t else h :: set_of_list t >>> >>> let insert x l = x :: l >>> >>> let size = List.length >>> >>> let member = List.mem >>> end >>> >>> This works fine -- I can put them into a little list, and run tests: >>> >>> let implementations = >>> [("Lists", (module SetList : SetType)); >>> ("Trees", (module SetTree : SetType)); >>> ("Red-black trees", (module SetRedBlack : SetType)); >>> ("Hash tables", (module SetHashtbl : SetType))] >>> >>> Now, it would be nice to include OCaml's Set module, but can it be made to fit the signature? So far I have: >>> >>> let make_setset (type s) () = >>> let module SetSet : sig include SetType end = >>> struct >>> module S = Set.Make (struct type t = s let compare = compare end) >>> >>> type 'a t = S.t >>> >>> let list_of_set s = S.elements s >>> >>> let set_of_list l = List.fold_right S.add l S.empty >>> >>> let member = S.mem >>> >>> let insert = S.add >>> >>> let size = S.cardinal >>> end >>> in >>> (module SetSet : SetType) >>> >>> and >>> >>> let implementations = >>> let module SetSet = (val (make_setset ())) in >>> [("Lists", (module SetList : SetType)); >>> ("Trees", (module SetTree : SetType)); >>> ("Red-black trees", (module SetRedBlack : SetType)); >>> ("Hash tables", (module SetHashtbl : SetType)); >>> ("OCaml sets", (module SetSet : SetType))] >>> >>> The problem here, it seems to me, is that the connection between 'a in make_setset and (type s) and S.elt is not >>> established, and so the return types of list_of_set etc. don't type-check. >>> >>> Is there any way to do this, or is the functorised implementation of Set fundamentally opposed to the normal >>> polymorphism of the type 'a t in SetType? >>> >>> Thanks, >>> >>> -- >>> John Whitington >>> Director, Coherent Graphics Ltd >>> http://www.coherentpdf.com/ >> >> -- >> 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