Hello,


I had not initially noticed that the 'in' operator (for AAs) returns a pointer to the looked up element. So that, to avoid double lookup in cases where lookups may fail, I naively used try...catch. In cases of very numerous lookups, my code suddenly became blitz fast. So that I wondered about exception handling efficiency. Below a test case (on my computer, both loops run in about the same average time):

void main () {
    byte[uint] table = [3:1, 33:1, 333:1];
    byte b;
    byte* p;
    Time t0;
    uint N1 = 246, N2 = 9999999;

    // try...catch
    t0 = time();
    foreach (n ; 0..N1) {
        try b = table[n];
        catch (RangeError e) {}
    }
    writefln("try...catch version time: %sms", time() - t0);

    // pointer
    t0 = time();
    foreach (n ; 0..N2) {
        p = (n in table);
        if (p) b = table[n];
    }
    writefln("pointer version time: %sms", time() - t0);

    writefln("pointer version is about %s times faster",N2/N1);
}
==>
try...catch version time: 387ms
pointer version time: 388ms
pointer version is about 40650 times faster

Note that both versions perform a single lookup trial; the difference thus only lies in pointer deref vs try...catch handling, i guess. What do you think?


Denis
-- -- -- -- -- -- --
vit esse estrany ☣

spir.wikidot.com

spir:

> try...catch version time: 387ms
> pointer version time: 388ms
> pointer version is about 40650 times faster

Those numbers look wrong :-)


> What do you think?

Compared to Oracle Java VM the DMD exceptions are very slow. Performance tuning of DMD is left for later, when the main features are all present.

Bye,
bearophile

On 2010-12-19 07:33:29 -0500, spir <denis.spir@gmail.com> said:

>     // pointer
>     t0 = time();
>     foreach (n ; 0..N2) {
>         p = (n in table);
>         if (p) b = table[n];
>     }

But why the double lookup? Just dereference the pointer:

	foreach (n ; 0..N2) {
		p = (n in table);
		if (p) b = *p;
	}


-- 
Michel Fortin
michel.fortin@michelf.com
http://michelf.com/

On Sun, 19 Dec 2010 07:47:11 -0500
Michel Fortin <michel.fortin@michelf.com> wrote:

> On 2010-12-19 07:33:29 -0500, spir <denis.spir@gmail.com> said:
> 
> >     // pointer
> >     t0 = time();
> >     foreach (n ; 0..N2) {
> >         p = (n in table);
> >         if (p) b = table[n];
> >     }
> 
> But why the double lookup? Just dereference the pointer:
> 
> 	foreach (n ; 0..N2) {
> 		p = (n in table);
> 		if (p) b = *p;
> 	}

Oops, sorry, code copy error. But this does not change the test result times (because nearly no key exists in the table).

denis
-- -- -- -- -- -- --
vit esse estrany ☣

spir.wikidot.com

On Sun, 19 Dec 2010 07:46:09 -0500
bearophile <bearophileHUGS@lycos.com> wrote:

> spir:
> 
> > try...catch version time: 387ms
> > pointer version time: 388ms
> > pointer version is about 40650 times faster
> 
> Those numbers look wrong :-)

I thought so. But in the real app a loop that lasted ~ 10s suddenly became instantaneous (human perception ;-) Try it. Sorry, but I'm not inventing the numbers.

> > What do you think?
> 
> Compared to Oracle Java VM the DMD exceptions are very slow. Performance tuning of DMD is left for later, when the main features are all present.

And what if the numbers are correct? Exception handling is explicitely recommanded in some docs --as opposed to C-like "manual" hacks.


Denis
-- -- -- -- -- -- --
vit esse estrany ☣

spir.wikidot.com

spir wrote:

> Hello,
> 
> 
> I had not initially noticed that the 'in' operator (for AAs) returns a pointer to the looked up element. So that, to avoid double lookup in cases where lookups may fail, I naively used try...catch. In cases of very numerous lookups, my code suddenly became blitz fast. So that I wondered about exception handling efficiency. Below a test case (on my computer, both loops run in about the same average time):
> 

Catching exceptions is known to be a bit costly. Generally, in C family languages with exceptions (such as D), it is considered bad practice to use exceptions for regular control flow. The cost is therefore acceptable because it is not suffered on the normal, happy code path.

That the performance cost is so huge is likely not only the inherent overhead of exceptions, but probably also some extra cache misses or something like that.[needs analysis]

On 2010-12-19 08:17:07 -0500, spir <denis.spir@gmail.com> said:

> On Sun, 19 Dec 2010 07:46:09 -0500
> bearophile <bearophileHUGS@lycos.com> wrote:
> 
>> spir:
>> 
>>> try...catch version time: 387ms
>>> pointer version time: 388ms
>>> pointer version is about 40650 times faster
>> 
>> Those numbers look wrong :-)
> 
> I thought so. But in the real app a loop that lasted ~ 10s suddenly became
> instantaneous (human perception ;-)
> Try it. Sorry, but I'm not inventing the numbers.

What looks wrong is that the output seem to say that 388ms was 40650 times faster than 387ms. Obviously, by looking at the code one can understand that you adjusted the number of iteration to get the same time for both versions, and from that number of iteration you can claim the pointer version is about X times faster. But the output alone is misleading. Add the iteration count to the output and it'll be easier to read.

Exceptions are slow, that's a fact of life. The idea is that an exception should be exceptional, so the case to optimize for is the case where you don't have any exception: a try...catch that doesn't throw. Other ways to implement exceptions exists which are faster at throwing (setjmp for instance), but they're also slower at entering and exiting a try..catch block when no exception occur.


>>> What do you think?
>> 
>> Compared to Oracle Java VM the DMD exceptions are very slow. Performance
>> tuning of DMD is left for later, when the main features are all present.
> 
> And what if the numbers are correct? Exception handling is explicitely reco
> mmanded in some docs --as opposed to C-like "manual" hacks.

Exceptions are recommended to avoid cluttering your normal code flow with error handling code. Clearly, in the code above exceptions are part of the normal code flow. That's not what exception are made for.

That said, I'd encourage you to profile this test case to see where the time is being spent. You might find one or two places that can be improved in the part of the runtime dedicated to exceptions.


-- 
Michel Fortin
michel.fortin@michelf.com
http://michelf.com/

On Sun, 19 Dec 2010 07:33:29 -0500, spir <denis.spir@gmail.com> wrote:

> Hello,
>
>
> I had not initially noticed that the 'in' operator (for AAs) returns a pointer to the looked up element. So that, to avoid double lookup in cases where lookups may fail, I naively used try...catch. In cases of very numerous lookups, my code suddenly became blitz fast. So that I wondered about exception handling efficiency. Below a test case (on my computer, both loops run in about the same average time):
>
> void main () {
>     byte[uint] table = [3:1, 33:1, 333:1];
>     byte b;
>     byte* p;
>     Time t0;
>     uint N1 = 246, N2 = 9999999;
>    // try...catch
>     t0 = time();
>     foreach (n ; 0..N1) {
>         try b = table[n];
>         catch (RangeError e) {}
>     }
>     writefln("try...catch version time: %sms", time() - t0);
>    // pointer
>     t0 = time();
>     foreach (n ; 0..N2) {
>         p = (n in table);
>         if (p) b = table[n];
>     }
>     writefln("pointer version time: %sms", time() - t0);
>    writefln("pointer version is about %s times faster",N2/N1);
> }
> ==>
> try...catch version time: 387ms
> pointer version time: 388ms
> pointer version is about 40650 times faster
>
> Note that both versions perform a single lookup trial; the difference thus only lies in pointer deref vs try...catch handling, i guess. What do you think?

This example is misleading.  First, catching an exception should be a rare occurrence (literally, an exception to the rule).  You are testing the case where catching an exception vastly outweighs the cases where an exception is not thrown.  What I'm saying is, catching an exception is very slow, but *trying* to catch an exception is not.

Second, exception handling is not meant to be used in the way you used it.  You don't use it as an extra return value.  I'd expect a more reasonable use of catching an exception in AAs as this:

try
{
  foreach(n ; 0..N1)
  {
     b = table[n];
  }
}
catch(RangeError e)
{
   writeln("Caught exception! ", e);
}

An exception is a recoverable error, but it usually means something is wrong, not 'business as usual'.  This doesn't mean it's impossible to design poor interfaces that use exceptions for everything, but it shouldn't be that way.  An exception should always be a rare occurrence, when something happens that you don't expect.  A huge clue that you are using exceptions poorly or that the interface is not meant to be used that way is if your exception handling is being done at the innermost level of your program.  Exception handling is great when it exists at a much higher level, because you can essentially do all error handling in one spot, and simply write code without worrying about error codes.

This is why the 'in' operator exists for AAs.

General rules of thumb for AAs:

1. if you expect that a value is always going to be present when you ask for it, use exception handling at a high level.
2. if you *don't* expect that, and want to check the existence of an element, use 'in'

Now, after saying all that, improving how exception handling works can only be good.  So comparing exception handling performance in D to exception handling in other languages can give a better idea of how well D's exception handling performs.

-Steve

On Mon, 20 Dec 2010 12:29:29 -0500
"Steven Schveighoffer" <schveiguy@yahoo.com> wrote:

> This example is misleading.  First, catching an exception should be a rare occurrence (literally, an exception to the rule).  You are testing the case where catching an exception vastly outweighs the cases where an exception is not thrown.  What I'm saying is, catching an exception is very slow, but *trying* to catch an exception is not.

Right, understood, thank you.

Denis
-- -- -- -- -- -- --
vit esse estrany ☣

spir.wikidot.com

Michel Fortin wrote:
> Exceptions are slow, that's a fact of life. The idea is that an exception should be exceptional, so the case to optimize for is the case where you don't have any exception: a try...catch that doesn't throw. Other ways to implement exceptions exists which are faster at throwing (setjmp for instance), but they're also slower at entering and exiting a try..catch block when no exception occur.

[...]

> Exceptions are recommended to avoid cluttering your normal code flow with error handling code. Clearly, in the code above exceptions are part of the normal code flow. That's not what exception are made for.

Right on all counts. Exceptions are for *exceptional* cases, i.e. unexpected errors, not normal control flow.

The implementation is designed so that the speed normal execution is strongly favored over speed of exception handling.