[Patches] Patch for thread_nt.h, radically increasing Python perfomance
Markovitch Yakov
Markovitch@ISO.RU
Tue, 11 Apr 2000 16:11:55 +0400
Hello Guido.
Here's the new version of thread_nt.h. More particular, there is a new
version of thread lock that uses kernel object (e.g. semaphore) only in case
of contention; in other case it simply uses interlocked functions, which are
faster by the order of magnitude. It doesn't make much difference without
threads present, but as soon as thread machinery initialised and (mostly)
the interpreter global lock is on, difference becomes tremendous. I've
included a small script, which initialises threads and launches pystone.
With original thread_nt.h, Pystone results with initialised threads are
twofold worse then w/o threads. With the new version, only 10% worse.
I have used this patch for about 6 months (with threaded and non-threaded
applications). It works remarkably well (though I'd desperately prefer
Python was free-threaded; I hope, it will soon).
Here's the legal mumbo-yumbo:
I confirm that, to the best of my knowledge and belief, this
contribution is free of any claims of third parties under
copyright, patent or other rights or interests ("claims"). To
the extent that I have any such claims, I hereby grant to CNRI a
nonexclusive, irrevocable, royalty-free, worldwide license to
reproduce, distribute, perform and/or display publicly, prepare
derivative versions, and otherwise use this contribution as part
of the Python software and its related documentation, or any
derivative versions thereof, at no cost to CNRI or its licensed
users, and to authorize others to do so.
I acknowledge that CNRI may, at its sole discretion, decide
whether or not to incorporate this contribution in the Python
software and its related documentation. I further grant CNRI
permission to use my name and other identifying information
provided to CNRI by me for use in connection with the Python
software and its related documentation.
Here's the diff against the current CVS version:
diff -r2.6 thread_nt.h
5c5
< All Rights Reserved
---
> All Rights Reserved
32a33
> /* Fast NonRecursiveMutex support by Yakov Markovitch, markovitch@iso.ru
*/
37a39,140
> typedef struct NRMUTEX {
> LONG owned ;
> DWORD thread_id ;
> HANDLE hevent ;
>
> } NRMUTEX, *PNRMUTEX ;
>
>
> typedef PVOID WINAPI interlocked_cmp_xchg_t(PVOID *dest, PVOID exc, PVOID
comperand) ;
>
> /* Sorry mate, but we haven't got InterlockedCompareExchange in Win95! */
> static PVOID WINAPI interlocked_cmp_xchg(PVOID *dest, PVOID exc, PVOID
comperand)
> {
> static LONG spinlock = 0 ;
> PVOID result ;
>
> /* Acqire spinlock (yielding control to other threads if cant aquire
for the moment) */
> while(InterlockedExchange(&spinlock, 1)) Sleep(0) ;
> result = *dest ;
> if (result == comperand)
> *dest = exc ;
> /* Release spinlock */
> spinlock = 0 ;
> return result ;
> } ;
>
> static interlocked_cmp_xchg_t *ixchg ;
> BOOL InitializeNonRecursiveMutex(PNRMUTEX mutex)
> {
> if (!ixchg)
> {
> /* Sorely, Win95 has no InterlockedCompareExchange API
(Win98 has), so we have to use emulation */
> HANDLE kernel = GetModuleHandle("kernel32.dll") ;
> if (!kernel || (ixchg = (interlocked_cmp_xchg_t
*)GetProcAddress(kernel, "InterlockedCompareExchange")) == NULL)
> ixchg = interlocked_cmp_xchg ;
> }
>
> mutex->owned = -1 ; /* No threads have entered NonRecursiveMutex */
> mutex->thread_id = 0 ;
> mutex->hevent = CreateEvent(NULL, FALSE, FALSE, NULL) ;
> return mutex->hevent != NULL ; /* TRUE if the mutex is created */
> }
>
> #define InterlockedCompareExchange(dest,exchange,comperand) (ixchg((dest),
(exchange), (comperand)))
>
> VOID DeleteNonRecursiveMutex(PNRMUTEX mutex)
> {
> /* No in-use check */
> CloseHandle(mutex->hevent) ;
> mutex->hevent = NULL ; /* Just in case */
> }
>
> DWORD EnterNonRecursiveMutex(PNRMUTEX mutex, BOOL wait)
> {
> /* Assume that the thread waits successfully */
> DWORD ret ;
>
> /* InterlockedIncrement(&mutex->owned) == 0 means that no thread
currently owns the mutex */
> if (!wait)
> {
> if (InterlockedCompareExchange((PVOID *)&mutex->owned,
(PVOID)0, (PVOID)-1) != (PVOID)-1)
> return WAIT_TIMEOUT ;
> ret = WAIT_OBJECT_0 ;
> }
> else
> ret = InterlockedIncrement(&mutex->owned) ?
> /* Some thread owns the mutex, let's wait... */
> WaitForSingleObject(mutex->hevent, INFINITE) :
WAIT_OBJECT_0 ;
>
> mutex->thread_id = GetCurrentThreadId() ; /* We own it */
> return ret ;
> }
>
> BOOL LeaveNonRecursiveMutex(PNRMUTEX mutex)
> {
> /* We don't own the mutex */
> mutex->thread_id = 0 ;
> return
> InterlockedDecrement(&mutex->owned) < 0 ||
> SetEvent(mutex->hevent) ; /* Other threads are waiting, wake
one on them up */
> }
>
> PNRMUTEX AllocNonRecursiveMutex()
> {
> PNRMUTEX mutex = (PNRMUTEX)malloc(sizeof(NRMUTEX)) ;
> if (mutex && !InitializeNonRecursiveMutex(mutex))
> {
> free(mutex) ;
> mutex = NULL ;
> }
> return mutex ;
> }
>
> void FreeNonRecursiveMutex(PNRMUTEX mutex)
> {
> if (mutex)
> {
> DeleteNonRecursiveMutex(mutex) ;
> free(mutex) ;
> }
> }
>
65c168
<
---
>
68c171
< dprintf(("%ld: PyThread_start_new_thread succeeded: %ld\n",
PyThread_get_thread_ident(), rv));
---
> dprintf(("%ld: PyThread_start_new_thread succeeded: %ld\n",
PyThread_get_thread_ident(), aThreadId));
82c185
<
---
>
136c239
< HANDLE aLock;
---
> PNRMUTEX aLock;
142,146c245
< aLock = CreateSemaphore(NULL, /* Security
attributes */
< 1, /* Initial value
*/
< 1, /* Maximum value
*/
< NULL);
< /* Name of semaphore */
---
> aLock = AllocNonRecursiveMutex() ;
157c256
< CloseHandle((HANDLE) aLock);
---
> FreeNonRecursiveMutex(aLock) ;
168,169c267
< int success = 1;
< DWORD waitResult;
---
> int success ;
173,177c271
< waitResult = WaitForSingleObject((HANDLE) aLock, (waitflag == 1 ?
INFINITE : 0));
<
< if (waitResult != WAIT_OBJECT_0) {
< success = 0; /* We failed */
< }
---
> success = aLock && EnterNonRecursiveMutex((PNRMUTEX) aLock,
(waitflag == 1 ? INFINITE : 0)) == WAIT_OBJECT_0 ;
188,192c282
< if (!ReleaseSemaphore(
< (HANDLE) aLock, /* Handle
of semaphore */
< 1, /*
increment count by one */
< NULL)) /* not
interested in previous count */
< {
---
> if (!(aLock && LeaveNonRecursiveMutex((PNRMUTEX) aLock)))
194d283
< }
Yours sincerely
Yakov Markovitch, Lead Programmer
InterSoft Lab
Phone: 7 095 218-4014
e-mail: markovitch@iso.ru
begin 600 thread_nt.h
M+RHJ*BHJ*BHJ*BHJ*BHJ*BHJ*BHJ*BHJ*BHJ*BHJ*BHJ*BHJ*BHJ*BHJ*BHJ
M*BHJ*BHJ*BHJ*BHJ*BHJ#0I#;W!Y<FEG:'0@,3DY,2TQ.3DU(&)Y(%-T:6-H
M=&EN9R!-871H96UA=&ES8V@@0V5N=')U;2P@06US=&5R9&%M+`T*5&AE($YE
M=&AE<FQA;F1S+@T*#0H@("`@("`@("`@("!!;&P@4FEG:'1S(%)E<V5R=F5D
M#0H-"E!E<FUI<W-I;VX@=&\@=7-E+"!C;W!Y+"!M;V1I9GDL(&%N9"!D:7-T
M<FEB=71E('1H:7,@<V]F='=A<F4@86YD(&ET<PT*9&]C=6UE;G1A=&EO;B!F
M;W(@86YY('!U<G!O<V4@86YD('=I=&AO=70@9F5E(&ES(&AE<F5B>2!G<F%N
M=&5D+`T*<')O=FED960@=&AA="!T:&4@86)O=F4@8V]P>7)I9VAT(&YO=&EC
M92!A<'!E87(@:6X@86QL(&-O<&EE<R!A;F0@=&AA=`T*8F]T:"!T:&%T(&-O
M<'ER:6=H="!N;W1I8V4@86YD('1H:7,@<&5R;6ES<VEO;B!N;W1I8V4@87!P
M96%R(&EN#0IS=7!P;W)T:6YG(&1O8W5M96YT871I;VXL(&%N9"!T:&%T('1H
M92!N86UE<R!O9B!3=&EC:'1I;F<@36%T:&5M871I<V-H#0I#96YT<G5M(&]R
M($-722!O<B!#;W)P;W)A=&EO;B!F;W(@3F%T:6]N86P@4F5S96%R8V@@26YI
M=&EA=&EV97,@;W(-"D-.4DD@;F]T(&)E('5S960@:6X@861V97)T:7-I;F<@
M;W(@<'5B;&EC:71Y('!E<G1A:6YI;F<@=&\-"F1I<W1R:6)U=&EO;B!O9B!T
M:&4@<V]F='=A<F4@=VET:&]U="!S<&5C:69I8RP@=W)I='1E;B!P<FEO<@T*
M<&5R;6ES<VEO;BX-"@T*5VAI;&4@0U=)(&ES('1H92!I;FET:6%L('-O=7)C
M92!F;W(@=&AI<R!S;V9T=V%R92P@82!M;V1I9FEE9"!V97)S:6]N#0II<R!M
M861E(&%V86EL86)L92!B>2!T:&4@0V]R<&]R871I;VX@9F]R($YA=&EO;F%L
M(%)E<V5A<F-H($EN:71I871I=F5S#0HH0TY222D@870@=&AE($EN=&5R;F5T
M(&%D9')E<W,@9G1P.B\O9G1P+G!Y=&AO;BYO<F<N#0H-"E-424-(5$E.1R!-
M051(14U!5$E30T@@0T5.5%)532!!3D0@0TY222!$25-#3$%)32!!3$P@5T%2
M4D%.5$E%4R!7251(#0I214=!4D0@5$\@5$A)4R!33T945T%212P@24Y#3%5$
M24Y'($%,3"!)35!,245$(%=!4E)!3E1)15,@3T8-"DU%4D-(04Y404))3$E4
M62!!3D0@1DE43D534RP@24X@3D\@159%3E0@4TA!3$P@4U1)0TA424Y'($U!
M5$A%34%425-#2`T*0T5.5%)532!/4B!#3E))($)%($Q)04),12!&3U(@04Y9
M(%-014-)04PL($E.1$E214-4($]2($-/3E-%455%3E1)04P-"D1!34%'15,@
M3U(@04Y9($1!34%'15,@5TA!5%-/159%4B!215-53%1)3D<@1E)/32!,3U-3
M($]&(%5312P@1$%402!/4@T*4%)/1DE44RP@5TA%5$A%4B!)3B!!3B!!0U1)
M3TX@3T8@0T].5%)!0U0L($Y%1TQ)1T5.0T4@3U(@3U1(15(-"E1/4E1)3U53
M($%#5$E/3BP@05))4TE.1R!/550@3T8@3U(@24X@0T].3D5#5$E/3B!7251(
M(%1(12!54T4@3U(-"E!%4D9/4DU!3D-%($]&(%1(25,@4T]&5%=!4D4N#0H-
M"BHJ*BHJ*BHJ*BHJ*BHJ*BHJ*BHJ*BHJ*BHJ*BHJ*BHJ*BHJ*BHJ*BHJ*BHJ
M*BHJ*BHJ*BHJ*BHJ*BHJ*BHJ*BHJ*B\-"@T*+RH@5&AI<R!C;V1E(&EM<&QE
M;65N=&5D(&)Y($1A9RY'<G5N96%U0&5L<V$N<')E<V5C;RYC;VUM+G-E("HO
M#0HO*B!&87-T($YO;E)E8W5R<VEV94UU=&5X('-U<'!O<G0@8GD@66%K;W8@
M36%R:V]V:71C:"P@;6%R:V]V:71C:$!I<V\N<G4@*B\-"@T*(VEN8VQU9&4@
M/'=I;F1O=W,N:#X-"B-I;F-L=61E(#QL:6UI=',N:#X-"B-I;F-L=61E(#QP
M<F]C97-S+F@^#0H-"G1Y<&5D968@<W1R=6-T($Y2355415@@>PT*("`@("`@
M($Q/3D<@("!O=VYE9"`[#0H@("`@("`@1%=/4D0@('1H<F5A9%]I9"`[#0H@
M("`@("`@2$%.1$Q%(&AE=F5N="`[#0H-"GT@3E)-551%6"P@*E!.4DU55$58
M(#L-"@T*#0IT>7!E9&5F(%!63TE$(%=)3D%022!I;G1E<FQO8VME9%]C;7!?
M>&-H9U]T*%!63TE$("ID97-T+"!05D])1"!E>&,L(%!63TE$(&-O;7!E<F%N
M9"D@.PT*#0HO*B!3;W)R>2!M871E+"!B=70@=V4@:&%V96XG="!G;W0@26YT
M97)L;V-K961#;VUP87)E17AC:&%N9V4@:6X@5VEN.34A("HO#0IS=&%T:6,@
M4%9/240@5TE.05!)(&EN=&5R;&]C:V5D7V-M<%]X8VAG*%!63TE$("ID97-T
M+"!05D])1"!E>&,L(%!63TE$(&-O;7!E<F%N9"D-"GL-"@ES=&%T:6,@3$].
M1R!S<&EN;&]C:R`](#`@.PT*"5!63TE$(')E<W5L="`[#0H-"@DO*B!!8W%I
M<F4@<W!I;FQO8VL@*'EI96QD:6YG(&-O;G1R;VP@=&\@;W1H97(@=&AR96%D
M<R!I9B!C86YT(&%Q=6ER92!F;W(@=&AE(&UO;65N="D@*B\-"@EW:&EL92A)
M;G1E<FQO8VME9$5X8VAA;F=E*"9S<&EN;&]C:RP@,2DI(%-L965P*#`I(#L-
M"@ER97-U;'0@/2`J9&5S="`[#0H):68@*')E<W5L="`]/2!C;VUP97)A;F0I
M#0H)"2ID97-T(#T@97AC(#L-"@DO*B!296QE87-E('-P:6YL;V-K("HO#0H)
M<W!I;FQO8VL@/2`P(#L-"@ER971U<FX@<F5S=6QT(#L-"GT@.PT*#0IS=&%T
M:6,@:6YT97)L;V-K961?8VUP7WAC:&=?="`J:7AC:&<@.PT*0D]/3"!);FET
M:6%L:7IE3F]N4F5C=7)S:79E375T97@H4$Y2355415@@;75T97@I#0I[#0H)
M:68@*"%I>&-H9RD-"@E[#0H)"2\J(%-O<F5L>2P@5VEN.34@:&%S(&YO($EN
M=&5R;&]C:V5D0V]M<&%R945X8VAA;F=E($%022`H5VEN.3@@:&%S*2P@<V\@
M=V4@:&%V92!T;R!U<V4@96UU;&%T:6]N("HO#0H)"4A!3D1,12!K97)N96P@
M/2!'971-;V1U;&5(86YD;&4H(FME<FYE;#,R+F1L;"(I(#L-"@D):68@*"%K
M97)N96P@?'P@*&EX8VAG(#T@*&EN=&5R;&]C:V5D7V-M<%]X8VAG7W0@*BE'
M9710<F]C061D<F5S<RAK97)N96PL("));G1E<FQO8VME9$-O;7!A<F5%>&-H
M86YG92(I*2`]/2!.54Q,*0T*"0D):7AC:&<@/2!I;G1E<FQO8VME9%]C;7!?
M>&-H9R`[#0H)?0T*#0H);75T97@M/F]W;F5D(#T@+3$@.R`@+RH@3F\@=&AR
M96%D<R!H879E(&5N=&5R960@3F]N4F5C=7)S:79E375T97@@*B\-"@EM=71E
M>"T^=&AR96%D7VED(#T@,"`[#0H);75T97@M/FAE=F5N="`]($-R96%T945V
M96YT*$Y53$PL($9!3%-%+"!&04Q312P@3E5,3"D@.PT*"7)E='5R;B!M=71E
M>"T^:&5V96YT("$]($Y53$P@.PDO*B!44E5%(&EF('1H92!M=71E>"!I<R!C
M<F5A=&5D("HO#0I]#0H-"B-D969I;F4@26YT97)L;V-K961#;VUP87)E17AC
M:&%N9V4H9&5S="QE>&-H86YG92QC;VUP97)A;F0I("AI>&-H9R@H9&5S="DL
M("AE>&-H86YG92DL("AC;VUP97)A;F0I*2D-"@T*5D])1"!$96QE=&5.;VY2
M96-U<G-I=F5-=71E>"A03E)-551%6"!M=71E>"D-"GL-"@DO*B!.;R!I;BUU
M<V4@8VAE8VL@*B\-"@E#;&]S94AA;F1L92AM=71E>"T^:&5V96YT*2`[#0H)
M;75T97@M/FAE=F5N="`]($Y53$P@.R`O*B!*=7-T(&EN(&-A<V4@*B\-"GT-
M"@T*1%=/4D0@16YT97).;VY296-U<G-I=F5-=71E>"A03E)-551%6"!M=71E
M>"P@0D]/3"!W86ET*0T*>PT*"2\J($%S<W5M92!T:&%T('1H92!T:')E860@
M=V%I=',@<W5C8V5S<V9U;&QY("HO#0H)1%=/4D0@<F5T(#L-"@T*"2\J($EN
M=&5R;&]C:V5D26YC<F5M96YT*"9M=71E>"T^;W=N960I(#T](#`@;65A;G,@
M=&AA="!N;R!T:')E860@8W5R<F5N=&QY(&]W;G,@=&AE(&UU=&5X("HO#0H)
M:68@*"%W86ET*0T*"7L-"@D):68@*$EN=&5R;&]C:V5D0V]M<&%R945X8VAA
M;F=E*"A05D])1"`J*29M=71E>"T^;W=N960L("A05D])1"DP+"`H4%9/240I
M+3$I("$]("A05D])1"DM,2D-"@D)"7)E='5R;B!704E47U1)345/550@.PT*
M"0ER970@/2!704E47T]"2D5#5%\P(#L-"@E]#0H)96QS90T*"0ER970@/2!)
M;G1E<FQO8VME9$EN8W)E;65N="@F;75T97@M/F]W;F5D*2`_#0H)"0DO*B!3
M;VUE('1H<F5A9"!O=VYS('1H92!M=71E>"P@;&5T)W,@=V%I="XN+B`J+PT*
M"0D)5V%I=$9O<E-I;F=L94]B:F5C="AM=71E>"T^:&5V96YT+"!)3D9)3DE4
M12D@.B!704E47T]"2D5#5%\P(#L-"@T*"6UU=&5X+3YT:')E861?:60@/2!'
M971#=7)R96YT5&AR96%D260H*2`[("\J(%=E(&]W;B!I="`J+PT*"7)E='5R
M;B!R970@.PT*?0T*#0I"3T],($QE879E3F]N4F5C=7)S:79E375T97@H4$Y2
M355415@@;75T97@I#0I[#0H)+RH@5V4@9&]N)W0@;W=N('1H92!M=71E>"`J
M+PT*"6UU=&5X+3YT:')E861?:60@/2`P(#L-"@ER971U<FX-"@D)26YT97)L
M;V-K961$96-R96UE;G0H)FUU=&5X+3YO=VYE9"D@/"`P('Q\#0H)"5-E=$5V
M96YT*&UU=&5X+3YH979E;G0I(#L@+RH@3W1H97(@=&AR96%D<R!A<F4@=V%I
M=&EN9RP@=V%K92!O;F4@;VX@=&AE;2!U<"`J+PT*?0T*#0I03E)-551%6"!!
M;&QO8TYO;E)E8W5R<VEV94UU=&5X*"D-"GL-"@E03E)-551%6"!M=71E>"`]
M("A03E)-551%6"EM86QL;V,H<VEZ96]F*$Y2355415@I*2`[#0H):68@*&UU
M=&5X("8F("%);FET:6%L:7IE3F]N4F5C=7)S:79E375T97@H;75T97@I*0T*
M"7L-"@D)9G)E92AM=71E>"D@.PT*"0EM=71E>"`]($Y53$P@.PT*"7T-"@ER
M971U<FX@;75T97@@.PT*?0T*#0IV;VED($9R965.;VY296-U<G-I=F5-=71E
M>"A03E)-551%6"!M=71E>"D-"GL-"@EI9B`H;75T97@I#0H)>PT*"0E$96QE
M=&5.;VY296-U<G-I=F5-=71E>"AM=71E>"D@.PT*"0EF<F5E*&UU=&5X*2`[
M#0H)?0T*?0T*#0IL;VYG(%!Y5&AR96%D7V=E=%]T:')E861?:61E;G0H=F]I
M9"D[#0H-"B\J#0H@*B!#:&%N9V4@86QL(&AE861E<G,@=&\@<'5R92!!3E-)
M(&%S(&YO(&]N92!W:6QL('5S92!+)E(@<W1Y;&4@;VX@86X-"B`J($Y4#0H@
M*B\-"@T*+RH-"B`J($EN:71I86QI>F%T:6]N(&]F('1H92!#('!A8VMA9V4L
M('-H;W5L9"!N;W0@8F4@;F5E9&5D+@T*("HO#0IS=&%T:6,@=F]I9"!0>51H
M<F5A9%]?:6YI=%]T:')E860H=F]I9"D-"GL-"GT-"@T*+RH-"B`J(%1H<F5A
M9"!S=7!P;W)T+@T*("HO#0II;G0@4'E4:')E861?<W1A<G1?;F5W7W1H<F5A
M9"AV;VED("@J9G5N8RDH=F]I9"`J*2P@=F]I9"`J87)G*0T*>PT*"6QO;F<@
M<G8[#0H):6YT('-U8V-E<W,@/2`P.PT*#0H)9'!R:6YT9B@H(B5L9#H@4'E4
M:')E861?<W1A<G1?;F5W7W1H<F5A9"!C86QL961<;B(L(%!Y5&AR96%D7V=E
M=%]T:')E861?:61E;G0H*2DI.PT*"6EF("@A:6YI=&EA;&EZ960I#0H)"5!Y
M5&AR96%D7VEN:71?=&AR96%D*"D[#0H-"@ER=B`](%]B96=I;G1H<F5A9"AF
M=6YC+"`P+"!A<F<I.R`O*B!U<V4@9&5F875L="!S=&%C:R!S:7IE("HO#0H-
M"@EI9B`H<G8@(3T@+3$I('L-"@D)<W5C8V5S<R`](#$[#0H)"61P<FEN=&8H
M*"(E;&0Z(%!Y5&AR96%D7W-T87)T7VYE=U]T:')E860@<W5C8V5E9&5D.B`E
M;&1<;B(L(%!Y5&AR96%D7V=E=%]T:')E861?:61E;G0H*2P@851H<F5A9$ED
M*2D[#0H)?0T*#0H)<F5T=7)N('-U8V-E<W,[#0I]#0H-"B\J#0H@*B!2971U
M<FX@=&AE('1H<F5A9"!)9"!I;G-T96%D(&]F(&%N(&AA;F1L92X@5&AE($ED
M(&ES('-A:60@=&\@=6YI<75E;'D@:61E;G1I9GD@=&AE#0H@*B!T:')E860@
M:6X@=&AE('-Y<W1E;0T*("HO#0IL;VYG(%!Y5&AR96%D7V=E=%]T:')E861?
M:61E;G0H=F]I9"D-"GL-"@EI9B`H(6EN:71I86QI>F5D*0T*"0E0>51H<F5A
M9%]I;FET7W1H<F5A9"@I.PT*#0H)<F5T=7)N($=E=$-U<G)E;G14:')E861)
M9"@I.PT*?0T*#0IS=&%T:6,@=F]I9"!D;U]0>51H<F5A9%]E>&ET7W1H<F5A
M9"AI;G0@;F]?8VQE86YU<"D-"GL-"@ED<')I;G1F*"@B)6QD.B!0>51H<F5A
M9%]E>&ET7W1H<F5A9"!C86QL961<;B(L(%!Y5&AR96%D7V=E=%]T:')E861?
M:61E;G0H*2DI.PT*"6EF("@A:6YI=&EA;&EZ960I#0H)"6EF("AN;U]C;&5A
M;G5P*0T*"0D)7V5X:70H,"D[#0H)"65L<V4-"@D)"65X:70H,"D[#0H)7V5N
M9'1H<F5A9"@I.PT*?0T*#0IV;VED(%!Y5&AR96%D7V5X:71?=&AR96%D*'9O
M:60I#0I[#0H)9&]?4'E4:')E861?97AI=%]T:')E860H,"D[#0I]#0H-"G9O
M:60@4'E4:')E861?7V5X:71?=&AR96%D*'9O:60I#0I[#0H)9&]?4'E4:')E
M861?97AI=%]T:')E860H,2D[#0I]#0H-"B-I9FYD968@3D]?15A)5%]04D]'
M#0IS=&%T:6,@=F]I9"!D;U]0>51H<F5A9%]E>&ET7W!R;V<H:6YT('-T871U
M<RP@:6YT(&YO7V-L96%N=7`I#0I[#0H)9'!R:6YT9B@H(E!Y5&AR96%D7V5X
M:71?<')O9R@E9"D@8V%L;&5D7&XB+"!S=&%T=7,I*3L-"@EI9B`H(6EN:71I
M86QI>F5D*0T*"0EI9B`H;F]?8VQE86YU<"D-"@D)"5]E>&ET*'-T871U<RD[
M#0H)"65L<V4-"@D)"65X:70H<W1A='5S*3L-"GT-"@T*=F]I9"!0>51H<F5A
M9%]E>&ET7W!R;V<H:6YT('-T871U<RD-"GL-"@ED;U]0>51H<F5A9%]E>&ET
M7W!R;V<H<W1A='5S+"`P*3L-"GT-"@T*=F]I9"!0>51H<F5A9%]?97AI=%]P
M<F]G(%]0,2AI;G0@<W1A='5S*0T*>PT*"61O7U!Y5&AR96%D7V5X:71?<')O
M9RAS=&%T=7,L(#$I.PT*?0T*(V5N9&EF("\J($Y/7T58251?4%)/1R`J+PT*
M#0HO*@T*("H@3&]C:R!S=7!P;W)T+B!)="!H87,@=&]O(&)E(&EM<&QE;65N
M=&5D(&%S('-E;6%P:&]R97,N#0H@*B!)(%M$86==('1R:65D('1O(&EM<&QE
M;65N="!I="!W:71H(&UU=&5X(&)U="!)(&-O=6QD(&9I;F0@82!W87D@=&\-
M"B`J('1E;&P@=VAE=&AE<B!A('1H<F5A9"!A;')E861Y(&]W;B!T:&4@;&]C
M:R!O<B!N;W0N#0H@*B\-"E!Y5&AR96%D7W1Y<&5?;&]C:R!0>51H<F5A9%]A
M;&QO8V%T95]L;V-K*'9O:60I#0I[#0H)4$Y2355415@@84QO8VL[#0H-"@ED
M<')I;G1F*"@B4'E4:')E861?86QL;V-A=&5?;&]C:R!C86QL961<;B(I*3L-
M"@EI9B`H(6EN:71I86QI>F5D*0T*"0E0>51H<F5A9%]I;FET7W1H<F5A9"@I
M.PT*#0H)84QO8VL@/2!!;&QO8TYO;E)E8W5R<VEV94UU=&5X*"D@.PT*#0H)
M9'!R:6YT9B@H(B5L9#H@4'E4:')E861?86QL;V-A=&5?;&]C:R@I("T^("5L
M>%QN(BP@4'E4:')E861?9V5T7W1H<F5A9%]I9&5N="@I+"`H;&]N9REA3&]C
M:RDI.PT*#0H)<F5T=7)N("A0>51H<F5A9%]T>7!E7VQO8VLI(&%,;V-K.PT*
M?0T*#0IV;VED(%!Y5&AR96%D7V9R965?;&]C:RA0>51H<F5A9%]T>7!E7VQO
M8VL@84QO8VLI#0I[#0H)9'!R:6YT9B@H(B5L9#H@4'E4:')E861?9G)E95]L
M;V-K*"5L>"D@8V%L;&5D7&XB+"!0>51H<F5A9%]G971?=&AR96%D7VED96YT
M*"DL*&QO;F<I84QO8VLI*3L-"@T*"49R965.;VY296-U<G-I=F5-=71E>"AA
M3&]C:RD@.PT*?0T*#0HO*@T*("H@4F5T=7)N(#$@;VX@<W5C8V5S<R!I9B!T
M:&4@;&]C:R!W87,@86-Q=6ER960-"B`J#0H@*B!A;F0@,"!I9B!T:&4@;&]C
M:R!W87,@;F]T(&%C<75I<F5D+B!4:&ES(&UE86YS(&$@,"!I<R!R971U<FYE
M9`T*("H@:68@=&AE(&QO8VL@:&%S(&%L<F5A9'D@8F5E;B!A8W%U:7)E9"!B
M>2!T:&ES('1H<F5A9"$-"B`J+PT*:6YT(%!Y5&AR96%D7V%C<75I<F5?;&]C
M:RA0>51H<F5A9%]T>7!E7VQO8VL@84QO8VLL(&EN="!W86ET9FQA9RD-"GL-
M"@EI;G0@<W5C8V5S<R`[#0H-"@ED<')I;G1F*"@B)6QD.B!0>51H<F5A9%]A
M8W%U:7)E7VQO8VLH)6QX+"`E9"D@8V%L;&5D7&XB+"!0>51H<F5A9%]G971?
M=&AR96%D7VED96YT*"DL*&QO;F<I84QO8VLL('=A:71F;&%G*2D[#0H-"@ES
M=6-C97-S(#T@84QO8VL@)B8@16YT97).;VY296-U<G-I=F5-=71E>"@H4$Y2
M355415@I(&%,;V-K+"`H=V%I=&9L86<@/3T@,2`_($E.1DE.251%(#H@,"DI
M(#T](%=!251?3T)*14-47S`@.PT*#0H)9'!R:6YT9B@H(B5L9#H@4'E4:')E
M861?86-Q=6ER95]L;V-K*"5L>"P@)60I("T^("5D7&XB+"!0>51H<F5A9%]G
M971?=&AR96%D7VED96YT*"DL*&QO;F<I84QO8VLL('=A:71F;&%G+"!S=6-C
M97-S*2D[#0H-"@ER971U<FX@<W5C8V5S<SL-"GT-"@T*=F]I9"!0>51H<F5A
M9%]R96QE87-E7VQO8VLH4'E4:')E861?='EP95]L;V-K(&%,;V-K*0T*>PT*
M"61P<FEN=&8H*"(E;&0Z(%!Y5&AR96%D7W)E;&5A<V5?;&]C:R@E;'@I(&-A
M;&QE9%QN(BP@4'E4:')E861?9V5T7W1H<F5A9%]I9&5N="@I+"AL;VYG*6%,
M;V-K*2D[#0H-"@EI9B`H(2AA3&]C:R`F)B!,96%V94YO;E)E8W5R<VEV94UU
M=&5X*"A03E)-551%6"D@84QO8VLI*2D-"@D)9'!R:6YT9B@H(B5L9#H@0V]U
M;&0@;F]T(%!Y5&AR96%D7W)E;&5A<V5?;&]C:R@E;'@I(&5R<F]R.B`E;%QN
M(BP@4'E4:')E861?9V5T7W1H<F5A9%]I9&5N="@I+"`H;&]N9REA3&]C:RP@
M1V5T3&%S=$5R<F]R*"DI*3L-"GT-"@T*+RH-"B`J(%-E;6%P:&]R92!S=7!P
M;W)T+@T*("HO#0I0>51H<F5A9%]T>7!E7W-E;6$@4'E4:')E861?86QL;V-A
M=&5?<V5M82AI;G0@=F%L=64I#0I[#0H)2$%.1$Q%(&%396UA<&AO<F4[#0H-
M"@ED<')I;G1F*"@B)6QD.B!0>51H<F5A9%]A;&QO8V%T95]S96UA(&-A;&QE
M9%QN(BP@4'E4:')E861?9V5T7W1H<F5A9%]I9&5N="@I*2D[#0H):68@*"%I
M;FET:6%L:7IE9"D-"@D)4'E4:')E861?:6YI=%]T:')E860H*3L-"@T*"6%3
M96UA<&AO<F4@/2!#<F5A=&5396UA<&AO<F4H($Y53$PL"2`@+RH@4V5C=7)I
M='D@871T<FEB=71E<PD@("HO#0H@("`@("`@("`@("`@("`@("`@("`@("`@
M("`@("`@("`@("`@('9A;'5E+"`@("`@("`@+RH@26YI=&EA;"!V86QU90D)
M("`J+PT*("`@("`@("`@("`@("`@("`@("`@("`@("`@("`@("`@("`@("!)
M3E1?34%8+"`@("`@("\J($UA>&EM=6T@=F%L=64)"2`@*B\-"B`@("`@("`@
M("`@("`@("`@("`@("`@("`@("`@("`@("`@("`@3E5,3"D["2`@("`O*B!.
M86UE(&]F('-E;6%P:&]R90D@("HO#0H-"@ED<')I;G1F*"@B)6QD.B!0>51H
M<F5A9%]A;&QO8V%T95]S96UA*"D@+3X@)6QX7&XB+"!0>51H<F5A9%]G971?
M=&AR96%D7VED96YT*"DL("AL;VYG*6%396UA<&AO<F4I*3L-"@T*"7)E='5R
M;B`H4'E4:')E861?='EP95]S96UA*2!A4V5M87!H;W)E.PT*?0T*#0IV;VED
M(%!Y5&AR96%D7V9R965?<V5M82A0>51H<F5A9%]T>7!E7W-E;6$@85-E;6%P
M:&]R92D-"GL-"@ED<')I;G1F*"@B)6QD.B!0>51H<F5A9%]F<F5E7W-E;6$H
M)6QX*2!C86QL961<;B(L(%!Y5&AR96%D7V=E=%]T:')E861?:61E;G0H*2P@
M*&QO;F<I85-E;6%P:&]R92DI.PT*#0H)0VQO<V5(86YD;&4H*$A!3D1,12D@
M85-E;6%P:&]R92D[#0I]#0H-"B\J#0H@(%A86"!M=7-T(&1O('-O;65T:&EN
M9R!A8F]U="!W86ET9FQA9PT*("HO#0II;G0@4'E4:')E861?9&]W;E]S96UA
M*%!Y5&AR96%D7W1Y<&5?<V5M82!A4V5M87!H;W)E+"!I;G0@=V%I=&9L86<I
M#0I[#0H)1%=/4D0@=V%I=%)E<W5L=#L-"@T*"61P<FEN=&8H*"(E;&0Z(%!Y
M5&AR96%D7V1O=VY?<V5M82@E;'@I(&-A;&QE9%QN(BP@4'E4:')E861?9V5T
M7W1H<F5A9%]I9&5N="@I+"`H;&]N9REA4V5M87!H;W)E*2D[#0H-"@EW86ET
M4F5S=6QT(#T@5V%I=$9O<E-I;F=L94]B:F5C="@@*$A!3D1,12D@85-E;6%P
M:&]R92P@24Y&24Y)5$4I.PT*#0H)9'!R:6YT9B@H(B5L9#H@4'E4:')E861?
M9&]W;E]S96UA*"5L>"D@<F5T=7)N.B`E;%QN(BP@4'E4:')E861?9V5T7W1H
M<F5A9%]I9&5N="@I+"AL;VYG*2!A4V5M87!H;W)E+"!W86ET4F5S=6QT*2D[
M#0H)<F5T=7)N(#`[#0I]#0H-"G9O:60@4'E4:')E861?=7!?<V5M82A0>51H
M<F5A9%]T>7!E7W-E;6$@85-E;6%P:&]R92D-"GL-"@E296QE87-E4V5M87!H
M;W)E*`T*"0DH2$%.1$Q%*2!A4V5M87!H;W)E+`D@("`@+RH@2&%N9&QE(&]F
M('-E;6%P:&]R90D)*B\-"@D),2P)"2\J(&EN8W)E;65N="!C;W5N="!B>2!O
M;F4)("`@("HO#0H)"4Y53$PI.PD)("`@("\J(&YO="!I;G1E<F5S=&5D(&EN
M('!R979I;W5S(&-O=6YT"2`@("`J+PT*#0H)9'!R:6YT9B@H(B5L9#H@4'E4
M:')E861?=7!?<V5M82@E;'@I7&XB+"!0>51H<F5A9%]G971?=&AR96%D7VED
?96YT*"DL("AL;VYG*6%396UA<&AO<F4I*3L-"GT-"@==
`
end
begin 600 thr_stone.py
M:6UP;W)T('1H<F5A9`T*(R!3=&%R="!E;7!T>2!T:')E860@=&\@:6YI=&EA
M;&ES92!T:')E860@;65C:&%N:6-S("AA;F0@9VQO8F%L(&QO8VLA*0T*(R!4
M:&ES('1H<F5A9"!W:6QL(&9I;FES:"!I;6UE9&EA=&5L>2!T:'5S('=O;B=T
M(&UA:V4@;75C:"!I;F9L=65N8V4@;VX-"B,@=&5S="!R97-U;'1S(&)Y(&ET
M<V5L9BP@;VYL>2!B>2!T:&%T(&9A8W0@=&AA="!I="!I;FET:6%L:7-E<R!G
M;&]B86P@;&]C:PT*=&AR96%D+G-T87)T7VYE=U]T:')E860H;&%M8F1A(#H@
M,2P@*"DI#0H-"FEM<&]R="!T97-T+G!Y<W1O;F4-"G1E<W0N<'ES=&]N92YM
'86EN*"D-"@==
`
end