1

I can't seem to make a performant D-ary Heap class in C#; a hard-coded number of children (BinaryHeap, TernaryHeap, etc.) seems to have significantly better performance.

The only difference in the code between my BinaryHeap and my D-ary Heap with d=2, is that d is a const in the prior, and a readonly member variable in the latter (and readonly has no affect on performance).

I'm guessing the const version might compile down to a bit-shifting operation whereas the member variable version might compile down to memory-fetch + devision.

Is there a way I could declare my class sorta like this:

 public class DaryHeap<T, const uint(d)> : IEnumerable<T> where T : IComparable<T>

Wherein const uint(d) would tell the compiler "d is a compile-time uint value". And thus, would let my D-ary Heap with d=2 perform identically to my BinaryHeap.

Community
  • 1
  • 1
Mr. Smith
  • 4,288
  • 7
  • 40
  • 82
  • This is not possible. Maybe you have noticed [the `Action` and `Func` types](http://msdn.microsoft.com/en-us/library/system.aspx#delegateToggle) where a large number of somewhat identical types have been created because the number of generic parameters of a single type must be fixed. – Jeppe Stig Nielsen Sep 20 '13 at 10:19

2 Answers2

1

When I experimented with D-ary heaps (1, 2) I found something similar (not mentioned in those threads), and then gave up. There aren't really many values of D that are relevant. 4 and 8 is about all. 16, very rarely. 2, not really: 4-ary was always faster in my tests (even in the cases where it "shouldn't be"). I also tested non-powers of 2, which are also not mentioned, because they sucked.

So I settled for making a couple of hard-coded versions. That violates some coding principles, but since performance was my primary reason for using D-ary heaps in the first place, the performance penalty of not making D a constant was just simply unacceptable.

There are, basically, only 2 values of D that matter, so the amount of copy/pasted code is not actually that high.

harold
  • 61,398
  • 6
  • 86
  • 164
1

CLR generics are way more limited than C++ templates.

There are other kinds of templates out there though. Take T4 for example. You can write your D-ary heap as a T4 template and then produce the concrete versions from it. I assume you use Visual Studio, which gives you automatic integration with T4. This keeps things DRY (because you only modify the template itself) and also fast (because you have optimal implementations). And the best part is that you get to use a real language to produce your code, instead of a meta-language like you do with C++ templates.

Stefan Dragnev
  • 14,143
  • 6
  • 48
  • 52