Boost logo

Boost :

From: Gennadiy Rozental (gennadiy.rozental_at_[hidden])
Date: 2006-12-17 04:37:30


"Joel de Guzman" <joel_at_[hidden]> wrote in message
news:elv64c$qao$1_at_sea.gmane.org...
> Gennadiy Rozental wrote:
>> "David Abrahams" <dave_at_[hidden]> wrote in message
>> news:87lkl93hlx.fsf_at_pereiro.luannocracy.com...
>>> "Gennadiy Rozental" <gennadiy.rozental_at_[hidden]> 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_at_8S$@(#T@
M,3L*:6YT(&,R(" ](#(["FEN="!C,R @/2 S.PII;G0_at_8S0@(#T_at_-#L*:6YT
M(&,U(" ](#4["FEN="!C-B @/2 V.PII;G0_at_8S<@(#T_at_-SL*:6YT(&,X(" ]
M(#@["FEN="!C.2 @/2 Y.PII;G0_at_8S$P(#T@,3 ["FEN="!C,3$@/2 Q,3L*
M:6YT(&,Q,B ](#$R.PII;G0_at_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_at_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_at_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_at_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_at_-# 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_at_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_at_-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_at_9&]?=&5S
M="@I"GL*(" @(&EN=" @(" @("!J(#T@,#L*(" @(&1O=6)L92 @("!T97-T
M7W1I;64["@H@(" @>PH@(" @(" @('1Y<&5D968_at_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_at_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_at_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_at_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_at_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_at_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_at_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_at_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_at_I*%0_at_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_at_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_at_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_at_8V]N<W0F('8@*0I["B @("!F
M;F0Z.F%C8U]T:6UE<B!T:6UE<CL*"B @("!I;G0_at_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_at_I(#P_at_-3 P,# P," I.PH*
M(" @(&QO;F<@;&]N9R @(" @(&5L87!S961?=&EM92 ](#4P,# P,# J,3 [
M"@H@(" @+R\@<F5P96%T('1E<W0_at_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_at_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_at_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


Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk