Re: [Caml-list] default fold for visitors

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

[-- Attachment #1: Type: text/plain, Size: 3827 bytes --]

This is only a minor comment not addressing the main question, but I was
surprised by Christoph's assumption that folding on a tree (repeatedly
calling Set.add) would be more efficient than a divide-and-conquer merge
approach (repeatedly calling Set.union), at least with a
balanced-search-tree implementation of sets. I would rather have assumed
that a divide-and-conquer merge may be faster, on the vague hunch that
merging whole trees instead of single leaves (adding a key is like merging
a leave) allows to reuse information between comparing the root of a tree
and merging its substrees.

I wrote a quick benchmark (
https://gitlab.com/gasche-snippets/tree-fold-merge-benchmark ) that
collects leaves of a binary tree into a set, and it turns out that which is
faster depends on the key ordering. If the keys are completely random, then
the fold-based code is twice faster. If the keys are mostly sorted, then
the merge-based code is twice faster. The fold-based code performance seems
independent of the key distribution, it is the merge-based code that goes
from twice slower to twice faster depending on the scenario.

My proposed explanation would be that merging two trees where all the keys
in a tree are larger than almost all the keys in the other is fast (this is
the case where little rebalancing is needed), so this hits a good case
where tree-form indeed reuses comparison information. On the contrary,
random trees are not faster than just calling add on all leaves.

(I would guess that in complexity tree union is always as good as
repeated-add or better, for all key distributions, but that the constant
factors of the current implementation are higher because we manipulate more
slightly complex data structures.)



On Thu, Aug 17, 2017 at 1:57 PM, Christoph Höger <
christoph.hoeger@celeraone.com> wrote:

> Dear all (especially Francois),
>
> I am currently porting a DSL to OCaml and wanted to use the most modern
> ppx approach for the typical boilerplate. One of the first things is the
> implementation of the free variables with the help of ppx_visitors.
> Naturally, the set of free variables forms a monoid, so I can comfortably
> use the reduce variety. But that allocates quite a lot of temporary sets,
> so I had a look into the fold variety.
>
> If I understand the documentation correctly, this class requires to define
> a build method for each variant of the datatype. I wonder if there is a way
> to have a "default" function, namely the identity of the result value?
>
> Consider, for example the simple lambda calculus:
>
>
> type expr = Abs of (string[@opaque]) * expr | App of expr * expr | Var of
> (string[@opaque]) [@@deriving visitors { variety = "fold" }]
>
> In that case, you'd want to define
>
> method build_Abs () x = StrSet.remove x
> method build_Var () = StrSet.singleton
>
> but also have to
>
> method build_App () = StrSet.union
>
> According to the manual, the visitor should be something like this:
>
> method visit_App () l r fvs0 =
>   let fvs1 = self#visit_expr () l fvs0 in
>   let fvs2 = self#visit_expr () l fvs1 in
>   self#build_App () fvs1 fvs2                (* Why is this /always/
> necessary ? *)
>
> I suppose this final step of building the results allows some flexibility,
> but in my case I could as well just yield fvs2. I wonder if it would be
> possible to have a default implementation like this:
>
> method build_App () _ r = r
>
> For now, I am perfectly fine with the reduce variety, but I suppose that
> there are some use cases where you would actually need to fold, but only
> some variants actually do something. Is this a reasonable idea or is there
> some caveat in the design of ppx_visitors that makes it impossible?
>
> thanks,
>
> Christoph
>

[-- Attachment #2: Type: text/html, Size: 4266 bytes --]