Delegate perfomance (outrage was redherring)

[Justin Johansson]

bearophile Wrote:

> Justin Johansson:
> 
> > downs:
> > > Also I have no idea what you mean. Should delegate _values_ be heap allocated?! That'd be insanity. Also, I'm fairly sure you're wrong. The stack is relatively likely to be in the CPU cache. A random pointer dereferencing .. isn't. Also, do you really want to heap even more work on the ailing GC?
> > 
> > I will be bold and say yes to off-stack allocation,
> > whether that be in the general heap or other (and probably other to avoid an "ailing CG").
> 
> This is a nice situation: with just 10-20 minutes of experimental tests (that later you have to show us) you can show us you are right, or wrong.
> 
> Bye,
> bearophile

Fresh light of morning ...

I'm really glad to have brought this up as I would not have bothered to revisit a performance
issue that I had in porting some C++ to D (and this was not looking good for D at first sight).

As it turns out though, my initial fear about the .sizeof delegate was unfounded as the performance
bottleneck was in an loop inside of a method taking what was effectively a callback parameter.

The C++ design was basically implementing a classical visitor pattern over a collection.

In porting to D I had a choice of either doing a one-for-one translation of the C++ classes or
redesigning using D delegates.

This morning I boiled the problem down to the simplest possible with the two forms and
benchmarked these.  From the code I have reproduced below, clearly the
issue is nothing to do with the cost of instantiating a delegate or visitor object.  That turns
out to be a one time cost and irrelevant given where the iteration actually occurs.

So while this isn't the proof or disproof that bearophile asked for, this turns out to be
a clear demonstration of the performance-enhancing power of D delegates over an
otherwise ingrained C++ thinking approach.

I'm impressed.  (Hope that statement isn't too emotional  :-)


#! /opt/dmd1/linux/bin/rdmd -I/opt/dmd1/src/phobos -L-L/opt/dmd1/linux/lib -release

import std.perf, std.stdio;


class SetOfIntegers
{
   private int from, to;
   
   this( int from, int to) {
      this.from = from;
      this.to = to;
   }

   int forEach( int delegate( int x) apply) {
      for (auto i = from; i <= to; ++i) {
         apply( i);
      }

      return 0;
   }

   int forEach( Visitor v) {
      for (auto i = from; i <= to; ++i) {
         v.visit( i);
      }

      return 0;
   }
}



class Visitor
{
   abstract int visit( int x);
}



class MyVisitor: Visitor
{
   int visit( int x) { return 0; }
}



void test1( SetOfIntegers s, Visitor v)
{
    auto pc = new PerformanceCounter();
    pc.start();

    scope(exit) {
       pc.stop();
       writefln( "Using D style delegate callback:  %d msec", pc.milliseconds());
    }

    s.forEach( &v.visit);
}


void test2( SetOfIntegers s, Visitor v)
{
    auto pc = new PerformanceCounter();
    pc.start();

    scope(exit) {
       pc.stop();
       writefln( "Using C++ style virtual callback: %d msec", pc.milliseconds());
    }

    s.forEach( v);
}


void main() {
   writefln( "Delegates vs virtual function callbacks");
   writefln();

   SetOfIntegers s = new SetOfIntegers( 1, 10000000);
   Visitor v = new MyVisitor();

   for (auto i = 0; i < 10; ++i) {
      test1( s, v);
      test2( s, v);
      writefln();
   }

   writefln();
}


$ ./perf.d
Delegates vs virtual function callbacks

Using D style delegate callback:  121 msec
Using C++ style virtual callback: 146 msec

Using D style delegate callback:  121 msec
Using C++ style virtual callback: 147 msec

Using D style delegate callback:  120 msec
Using C++ style virtual callback: 145 msec

Using D style delegate callback:  121 msec
Using C++ style virtual callback: 145 msec

Using D style delegate callback:  120 msec
Using C++ style virtual callback: 145 msec

Using D style delegate callback:  120 msec
Using C++ style virtual callback: 147 msec

Using D style delegate callback:  121 msec
Using C++ style virtual callback: 147 msec

Using D style delegate callback:  121 msec
Using C++ style virtual callback: 147 msec

Using D style delegate callback:  121 msec
Using C++ style virtual callback: 146 msec

Using D style delegate callback:  121 msec
Using C++ style virtual callback: 147 msec


Sweet.


cheers
Justin Johansson