optimization question: mpl
I'm writing a decoder using a meta programming techniques alla
boost::mpl and I'd like to know if I'm asking too much of the compiler.
Basically I've got lots of packet types with different ids. The
classical way to write these would be a switch case
int id;
switch(id){
case Id1: decode1() break;
case Id2: decode2() break;
...
}
I'm tring to use the template compiler to generate equivalent code. I
have a mpl::list of packet descriptions like this:
struct Packet1{
static const int id=1;
void decode();
};
I then use boost::mpl::fold to generate a decode function which might
look sort of like this:
void decode1(int id){
if(id==1)
Packet1::decode();
else
decode2(id);
}
What I'm hoping is that the compiler is smart enough
* to inline all decode*() calls into one function
* to notice I compare id to N constants and use switch case optimization
(binary search or lookup table)
Am I asking too much?
Do I have to watch for any pitfalls that willl break the optimization,
like making id a member of a class or leaving out the 'else' ?
I could write more complicated meta-code which sorts by id and does a
runtime binary search, that would probably prevent the optimizer from
doing anything smarter.
Chris Hite
Re: optimization question: mpl
On Wed, Jul 28, 2010 at 4:37 PM, Hite, Christopher
wrote:
>
>
>
> I'm writing a decoder using a meta programming techniques alla
> boost::mpl and I'd like to know if I'm asking too much of the compiler.
>
> Basically I've got lots of packet types with different ids. The
> classical way to write these would be a switch case
>
> int id;
> switch(id){
> case Id1: decode1() break;
> case Id2: decode2() break;
> ...
> }
>
> I'm tring to use the template compiler to generate equivalent code. I
> have a mpl::list of packet descriptions like this:
> struct Packet1{
> static const int id=1;
> void decode();
> };
>
> I then use boost::mpl::fold to generate a decode function which might
> look sort of like this:
>
> void decode1(int id){
> if(id==1)
> Packet1::decode();
> else
> decode2(id);
> }
>
> What I'm hoping is that the compiler is smart enough
> * to inline all decode*() calls into one function
> * to notice I compare id to N constants and use switch case optimization
> (binary search or lookup table)
>
> Am I asking too much?
>
> Do I have to watch for any pitfalls that willl break the optimization,
> like making id a member of a class or leaving out the 'else' ?
>
>
> I could write more complicated meta-code which sorts by id and does a
> runtime binary search, that would probably prevent the optimizer from
> doing anything smarter.
Generally without knowing the compiler version you are using
it is hard to tell. The same is true without a complete compilable
testcase.
You can use the flatten attribute to tell the compiler to inline all
calls in a given function, like
void __attribute__((flatten)) foo(void)
{
...
decode1();
...
}
and it will inline decode1() (and recursively all its callees).
Richard.
> Chris Hite
>
>
Re: optimization question: mpl
On 07/28/10 09:37, Hite, Christopher wrote:
[snip]
I'm tring to use the template compiler to generate equivalent code. I
have a mpl::list of packet descriptions like this:
struct Packet1{
static const int id=1;
void decode();
};
I then use boost::mpl::fold to generate a decode function which might
look sort of like this:
void decode1(int id){
if(id==1)
Packet1::decode();
else
decode2(id);
}
[snip]
boost::mpl::fold generates types, not functions; hence, I don't
understand how it can be used to generate this function.
Maybe if you posted the code that generates the function or functions
it would be open my eyes.
Also, maybe the proposed boost switch library would be some help:
http://svn.boost.org/svn/boost/sandbox/switch/
HTH.
-Larry
BTW, I've asked a somewhat similar question about used a
constant vector of function pointers and whether that would
be faster than a switch:
http://groups.google.com/group/comp.lang.c++.moderated/browse_thread/thread/364c0dd5ce512497#
The response was it wouldn't.
Re: GCC RM Q&A: August 5th
Mark Mitchell wrote: > As before, feel free to put questions that you would like to ask on this > Wiki page: I failed to include the URL. It is: http://gcc.gnu.org/wiki/Release%20Manager%20Q%26A Thanks, -- Mark Mitchell CodeSourcery m...@codesourcery.com (650) 331-3385 x713
RE: optimization question: mpl
> Generally without knowing the compiler version you are using
> it is hard to tell.
I'll use whatever's best. Right now I'm still on 4.4.3. I'll probably
upgrade soon to 4.5.
> The same is true without a complete compilable testcase.
I didn't want to make a test case that depends on boost::mpl. How's
this:
struct DecodeContext;
struct M1{
static const int id=1;
static void decode(DecodeContext& ){}
};
struct M2{
static const int id=2;
static void decode(DecodeContext& ){}
};
struct M3{
static const int id=3;
static void decode(DecodeContext& ){}
};
template struct ListMember;
template <> struct ListMember<1>{ typedef M1 type; };
template <> struct ListMember<2>{ typedef M2 type; };
template <> struct ListMember<3>{ typedef M3 type; };
template
void foo(int id, DecodeContext& dc) {
typedef typename ListMember::type M;
if(M::id==id)
M::decode(dc);
else
foo(id,dc);
}
template<>
void foo<0>(int id, DecodeContext& dc) {}
int main(){
DecodeContext& dc= *(DecodeContext*)0;// junk for now
int id=2; //sometime runtime dependent
foo<3>(id,dc);
return 0;
}
> You can use the flatten attribute to tell the compiler to inline all
> calls in a given function, like
>
> void __attribute__((flatten)) foo(void)
> {
> ...
> decode1();
> ...
> }
That would cause decode1() to be inlined, which might not be what you
want.
Hmm maybe I could rewrite things so the switch case returns a function
pointer. I'm guessing that would make things slower though.
Re: optimization question: mpl
On 07/28/10 10:53, Hite, Christopher wrote:
[snip]
struct DecodeContext;
struct M1{
static const int id=1;
static void decode(DecodeContext& ){}
};
struct M2{
static const int id=2;
static void decode(DecodeContext& ){}
};
struct M3{
static const int id=3;
static void decode(DecodeContext& ){}
};
template struct ListMember;
template <> struct ListMember<1>{ typedef M1 type; };
template <> struct ListMember<2>{ typedef M2 type; };
template <> struct ListMember<3>{ typedef M3 type; };
template
void foo(int id, DecodeContext& dc) {
typedef typename ListMember::type M;
if(M::id==id)
M::decode(dc);
else
foo(id,dc);
}
template<>
void foo<0>(int id, DecodeContext& dc) {}
int main(){
DecodeContext& dc= *(DecodeContext*)0;// junk for now
int id=2; //sometime runtime dependent
foo<3>(id,dc);
return 0;
}
[snip]
Wouldn't the following simplification work just as well?
template struct ListMember{
static void decode(DecodeContext& ){}
};
template
void foo(int id, DecodeContext& dc) {
if(i=id)
ListMember::decode(dc);
else
foo(id,dc);
}
Re: optimization question: mpl
Hi,
2010/7/28 Hite, Christopher :
>> Generally without knowing the compiler version you are using
>> it is hard to tell.
> I'll use whatever's best. Right now I'm still on 4.4.3. I'll probably
> upgrade soon to 4.5.
>
>> The same is true without a complete compilable testcase.
> I didn't want to make a test case that depends on boost::mpl. How's
> this:
>
> struct DecodeContext;
>
> struct M1{
> static const int id=1;
> static void decode(DecodeContext& ){}
> };
>
> struct M2{
> static const int id=2;
> static void decode(DecodeContext& ){}
> };
>
> struct M3{
> static const int id=3;
> static void decode(DecodeContext& ){}
> };
>
>
> template struct ListMember;
>
> template <> struct ListMember<1>{ typedef M1 type; };
> template <> struct ListMember<2>{ typedef M2 type; };
> template <> struct ListMember<3>{ typedef M3 type; };
>
> template
> void foo(int id, DecodeContext& dc) {
> typedef typename ListMember::type M;
> if(M::id==id)
> M::decode(dc);
> else
> foo(id,dc);
> }
>
> template<>
> void foo<0>(int id, DecodeContext& dc) {}
>
>
>
> int main(){
> DecodeContext& dc= *(DecodeContext*)0;// junk for now
> int id=2; //sometime runtime dependent
> foo<3>(id,dc);
> return 0;
> }
>
>
>> You can use the flatten attribute to tell the compiler to inline all
>> calls in a given function, like
>>
>> void __attribute__((flatten)) foo(void)
>> {
>> ...
>> decode1();
>> ...
>> }
>
> That would cause decode1() to be inlined, which might not be what you
> want.
>
> Hmm maybe I could rewrite things so the switch case returns a function
> pointer. I'm guessing that would make things slower though.
>
Or you could just initialize static array of pointers, like that
(please note, that I never compiled code below):
typedef void (*pfn) (DeclContext&);
tempate
struct InitDispatchHelper
{
static void init(std::tr1::array& a)
{
a[I-1] = ListMemeber::foo;
InitPointersHelper::init(a);
}
};
// End recursion
template<>
struct InitDispatchHelper
{
static void init(std::tr1::array& a)
{/*does nothing */ }
};
// Dispatch table;
template
struct DispatchFoo : std::tr1::array
{
DispatchFoo() : std::tr1::array()
{
InitDispatchHelper::init(*this);
}
};
then your call would look like:
static const int X = /* your maximal I in ListMembers meta-class */
void call_foo(int i, DeclContext& c)
{
static const DispatchFoo foo_dispatch;
foo_dispatch[i] (c);
}
Bonus points for benchmarking both solutions and making it policy
class choosing between those two solutions depending on X.
Good luck,
Piotr
Re: optimization question: mpl
On 07/28/10 13:16, Piotr Rak wrote: [snip] Or you could just initialize static array of pointers, like that (please note, that I never compiled code below): [snip] Piotr, something similar was proposed here: http://groups.google.com/group/comp.lang.c++.moderated/browse_thread/thread/364c0dd5ce512497# however, the response there indicates the code would be faster with a switch. I don't really understand why, especially if the array of pointers was a constexpr, but then I'm not compiler writer. -regards, Larry
Re: GFDL/GPL issues
On Tue, Jul 27, 2010 at 10:25 PM, Richard Guenther wrote: > Why not just ignore RMS and the license issues and simply do what we > think suits us and the project. Let the FSF deal with the legal consequences, > they put us in this messy situation, they deal with it. It seems to me that escalating the issue is more helpful. GCC is not the only project with this problem. Ciao! Steven
Re: GFDL/GPL issues
Steven Bosscher wrote: >> Why not just ignore RMS and the license issues and simply do what we >> think suits us and the project. Let the FSF deal with the legal >> consequences, >> they put us in this messy situation, they deal with it. > > It seems to me that escalating the issue is more helpful. GCC is not > the only project with this problem. Sadly, at this point, RMS is simply taking the position that this is not a problem worth solving. -- Mark Mitchell CodeSourcery m...@codesourcery.com (650) 331-3385 x713
Re: GFDL/GPL issues
On Wed, Jul 28, 2010 at 11:17 PM, Mark Mitchell wrote: > Steven Bosscher wrote: > >>> Why not just ignore RMS and the license issues and simply do what we >>> think suits us and the project. Let the FSF deal with the legal >>> consequences, >>> they put us in this messy situation, they deal with it. >> >> It seems to me that escalating the issue is more helpful. GCC is not >> the only project with this problem. > > Sadly, at this point, RMS is simply taking the position that this is not > a problem worth solving. Ah, how the "free" in Free Software Foundation takes a whole different meaning when it comes to actual freedom... Ciao! Steven
Re: GFDL/GPL issues
On Thu, Jul 29, 2010 at 12:08 AM, Steven Bosscher wrote: > On Wed, Jul 28, 2010 at 11:17 PM, Mark Mitchell wrote: >> Steven Bosscher wrote: >> Why not just ignore RMS and the license issues and simply do what we think suits us and the project. Let the FSF deal with the legal consequences, they put us in this messy situation, they deal with it. >>> >>> It seems to me that escalating the issue is more helpful. GCC is not >>> the only project with this problem. >> >> Sadly, at this point, RMS is simply taking the position that this is not >> a problem worth solving. > > Ah, how the "free" in Free Software Foundation takes a whole different > meaning when it comes to actual freedom... Ha! Sounds like time to overturn the (benevolent?) dictator! Richard.
