Passing arguments a template parameters vs. function parameters

[John Colvin]

On Tuesday, 11 June 2013 at 20:46:32 UTC, Craig Dillabaugh wrote:
> I was looking at D code for constructing kd-trees, the full code
> listing for which can be found here:
>
> http://rosettacode.org/wiki/K-d_tree#Faster_Alternative_Version
>
> Of particular interest were the following functions:
>
> KdNode* makeTree(size_t dim, size_t i)(KdNode[] nodes) pure
> nothrow {
>      if (!nodes.length)
>          return null;
>
>      auto n = findMedian!i(nodes);
>      if (n != null) {
>          enum i2 = (i + 1) % dim;
>          immutable size_t nPos = n - nodes.ptr;
>          n.left  = makeTree!(dim, i2)(nodes[0 .. nPos]);
>          n.right = makeTree!(dim, i2)(nodes[nPos + 1 .. $]);
>      }
>
>      return n;
> }
>
> // See QuickSelect method.
> KdNode* findMedian(size_t idx)(KdNode[] nodes) pure nothrow {
>      auto start = nodes.ptr;
>      auto end = &nodes[$ - 1] + 1;
>
>      if (end <= start)
>          return null;
>      if (end == start + 1)
>          return start;
>
>      KdNode* md = start + (end - start) / 2;
>
>      //clipped for sake of brevity.
> }
>
> A kd-tree is a search structure for storing multi-dimensional
> points.  At each level it splits the input point set along a
> plane in one of the dimensions. In the code above this is the
> value pased as 'idx' to findMedian.  findMedian finds the median
> point in the current dimension, and uses this to define the
> splitting plane for the points. At each level in the tree the
> splitting dimension is changed (which is what i/i2 is used for 
> in
> makeTree()).
>
> If I had been coding this I would almost certainly have passed
> the splitting dimensions as a function parameter, since the
> compiler has to generate separate makeTree/findMedian functions
> for each dimension that i/idx takes in the program.
>
> So my question is, does anyone have any idea why the author may
> have used templates here. It was on Rosettacode so maybe they 
> are
> just there to show off D's nice template abilities, but I am
> curious if in idiomatic D using templates this way is somehow
> superior to the function parameter method I would have tried.
>
> Cheers,
> Craig

It's just a trade-off between template bloat and having more 
values hard-coded in for efficiency.

In this particular case, due to the use of the static array in 
KdNode, if idx is known at compile time then the optimizer can go 
to town on those loops in findMedian. e.g. in

foreach (p; start .. end) {
     if (p.x[idx] < pivot) {
         if (p != store)
             swap(p.x, store.x);
         store++;
     }
}

given offset = p.x.offsetof + idx
p.x[idx] becomes just *(p+offset) which is fast and completely 
predictable behaviour. Great for optimizers and cache prefetching 
etc...


All that is meaningless guesswork though, the only thing that 
will tell you for sure is benchmarking and profiling.