Re: [boost] [proprocessor] PP challenge!

From: Tobias Schwinger (tschwinger_at_[hidden])
Date: 2006-11-07 19:53:33

David Abrahams wrote:
> Tobias Schwinger <tschwinger_at_[hidden]> writes:
> 
> 
>>Next fun challenge: build a tree instead:
> 
> Okay,
> 
> I'm sure this could be faster, and it does have "comma limitations",
> but I'm sure those could be overcome.
> 

Well then, (it was actually half a joke, but) time to attend to duty (:
I tried a different algorithm: Traversal of an imaginary, linearized tree.

It does not have the "comma limitation" but surprisingly (for me, at least) it runs awfully slow. I believe it's still worth a post and I'd be most thankful for a hint on what causes the poor performance.

Regards,

Tobias


#include <boost/preprocessor/arithmetic/add.hpp>
#include <boost/preprocessor/arithmetic/dec.hpp>
#include <boost/preprocessor/arithmetic/div.hpp>
#include <boost/preprocessor/arithmetic/inc.hpp>
#include <boost/preprocessor/arithmetic/mod.hpp>
#include <boost/preprocessor/arithmetic/mul.hpp>
#include <boost/preprocessor/comparison/greater.hpp>
#include <boost/preprocessor/comparison/equal.hpp>
#include <boost/preprocessor/selection/min.hpp>
#include <boost/preprocessor/logical/or.hpp>
#include <boost/preprocessor/repetition/for.hpp>
#include <boost/preprocessor/control/iif.hpp>
#include <boost/preprocessor/control/if.hpp>
#include <boost/preprocessor/tuple/eat.hpp>
#include <boost/preprocessor/tuple/elem.hpp>
#include <boost/preprocessor/tuple/rem.hpp>
#include <boost/preprocessor/facilities/expand.hpp>
#include <boost/preprocessor/facilities/empty.hpp>
#include <boost/preprocessor/punctuation/comma.hpp>

// operations on linearized 4ary (right-balanced) tree 

// number of branch nodes for 4-ary tree
#define N_INNER_NODES(n_leafes) BOOST_PP_DIV(BOOST_PP_INC(n_leafes),3)

// the last valid index for the linearized tree
#define I_MAX(n_leafes) \
    BOOST_PP_DEC(BOOST_PP_ADD(n_leafes,N_INNER_NODES(n_leafes)))

// index operations
#define FIRST_CHILD(i) BOOST_PP_INC(BOOST_PP_MUL(i,4))
#define LAST_CHILD(i,i_max) BOOST_PP_MIN(BOOST_PP_MUL(BOOST_PP_INC(i),4),i_max)
#define PARENT_NODE(i) BOOST_PP_DEC(BOOST_PP_DIV(BOOST_PP_ADD(i,3),4))

// node properties
#define IS_LEAF(i,i_max) BOOST_PP_GREATER(FIRST_CHILD(i),i_max)
#define IS_FIRST_CHILD(i) BOOST_PP_NOT(BOOST_PP_MOD(BOOST_PP_DEC(i),4))
#define IS_LAST_CHILD(i,i_max) BOOST_PP_OR(BOOST_PP_NOT(BOOST_PP_MOD(i,4)), \
                                  BOOST_PP_EQUAL(i,i_max))

// FSM for tree traversal (pre&post order)
//
// Using right-to-left traversal
// L,D,U and F abbreviate Left, Down, Up and Finish
//
//  state : condition | next
// =======:===========|======
//  * D   : leaf      |  L
//  * D   : ~         |  D     
//    L   : last_leaf |  U
//    L   : leaf      |  L
//    L   : ~         |  D
//    U   : last      |  U
//    U   : ~         |  L
//    U   : root      |  F
//  + F   : ~         |  F
//
// *  start state
// +  end state
// ~  any condition not explicitly specified

// move to rightmost child (push)
#define STP_D(i,i_max) (D) (LAST_CHILD(i,i_max),i_max)(i,i_max)
#define TRN_D(i,i_max) (BOOST_PP_IIF(IS_LEAF(i,i_max),L,D)) (i,i_max)

// move left (decrement index)
#define STP_L(i,i_max) (L) (BOOST_PP_DEC(i),i_max)
#define TRN_L(i,i_max) (BOOST_PP_IIF( IS_LEAF(i,i_max), \
                          BOOST_PP_IIF(IS_FIRST_CHILD(i),U,L),D)) (i,i_max)
// move up (pop)
#define STP_U(i,i_max) (U)
#define TRN_U(i,i_max) \
    (BOOST_PP_IIF(IS_FIRST_CHILD(i),BOOST_PP_IF(i,U,F),L)) (i,i_max)

// "traversal driver"
#define OP(r,for_state) OP_I(r, BOOST_PP_TUPLE_ELEM(2,0,for_state), \
      BOOST_PP_TUPLE_ELEM(2,1,for_state))

#define OP_I(r,cnt,stack) \
    ( BOOST_PP_IIF( BOOST_PP_EXPAND(IS_LEAF GET_POS(stack)),BOOST_PP_INC, \
          BOOST_PP_TUPLE_REM(1))(cnt) \
    , BOOST_PP_EXPAND(DO_TRN DO_STP stack) )

#define DO_TRN(state) TRN_ ## state
#define DO_STP(state) STP_ ## state

// state queries (is this the bottleneck?)
#define GET_STATE(stack) BOOST_PP_CAT(GET_STATE_I stack, _FIN) 
#define GET_POS(stack) BOOST_PP_CAT(GET_POS_I stack, _FIN)

#define GET_STATE_I(state) state BSEQ_EAT_I
#define GET_POS_I(state) BSEQ_HEAD_I
#define BSEQ_HEAD_I(a,b) (a,b) BSEQ_EAT_I
#define BSEQ_EAT_I(a,b) BSEQ_EAT_II
#define BSEQ_EAT_II(a,b) BSEQ_EAT_I
#define BSEQ_EAT_I_FIN
#define BSEQ_EAT_II_FIN

// termination
#define PRED(r,for_state) \
    BOOST_PP_CAT(CHK_CONT_,GET_STATE(BOOST_PP_TUPLE_ELEM(2,1,for_state)))

#define CHK_CONT_D 1 
#define CHK_CONT_L 1 
#define CHK_CONT_U 1 
#define CHK_CONT_F 0 

// code generation
#define CODEGEN_PRED(cnt,pos) CODEGEN_COMMA pos p ## cnt
#define CODEGEN_COMMA(i,i_max) \
    BOOST_PP_IIF(IS_LAST_CHILD(i,i_max),BOOST_PP_EMPTY,BOOST_PP_COMMA)()
#define CODEGEN_D(cnt,pos) CODEGEN_COMMA pos mpl::and_<  
#define CODEGEN_L(cnt,pos) \
    BOOST_PP_IIF(IS_LEAF pos,CODEGEN_PRED,BOOST_PP_TUPLE_EAT(2))(cnt,pos)

#define CODEGEN_U(cnt,pos) \
    BOOST_PP_IIF(IS_LEAF pos,CODEGEN_PRED,BOOST_PP_TUPLE_EAT(2))(cnt,pos) >
#define CODEGEN_F(cnt,pos) 

#define MACRO(r,for_state) MACRO_I(r, BOOST_PP_TUPLE_ELEM(2,0,for_state), \
    BOOST_PP_TUPLE_ELEM(2,1,for_state))
#define MACRO_I(r,cnt,stack) \
    BOOST_PP_CAT(CODEGEN_,GET_STATE(stack))(cnt, GET_POS(stack))

// put it all together
#define ALL(n) BOOST_PP_FOR( (0, (D) (0,I_MAX(n)) ),PRED,OP,MACRO)

// ALL(1) would need special treatment
ALL(2)
ALL(3)
ALL(4)
ALL(5)
ALL(6)
ALL(7)
ALL(8)
ALL(9)
ALL(10)
ALL(11)
ALL(12)
ALL(13)
ALL(14)
ALL(15)
ALL(16)
ALL(17)
ALL(18)
ALL(19)
ALL(20)
ALL(21)
ALL(22)
ALL(23)
ALL(24)
ALL(25)
ALL(26)
ALL(27)
ALL(28)
ALL(29)