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.
