From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail3-relais-sop.national.inria.fr (mail3-relais-sop.national.inria.fr [192.134.164.104]) by sympa.inria.fr (Postfix) with ESMTPS id 97DC37ED11 for ; Thu, 22 Sep 2016 02:39:16 +0200 (CEST) Authentication-Results: mail3-smtp-sop.national.inria.fr; spf=None smtp.pra=markus.mottl@gmail.com; spf=Pass smtp.mailfrom=markus.mottl@gmail.com; spf=None smtp.helo=postmaster@mail-io0-f178.google.com Received-SPF: None (mail3-smtp-sop.national.inria.fr: no sender authenticity information available from domain of markus.mottl@gmail.com) identity=pra; client-ip=209.85.223.178; receiver=mail3-smtp-sop.national.inria.fr; envelope-from="markus.mottl@gmail.com"; x-sender="markus.mottl@gmail.com"; x-conformance=sidf_compatible Received-SPF: Pass (mail3-smtp-sop.national.inria.fr: domain of markus.mottl@gmail.com designates 209.85.223.178 as permitted sender) identity=mailfrom; client-ip=209.85.223.178; receiver=mail3-smtp-sop.national.inria.fr; envelope-from="markus.mottl@gmail.com"; x-sender="markus.mottl@gmail.com"; x-conformance=sidf_compatible; x-record-type="v=spf1" Received-SPF: None (mail3-smtp-sop.national.inria.fr: no sender authenticity information available from domain of postmaster@mail-io0-f178.google.com) identity=helo; client-ip=209.85.223.178; receiver=mail3-smtp-sop.national.inria.fr; envelope-from="markus.mottl@gmail.com"; x-sender="postmaster@mail-io0-f178.google.com"; x-conformance=sidf_compatible IronPort-PHdr: =?us-ascii?q?9a23=3AMS8hBh0AXlK3lKuWsmDT+DRfVm0co7zxezQtwd8Z?= =?us-ascii?q?segfI/ad9pjvdHbS+e9qxAeQG96KsbQc0KGN4ujJYi8p2d65qncMcZhBBVcuqP?= =?us-ascii?q?49uEgeOvODElDxN/XwbiY3T4xoXV5h+GynYwAOQJ6tL2PbrnD61zMOABK3bVMz?= =?us-ascii?q?fbWvXNaJxJ/mn8mJuLTrKz1SgzS8Zb4gZD6Xli728vcsvI15N6wqwQHIqHYbM8?= =?us-ascii?q?5fxGdvOE7B102kvpT41NdZ/i9Ro/Ms8dJbGeW/JvxgDO9uNyk9K20++OHssBDC?= =?us-ascii?q?S0PPuipdAS0qlU9nCgLf7Rz+Fqz6sibgu/A1jCaTN9f3QLRyQj+i4r1mUjfnjS?= =?us-ascii?q?4GM3gy92SB2eJqi6cOhRu7pAFki6vTfJ2RfK57d7neYMhcQG1dQsJ5WClIA4f6?= =?us-ascii?q?ZIwKWblSdd1EppXw8gNd5SC1AhOhUaaykzI=3D?= X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: =?us-ascii?q?A0ABAQCHJ+NXhrLfVdFeGwEBAQMBAQEJA?= =?us-ascii?q?QEBFwEBBAEBCgEBgxABAQEBATw5bQ8Hpn+JcYgBggQkhXoCgV8HORMBAQEBAQE?= =?us-ascii?q?BAQEBARIBAQEICwsJGS+CMgQBFQWCEQEBBBIRBBkBFAcSCwEDDAYFCw0CAgkdA?= =?us-ascii?q?gIhAQERAQUBChIGExIJB4gOAQMXDqEpgTI+Mos9gWuCXwWDfwoZJwMKVIJeAQE?= =?us-ascii?q?BAQEBBAEBAQEBARkCBhB2hTGDT4EFgkeFAYJaBYZqDIFAkQo1gWWEQoZHgnSCP?= =?us-ascii?q?I0wiFiED4I6Ex6BESADgzwfgXciNIUFgUABAQE?= X-IPAS-Result: =?us-ascii?q?A0ABAQCHJ+NXhrLfVdFeGwEBAQMBAQEJAQEBFwEBBAEBCgE?= =?us-ascii?q?BgxABAQEBATw5bQ8Hpn+JcYgBggQkhXoCgV8HORMBAQEBAQEBAQEBARIBAQEIC?= =?us-ascii?q?wsJGS+CMgQBFQWCEQEBBBIRBBkBFAcSCwEDDAYFCw0CAgkdAgIhAQERAQUBChI?= =?us-ascii?q?GExIJB4gOAQMXDqEpgTI+Mos9gWuCXwWDfwoZJwMKVIJeAQEBAQEBBAEBAQEBA?= =?us-ascii?q?RkCBhB2hTGDT4EFgkeFAYJaBYZqDIFAkQo1gWWEQoZHgnSCPI0wiFiED4I6Ex6?= =?us-ascii?q?BESADgzwfgXciNIUFgUABAQE?= X-IronPort-AV: E=Sophos;i="5.30,376,1470693600"; d="scan'208";a="194230181" Received: from mail-io0-f178.google.com ([209.85.223.178]) by mail3-smtp-sop.national.inria.fr with ESMTP/TLS/AES128-GCM-SHA256; 22 Sep 2016 02:39:15 +0200 Received: by mail-io0-f178.google.com with SMTP id r145so70440628ior.0 for ; Wed, 21 Sep 2016 17:39:15 -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; bh=SWSLqk1+l7YSCAYw7pqqMHnilC6PP0tmPmwNGr1g0EI=; b=NKcsXkVIm6gX9YvuDZ0rDuiDX2EW+Bw1n774OxpbHixNbtP7aOgkSv5TIYqS8z+x1f wVpd3JhJUM7jKh0uWmXe02IjqlknqZY5FOKLA2ugsmZI7wYusbeg58D8TQZqtWtKeve8 3oGMBYCpTnk8HmY5gnrjrVmmUOOKpSbg6H8gfzmgoKENYEz/ReV7SadeebmD8BckAtPU j2ANpsPIhAG1E2JkpcyOjgFAp49AZyJ6g8CEOovNFa0OjwAmULYqKKW5O0hS9T68mTdI idbJJ3yf5gseeuAQlbCWEb0b6hFHmXbkkcSAOO3Kkl6F1/vtXityzQQOnSbdEFTPABk3 cHoQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:mime-version:in-reply-to:references:from:date :message-id:subject:to:cc; bh=SWSLqk1+l7YSCAYw7pqqMHnilC6PP0tmPmwNGr1g0EI=; b=hD8DeH/xP2LQJA3EWrstEK6XyrU+EkJdmE51q+CGzXN5+WjLuP2rg8lxqACfeClL4P YJDa8iToacReKQN+MScKbIqoVDoumca5vcVJAcQa1Znk7BqZvkjfhU6Hrj71nooityjq 3Si8J2AKXzO1tLBlXjFXFsG1It78CYCY8UmZAoIn1xCYwC0CL62pTrEG+/vsfNEkKTe2 zLR6TxMQydzGe1PnkvXTU9O7+M4ngidYNPKyX7y9VF1aUZP62GzdyWyiFALCQ1iC30Q7 edw9sGb65t2YZGQUQmBK2+eA3cj9bZ/7UrKfdqyDwoyju64wOR5/nT9MJsyFOXrHGBpb GZXg== X-Gm-Message-State: AE9vXwMLhGyuYL1kERQslF6+sDwW44OmsC99CsGKOV70Z7sEWArAJwHNdZwA5wm+3zHtqr8bDxZPpvgau+haWw== X-Received: by 10.107.201.20 with SMTP id z20mr52505636iof.90.1474504753626; Wed, 21 Sep 2016 17:39:13 -0700 (PDT) MIME-Version: 1.0 Received: by 10.107.131.219 with HTTP; Wed, 21 Sep 2016 17:39:12 -0700 (PDT) In-Reply-To: References: <2161155.JggR3X9ZFM@molnar> <2324346.DfHVUap7Qc@molnar> From: Markus Mottl Date: Wed, 21 Sep 2016 20:39:12 -0400 Message-ID: To: Gabriel Scherer Cc: Lukasz Stafiniak , OCaml List Content-Type: text/plain; charset=UTF-8 Subject: Re: [Caml-list] Covariant GADTs The direct comparison with the Jane Street implementation showed a 40% speed increase for some random things I tried, but that's not a fair comparison. If I improve the JS code, e.g. to avoid allocations, the performance improvement due to the GADT + inlined records drops to only about 10%. In terms of memory, a freshly created set costs 7 machine words in the original code vs. 5 for the GADT. Adding one rank costs 4 machine words in the standard implementation vs. only 2 for GADTs. That's a pretty significant size reduction. The GADT representation would surely help in programs that allocate a lot of these values, but the values don't tend to grow much internally due to the tree compression algorithm. I'm sure there are better examples where a program would typically allocate GADT-based data structures of more significant size. Regards, Markus On Wed, Sep 21, 2016 at 5:40 PM, Gabriel Scherer wrote: > Very nice. Would you have more precise numbers for the "considerably more > efficient" part? It's not always easy to find clear benefits to inline > records on representative macro-benchmarks. > > On Thu, Sep 22, 2016 at 2:04 AM, Markus Mottl > wrote: >> >> Here is a complete working example of the advantages of using GADTs >> with inline records. It also uses the [@@unboxed] feature now >> available with OCaml 4.04 as discussed before here, though it required >> a little workaround due to an apparent bug in the current beta. >> >> The below implementation of the union-find algorithm is considerably >> more efficient (with the 4.04 beta only) than the Union_find >> implementation in the Jane Street Core kernel. The problem admittedly >> lends itself to the GADT + inline record trick. >> >> There is actually one advantage to using an intermediate, unboxed GADT >> tag compared to records with existentially quantified fields (if they >> were available): functions matching the tag don't require those >> horrible type annotations for locally abstract types, because the >> match automatically sets up the scope for you. Having to write "Node >> foo" instead of just "foo" in some places isn't too bad. Not sure >> it's possible to have the best of both worlds. >> >> ---------- >> module Union_find = struct >> (* This does not work yet due to an OCaml 4.04 beta bug >> type ('a, 'kind) tree = >> | Root : { mutable value : 'a; mutable rank : int } -> ('a, [ `root ]) >> tree >> | Inner : { mutable parent : 'a node } -> ('a, [ `inner ]) tree >> >> and 'a node = Node : ('a, _) tree -> 'a node [@@ocaml.unboxed] >> >> type 'a t = ('a, [ `inner ]) tree >> *) >> >> type ('a, 'kind, 'parent) tree = >> | Root : { mutable value : 'a; mutable rank : int } -> >> ('a, [ `root ], 'parent) tree >> | Inner : { mutable parent : 'parent } -> ('a, [ `inner ], 'parent) >> tree >> >> type 'a node = Node : ('a, _, 'a node) tree -> 'a node >> [@@ocaml.unboxed] >> >> type 'a t = ('a, [ `inner ], 'a node) tree >> >> let create v = Inner { parent = Node (Root { value = v; rank = 0 }) } >> >> let rec compress ~repr:(Inner inner as repr) = function >> | Node (Root _ as root) -> repr, root >> | Node (Inner next_inner as repr) -> >> let repr, _ as res = compress ~repr next_inner.parent in >> inner.parent <- Node repr; >> res >> >> let compress_inner (Inner inner as repr) = compress ~repr inner.parent >> >> let get_root (Inner inner) = >> match inner.parent with >> | Node (Root _ as root) -> root (* Avoids compression call *) >> | Node (Inner _ as repr) -> >> let repr, root = compress_inner repr in >> inner.parent <- Node repr; >> root >> >> let get t = let Root r = get_root t in r.value >> >> let set t x = let Root r = get_root t in r.value <- x >> >> let same_class t1 t2 = get_root t1 == get_root t2 >> >> let union t1 t2 = >> let Inner inner1 as repr1, (Root r1 as root1) = compress_inner t1 in >> let Inner inner2 as repr2, (Root r2 as root2) = compress_inner t2 in >> if root1 == root2 then () >> else >> let n1 = r1.rank in >> let n2 = r2.rank in >> if n1 < n2 then inner1.parent <- Node repr2 >> else begin >> inner2.parent <- Node repr1; >> if n1 = n2 then r1.rank <- r1.rank + 1 >> end >> end (* Union_find *) >> ---------- >> >> Regards, >> Markus >> >> On Wed, Sep 21, 2016 at 6:14 AM, Lukasz Stafiniak >> wrote: >> > On Wed, Sep 21, 2016 at 12:11 PM, Lukasz Stafiniak >> > wrote: >> >> >> >> A simple solution would be to "A-transform" (IIRC the term) accesses >> > >> > Sorry, I forgot to define this. I mean rewrite rules like: >> > [f r.x] ==> [let x = r.x in f x] >> > where subsequently the existential variable is introduced (unpacked) >> > at the let-binding level. This corresponds to a single-variant GADT >> > pattern match. >> > >> >> to fields with existential type variables. This would give a more >> >> narrow scope on the expression level than you suggest, but a >> >> well-defined one prior to type inference. To broaden the scope you >> >> would need to let-bind the field access yourself at the appropriate >> >> level. >> >> >> >> -- >> Markus Mottl http://www.ocaml.info markus.mottl@gmail.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 > > -- Markus Mottl http://www.ocaml.info markus.mottl@gmail.com