Removing thrown (C++) exceptions

graph-tool
1

C++ exceptions are zero cost only when *not* thrown; keeping them out of
critical paths can make a significant difference in performance.

Throwing exceptions is currently a routine part of the process of
identifying concrete types for dispatching. When runtime is dominated by
code strictly inside C++ this is not an issue, but for algorithms that must
repeatedly cross the C++/Python boundary it can become a real performance
problem. In particular, the search algorithms and their Visitors do this; I
have found that using a non-throwing approach makes a dramatic speed
improvement - over 2X for a maze router benchmark based on an implicit A*
search.

I'm offering this patch
<https://git.skewed.de/count0/graph-tool/-/merge_requests/24&gt; as an
implementation; I think it may be worth investigating if similar
optimizations are available elsewhere in the code.

Best,
Jeff

attachment.html (998 Bytes)

2

Thanks for this. The patch looks very good, and I'll merge it if testing
does not dredge up anything, which is unlikely.

Indeed the most typical case in graph-tool is that the exception is
thrown only once, so the runtime cost is imperceptible. However, as you
point out, this is not true for the visitor pattern in the search
module, where the exception is thrown constantly. I've never benchmark
this because I thought the exception throwing would still not be
noticeable from the Python side of things, but it seems I was wrong.
Thanks for noticing this, and for providing the benchmark!

If there are any problems I will point this out via the gitlab interface.

Best,
Tiago