Re: [boost] If boost::fusion is the hammer, then what's the nail?

17 Dec 2006

      "Joel de Guzman" <joel@boost-consulting.com> wrote in message 
news:elv64c$qao$1@sea.gmane.org...
...
Gennadiy Rozental wrote:
...
"David Abrahams" <dave@boost-consulting.com> wrote in message
news:87lkl93hlx.fsf@pereiro.luannocracy.com...
...
"Gennadiy Rozental" <gennadiy.rozental@thomson.com> writes:
...
This is not clear cut. I do not see in theory why any boost::variant
based
algorithm couldn't be optimized to almost the same code (module type
switching). On the other hand excessive usage of tuples will cause
appropriate code bloat, eventually leading to code slow down.
Not clear cut at all.  When operating on a sequence where all the
types are different, the version with variant will be both slower and
larger.
I love these performance "estimations"
Do you have any numbers to sustain this?
Yes. Dan posted some in my answer to your post in the fusion
review sometime ago. You must've missed it. Here it is again
(see attached). Here's the link to Dan's post:
http://tinyurl.com/yawqs3
You must've missed it.
I did not have resources at the time to analize your test.
...
We see speed differences as much as 20X. In addition to speed,
notice the variant size too.
It does indeed looks like the test in hand indicate that for the more or 
less trivial actors most (not all BTW) are able to optimize fusion version 
much better. Plus all the type switching and loop iteration is starting to 
play the role.

  But let's get to the problem at hand: output operation. I changed 
accumulator implementation in your test to still very trivial one like this:

struct accumulator {
    accumulator( std::ostream& os )
    : m_os( os ) {}

    template<typename T>
    void operator()(T const &t) const
    {
        this->m_os << t << ',';
    }

    std::ostream& m_os;
};

(and the rest of the test appropriately)

See attached files.

 When I used onullstream as ostream in test the fusion based version shows 
stable results of only 20% better performance advantage. onullstream does 
nothing whatsoever, just some virtual calls.
  When I used std::cerr instead, both fusion and boost::variant version show 
exactly the same performance (maybe 1-2% difference, but it depends on how 
long you run the test).
boost::variant based version used offline implementation of test routine and 
test executable size doesn't grow that much when number of calls increases
fusion based used inline implementation of test routine and test executable 
size grows faster.

So my concluding is that I may use either version for the task at hand. 
Actual decision will depend on other factors but performance. If I keep the 
values in vectors of variant anyway I obviously prefer variant based 
version. If I need to create these collection on a fly I may opt to stick 
with the fusion. There maybe some other reasoning.

Gennadiy

P.S. I am using my own acc_timer in the attached files. You could use any 
one of your own.

begin 666 b.cpp
M(V1E9FEN92!&55-)3TY?34%87U9%0U1/4E]325I%(#$V"@HC:6YC;'5D92 \
M:6]S=')E86T^"B-I;F-L=61E(#QA;&=O<FET:&T^"B-I;F-L=61E(#QV96-T
M;W(^"@HC:6YC;'5D92 \9FYD+V%C8U]T:6UE<BYH<' ^"@HC:6YC;'5D92 \
M8F]O<W0O9G5S:6]N+W-E<75E;F-E+FAP<#X*(VEN8VQU9&4@/&)O;W-T+V9U
M<VEO;B]A;&=O<FET:&TN:'!P/@H*;F%M97-P86-E('1E<W0@>PH*='EP961E
M9B!I;G0@("!4,#L*='EP961E9B!C:&%R("!4,3L*='EP961E9B!S:&]R="!4
M,CL*='EP961E9B!L;VYG("!4,SL*"FEN="!C," @/2 P.PII;G0@8S$@(#T@
M,3L*:6YT(&,R(" ](#(["FEN="!C,R @/2 S.PII;G0@8S0@(#T@-#L*:6YT
M(&,U(" ](#4["FEN="!C-B @/2 V.PII;G0@8S<@(#T@-SL*:6YT(&,X(" ]
M(#@["FEN="!C.2 @/2 Y.PII;G0@8S$P(#T@,3 ["FEN="!C,3$@/2 Q,3L*
M:6YT(&,Q,B ](#$R.PII;G0@8S$S(#T@,3,["FEN="!C,30@/2 Q-#L*:6YT
M(&,Q-2 ](#$U.PH*+R\M+2TM+2TM+2TM+2TM+2TM+2TM+2TM+2TM+2TM+2TM
M+2TM+2TM+2TM+2TM+2TM+2TO+PH*<W1R=6-T(&%C8W5M=6QA=&]R('L*(" @
M(&%C8W5M=6QA=&]R*"!S=&0Z.F]S=')E86TF(&]S("D*(" @(#H@;5]O<R@@
M;W,@*2![?0H*(" @('1E;7!L871E/'1Y<&5N86UE(%0^"B @("!V;VED(&]P
M97)A=&]R*"DH5"!C;VYS=" F="D@8V]N<W0*(" @('L*(" @(" @("!T:&ES
M+3YM7V]S(#P\('0@/#P@)RPG.PH@(" @?0H*(" @('-T9#HZ;W-T<F5A;28@
M;5]O<SL*?3L*"B\O+2TM+2TM+2TM+2TM+2TM+2TM+2TM+2TM+2TM+2TM+2TM
M+2TM+2TM+2TM+2TM+2TM+R\*"G1E;7!L871E/'1Y<&5N86UE(%0^"FEN;&EN
M92!V;VED"G1E<W1?<F]U=&EN92@@<W1D.CIO<W1R96%M)B!O<RP@5"!C;VYS
M="8@=B I"GL*(" @(&)O;W-T.CIF=7-I;VXZ.F9O<E]E86-H*"!V+"!A8V-U
M;75L871O<B@@;W,@*2 I.PI]"@HO+RTM+2TM+2TM+2TM+2TM+2TM+2TM+2TM
M+2TM+2TM+2TM+2TM+2TM+2TM+2TM+2TM+2\O"@IT96UP;&%T93QT>7!E;F%M
M92!4/@II;FQI;F4@9&]U8FQE"G1I;65?<F]U=&EN92@@5"!C;VYS="8@=B I
M"GL*(" @(&9N9#HZ86-C7W1I;65R('1I;65R.PH*(" @(&EN="!C;VYS=" @
M(%)%4$5!5%].54T@/2 S.PH@(" @:6YT(" @(" @(" @<F5P96%T<SL*"B @
M("!L;VYG(&QO;F<@("!I=&5R(" @(" @(#T@-# Y-CL*(" @(&QO;F<@;&]N
M9R @(&-O=6YT97(["@H@(" @9&\@>PH@(" @(" @(&ET97(@*CT@,CL*"B @
M(" @(" @=&EM97(N<W1A<G0H*3L*"B @(" @(" @9F]R*"!C;W5N=&5R(#T@
M,#L@8V]U;G1E<B \(&ET97([("LK8V]U;G1E<B I"B @(" @(" @(" @('1E
M<W1?<F]U=&EN92@@<W1D.CIC97)R+"!V("D["@H@(" @(" @('1I;65R+G-T
M;W H*3L*(" @('T@=VAI;&4H('1I;65R+F5L87!S961?;6MS*"D@/" U,# P
M,# P("D["@H@(" @;&]N9R!L;VYG(" @(" @96QA<'-E9%]T:6UE(#T@-3 P
M,# P,"HQ,#L*"B @(" O+R!R97!E870@=&5S="!A;F0@<F5P;W)T(&QE87-T
M('9A;'5E(&9O<B!C;VYS:7-T96YC>3H*(" @(&9O<B@@<F5P96%T<R ](# [
M(')E<&5A=',@/"!215!%051?3E5-.R K*W)E<&5A=',@*2!["@H@(" @(" @
M('1I;65R+G-T87)T*"D["@H@(" @(" @(&9O<B@@8V]U;G1E<B ](# [(&-O
M=6YT97(@/"!I=&5R.R K*V-O=6YT97(@*0H@(" @(" @(" @("!T97-T7W)O
M=71I;F4H('-T9#HZ8V5R<BP@=B I.PH*(" @(" @("!T:6UE<BYS=&]P*"D[
M"@H@(" @(" @(&5L87!S961?=&EM92 ]("AS=&0Z.FUI;BDH(&5L87!S961?
M=&EM92P@=&EM97(N96QA<'-E9%]M:W,H*2 I.PH@(" @?0H*(" @('-T9#HZ
M8V]U=" \/" B3G5M8F5R(&]F(&ET97)A=&EO;CH@(B \/"!I=&5R(#P\('-T
M9#HZ96YD;#L*"B @("!R971U<FX@*&1O=6)L92DH(&5L87!S961?=&EM92 J
M(#$P,# @+R!I=&5R("D@+R Q,# P.PI]"@HO+RTM+2TM+2TM+2TM+2TM+2TM
M+2TM+2TM+2TM+2TM+2TM+2TM+2TM+2TM+2TM+2TM+2\O"@II;G0@9&]?=&5S
M="@I"GL*(" @(&EN=" @(" @("!J(#T@,#L*(" @(&1O=6)L92 @("!T97-T
M7W1I;64["@H@(" @>PH@(" @(" @('1Y<&5D968@8F]O<W0Z.F9U<VEO;CHZ
M=F5C=&]R/%0P+%0Q+%0R+%0S/B!T97-T7W1Y<&4["B @(" @(" @=&5S=%]T
M>7!E('8H(&,P+&,Q+&,R+&,S("D["@H@(" @(" @('1E<W1?=&EM92 ]('1I
M;65?<F]U=&EN92@@=B I.PH*(" @(" @("!S=&0Z.F-O=70@/#P@(E1E<W0@
M=F5C=&]R('-I>F4Z("(@/#P@<VEZ96]F*'1E<W1?='EP92D@/#P@<W1D.CIE
M;F1L.PH@(" @(" @('-T9#HZ8V]U=" \/" B5&5S="!T:6UE.B B(#P\('1E
M<W1?=&EM92 \/"!S=&0Z.F5N9&P["B @(" @(" @<W1D.CIC;W5T(#P\(")4
M97-T(')E<W5L=#H@(B \/"!J(#P\('-T9#HZ96YD;#L*(" @('T*(" @('L*
M(" @(" @("!T>7!E9&5F(&)O;W-T.CIF=7-I;VXZ.G9E8W1O<CQ4,"Q4,2Q4
M,BQ4,RQ4,#X@=&5S=%]T>7!E.PH@(" @(" @('1E<W1?='EP92!V*"!C,"QC
M,2QC,BQC,RQC-" I.PH*(" @(" @("!T97-T7W1I;64@/2!T:6UE7W)O=71I
M;F4H('8@*3L*"B @(" @(" @<W1D.CIC;W5T(#P\(")497-T('9E8W1O<B!S
M:7IE.B B(#P\('-I>F5O9BAT97-T7W1Y<&4I(#P\('-T9#HZ96YD;#L*(" @
M(" @("!S=&0Z.F-O=70@/#P@(E1E<W0@=&EM93H@(B \/"!T97-T7W1I;64@
M/#P@<W1D.CIE;F1L.PH@(" @(" @('-T9#HZ8V]U=" \/" B5&5S="!R97-U
M;'0Z("(@/#P@:B \/"!S=&0Z.F5N9&P["B @("!]"B @("!["B @(" @(" @
M='EP961E9B!B;V]S=#HZ9G5S:6]N.CIV96-T;W(\5# L5#$L5#(L5#,L5# L
M5#$^('1E<W1?='EP93L*(" @(" @("!T97-T7W1Y<&4@=B@@8S L8S$L8S(L
M8S,L8S0L8S4@*3L*"B @(" @(" @=&5S=%]T:6UE(#T@=&EM95]R;W5T:6YE
M*"!V("D["@H@(" @(" @('-T9#HZ8V]U=" \/" B5&5S="!V96-T;W(@<VEZ
M93H@(B \/"!S:7IE;V8H=&5S=%]T>7!E*2 \/"!S=&0Z.F5N9&P["B @(" @
M(" @<W1D.CIC;W5T(#P\(")497-T('1I;64Z("(@/#P@=&5S=%]T:6UE(#P\
M('-T9#HZ96YD;#L*(" @(" @("!S=&0Z.F-O=70@/#P@(E1E<W0@<F5S=6QT
M.B B(#P\(&H@/#P@<W1D.CIE;F1L.PH@(" @?0H@(" @>PH@(" @(" @('1Y
M<&5D968@8F]O<W0Z.F9U<VEO;CHZ=F5C=&]R/%0P+%0Q+%0R+%0S+%0P+%0Q
M+%0R/B!T97-T7W1Y<&4["B @(" @(" @=&5S=%]T>7!E('8H(&,P+&,Q+&,R
M+&,S+&,T+&,U+&,V("D["@H@(" @(" @('1E<W1?=&EM92 ]('1I;65?<F]U
M=&EN92@@=B I.PH*(" @(" @("!S=&0Z.F-O=70@/#P@(E1E<W0@=F5C=&]R
M('-I>F4Z("(@/#P@<VEZ96]F*'1E<W1?='EP92D@/#P@<W1D.CIE;F1L.PH@
M(" @(" @('-T9#HZ8V]U=" \/" B5&5S="!T:6UE.B B(#P\('1E<W1?=&EM
M92 \/"!S=&0Z.F5N9&P["B @(" @(" @<W1D.CIC;W5T(#P\(")497-T(')E
M<W5L=#H@(B \/"!J(#P\('-T9#HZ96YD;#L*(" @('T*(" @('L*(" @(" @
M("!T>7!E9&5F(&)O;W-T.CIF=7-I;VXZ.G9E8W1O<CQ4,"Q4,2Q4,BQ4,RQ4
M,"Q4,2Q4,BQ4,SX@=&5S=%]T>7!E.PH@(" @(" @('1E<W1?='EP92!V*"!C
M,"QC,2QC,BQC,RQC-"QC-2QC-BQC-R I.PH*(" @(" @("!T97-T7W1I;64@
M/2!T:6UE7W)O=71I;F4H('8@*3L*"B @(" @(" @<W1D.CIC;W5T(#P\(")4
M97-T('9E8W1O<B!S:7IE.B B(#P\('-I>F5O9BAT97-T7W1Y<&4I(#P\('-T
M9#HZ96YD;#L*(" @(" @("!S=&0Z.F-O=70@/#P@(E1E<W0@=&EM93H@(B \
M/"!T97-T7W1I;64@/#P@<W1D.CIE;F1L.PH@(" @(" @('-T9#HZ8V]U=" \
M/" B5&5S="!R97-U;'0Z("(@/#P@:B \/"!S=&0Z.F5N9&P["B @("!]"B @
M("!["B @(" @(" @='EP961E9B!B;V]S=#HZ9G5S:6]N.CIV96-T;W(\5# L
M5#$L5#(L5#,L5# L5#$L5#(L5#,L5# ^('1E<W1?='EP93L*(" @(" @("!T
M97-T7W1Y<&4@=B@@8S L8S$L8S(L8S,L8S0L8S4L8S8L8S<L8S@@*3L*"B @
M(" @(" @=&5S=%]T:6UE(#T@=&EM95]R;W5T:6YE*"!V("D["@H@(" @(" @
M('-T9#HZ8V]U=" \/" B5&5S="!V96-T;W(@<VEZ93H@(B \/"!S:7IE;V8H
M=&5S=%]T>7!E*2 \/"!S=&0Z.F5N9&P["B @(" @(" @<W1D.CIC;W5T(#P\
M(")497-T('1I;64Z("(@/#P@=&5S=%]T:6UE(#P\('-T9#HZ96YD;#L*(" @
M(" @("!S=&0Z.F-O=70@/#P@(E1E<W0@<F5S=6QT.B B(#P\(&H@/#P@<W1D
M.CIE;F1L.PH@(" @?0H@(" @>PH@(" @(" @('1Y<&5D968@8F]O<W0Z.F9U
M<VEO;CHZ=F5C=&]R/%0P+%0Q+%0R+%0S+%0P+%0Q+%0R+%0S+%0P+%0Q/B!T
M97-T7W1Y<&4["B @(" @(" @=&5S=%]T>7!E('8H(&,P+&,Q+&,R+&,S+&,T
M+&,U+&,V+&,W+&,X+&,Y("D["@H@(" @(" @('1E<W1?=&EM92 ]('1I;65?
M<F]U=&EN92@@=B I.PH*(" @(" @("!S=&0Z.F-O=70@/#P@(E1E<W0@=F5C
M=&]R('-I>F4Z("(@/#P@<VEZ96]F*'1E<W1?='EP92D@/#P@<W1D.CIE;F1L
M.PH@(" @(" @('-T9#HZ8V]U=" \/" B5&5S="!T:6UE.B B(#P\('1E<W1?
M=&EM92 \/"!S=&0Z.F5N9&P["B @(" @(" @<W1D.CIC;W5T(#P\(")497-T
M(')E<W5L=#H@(B \/"!J(#P\('-T9#HZ96YD;#L*(" @('T*(" @('L*(" @
M(" @("!T>7!E9&5F(&)O;W-T.CIF=7-I;VXZ.G9E8W1O<CQ4,"Q4,2Q4,BQ4
M,RQ4,"Q4,2Q4,BQ4,RQ4,"Q4,2Q4,CX@=&5S=%]T>7!E.PH@(" @(" @('1E
M<W1?='EP92!V*"!C,"QC,2QC,BQC,RQC-"QC-2QC-BQC-RQC."QC.2QC,3 @
M*3L*"B @(" @(" @=&5S=%]T:6UE(#T@=&EM95]R;W5T:6YE*"!V("D["@H@
M(" @(" @('-T9#HZ8V]U=" \/" B5&5S="!V96-T;W(@<VEZ93H@(B \/"!S
M:7IE;V8H=&5S=%]T>7!E*2 \/"!S=&0Z.F5N9&P["B @(" @(" @<W1D.CIC
M;W5T(#P\(")497-T('1I;64Z("(@/#P@=&5S=%]T:6UE(#P\('-T9#HZ96YD
M;#L*(" @(" @("!S=&0Z.F-O=70@/#P@(E1E<W0@<F5S=6QT.B B(#P\(&H@
M/#P@<W1D.CIE;F1L.PH@(" @?0H@(" @>PH@(" @(" @('1Y<&5D968@8F]O
M<W0Z.F9U<VEO;CHZ=F5C=&]R/%0P+%0Q+%0R+%0S+%0P+%0Q+%0R+%0S+%0P
M+%0Q+%0R+%0S/B!T97-T7W1Y<&4["B @(" @(" @=&5S=%]T>7!E('8H(&,P
M+&,Q+&,R+&,S+&,T+&,U+&,V+&,W+&,X+&,Y+&,Q,"QC,3$@*3L*"B @(" @
M(" @=&5S=%]T:6UE(#T@=&EM95]R;W5T:6YE*"!V("D["@H@(" @(" @('-T
M9#HZ8V]U=" \/" B5&5S="!V96-T;W(@<VEZ93H@(B \/"!S:7IE;V8H=&5S
M=%]T>7!E*2 \/"!S=&0Z.F5N9&P["B @(" @(" @<W1D.CIC;W5T(#P\(")4
M97-T('1I;64Z("(@/#P@=&5S=%]T:6UE(#P\('-T9#HZ96YD;#L*(" @(" @
M("!S=&0Z.F-O=70@/#P@(E1E<W0@<F5S=6QT.B B(#P\(&H@/#P@<W1D.CIE
M;F1L.PH@(" @?0H@(" @>PH@(" @(" @('1Y<&5D968@8F]O<W0Z.F9U<VEO
M;CHZ=F5C=&]R/%0P+%0Q+%0R+%0S+%0P+%0Q+%0R+%0S+%0P+%0Q+%0R+%0S
M+%0P/B!T97-T7W1Y<&4["B @(" @(" @=&5S=%]T>7!E('8H(&,P+&,Q+&,R
M+&,S+&,T+&,U+&,V+&,W+&,X+&,Y+&,Q,"QC,3$L8S$R("D["@H@(" @(" @
M('1E<W1?=&EM92 ]('1I;65?<F]U=&EN92@@=B I.PH*(" @(" @("!S=&0Z
M.F-O=70@/#P@(E1E<W0@=F5C=&]R('-I>F4Z("(@/#P@<VEZ96]F*'1E<W1?
M='EP92D@/#P@<W1D.CIE;F1L.PH@(" @(" @('-T9#HZ8V]U=" \/" B5&5S
M="!T:6UE.B B(#P\('1E<W1?=&EM92 \/"!S=&0Z.F5N9&P["B @(" @(" @
M<W1D.CIC;W5T(#P\(")497-T(')E<W5L=#H@(B \/"!J(#P\('-T9#HZ96YD
M;#L*(" @('T*(" @('L*(" @(" @("!T>7!E9&5F(&)O;W-T.CIF=7-I;VXZ
M.G9E8W1O<CQ4,"Q4,2Q4,BQ4,RQ4,"Q4,2Q4,BQ4,RQ4,"Q4,2Q4,BQ4,RQ4
M,"Q4,3X@=&5S=%]T>7!E.PH@(" @(" @('1E<W1?='EP92!V*"!C,"QC,2QC
M,BQC,RQC-"QC-2QC-BQC-RQC."QC.2QC,3 L8S$Q+&,Q,BQC,3,@*3L*"B @
M(" @(" @=&5S=%]T:6UE(#T@=&EM95]R;W5T:6YE*"!V("D["@H@(" @(" @
M('-T9#HZ8V]U=" \/" B5&5S="!V96-T;W(@<VEZ93H@(B \/"!S:7IE;V8H
M=&5S=%]T>7!E*2 \/"!S=&0Z.F5N9&P["B @(" @(" @<W1D.CIC;W5T(#P\
M(")497-T('1I;64Z("(@/#P@=&5S=%]T:6UE(#P\('-T9#HZ96YD;#L*(" @
M(" @("!S=&0Z.F-O=70@/#P@(E1E<W0@<F5S=6QT.B B(#P\(&H@/#P@<W1D
M.CIE;F1L.PH@(" @?0H@(" @>PH@(" @(" @('1Y<&5D968@8F]O<W0Z.F9U
M<VEO;CHZ=F5C=&]R/%0P+%0Q+%0R+%0S+%0P+%0Q+%0R+%0S+%0P+%0Q+%0R
M+%0S+%0P+%0Q+%0R/B!T97-T7W1Y<&4["B @(" @(" @=&5S=%]T>7!E('8H
M(&,P+&,Q+&,R+&,S+&,T+&,U+&,V+&,W+&,X+&,Y+&,Q,"QC,3$L8S$R+&,Q
M,RQC,30@*3L*"B @(" @(" @=&5S=%]T:6UE(#T@=&EM95]R;W5T:6YE*"!V
M("D["@H@(" @(" @('-T9#HZ8V]U=" \/" B5&5S="!V96-T;W(@<VEZ93H@
M(B \/"!S:7IE;V8H=&5S=%]T>7!E*2 \/"!S=&0Z.F5N9&P["B @(" @(" @
M<W1D.CIC;W5T(#P\(")497-T('1I;64Z("(@/#P@=&5S=%]T:6UE(#P\('-T
M9#HZ96YD;#L*(" @(" @("!S=&0Z.F-O=70@/#P@(E1E<W0@<F5S=6QT.B B
M(#P\(&H@/#P@<W1D.CIE;F1L.PH@(" @?0H@(" @>PH@(" @(" @('1Y<&5D
M968@8F]O<W0Z.F9U<VEO;CHZ=F5C=&]R/%0P+%0Q+%0R+%0S+%0P+%0Q+%0R
M+%0S+%0P+%0Q+%0R+%0S+%0P+%0Q+%0R+%0S/B!T97-T7W1Y<&4["B @(" @
M(" @=&5S=%]T>7!E('8H(&,P+&,Q+&,R+&,S+&,T+&,U+&,V+&,W+&,X+&,Y
M+&,Q,"QC,3$L8S$R+&,Q,RQC,30L8S$U("D["@H@(" @(" @('1E<W1?=&EM
M92 ]('1I;65?<F]U=&EN92@@=B I.PH*(" @(" @("!S=&0Z.F-O=70@/#P@
M(E1E<W0@=F5C=&]R('-I>F4Z("(@/#P@<VEZ96]F*'1E<W1?='EP92D@/#P@
M<W1D.CIE;F1L.PH@(" @(" @('-T9#HZ8V]U=" \/" B5&5S="!T:6UE.B B
M(#P\('1E<W1?=&EM92 \/"!S=&0Z.F5N9&P["B @(" @(" @<W1D.CIC;W5T
M(#P\(")497-T(')E<W5L=#H@(B \/"!J(#P\('-T9#HZ96YD;#L*(" @('T*
M"B @("!R971U<FX@:CL*?0H*+R\M+2TM+2TM+2TM+2TM+2TM+2TM+2TM+2TM
M+2TM+2TM+2TM+2TM+2TM+2TM+2TM+2TO+PH*?0H*:6YT"FUA:6XH*0I["B @
<("!R971U<FX@=&5S=#HZ9&]?=&5S="@I.PI]"@``
`
end

begin 666 a.cpp
M(VEN8VQU9&4@/&EO<W1R96%M/@HC:6YC;'5D92 \86QG;W)I=&AM/@HC:6YC
M;'5D92 \=F5C=&]R/@H*(VEN8VQU9&4@/&9N9"]A8V-?=&EM97(N:'!P/@HC
M:6YC;'5D92 \8F]O<W0O=F%R:6%N="YH<' ^"@IN86UE<W!A8V4@=&5S="![
M"@IT>7!E9&5F(&EN=" @(%0P.PIT>7!E9&5F(&-H87(@(%0Q.PIT>7!E9&5F
M('-H;W)T(%0R.PIT>7!E9&5F(&QO;F<@(%0S.PH*='EP961E9B!B;V]S=#HZ
M=F%R:6%N=#Q4,"Q4,2Q4,BQ4,SX@=F%R:6%N=%]T>7!E.PIT>7!E9&5F('-T
M9#HZ=F5C=&]R/'9A<FEA;G1?='EP93X@("!T97-T7W1Y<&4["@HO+RTM+2TM
M+2TM+2TM+2TM+2TM+2TM+2TM+2TM+2TM+2TM+2TM+2TM+2TM+2TM+2TM+2\O
M"@IS=')U8W0@86-C=6UU;&%T;W(@.B!B;V]S=#HZ<W1A=&EC7W9I<VET;W(\
M/B!["B @("!A8V-U;75L871O<B@@<W1D.CIO<W1R96%M)B!O<R I"B @(" Z
M(&U?;W,H(&]S("D@>WT*"B @("!T96UP;&%T93QT>7!E;F%M92!4/@H@(" @
M=F]I9"!O<&5R871O<B@I*%0@8V]N<W0@)G0I(&-O;G-T"B @("!["B @(" @
M(" @=&AI<RT^;5]O<R \/"!T(#P\("<L)SL*(" @('T*"B @("!S=&0Z.F]S
M=')E86TF(&U?;W,["GT["@HO+RTM+2TM+2TM+2TM+2TM+2TM+2TM+2TM+2TM
M+2TM+2TM+2TM+2TM+2TM+2TM+2TM+2\O"@IS=')U8W0@=F%R:6%N=%]A8V-U
M;75L871O<B![(" @( H@(" @=F%R:6%N=%]A8V-U;75L871O<B@@<W1D.CIO
M<W1R96%M)B!O<R I"B @(" Z(&U?;W,H(&]S("D@>WT*"B @("!V;VED(&]P
M97)A=&]R*"DH('9A<FEA;G1?='EP92!C;VYS="8@=BD@8V]N<W0*(" @('L*
M(" @(" @("!B;V]S=#HZ87!P;'E?=FES:71O<B@@86-C=6UU;&%T;W(H(&U?
M;W,@*2P@=B I.PH@(" @?0H*(" @('-T9#HZ;W-T<F5A;28@;5]O<SL*?3L*
M"B\O+2TM+2TM+2TM+2TM+2TM+2TM+2TM+2TM+2TM+2TM+2TM+2TM+2TM+2TM
M+2TM+2TM+R\*"G9O:60@=&5S=%]R;W5T:6YE*"!S=&0Z.F]S=')E86TF(&]S
M+"!T97-T7W1Y<&4@8V]N<W0F('8@*3L*"B\O+2TM+2TM+2TM+2TM+2TM+2TM
M+2TM+2TM+2TM+2TM+2TM+2TM+2TM+2TM+2TM+2TM+R\*"FEN;&EN92!D;W5B
M;&4*=&EM95]R;W5T:6YE*"!T97-T7W1Y<&4@8V]N<W0F('8@*0I["B @("!F
M;F0Z.F%C8U]T:6UE<B!T:6UE<CL*"B @("!I;G0@8V]N<W0@("!215!%051?
M3E5-(#T@,SL*(" @(&EN=" @(" @(" @(')E<&5A=',["@H@(" @;&]N9R!L
M;VYG(" @:71E<B @(" @(" ](#0P.38["B @("!L;VYG(&QO;F<@("!C;W5N
M=&5R.PH*(" @(&1O('L*(" @(" @("!I=&5R("H](#(["@H@(" @(" @('1I
M;65R+G-T87)T*"D["@H@(" @(" @(&9O<B@@8V]U;G1E<B ](# [(&-O=6YT
M97(@/"!I=&5R.R K*V-O=6YT97(@*0H@(" @(" @(" @("!T97-T7W)O=71I
M;F4H('-T9#HZ8V5R<BP@=B I.PH*(" @(" @("!T:6UE<BYS=&]P*"D["B @
M("!]('=H:6QE*"!T:6UE<BYE;&%P<V5D7VUK<R@I(#P@-3 P,# P," I.PH*
M(" @(&QO;F<@;&]N9R @(" @(&5L87!S961?=&EM92 ](#4P,# P,# J,3 [
M"@H@(" @+R\@<F5P96%T('1E<W0@86YD(')E<&]R="!L96%S="!V86QU92!F
M;W(@8V]N<VES=&5N8WDZ"B @("!F;W(H(')E<&5A=',@/2 P.R!R97!E871S
M(#P@4D5014%47TY533L@*RMR97!E871S("D@>PH*(" @(" @("!T:6UE<BYS
M=&%R="@I.PH*(" @(" @("!F;W(H(&-O=6YT97(@/2 P.R!C;W5N=&5R(#P@
M:71E<CL@*RMC;W5N=&5R("D*(" @(" @(" @(" @=&5S=%]R;W5T:6YE*"!S
M=&0Z.F-E<G(L('8@*3L*"B @(" @(" @=&EM97(N<W1O<"@I.PH*(" @(" @
M("!E;&%P<V5D7W1I;64@/2 H<W1D.CIM:6XI*"!E;&%P<V5D7W1I;64L('1I
M;65R+F5L87!S961?;6MS*"D@*3L*(" @('T*"B @("!S=&0Z.F-O=70@/#P@
M(DYU;6)E<B!O9B!I=&5R871I;VXZ("(@/#P@:71E<B \/"!S=&0Z.F5N9&P[
M"@H@(" @<F5T=7)N("AD;W5B;&4I*"!E;&%P<V5D7W1I;64@*B Q,# P("\@
M:71E<B I("\@,3 P,#L*?0H*+R\M+2TM+2TM+2TM+2TM+2TM+2TM+2TM+2TM
M+2TM+2TM+2TM+2TM+2TM+2TM+2TM+2TO+PH*:6YT(&1O7W1E<W0H*0I["B @
M("!I;G0@(" @(" @:B ](# ["B @("!I;G0@(" @(" @;B ](#0["B @("!T
M97-T7W1Y<&4@=CL*(" @(&1O=6)L92 @("!T97-T7W1I;64["@H@(" @=BYP
M=7-H7V)A8VLH*%0P*3 I.PH@(" @=BYP=7-H7V)A8VLH*%0Q*3$I.PH@(" @
M=BYP=7-H7V)A8VLH*%0R*3(I.PH@(" @=BYP=7-H7V)A8VLH*%0S*3,I.PH*
M(" @('1E<W1?=&EM92 ]('1I;65?<F]U=&EN92@@=B I.PH*(" @('-T9#HZ
M8V]U=" \/" B5&5S="!V96-T;W(@<VEZ92 H:6YC;'5D97,@=F5C=&]R('-I
M>F4@*R!D871A*2 Z("(@"B @(" @(" @(" @(" @/#P@*'-I>F5O9BAV87)I
M86YT7W1Y<&4I*FXI*W-I>F5O9BAT97-T7W1Y<&4I(" @/#P@<W1D.CIE;F1L
M.PH*(" @('-T9#HZ8V]U=" \/" B5&5S="!T:6UE.B B(#P\('1E<W1?=&EM
M92 \/"!S=&0Z.F5N9&P["B @("!S=&0Z.F-O=70@/#P@(E1E<W0@<F5S=6QT
M.B B(#P\(&H@/#P@<W1D.CIE;F1L.PH*(" @('8N<'5S:%]B86-K*&XK*RD[
M"@H@(" @+R\M+2TM+2TM+2TM+2TM+2TM+2TM+2TM+2TM+2TO+PH*(" @('1E
M<W1?=&EM92 ]('1I;65?<F]U=&EN92@@=B I.PH*(" @('-T9#HZ8V]U=" \
M/" B5&5S="!V96-T;W(@<VEZ92 H:6YC;'5D97,@=F5C=&]R('-I>F4@*R!D
M871A*2 Z("(@"B @(" @(" @(" @(" @/#P@*'-I>F5O9BAV87)I86YT7W1Y
M<&4I*FXI*W-I>F5O9BAT97-T7W1Y<&4I(" @/#P@<W1D.CIE;F1L.PH*(" @
M('-T9#HZ8V]U=" \/" B5&5S="!T:6UE.B B(#P\('1E<W1?=&EM92 \/"!S
M=&0Z.F5N9&P["B @("!S=&0Z.F-O=70@/#P@(E1E<W0@<F5S=6QT.B B(#P\
M(&H@/#P@<W1D.CIE;F1L.PH*(" @('8N<'5S:%]B86-K*&XK*RD["@H@(" @
M+R\M+2TM+2TM+2TM+2TM+2TM+2TM+2TM+2TM+2TO+PH*(" @('1E<W1?=&EM
M92 ]('1I;65?<F]U=&EN92@@=B I.PH*(" @('-T9#HZ8V]U=" \/" B5&5S
M="!V96-T;W(@<VEZ92 H:6YC;'5D97,@=F5C=&]R('-I>F4@*R!D871A*2 Z
M("(@"B @(" @(" @(" @(" @/#P@*'-I>F5O9BAV87)I86YT7W1Y<&4I*FXI
M*W-I>F5O9BAT97-T7W1Y<&4I(" @/#P@<W1D.CIE;F1L.PH*(" @('-T9#HZ
M8V]U=" \/" B5&5S="!T:6UE.B B(#P\('1E<W1?=&EM92 \/"!S=&0Z.F5N
M9&P["B @("!S=&0Z.F-O=70@/#P@(E1E<W0@<F5S=6QT.B B(#P\(&H@/#P@
M<W1D.CIE;F1L.PH*(" @('8N<'5S:%]B86-K*&XK*RD["@H@(" @+R\M+2TM
M+2TM+2TM+2TM+2TM+2TM+2TM+2TM+2TO+PH*(" @('1E<W1?=&EM92 ]('1I
M;65?<F]U=&EN92@@=B I.PH*(" @('-T9#HZ8V]U=" \/" B5&5S="!V96-T
M;W(@<VEZ92 H:6YC;'5D97,@=F5C=&]R('-I>F4@*R!D871A*2 Z("(@"B @
M(" @(" @(" @(" @/#P@*'-I>F5O9BAV87)I86YT7W1Y<&4I*FXI*W-I>F5O
M9BAT97-T7W1Y<&4I(" @/#P@<W1D.CIE;F1L.PH*(" @('-T9#HZ8V]U=" \
M/" B5&5S="!T:6UE.B B(#P\('1E<W1?=&EM92 \/"!S=&0Z.F5N9&P["B @
M("!S=&0Z.F-O=70@/#P@(E1E<W0@<F5S=6QT.B B(#P\(&H@/#P@<W1D.CIE
M;F1L.PH*(" @('8N<'5S:%]B86-K*&XK*RD["@H@(" @+R\M+2TM+2TM+2TM
M+2TM+2TM+2TM+2TM+2TM+2TO+PH*(" @('1E<W1?=&EM92 ]('1I;65?<F]U
M=&EN92@@=B I.PH*(" @('-T9#HZ8V]U=" \/" B5&5S="!V96-T;W(@<VEZ
M92 H:6YC;'5D97,@=F5C=&]R('-I>F4@*R!D871A*2 Z("(@"B @(" @(" @
M(" @(" @/#P@*'-I>F5O9BAV87)I86YT7W1Y<&4I*FXI*W-I>F5O9BAT97-T
M7W1Y<&4I(" @/#P@<W1D.CIE;F1L.PH*(" @('-T9#HZ8V]U=" \/" B5&5S
M="!T:6UE.B B(#P\('1E<W1?=&EM92 \/"!S=&0Z.F5N9&P["B @("!S=&0Z
M.F-O=70@/#P@(E1E<W0@<F5S=6QT.B B(#P\(&H@/#P@<W1D.CIE;F1L.PH*
M(" @('8N<'5S:%]B86-K*&XK*RD["@H@(" @+R\M+2TM+2TM+2TM+2TM+2TM
M+2TM+2TM+2TM+2TO+PH*(" @('1E<W1?=&EM92 ]('1I;65?<F]U=&EN92@@
M=B I.PH*(" @('-T9#HZ8V]U=" \/" B5&5S="!V96-T;W(@<VEZ92 H:6YC
M;'5D97,@=F5C=&]R('-I>F4@*R!D871A*2 Z("(@"B @(" @(" @(" @(" @
M/#P@*'-I>F5O9BAV87)I86YT7W1Y<&4I*FXI*W-I>F5O9BAT97-T7W1Y<&4I
M(" @/#P@<W1D.CIE;F1L.PH*(" @('-T9#HZ8V]U=" \/" B5&5S="!T:6UE
M.B B(#P\('1E<W1?=&EM92 \/"!S=&0Z.F5N9&P["B @("!S=&0Z.F-O=70@
M/#P@(E1E<W0@<F5S=6QT.B B(#P\(&H@/#P@<W1D.CIE;F1L.PH*(" @('8N
M<'5S:%]B86-K*&XK*RD["@H@(" @+R\M+2TM+2TM+2TM+2TM+2TM+2TM+2TM
M+2TM+2TO+PH*(" @('1E<W1?=&EM92 ]('1I;65?<F]U=&EN92@@=B I.PH*
M(" @('-T9#HZ8V]U=" \/" B5&5S="!V96-T;W(@<VEZ92 H:6YC;'5D97,@
M=F5C=&]R('-I>F4@*R!D871A*2 Z("(@"B @(" @(" @(" @(" @/#P@*'-I
M>F5O9BAV87)I86YT7W1Y<&4I*FXI*W-I>F5O9BAT97-T7W1Y<&4I(" @/#P@
M<W1D.CIE;F1L.PH*(" @('-T9#HZ8V]U=" \/" B5&5S="!T:6UE.B B(#P\
M('1E<W1?=&EM92 \/"!S=&0Z.F5N9&P["B @("!S=&0Z.F-O=70@/#P@(E1E
M<W0@<F5S=6QT.B B(#P\(&H@/#P@<W1D.CIE;F1L.PH*(" @('8N<'5S:%]B
M86-K*&XK*RD["@H@(" @+R\M+2TM+2TM+2TM+2TM+2TM+2TM+2TM+2TM+2TO
M+PH*(" @('1E<W1?=&EM92 ]('1I;65?<F]U=&EN92@@=B I.PH*(" @('-T
M9#HZ8V]U=" \/" B5&5S="!V96-T;W(@<VEZ92 H:6YC;'5D97,@=F5C=&]R
M('-I>F4@*R!D871A*2 Z("(@"B @(" @(" @(" @(" @/#P@*'-I>F5O9BAV
M87)I86YT7W1Y<&4I*FXI*W-I>F5O9BAT97-T7W1Y<&4I(" @/#P@<W1D.CIE
M;F1L.PH*(" @('-T9#HZ8V]U=" \/" B5&5S="!T:6UE.B B(#P\('1E<W1?
M=&EM92 \/"!S=&0Z.F5N9&P["B @("!S=&0Z.F-O=70@/#P@(E1E<W0@<F5S
M=6QT.B B(#P\(&H@/#P@<W1D.CIE;F1L.PH*(" @('8N<'5S:%]B86-K*&XK
M*RD["@H@(" @+R\M+2TM+2TM+2TM+2TM+2TM+2TM+2TM+2TM+2TO+PH*(" @
M('1E<W1?=&EM92 ]('1I;65?<F]U=&EN92@@=B I.PH*(" @('-T9#HZ8V]U
M=" \/" B5&5S="!V96-T;W(@<VEZ92 H:6YC;'5D97,@=F5C=&]R('-I>F4@
M*R!D871A*2 Z("(@"B @(" @(" @(" @(" @/#P@*'-I>F5O9BAV87)I86YT
M7W1Y<&4I*FXI*W-I>F5O9BAT97-T7W1Y<&4I(" @/#P@<W1D.CIE;F1L.PH*
M(" @('-T9#HZ8V]U=" \/" B5&5S="!T:6UE.B B(#P\('1E<W1?=&EM92 \
M/"!S=&0Z.F5N9&P["B @("!S=&0Z.F-O=70@/#P@(E1E<W0@<F5S=6QT.B B
M(#P\(&H@/#P@<W1D.CIE;F1L.PH*(" @('8N<'5S:%]B86-K*&XK*RD["@H@
M(" @+R\M+2TM+2TM+2TM+2TM+2TM+2TM+2TM+2TM+2TO+PH*(" @('1E<W1?
M=&EM92 ]('1I;65?<F]U=&EN92@@=B I.PH*(" @('-T9#HZ8V]U=" \/" B
M5&5S="!V96-T;W(@<VEZ92 H:6YC;'5D97,@=F5C=&]R('-I>F4@*R!D871A
M*2 Z("(@"B @(" @(" @(" @(" @/#P@*'-I>F5O9BAV87)I86YT7W1Y<&4I
M*FXI*W-I>F5O9BAT97-T7W1Y<&4I(" @/#P@<W1D.CIE;F1L.PH*(" @('-T
M9#HZ8V]U=" \/" B5&5S="!T:6UE.B B(#P\('1E<W1?=&EM92 \/"!S=&0Z
M.F5N9&P["B @("!S=&0Z.F-O=70@/#P@(E1E<W0@<F5S=6QT.B B(#P\(&H@
M/#P@<W1D.CIE;F1L.PH*(" @('8N<'5S:%]B86-K*&XK*RD["@H@(" @+R\M
M+2TM+2TM+2TM+2TM+2TM+2TM+2TM+2TM+2TO+PH*(" @('1E<W1?=&EM92 ]
M('1I;65?<F]U=&EN92@@=B I.PH*(" @('-T9#HZ8V]U=" \/" B5&5S="!V
M96-T;W(@<VEZ92 H:6YC;'5D97,@=F5C=&]R('-I>F4@*R!D871A*2 Z("(@
M"B @(" @(" @(" @(" @/#P@*'-I>F5O9BAV87)I86YT7W1Y<&4I*FXI*W-I
M>F5O9BAT97-T7W1Y<&4I(" @/#P@<W1D.CIE;F1L.PH*(" @('-T9#HZ8V]U
M=" \/" B5&5S="!T:6UE.B B(#P\('1E<W1?=&EM92 \/"!S=&0Z.F5N9&P[
M"B @("!S=&0Z.F-O=70@/#P@(E1E<W0@<F5S=6QT.B B(#P\(&H@/#P@<W1D
M.CIE;F1L.PH*(" @('8N<'5S:%]B86-K*&XK*RD["@H@(" @+R\M+2TM+2TM
M+2TM+2TM+2TM+2TM+2TM+2TM+2TO+PH*(" @('1E<W1?=&EM92 ]('1I;65?
M<F]U=&EN92@@=B I.PH*(" @('-T9#HZ8V]U=" \/" B5&5S="!V96-T;W(@
M<VEZ92 H:6YC;'5D97,@=F5C=&]R('-I>F4@*R!D871A*2 Z("(@"B @(" @
M(" @(" @(" @/#P@*'-I>F5O9BAV87)I86YT7W1Y<&4I*FXI*W-I>F5O9BAT
M97-T7W1Y<&4I(" @/#P@<W1D.CIE;F1L.PH*(" @('-T9#HZ8V]U=" \/" B
M5&5S="!T:6UE.B B(#P\('1E<W1?=&EM92 \/"!S=&0Z.F5N9&P["B @("!S
M=&0Z.F-O=70@/#P@(E1E<W0@<F5S=6QT.B B(#P\(&H@/#P@<W1D.CIE;F1L
M.PH*(" @('8N<'5S:%]B86-K*&XK*RD["@H@(" @+R\M+2TM+2TM+2TM+2TM
M+2TM+2TM+2TM+2TM+2TO+PH*(" @('1E<W1?=&EM92 ]('1I;65?<F]U=&EN
M92@@=B I.PH*(" @('-T9#HZ8V]U=" \/" B5&5S="!V96-T;W(@<VEZ92 H
M:6YC;'5D97,@=F5C=&]R('-I>F4@*R!D871A*2 Z("(@"B @(" @(" @(" @
M(" @/#P@*'-I>F5O9BAV87)I86YT7W1Y<&4I*FXI*W-I>F5O9BAT97-T7W1Y
M<&4I(" @/#P@<W1D.CIE;F1L.PH*(" @('-T9#HZ8V]U=" \/" B5&5S="!T
M:6UE.B B(#P\('1E<W1?=&EM92 \/"!S=&0Z.F5N9&P["B @("!S=&0Z.F-O
M=70@/#P@(E1E<W0@<F5S=6QT.B B(#P\(&H@/#P@<W1D.CIE;F1L.PH*(" @
M('8N<'5S:%]B86-K*&XK*RD["@H@(" @+R\M+2TM+2TM+2TM+2TM+2TM+2TM
M+2TM+2TM+2TO+PH*(" @(')E='5R;B!J.PI]"@HO+RTM+2TM+2TM+2TM+2TM
M+2TM+2TM+2TM+2TM+2TM+2TM+2TM+2TM+2TM+2TM+2TM+2\O"@IV;VED"G1E
M<W1?<F]U=&EN92@@<W1D.CIO<W1R96%M)B!O<RP@=&5S=%]T>7!E(&-O;G-T
M)B!V("D*>PH@(" @<W1D.CIF;W)?96%C:"@@=BYB96=I;B@I+"!V+F5N9"@I
M+"!V87)I86YT7V%C8W5M=6QA=&]R*"!O<R I("D["GT*"B\O+2TM+2TM+2TM
M+2TM+2TM+2TM+2TM+2TM+2TM+2TM+2TM+2TM+2TM+2TM+2TM+2TM+R\*"GT*
L"FEN= IM86EN*"D*>PH@(" @<F5T=7)N('1E<W0Z.F1O7W1E<W0H*3L*?0H`
`
end