Re: [boost] Efficient tuple implementation

Subject: Re: [boost] Efficient tuple implementation
From: Agustín K-ballo Bergé (kaballo86_at_[hidden])
Date: 2014-06-06 22:56:49

On 06/06/2014 11:18 p.m., Louis Dionne wrote:
> Hi,
>
> I recently discovered (or maybe not) a neat trick to implement a tuple-like
> container. The technique has a couple of drawbacks which I will explain later.
> For a real example, you can see my list implementation in Boost.Hana at [1].
> Here's the idea:
>
>      auto list = [](auto ...xs) {
>          return [=](auto access) { return access(xs...); };
>      };
>
>      auto head = [](auto xs) {
>          return xs([](auto first, auto ...rest) { return first; });
>      };
>
>      auto tail = [](auto xs) {
>          return xs([](auto first, auto ...rest) { return list(rest...); });
>      };
>
>      auto length = [](auto xs) {
>          return xs([](auto ...z) { return sizeof...(z); });
>      };
>
>      // etc...
>      // then use it like
>
>      auto three = length(list(1, '2', "3"));
>
>
> The idea is to use the capture of the lambda as a fast compiler-generated
> struct with the desired members. By passing a function to that lambda, we
> get an access to the unpacked representation of those members and we can
> then apply any fast algorithm on parameter packs.
>

We have experimented with lambdas in Spirit.X3 as a way to drastically 
reduce compile times (although not in the form of tuples), and I would 
like to add some information on the why. The unique feature of lambdas 
is that name mangling is independent of the captures (at least in 
Itanium and Microsoft ABIs), so their symbol length remains the same 
(for all intent and purposes) regardless of the number of member 
captures and the length of their types. This is not true of templates, 
and it is what dominates the compilation time and memory usage nowadays. 
Lambdas have opaque mangled names, effectively acting as a mangler firewall.

Regards,
-- 
Agustín K-ballo Bergé.-
http://talesofcpp.fusionfenix.com