Partial inline on recursive functions?
Hi there,
I found the C++11 code below:
int Fib(int n) {
if (n <= 1) return n;
return [&] { return Fib(n-2) + Fib(n-1); }();
}
is ~2x faster than normal one:
int Fib(int n) {
if (n <= 1) return n;
return Fib(n-2) + Fib(n-1);
}
I tested them with "-std=c++11 -O3/-O2" using trunk and the first
version is ~2x (1.618x in theory?) faster. However, the first version
has larger binary size (101k compared to 3k, which is for the second
version). Clang produces 4k for the first version (with similar speed
improvement) though.
My guess is that the first `if (n <= 1) return n;` is easier to inline
into the caller side, since the returned expression is a call to a
separated function. It's translated to something like (ignoring
linkage difference):
int foo(int n);
int Fib(int n) {
if (n <= 1) {
return n;
}
return foo(n);
}
int foo(int n) {
return Fib(n-2) + Fib(n-1);
};
After inline optimizations, it's translated to:
int foo(int n);
int Fib(int n) {
if (n <= 1) {
return n;
}
return foo(n);
}
int foo(int n) {
return (n-2<=1) ? n-2 : foo(n-2) + (n-1<=1) ? n-1 : foo(n-1);
};
As a result, the maximum depth of the stack reduces by 1, since all
boundary checkings (if (n <= 1) return n;) are done by the caller
side, which may eliminate unnecessary function call overhead.
To me the optimization should be: For a given recursive function A,
split it into function B and C, so that A is equivalent to { B();
return C(); }, where B should be easy to inline (e.g. no recursive
calls) and C may not.
Is it possible/reasonable to do such an optimization? I hope it can help. :)
Thanks!
--
Regards,
Tim Shen
Re: [GSoC] Does this proposal look good?
Hmm...So finally we need partially compiled NFA(Because DFA is a special NFA, so can be embeded in an NFA)? That's worth trying. Anyway, I don't know much about it. Maybe I should read others code or just wirte a prototype first, if my proposal's accepted by GCC :) On Wed, Apr 24, 2013 at 6:56 PM, Florian Weimer wrote: > On 04/24/2013 12:45 PM, Tim Shen wrote: >> >> I'm very interested in implementing a NFA->DFA module(does that mean a >> Thompson automaton?) so that the exponential searching algorithm can >> be reduced to a linear state transition(though the states may be >> potentially exponential) loop. I can't understand how some language >> dare use a search algo as a final solution :) > > > DFA construction requires exponential space even for a fairly restricted > subset of regular expressions. The cache misses from large DFAs (which can > arise in practice, not just with maliciously crafted regular expressions) > often negate the wins from a simplified execution model. > > > -- > Florian Weimer / Red Hat Product Security Team -- Tim Shen
Re: [GSoC] Does this proposal look good?
I'm very interested in implementing a NFA->DFA module(does that mean a Thompson automaton?) so that the exponential searching algorithm can be reduced to a linear state transition(though the states may be potentially exponential) loop. I can't understand how some language dare use a search algo as a final solution :) On Wed, Apr 24, 2013 at 4:30 PM, Florian Weimer wrote: > On 04/23/2013 07:21 PM, Tim Shen wrote: >> >> I've made a proposal under the guide of application. Is it detailed >> and realistic? > > > Out of curiosity, do you plan to use a Thompson automaton where possible, or > just NFAs throughout? > > -- > Florian Weimer / Red Hat Product Security Team -- Tim Shen
[GSoC] Does this proposal look good?
I've made a proposal under the guide of application. Is it detailed and realistic? By the way, here is a naive version of my implementation of lookup_name in regex_traits : https://gist.github.com/innocentim/5445457 It's not GCC style but will be, if everything else's fine. So, am I in the right direction? Thanks! -- Tim Shen Completing C++11 regex * The Project This proposal aims to implement regex interfaces required by the C++11 standard as much as the student can. Besides, I get a clear status here(http://stackoverflow.com/questions/12530406/is-gcc4-7-buggy-about-regular-expressions) and here(http://gcc.gnu.org/bugzilla/show%5C_bug.cgi?id=53631) :) * Goal To finish: regex_traits format in match_results regex_iterator regex_token_iterator different styles in basic_regex * Time-line May 27 - June 30 Read basic regex and regex nfa, try submit small patches, get familiar with GCC workflow, coding and documenting style July 1 - July 7 Complete regex traits July 8 - July 14 Implement format in match results July 15 - July 21 Implement regex iterator July 22 - July 28 Implement regex token iterator July 29 - Aug 31 Implement different styles(basic, extended, awk, grep and egrep) Sep 1 - Sep 16 Undefined so far. Must have some ideas at that time. * Details ** regex_traits Not tough. However on how to implement transform_primary for all platform, I need to ask in the mail list or ask the mentor. ** Format string, iterators Shouldn't be tough. This is a deeper practicing. ** Different regex styles It's the core part. I should already know anything about basic_regex and regex_nfa(even have made changes, I'm very interested in algorithms of compiling to NFA/DFAs and executing approaches). Then get to know all flavors of regular expressions. My experiences of compilers may help.
Completing libstdc++ regex in GSoC
Hi there, I'm a student interested in GCC and want to make a proposal of completing regex in libstdc++. I've read include/bits/regex.h. As far as I can see, the implementation of regex_traits is partial because C++11(N3290) requires two specializations : regex_traits and regex_triats (28.3.5), which hasn't been implement yet. Since the GSoC application guide says "Starting with some small patch for the area you are interested in before the proposal submittal period can help (ask for guidance and a simple enough project)", is it fine for me to start my work at those two specializations? Thanks! -- Tim Shen
