www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Performance of method calls

reply Daniel Keep <daniel.keep+lists gmail.com> writes:
Hi.

I'm currently working on a research project as part of my Honours, and 
one of the requirements is speed--the code I'm writing has to be very 
efficient.

Before I started, my supervisor warned me about object-oriented 
programming and that it seems to be much slower than just flat function 
calls.

Anyway, I was wondering what the difference between three kinds of 
function calls would be:

1. Foo x; x.call(); // Where Foo is a struct
2. Foo_call(x); // C-style API
3. auto y = new FooClass; y.call(); // Where call is final

I hooked up a test app which used a loop with 100,000 iterations for 
each call type, and ran that program 100 times, and averaged the outputs.


  Are those numbers right??  Is it really that much slower?  I would 
have thought that they should have been about the same since each one 
needs to pass only one thing: a pointer.  I've attached the test 
programs I used; if anyone can offer any insight or even corrections, 
I'd be very grateful.

Incidentally, any other insights regarding performance differences 
between OO-style and flat procedural-style would be very welcome.

	-- Daniel
Nov 29 2006
next sibling parent reply Bill Baxter <wbaxter gmail.com> writes:
Daniel Keep wrote:

 Hi.
 
 I'm currently working on a research project as part of my Honours, and 
 one of the requirements is speed--the code I'm writing has to be very 
 efficient.
 
 Before I started, my supervisor warned me about object-oriented 
 programming and that it seems to be much slower than just flat function 
 calls.
 
 Anyway, I was wondering what the difference between three kinds of 
 function calls would be:
 
 1. Foo x; x.call(); // Where Foo is a struct
 2. Foo_call(x); // C-style API
 3. auto y = new FooClass; y.call(); // Where call is final
 
 I hooked up a test app which used a loop with 100,000 iterations for 
 each call type, and ran that program 100 times, and averaged the outputs.
 

  Are those numbers right??  Is it really that much slower?  I would have 
 thought that they should have been about the same since each one needs 
 to pass only one thing: a pointer.  I've attached the test programs I 
 used; if anyone can offer any insight or even corrections, I'd be very 
 grateful.
 
 Incidentally, any other insights regarding performance differences 
 between OO-style and flat procedural-style would be very welcome.
 
     -- Daniel
 
 
 ------------------------------------------------------------------------
 

 
 for I in {1..100}; do
     ./struct_calls
 done | awk '
     BEGIN {sum1 = 0; sum2 = 0; count = 0;}
     {sum1 += $5; sum2 += $11; count += 1;
      print $1, $2, $3, $4, $5, $6, $7, $8, $9, $10, $11;}
     END {print "Averages: " sum1/count ", " sum2/count}
 ' | tee struct_calls.log
 
 
 
 ------------------------------------------------------------------------
 
 module struct_calls;
 
 import std.perf;
 import std.stdio;
 
 const COUNT = 100_000u;
 
 struct Foo
 {
     uint dummy;
 
     void call()
     {
         //this.dummy = arg;
     }
 }
 
 class FooClass
 {
     uint dummy;
 
     final void call()
     {
         //this.dummy = arg;
     }
 }
 
 void Foo_call(Foo* _this)
 {
     //_this.dummy = arg;
 }
 
 void main()
 {
     Foo x;
 
     scope perf = new HighPerformanceCounter();
 
     perf.start();
     for( uint i=0; i<COUNT; i++ )
         x.call();
     perf.stop();
 
     // count1: x.call()
     auto count1 = perf.periodCount();
 
     perf.start();
     for( uint i=0; i<COUNT; i++ )
         Foo_call(&x);
     perf.stop();
 
     // count2: Foo_call(&x)
     auto count2 = perf.periodCount();
 
     scope y = new FooClass();
 
     perf.start();
     for( uint i=0; i<COUNT; i++ )
         y.call();
     perf.stop();
 
     // count3: y.call()
     auto count3 = perf.periodCount();
 
     writefln("%d / %d = %f -- %d / %d = %f",
             count1, count2, cast(real)count1 / cast(real)count2,
             count3, count2, cast(real)count3 / cast(real)count2);
 }
 



A call to a final method shouldn't be any slower than straight funciton 
call.  But I have heard grumblings that final in D doesn't actually work 
as spec'ed.

But anyway the main point of this reply is that even if method call is 
3x slower than function call, it really means nothing if function call 
overhead is 0.01% of your run time to begin with.  There's a popular 
thing to teach in computer architecture classes called "Amdahl's Law", 
and basically to paraphrase it says don't fixate on optimizing things 
that represent trivial fractions of the overall runtime to begin with. 
For example if method calls represents 0.03% of your overall runtime the 
BEST speedup you could achieve by eliminating all calls entirely would 
be 0.03%.  Pretty trivial.  It's like trying to figure out how to 
improve driving times from home to work, and focusing on increasing your 
speed in your driveway.  Even if you achieve a 100x speedup in how long 
you spend driving on your driveway, you've still only sped up the hour 
long drive by a second or two.  Not worth the effort.

In other words, for all but the most rare of cases, the benifits reaped 
in terms of code reability, maintainablity, and speed of development 
when using virtual functions vastly outweighs the tiny cost.

What you should do is put something representative of the work you 
actually plan to do inside those functions in your test program and see 
if the 3x difference in call speed actually makes any significant 
difference.

--bb
Nov 29 2006
parent reply Daniel Keep <daniel.keep+lists gmail.com> writes:
Bill Baxter wrote:

 Daniel Keep wrote:
 

 Hi.

 I'm currently working on a research project as part of my Honours, and 
 one of the requirements is speed--the code I'm writing has to be very 
 efficient.

 Before I started, my supervisor warned me about object-oriented 
 programming and that it seems to be much slower than just flat 
 function calls.

 Anyway, I was wondering what the difference between three kinds of 
 function calls would be:

 1. Foo x; x.call(); // Where Foo is a struct
 2. Foo_call(x); // C-style API
 3. auto y = new FooClass; y.call(); // Where call is final

 I hooked up a test app which used a loop with 100,000 iterations for 
 each call type, and ran that program 100 times, and averaged the outputs.



 would have thought that they should have been about the same since 
 each one needs to pass only one thing: a pointer.  I've attached the 
 test programs I used; if anyone can offer any insight or even 
 corrections, I'd be very grateful.

 Incidentally, any other insights regarding performance differences 
 between OO-style and flat procedural-style would be very welcome.

     -- Daniel


 ------------------------------------------------------------------------



 for I in {1..100}; do
     ./struct_calls
 done | awk '
     BEGIN {sum1 = 0; sum2 = 0; count = 0;}
     {sum1 += $5; sum2 += $11; count += 1;
      print $1, $2, $3, $4, $5, $6, $7, $8, $9, $10, $11;}
     END {print "Averages: " sum1/count ", " sum2/count}
 ' | tee struct_calls.log



 ------------------------------------------------------------------------

 module struct_calls;

 import std.perf;
 import std.stdio;

 const COUNT = 100_000u;

 struct Foo
 {
     uint dummy;

     void call()
     {
         //this.dummy = arg;
     }
 }

 class FooClass
 {
     uint dummy;

     final void call()
     {
         //this.dummy = arg;
     }
 }

 void Foo_call(Foo* _this)
 {
     //_this.dummy = arg;
 }

 void main()
 {
     Foo x;

     scope perf = new HighPerformanceCounter();

     perf.start();
     for( uint i=0; i<COUNT; i++ )
         x.call();
     perf.stop();

     // count1: x.call()
     auto count1 = perf.periodCount();

     perf.start();
     for( uint i=0; i<COUNT; i++ )
         Foo_call(&x);
     perf.stop();

     // count2: Foo_call(&x)
     auto count2 = perf.periodCount();

     scope y = new FooClass();

     perf.start();
     for( uint i=0; i<COUNT; i++ )
         y.call();
     perf.stop();

     // count3: y.call()
     auto count3 = perf.periodCount();

     writefln("%d / %d = %f -- %d / %d = %f",
             count1, count2, cast(real)count1 / cast(real)count2,
             count3, count2, cast(real)count3 / cast(real)count2);
 }


 
 
 A call to a final method shouldn't be any slower than straight funciton 
 call.  But I have heard grumblings that final in D doesn't actually work 
 as spec'ed.
 
 But anyway the main point of this reply is that even if method call is 
 3x slower than function call, it really means nothing if function call 
 overhead is 0.01% of your run time to begin with.  There's a popular 
 thing to teach in computer architecture classes called "Amdahl's Law", 
 and basically to paraphrase it says don't fixate on optimizing things 
 that represent trivial fractions of the overall runtime to begin with. 
 For example if method calls represents 0.03% of your overall runtime the 
 BEST speedup you could achieve by eliminating all calls entirely would 
 be 0.03%.  Pretty trivial.  It's like trying to figure out how to 
 improve driving times from home to work, and focusing on increasing your 
 speed in your driveway.  Even if you achieve a 100x speedup in how long 
 you spend driving on your driveway, you've still only sped up the hour 
 long drive by a second or two.  Not worth the effort.
 
 In other words, for all but the most rare of cases, the benifits reaped 
 in terms of code reability, maintainablity, and speed of development 
 when using virtual functions vastly outweighs the tiny cost.
 
 What you should do is put something representative of the work you 
 actually plan to do inside those functions in your test program and see 
 if the 3x difference in call speed actually makes any significant 
 difference.
 
 --bb


I'm well aware that the time it takes to call into the function and pass 
back out may be a very small amount of the overall time, but when 
there's a 2-3x difference between supposedly identical code, that puts 
up red warning flags in my head.  If this is so much slower, what other 
things are slower?

Also, normally I would agree that the benefits of "elegant" code 
outweigh the performance drop.  But not in this case.  I'm not sure if I 
can go into specifics, but the system will potentially be simulating 
millions of individual agents across a networked cluster, with the 
eventual aim to become faster than realtime.

As for putting code representative of what it'll be doing... I can't at 
this stage since I'm still building the utility libraries.  That 
representative code doesn't exist yet.

I don't want to get bogged down in premature optimisation, but I also 
want to eliminate any potential bottlenecks early if it isn't too much 
effort.

In any case, I just want to understand where the difference is coming 
from.  If I understand the difference, I can hopefully make better 
decisions.  My supervisor originally wanted the code written in C, and I 
want to prove that D is more than up to the task.

	-- Daniel

P.S.  To give you an idea of how badly I want to use D: I ported CWEB 
over to support D :)
Nov 29 2006
parent Bill Baxter <wbaxter gmail.com> writes:
Daniel Keep wrote:

 Bill Baxter wrote:
 
 As for putting code representative of what it'll be doing... I can't at 
 this stage since I'm still building the utility libraries.  That 
 representative code doesn't exist yet.


You can at least put in a loop that adds a bunch of numbers up.
Or writes to elements in an array passed in or something like that.

I think D won't inline anything with a loop, so that would also help to 
rule out the inlining affecting results.

Another thing the D optimizer does, though, (reportedly) is to turn 
virtual calls into non-virtual ones when the actual class is known at 
compile time, so it that could affect your results too.

--bb
Nov 29 2006
prev sibling next sibling parent reply Walter Bright <newshound digitalmars.com> writes:
Daniel Keep wrote:

 I hooked up a test app which used a loop with 100,000 iterations for 
 each call type, and ran that program 100 times, and averaged the outputs.


What flags did you use to compile it?
Nov 29 2006
parent reply Daniel Keep <daniel.keep+lists gmail.com> writes:
Walter Bright wrote:

 Daniel Keep wrote:
 

 I hooked up a test app which used a loop with 100,000 iterations for 
 each call type, and ran that program 100 times, and averaged the outputs.


 
 
 What flags did you use to compile it?


I didn't use any flags; I was worried about the compiler being "smart" 
and inlining the functions calls which would... well, eliminate them 
entirely :P

If there are any flags you can recommend that would give more realistic 
results, I'd love to know.

	-- Daniel
Nov 29 2006
parent reply Daniel Keep <daniel.keep+lists gmail.com> writes:
Daniel Keep wrote:

 Walter Bright wrote:
 

 Daniel Keep wrote:


 I hooked up a test app which used a loop with 100,000 iterations for 
 each call type, and ran that program 100 times, and averaged the 
 outputs.




 What flags did you use to compile it?


 
 
 I didn't use any flags; I was worried about the compiler being "smart" 
 and inlining the functions calls which would... well, eliminate them 
 entirely :P
 
 If there are any flags you can recommend that would give more realistic 
 results, I'd love to know.
 
     -- Daniel
 


I just recompiled and re-ran with some different flags.  The results 
are... interesting.



-O: 1.39892 and 3.61384
-O -release: 1.00703 and 1.0163
-O -inline: 1.89054 and 13.4001
-O -release -inline: 1.8257 and 1.00007

Now I've got *no* idea what to think :P

	-- Daniel
Nov 29 2006
next sibling parent reply Walter Bright <newshound digitalmars.com> writes:
Daniel Keep wrote:

 I just recompiled and re-ran with some different flags.  The results 
 are... interesting.
 

 
 -O: 1.39892 and 3.61384
 -O -release: 1.00703 and 1.0163
 -O -inline: 1.89054 and 13.4001
 -O -release -inline: 1.8257 and 1.00007
 
 Now I've got *no* idea what to think :P


You really need to use obj2asm on the results. It'll make things a lot 
more sensible!
Nov 30 2006
parent reply Daniel Keep <daniel.keep+lists gmail.com> writes:
Walter Bright wrote:

 Daniel Keep wrote:
 

 I just recompiled and re-ran with some different flags.  The results 
 are... interesting.



 -O: 1.39892 and 3.61384
 -O -release: 1.00703 and 1.0163
 -O -inline: 1.89054 and 13.4001
 -O -release -inline: 1.8257 and 1.00007

 Now I've got *no* idea what to think :P


 
 
 You really need to use obj2asm on the results. It'll make things a lot 
 more sensible!


Isn't obj2asm linux only?  I used ndisasm on the object files, but my 
x86 assembler isn't quite good enough to work out what's going on :P

	-- Daniel
Nov 30 2006
parent Sean Kelly <sean f4.ca> writes:
Daniel Keep wrote:

 Walter Bright wrote:

 Daniel Keep wrote:


 I just recompiled and re-ran with some different flags.  The results 
 are... interesting.



 -O: 1.39892 and 3.61384
 -O -release: 1.00703 and 1.0163
 -O -inline: 1.89054 and 13.4001
 -O -release -inline: 1.8257 and 1.00007

 Now I've got *no* idea what to think :P



 You really need to use obj2asm on the results. It'll make things a lot 
 more sensible!


 
 Isn't obj2asm linux only?  I used ndisasm on the object files, but my 
 x86 assembler isn't quite good enough to work out what's going on :P


A Win32 version exists as part of the "extended utilities package" 
available from digitalmars.com.  It's worth the $15 cost all by itself IMO.


Sean
Nov 30 2006
prev sibling next sibling parent Sean Kelly <sean f4.ca> writes:
Daniel Keep wrote:

 
 I just recompiled and re-ran with some different flags.  The results 
 are... interesting.
 

 
 -O: 1.39892 and 3.61384
 -O -release: 1.00703 and 1.0163
 -O -inline: 1.89054 and 13.4001
 -O -release -inline: 1.8257 and 1.00007
 
 Now I've got *no* idea what to think :P


For what it's worth, I've noticed that inlining of struct methods is 
inconsistent (the last case).  I ran some tests a while back and in some 
cases simply changing the method to/from a static method was enough to 
affect whether it was inlined.  And I think how the method is used is a 
factor as well.  I am using structs with opCall as default comparators 
in my algorithm code because they have the potential to be inlined, 
while delegates currently do not, but even:

struct IsEqual(T) { bool opCall(T a, T b) { return a == b; } }

only inlines in some of the algorithms.  And this may be true of 
inlining in general--I simply haven't looked into the problem enough.


Sean
Nov 30 2006
prev sibling parent Dave <Dave_member pathlink.com> writes:
Daniel Keep wrote:

 Daniel Keep wrote:

 Walter Bright wrote:


 Daniel Keep wrote:


 I hooked up a test app which used a loop with 100,000 iterations for 
 each call type, and ran that program 100 times, and averaged the 
 outputs.




 What flags did you use to compile it?



 I didn't use any flags; I was worried about the compiler being "smart" 
 and inlining the functions calls which would... well, eliminate them 
 entirely :P

 If there are any flags you can recommend that would give more 
 realistic results, I'd love to know.

     -- Daniel


 
 I just recompiled and re-ran with some different flags.  The results 
 are... interesting.
 

 
 -O: 1.39892 and 3.61384
 -O -release: 1.00703 and 1.0163
 -O -inline: 1.89054 and 13.4001
 -O -release -inline: 1.8257 and 1.00007
 
 Now I've got *no* idea what to think :P
 
     -- Daniel


I think there's some kind of stack alignment issue going on or something... If
you comment out the 
timing code, change the 'scope y' to 'auto y' and run each one at a time [with
-O -release -inline] 
you get very close to the same results for each (as expected).
Nov 30 2006
prev sibling next sibling parent Marcio <mqmnews123 sglebs.com> writes:
Daniel Keep wrote:

 Anyway, I was wondering what the difference between three kinds of 
 function calls would be:
 
 1. Foo x; x.call(); // Where Foo is a struct
 2. Foo_call(x); // C-style API
 3. auto y = new FooClass; y.call(); // Where call is final




	I remember using SmartEiffel a couple of years ago and it used to do 
global analysis and would optimize out polymorphic calls that weren't 
really polymorphic. Normal numbers were 90% of polymorphic calls 
transformed into regular function calls. The performance was amazing.

	Maybe you want to test your code under their compiler as well?

marcio
Nov 30 2006
prev sibling parent reply John Demme <me teqdruid.com> writes:
Daniel Keep wrote:


 Hi.
 
 I'm currently working on a research project as part of my Honours, and
 one of the requirements is speed--the code I'm writing has to be very
 efficient.
 
 Before I started, my supervisor warned me about object-oriented
 programming and that it seems to be much slower than just flat function
 calls.
 
 Anyway, I was wondering what the difference between three kinds of
 function calls would be:
 
 1. Foo x; x.call(); // Where Foo is a struct
 2. Foo_call(x); // C-style API
 3. auto y = new FooClass; y.call(); // Where call is final
 
 I hooked up a test app which used a loop with 100,000 iterations for
 each call type, and ran that program 100 times, and averaged the outputs.
 

   Are those numbers right??  Is it really that much slower?  I would
 have thought that they should have been about the same since each one
 needs to pass only one thing: a pointer.  I've attached the test
 programs I used; if anyone can offer any insight or even corrections,
 I'd be very grateful.
 
 Incidentally, any other insights regarding performance differences
 between OO-style and flat procedural-style would be very welcome.
 
 -- Daniel


D's advantages over C are far more than just OO.  Write equivalent test
programs in C and D and test them with DMC and DMD.  I'd bet that they'll
be about the same.  This being the case, you can use D but avoid OO calls
if they turn out to be too heavy weight.  For a program of any size in C,
I'd kill for features like dynamic arrays, templates, and the like.

Of course, I suspect that even if DMD's OO performance isn't top notch right
now, it will become so.  I've heard Walter mention that he hasn't yet tuned
the backend optimizer for OO code- I don't know if this is still true, but
it's probably a safe bet that DMD's performance a few months from now will
be significantly better than now.

-- 
~John Demme
me teqdruid.com
http://www.teqdruid.com/
Dec 01 2006
parent reply Daniel Keep <daniel.keep+lists gmail.com> writes:
John Demme wrote:

 Daniel Keep wrote:
 
 

Hi.

I'm currently working on a research project as part of my Honours, and
one of the requirements is speed--the code I'm writing has to be very
efficient.

Before I started, my supervisor warned me about object-oriented
programming and that it seems to be much slower than just flat function
calls.

Anyway, I was wondering what the difference between three kinds of
function calls would be:

1. Foo x; x.call(); // Where Foo is a struct
2. Foo_call(x); // C-style API
3. auto y = new FooClass; y.call(); // Where call is final

I hooked up a test app which used a loop with 100,000 iterations for
each call type, and ran that program 100 times, and averaged the outputs.


  Are those numbers right??  Is it really that much slower?  I would
have thought that they should have been about the same since each one
needs to pass only one thing: a pointer.  I've attached the test
programs I used; if anyone can offer any insight or even corrections,
I'd be very grateful.

Incidentally, any other insights regarding performance differences
between OO-style and flat procedural-style would be very welcome.

-- Daniel


 
 
 D's advantages over C are far more than just OO.  Write equivalent test
 programs in C and D and test them with DMC and DMD.  I'd bet that they'll
 be about the same.  This being the case, you can use D but avoid OO calls
 if they turn out to be too heavy weight.  For a program of any size in C,
 I'd kill for features like dynamic arrays, templates, and the like.


Damn straight.  Very first thing I wrote involved templated structs, 
simply because it allowed me to write much cleaner, safer code.  I now 
have a literate library module with contracts and unit tests.


 Of course, I suspect that even if DMD's OO performance isn't top notch right
 now, it will become so.  I've heard Walter mention that he hasn't yet tuned
 the backend optimizer for OO code- I don't know if this is still true, but
 it's probably a safe bet that DMD's performance a few months from now will
 be significantly better than now.


Lamentably, I can't go back to my supervisor and say "but this guy said 
that Walter said that it'll totally get faster!"

Incidentally, I wrote up a much larger test program, compiled with about 
five different sets of compiler switches and then disassembled the whole 
shtick and started reading through it.

It's really annoying to write test applications and then discover the 
compiler's elided half of it :P  Damn optimisations...  at least it 
explains the performance increases!

I've decided that I'll try to stick to structures with member functions 
wherever possible.  The main difference in performance appears to be 
creation and destruction of classes vs. structs.  I still want to get 
the newest DMD and see what difference stack allocation makes (silly me 
for doing this without checking to make sure I had the newest compiler...)

The only thing I really miss when using structures are constructors and 
destructors.  Any reason why we can't have them, Walter?  Pwetty pweese? 
  You can make it my Christmas Pressy...

	-- Daniel
Dec 01 2006
parent reply Mike Capp <mike.capp gmail.com> writes:
== Quote from Daniel Keep (daniel.keep+lists gmail.com)'s article


 The only thing I really miss when using structures are constructors and
 destructors.  Any reason why we can't have them, Walter?  Pwetty pweese?


I think most people use static opCall as a workaround for the lack of struct
ctors. It's not a perfect substitute (in particular, you don't get invariant
checks on 'construction') but it's liveable.

I doubt very much whether Walter will ever add struct dtors - it requires a
bunch
of extra code to be generated, and with "scope" there's no great need for them.

cheers
Mike
Dec 01 2006
parent Daniel Keep <daniel.keep+lists gmail.com> writes:
Mike Capp wrote:

 == Quote from Daniel Keep (daniel.keep+lists gmail.com)'s article
 
 

The only thing I really miss when using structures are constructors and
destructors.  Any reason why we can't have them, Walter?  Pwetty pweese?


 
 
 I think most people use static opCall as a workaround for the lack of struct
 ctors. It's not a perfect substitute (in particular, you don't get invariant
 checks on 'construction') but it's liveable.


True.  What I'm worried about is the performance difference between


 Foo x = Foo();


and


 Foo x; x.init();


Ah well.  It's only one extra statement :)


 I doubt very much whether Walter will ever add struct dtors - it requires a
bunch
 of extra code to be generated, and with "scope" there's no great need for them.
 
 cheers
 Mike


I know, I know.  I just wish I could omit `foo.init(); scope(exit) 
foo.cleanup()` every time I make a Foo.  Then again, it would only be 
worse in C :3

*sigh*  This is what happens when someone says "It has to be efficient": 
I go nuts over every little instruction...

	-- Daniel
Dec 01 2006