The problem that took him 5 years to fix in C++, I solved in a minute with D

[Timon Gehr]

On 10.03.22 12:52, Paul Backus wrote:
> 
> Reminds me of this CppCon talk by Andrei Alexandrescu that was posted in 
> the community Discord recently:
> 
> https://youtu.be/va9I2qivBOA

Nice talk, but the explanation why there is a quadratic number of 
template instantiations for `destroyLog` seems to be wrong.

`destroyLog` itself is actually only instantiated a linear number of 
times. In particular, it is not true that it is instantiated with every 
combination of `lo` and `hi` where `0≤lo<hi≤n`. Most of them are never 
reached.

E.g., n=8, recursion tree of (lo,hi)-arguments:

```
                      (0,8)
                /               \
          (0,4)                   (4,8)
         /     \                 /     \
    (0,2)       (2,4)       (4,6)       (6,8)
    /   \       /   \       /   \       /   \
(0,1) (1,2) (2,3) (3,4) (4,5) (5,6) (6,7) (7,8)
```

Of course, the number of instantiated templates is indeed quadratic 
because each static index operation instantiates a linear number of 
templates and there are n index operations.

There is also something weird going on with the computation of the 
middle point:

```c++
constexpr size_t m = lo + (hi + low)/2;
```

This should be

```c++
constexpr unsigned m = lo + (hi - lo)/2;
```

(Or just (lo + hi)/2, I highly doubt this is ever going to wrap around 
:o). )

The following glorious hack avoids the linear indexing by consuming each 
element in the type sequence exactly once, when it is needed. The 
template parameter Ts is a type_sequence and the automatically deducted 
function return type is Ts[hi - lo .. $].

This only causes a linear number of template instantiations.

```c++
template<unsigned lo,unsigned hi,typename Ts>
auto destroyLog(unsigned i,void *p){
     static_assert(lo < hi);
     assert(lo <= i && i < hi);
     if constexpr (lo + 1 != hi) {
         constexpr unsigned m = lo + (hi - lo)/2;
         using Rs = decltype(destroyLog<lo, m, Ts>(i, p));
         if (i < m){
             destroyLog<lo, m, Ts>(i, p);
             return decltype(destroyLog<m, hi, Rs>(i, p))();
         } else {
             return destroyLog<m, hi, Rs>(i, p);
         }
     } else{
         using T = typename head<Ts>::type;
         static_cast<T*>(p)->~T();
         return typename tail<Ts>::type();
     }
}
```