source/blog/posts/2010/06/28-delegates-and-inlining.rst

   1 Title: Delegates and inlining
   2 Tags: en, d, delegate, inline, inlining, optimization, performance, dgc, gc
   3
   4 Sometimes performance issues matter more than you might think for a language. In
   5 this case I'm talking about the `D programming language`__.
   6
   7 __ http://www.digitalmars.com/d/
   8
   9 I'm trying to improve the GC__, and I want to improve it not only in terms of
  10 performance, but in terms of code quality too. But I'm hitting some performance
  11 issues that prevent me to make the code better.
  12
  13 __ http://en.wikipedia.org/wiki/Garbage_collector_%28computer_science%29
  14
  15 D support high level constructs, like delegates__ (aka closures__). For example,
  16 to do a simple linear search I wanted to use this code::
  17
  18    T* find_if(bool delegate(ref T) predicate)
  19    {
  20       for (size_t i = 0; i < this._size; i++)
  21          if (predicate(this._data[i]))
  22             return this._data + i;
  23       return null;
  24    }
  25    ...
  26    auto p = find_if((ref T t) { return t > 5; });
  27
  28 __ http://www.digitalmars.com/d/1.0/function.html#closures
  29 __ http://en.wikipedia.org/wiki/Closure_%28computer_science%29
  30
  31 But in DMD__, you don't get that ``predicate`` inlined (neither the
  32 ``find_if()`` call, for that matter), so you're basically screwed, suddenly you
  33 code is ~4x slower. Seriously, I'm not joking, using callgrind__ to profile the
  34 program (DMD's profiler doesn't work for me, I get a stack overflow for
  35 a recursive call when I try to use it), doing the ``call`` takes 4x more
  36 instructions, and in a real life example, using Dil__ to generate the Tango__
  37 documentation, I get a 3.3x performance penalty for using this high-level
  38 construct.
  39
  40 __ http://www.dsource.org/projects/dmd
  41 __ http://valgrind.org/docs/manual/cl-manual.html
  42 __ http://code.google.com/p/dil/
  43 __ http://www.dsource.org/projects/tango
  44
  45 I guess this is why D2__\ 's sort__ uses `string mixins`__ instead of delegates
  46 for this kind of things. The only lectures that I can find from this is
  47 delegates are failing in D, either because they have a bad syntax (compare
  48 ``sort(x, (ref X a, ref X b) { return a > b; })`` with ``sort!"a < b"(x)``) or
  49 because their performance sucks (mixins are *inlined* by definition, think of
  50 C macros). The language designer is telling you "don't use that feature".
  51
  52 __ http://www.digitalmars.com/d/2.0/index.html
  53 __ http://www.digitalmars.com/d/2.0/phobos/std_algorithm.html#sort
  54 __ http://www.digitalmars.com/d/1.0/expression.html#MixinExpression
  55
  56 Fortunately the later is only a DMD issue, LDC__ is able to inline those
  57 predicates (they have to inhibit the DMD front-end inlining to let LLVM__ do the
  58 dirty work, and it definitely does it better).
  59
  60 __ http://www.dsource.org/projects/ldc
  61 __ http://www.llvm.org/
  62
  63 The problem is I can't use LDC because for some unknown reason it `produces
  64 a non-working Dil executable`__, and Dil is the only **real-life** program
  65 I have to test and benchmark the GC.
  66
  67 __ http://www.dsource.org/projects/ldc/ticket/407
  68
  69 I think this issue__ really hurts D, because if you can't write performance
  70 critical code using higher-level D constructs, you can't showcase your own
  71 language in the important parts.
  72
  73 __ http://d.puremagic.com/issues/show_bug.cgi?id=859
  74
  75
  76 .. vim: set et sw=3 sts=3 :