[boost] Overload resolution speed

Subject: [boost] Overload resolution speed
From: Mathias Gaunard (mathias.gaunard_at_[hidden])
Date: 2011-09-21 14:20:06

As part of the Boost.SIMD effort, another library was developed, 
Boost.Dispatch, which relies heavily on overload resolution.

Before submitting this library for review, however, I did some 
compile-time benchmarking, and it's not looking very good.
I'm therefore asking the Boost community if 1) this is expected, 2) if 
there is a workaround to this problem and 3) if compilers should be made 
to deal with this better.

Boost.Dispatch essentially overloads a single free function, with, as 
arguments, a tag identifying the function followed by tags identifying 
properties/categories of the arguments (in an attempt to make a 
transparent tag dispatching system).

The scripts from the link below [1] (the shell script is POSIX/GCC-only 
but should be easily adaptable) performs two tests:

  - Resolving a call with 1,000 function tags, overloaded 10 times each, 
everything implemented by overloading the same function as described above,
  - Resolving a call with 1,000 function tags, overloaded 10 times each, 
but with each function tag using a different functon.

It takes 30s in the first case, 160ms in the second one.
Unfortunately, the second solution is very restrictive and doesn't play 
very nice with generic programming.

C++ apparently lacks a mechanism to define overloadable free functions 
with template parameters in their name.

Back to the benchmark, making the number of functions vary show an 
apparent exponential increase in compile time. It's reasonably fast for 
100 functions, but not at all for 1,000.
On the other hand, changing the depth of the inheritance tree used for 
the category tags doesn't seem to affect it much.

Any suggestions?

[1] http://dl.dropbox.com/u/26902324/dispatching_bench.tar.gz