Re: [boost] Overload resolution speed

Subject: Re: [boost] Overload resolution speed
From: John Bytheway (jbytheway+boost_at_[hidden])
Date: 2011-09-21 18:42:57

On 21/09/11 19:20, Mathias Gaunard wrote:
> 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.

clang's a bit faster than g++ here, but not much; I suspect a newer g++
would match it:

$ time clang++ -fsyntax-only test.cpp

real    0m30.909s
user    0m29.974s
sys     0m0.088s
$ time g++ -fsyntax-only test.cpp

real    0m53.748s
user    0m53.017s
sys     0m0.140s
$ clang++ --version
clang version 3.0 (trunk 134846)
Target: x86_64-unknown-linux-gnu
Thread model: posix
$ g++ --version
g++ (Gentoo 4.4.5 p1.0, pie-0.4.5) 4.4.5
Copyright (C) 2010 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

> 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.

I'm not really sure what your constraints are, but here are a couple of
ideas (not benchmarked):

What about using functors; so the call would be something like

dispatching<f0_>()(h49_<int>(), h49_<int>(), h49_<int>(), h49_<int>(),
h49_<int>());

with the f parameter choosing a template specialization, and then the
other parameters picking an overload of operator() ion it?

Or, if you must use functions, you could have two layers.  The 'outer'
layer would be called as in your test.cpp:

dispatching(f0_(), h49_<int>(), h49_<int>(), h49_<int>(), h49_<int>(),
h49_<int>());

and would be overloaded only on the first argument, forwarding the rest
to one of a number of 'inner' functions (one for each f).  So, one such
overload would be:

template<typename... A>
void dispatching(f0_, A... a) {
  dispatching_f0_(a...)
}

(adapt in the obvious way to get a C++03 version)

John Bytheway