From 397b972807c939db6becda7be9e67966326b4966 Mon Sep 17 00:00:00 2001 From: fennecdjay Date: Fri, 28 Jun 2019 12:14:05 +0200 Subject: [PATCH] :book: Benchmarks --- .gitignore | 2 + docs.mk | 6 +- docs/01_Overview/declaration.mdr | 5 +- docs/Benchmarks.mdr | 86 +++++++++++++++++++++++++ docs/{ => Extending}/WIP_Driver.mdr | 0 docs/{ => Extending}/WIP_Plugins.mdr | 0 docs/Functions/function.mdr | 3 +- docs/Make.mdr | 2 +- docs/assets/benchmark/binary_trees.dat | 3 + docs/assets/benchmark/binary_trees.png | Bin 0 -> 8091 bytes docs/assets/doc.css | 7 ++ help/benchmark.sh | 20 ------ help/doc-config.sh | 12 ++-- tests/benchmark/binary_trees.dart | 56 ++++++++++++++++ tests/benchmark/binary_trees.gw | 51 +++++++++++++++ tests/benchmark/binary_trees.lua | 50 ++++++++++++++ tests/benchmark/binary_trees.py | 46 +++++++++++++ tests/benchmark/binary_trees.rb | 49 ++++++++++++++ tests/benchmark/binary_trees.wren | 51 +++++++++++++++ tests/benchmark/binary_trees_gc.wren | 55 ++++++++++++++++ 20 files changed, 472 insertions(+), 32 deletions(-) create mode 100644 docs/Benchmarks.mdr rename docs/{ => Extending}/WIP_Driver.mdr (100%) rename docs/{ => Extending}/WIP_Plugins.mdr (100%) create mode 100644 docs/assets/benchmark/binary_trees.dat create mode 100644 docs/assets/benchmark/binary_trees.png create mode 100644 docs/assets/doc.css delete mode 100644 help/benchmark.sh create mode 100644 tests/benchmark/binary_trees.dart create mode 100644 tests/benchmark/binary_trees.gw create mode 100644 tests/benchmark/binary_trees.lua create mode 100644 tests/benchmark/binary_trees.py create mode 100644 tests/benchmark/binary_trees.rb create mode 100644 tests/benchmark/binary_trees.wren create mode 100644 tests/benchmark/binary_trees_gc.wren diff --git a/.gitignore b/.gitignore index 3b548b3c..d741608c 100644 --- a/.gitignore +++ b/.gitignore @@ -3,3 +3,5 @@ gwion config.mk include/generated.h .desk +mkdocs.yml +*.a diff --git a/docs.mk b/docs.mk index b767302d..af87eff9 100644 --- a/docs.mk +++ b/docs.mk @@ -42,18 +42,18 @@ doc-deploy: $(md_list) .SUFFIXES: .gw .test .gw.test: - @${VALGRIND} ${VALGRIND_OPT} gwion $< &> log + @${VALGRIND} ${VALGRIND_OPT} gwion $< 2>&1 > log @[ -t 1 ] && $(call _interm) || $(call _noterm) define _test_check for a in $(CONTAINS); do grep "$$a" log >/dev/null; done && valgrind_parse vlog endef -_interm_status=echo -e "$(INTERM_OK)" || echo -e "$(INTERM_NOT_OK)" +_interm_status=printf "$(INTERM_OK)\n" || printf "$(INTERM_NOT_OK)\n" _interm=(cat log; $(call _test_check) && $(call _interm_status)) _noterm_log=sed 's/$$/\/' log -_noterm_status=echo -e "$(NOTERM_OK)" || echo -e "$(NOTERM_NOT_OK)" +_noterm_status=printf "$(NOTERM_OK)\n" || printf "$(NOTERM_NOT_OK)\n" _noterm_test=$(call _test_check) && $(call _noterm_status) _noterm_header=echo '

' _noterm_footer=echo '

' diff --git a/docs/01_Overview/declaration.mdr b/docs/01_Overview/declaration.mdr index e359c6a3..9afb021c 100644 --- a/docs/01_Overview/declaration.mdr +++ b/docs/01_Overview/declaration.mdr @@ -19,15 +19,16 @@ Object @ref; new Object @=> ref; <<<"But now it does: ", ref>>>; @``` -@exec gwion decl1.gw 2>&1 +@exec make decl1.test ## Arrays ### array as refs + @``` decl2.gw int ref[]; <<>>; new int[2] @=> ref; <<>>; @``` -@exec gwion decl2.gw 2>&1 +@exec make decl2.test diff --git a/docs/Benchmarks.mdr b/docs/Benchmarks.mdr new file mode 100644 index 00000000..ef684742 --- /dev/null +++ b/docs/Benchmarks.mdr @@ -0,0 +1,86 @@ +# Benchmarks + +We'll need a bash script + + + +### and a gnuplot script + + + +## Show the results +Then just run it +@exec bash benchmark.sh; rm bench.plot benchmark.sh diff --git a/docs/WIP_Driver.mdr b/docs/Extending/WIP_Driver.mdr similarity index 100% rename from docs/WIP_Driver.mdr rename to docs/Extending/WIP_Driver.mdr diff --git a/docs/WIP_Plugins.mdr b/docs/Extending/WIP_Plugins.mdr similarity index 100% rename from docs/WIP_Plugins.mdr rename to docs/Extending/WIP_Plugins.mdr diff --git a/docs/Functions/function.mdr b/docs/Functions/function.mdr index 5a656e45..f92a174f 100644 --- a/docs/Functions/function.mdr +++ b/docs/Functions/function.mdr @@ -1,7 +1,8 @@ # Functions ## a simple (commented example) -@```function0.gw + +@``` function0.gw // declare function 'test_function' // with return type int // taking an int as argument diff --git a/docs/Make.mdr b/docs/Make.mdr index 56000b97..45a5452d 100644 --- a/docs/Make.mdr +++ b/docs/Make.mdr @@ -1,4 +1,4 @@ -# Gwion's Makefile +# Makefile ## Basic operations diff --git a/docs/assets/benchmark/binary_trees.dat b/docs/assets/benchmark/binary_trees.dat new file mode 100644 index 00000000..a8dc8e81 --- /dev/null +++ b/docs/assets/benchmark/binary_trees.dat @@ -0,0 +1,3 @@ +gwion 0.244813625 0.33 +wren 0.358684268 1.43 +lua5.3 0.621848489 5.69 diff --git a/docs/assets/benchmark/binary_trees.png b/docs/assets/benchmark/binary_trees.png new file mode 100644 index 0000000000000000000000000000000000000000..ea48d1cc65de9805df5643b55b0f569ce1c4e75e GIT binary patch literal 8091 zcmds+c|4T++sAJdofg_DTf3qfktEAhiV7)N(qQV?D$9_>m>Huwr6MZH7K$Y69LY8q zDzbBA8T-hZF!q_jEYGEWzt?k~bDr~i&hy{zdG6P%+>N_?zW4RLuFv(k-uL}8r}bAX z-MAD%kQFCS95X=>VLt>B>RuuYpHMRmGU3NhZYL}~5JbFW;g3+LlDIU2$QzwJcEr^C z`Do`Q=cjB^vAg`si|1afiobXMvB;9;@AsIRS6IuSS?!q(%(^HImKmHn^=z;8T%{7_Snv{L zGG&u+f#-1Z+qZ97ELKcR%xy6Vxr1)qVrb5h=@-bR;MI4=*?s~RPH=-aH{;dmY2h=0 z7EGa2l9Tt^6i8_*BIU73^&&eJ6&2@tB#Xiez2UOisX_e}qKND5TL%|MkJ5|yp1Qia zwzjs@hv9}xm5T2li%U&)u6?e7tfO<6h^++*jM%YzDtC{f1RY~ z-{P!pUTKkTm6V)($YY>-C*644(g_>HEwRc8yR>KRv;nH{`pmbc>Yt5`>$05a!et`J ztocgDEuCw9C&*;MYon-vnkafx)65Ko%*$u+T)#il(jM9I6bj9U*^&3{+qc$CM>?G@ z7>eZ&^#-Hmw09!q@%P7vlIr|~%Kh&PHYg*82mV%=|Hpm!_r4(J^6LA?rdRq&#qhn> z3&mVENiv0hX?~6m)`{fg-dQFYlsdftfcbFPM-gv%SddhFJczh=kTSN-&AanTXk^<9bNmcfOs` z8|bEH(&v6fpe&#QMt&$k+rzMW%t zdNE>ot+6~hnP)MVY^S0@V2#vw@Xr}*&s3|{5eHObXB!iBvaSz(E+nv-Eg7~lWoXM+ zlLHV9I3h~Z)6+kH{`@5+&8Co=k}@1JvXjEzQWAxu`3IkJFFHb$?JkkdMU;ldn* z$qTO350crXq~zq{Vnn%e%5Zr^qTrE5=}4)VJaN2K5<9|V%E`!Rk>;isVvFmfs*##{ zN&`YF`lMI{D7tk@=7FA#i}z4Sd88pKadz^aklfVfx^Qoy^rWOKSFTj-X0~N1k>qon zTPJ%0P_IprT-vkKEHej&u>v2(&^CzIvppCUB}eqetgI}5aoNh<+3(&pHa5PZ0*j5cYBa1r?$7fWq|Gz))zs8VOG~T5P-NZ=T|ct{w&J0*`fD;j%6qactew3*bugCf3wioc zpdDc-r|olnv@Hv=e%-otxPpmKF489N55d#lme2{eB=$Yl|18;@hM~8$T`)Dh&gD$# z%i;St6TPskw6rvMf~{Sr355AbH7At-2_4QweSQ78$!|?54U)ctUcL$uhCu?-CV`%+ zyown0%^TPu7tq*-7-nelv!98Ew+nR2`v8@bOUz7_5t}>!3jQQCCw-K)YII{9IavD$?pJ@nvmQhVOt4 zbzG0a(zM|GsYUxw+t>?B8?259(WbnOSiR=sJt5}USe?znmTi=l*3{I5l{Re6ly4&HH@ByVb2XyEG#S}*R3W-naOJV?9cQbX~{@V zPUbF;kjmLFpPZ7CIViHGWu!HeJQc-wh04jwvd1=oFtoJff|yNvg<~#UP_eKs@ZLwL z${uI%Fg!Dv;uWFtFEb7AxJRaIX9P?K}$*@T06A!dRh&nVF}7 zX610BqSy6BD9a_ z_kvCZNTN=Ym(BH6gj7A-ZWp8ECc*L*%7$_-8+zrmF>BpN50Btde5 z1Vn3kxn8{3{k1+GzOITdXUwN9MMXsqX=2o~7$AzCv6)9a}_u`SKEIVf}64@au~>JK#=2 zI~U$8IlP)tzEN(P4LZ7(Cm(Yu7HzylefMV+Cupw;<(|TT8~F z4-D2u6Z*;@+o|N?7&Pnr8@zFUbfDZ?r0?vO&{M~QUw$3UVRZd^>ErZJLqk9je})20 z^}Pg|>-IECVfA8n6cTwf;T-c#IGviR)J8!mf7n_$R!-x@;Gng`hMgN<;>|LSXk~v znS7BiZ!Q?r43maCd-klNfzDkqq!%WI4mv#tepMz%7?Eah^rp`v-8XjL8ED@-^%4brC=Vpd=`5E!?@o{lK?~huhjLbfw)7F-R{mLIC^A&uS zAa0m-C62|2a_hgGVgB!@#_wl{a-1J}?rXe4EK%k0iN5oL_4@Kg#15FwrVc40OTx;K zvDVB)5H%|G5c_I{-P`#1t)czU=4PeWA!~1GiE@5>sjD9>$7`e0o)NNscuVdI5oGBZ z$f16c{Cz8eFaF#DztVFCOb7VGczv_KTsV}7A#Mm8%h)t6Dyi)qUZ%LLne3f*G{i2;*_F539cJ3 zK5m@cyUhW7@J^FpY1JZdUnV>*!;?NNP1xWo#H_Q;-W1)7-ou zmy4IJ-+$nM&P2(Y9O~A@7eZ2AUR=lG*&W4@af<}YrH~z)|Mpn?|0AWAZZDQ6P1lDQ z>qMN`wov3bx7n^G z9o6=Zp+e!sKo~A8E4J%hyZ>Kch<}H8zt)pL{Jig%l&wFP^upb6hw$=Z!8-NFkGk5+ zc3u7pe8Szh`fx!kZ@14P0mV&k@;BZ3t>vm?e}pW*f4Xiqgfls1zU5AHb8&{@dg0}M zJ)&+)HzLA)>czOi8S~@EOF`ZjMzI`*FQLR!4tB7lY>!p0G9_Nv&ke7&m{*16zlCPX zppjC{)4-K53h-067B4eTx6-hKif^s22Wfs>^cXq(vZ7bB8w``I<_#i$DmGTlsktr7 zNm^PuDl+me<(c6QKr7Kjmyp9km9~DtvYO^$vo_Xe&stk|X4sb9r9kZ%9>p&o2j2|C zQ&;uRmX?+l7WDC^Cl!75@%r?1YmAAB$=S0LpQLepxD&{kO_Q7rZe%j~xy0L%Ru>_0fN4ZI+L5Uij1%vFbDxFe4BTX$+nXs^}26&H7GOK@m)@2;=l z34spSug|AaD=RBqsb>E)+t{StIn+H!hcAA)n~{+bSUiV}goK3b>>He`k|>*M8)qjc zB^0WT@dkOZvTs7Q+c5?|0KgzUHPx!nXXgGIg&WL{*2o!hw0#!ag>|u)ebqjxidfx$7`1brllA_F5kzW(^DsjJD^%|Ar9^ zb^g~E85tAMQvdn2z5VSwDDqE4Iz(x|s69tr5<+^7|5Yme3FzUuPA3i@Ik`$ zNnQ7sFAgqV@xQQR>f1r?8gH6zx9!MfKue zRL}40;!h9r`=0oh`0|f;cyUIU+l;}PnVK5L>hSpUW90eKoOpjge`;zz2u#(-i@5zL z>5Us%un$+8k^yYiM5)78T6JUJUW;jj%jKLqvWNq8#?#aD`^;@y7PL4>44F*ZBus?42E4s`=6Q4T=BB1~ z2j!6RoLfu&Yi(?D(?TBM?wcyE)4m&Lndx9ny}qlVn?|F-3ke90gTWP=ojtn`=*B$A7g$v}_vru5@v8P*1%8xQj}4dd zZ9;QDqP510MF5ciUn^z^cnnAE445A6*}jmExMT`ttkp5rI@j&e$&(eI6AZBU{?HL8 zGE5~rK43Z!4W0ScIvuzeIJUYh_dk*3LHbg5!&0@?o!OLSiy&7sOLZC&&H&4Sk4DY7PC{+F1oh17KAg{`|@3E z7WjEEHt@;Kn>XQaKt}u-tiW?F*#b-QtdBbmDfba~wfECQhJerhffg2s+4x6^v93Z* zl9@_GDsXPM?!$l@fFA%H$$+^rN*pZr4B*oo?i-_x@z3Qnf((N650=T4yYKgK4&6tj z^@oeZx?w|FcP5s##6)S>h8HJt=L2sb7-4p>PBdQVrNC=d(RcX1nIOMgg4$+&FXfu#RxPS-NXls|+BYdFuJcv;v2kNQhC_^*&wEBJYVFu+foeI}$UDf=7Cv^scJi zCw5JyCaU(i%(;DA3F5>jB%^B(eOrR7!*XCTUl9ITSxa=ondvu5DA=ethupqt)wI%E$$2* zTSqEWh}vfuyt!<9+1BT_;(Z4r^BhkHC57)HhzH`af!BNjNAn`~aSsN$hzHJ_1LSNS z^CJTXt`6VVtLNo%YgPBeKKsh2n*}NW`#PdV+Oks8)AxGxe1-S|Rp58umiQdd>Y-j{ zmShV3Fs70ihwe#=l0m%~N_$)9WfXlVi%OjXeg~M@#l-~_bF1(4LA!DICdPahd#_dQ zZ|&^_&iEHlA1Dbmc4w@qtEbO$^xi!AFVZzPJM^dYF#R#O4Y~uxEv(~L8yjq$>uLg5 z1^2cL6mwjgnwzs-JEs94cz!SpKr@#?9LXdj=OyD(WrI6>7n zr&@Y6yq9nXUJFAwqXca^>6yl2Gig5ly6$GiXh7qe#4-hSCCA6xg7Sf8Lw#gQ!e>yoxI=*zwto}=2&K$I zB;zjs*mjv8BBo7X*$FDWJv^p>Q|XaWOy}5FU3LZV!U7Zuq)l5}8`%EdJ$qy)Za=zv z_b%Or;Idymy!SUd>`a>zMSHS*>kuPd6Kd?!Lur4q&{d960@>-;loTbNCLXG<+!=B` zX@ME5tHbN4cR4wf3t5U&mbO9fVdtFNv-j|v?!l;So$VYkcFA74f4bb=>YCOEje)~K z@fwj4s>EMFwsJ?Du5Ij}mTLD6(9@@2=y$7py6Ut>AjjyzS7FndDx0MU?RF-F1MI{r&y%+|9No8*09<9Q{E( zQY1-QzNQ0XFU?!T@0*W&r>ClIV(a5N;LA|EtD(%q03!gy#DMjwI#jp(dP$en%J~WP vnEHN|Ffv&Ntme&1 | grep "time elapsed" | cut -d s -f 1 | sed 's/+-//' | sed 's/,/./g')" - printf "$(perf stat -r"$repeats" "$1" "fib_recurs.$2" 2>&1 | grep "time elapsed" | cut -d s -f 1 | sed 's/+-//' | sed 's/,/./g')" -} - -cd ~/fib_recurs/ || exit 1 -printf "\"fib recurs\" " -fib_test gwion gw -fib_test lua lua -fib_test wren wren -#fib_test chuck ck -#fib_test ruby rb -#fib_test perl pl -#fib_test python2 py -#fib_test python3 py -#fib_test runhaskell hs diff --git a/help/doc-config.sh b/help/doc-config.sh index 4fccb6af..6f197cec 100644 --- a/help/doc-config.sh +++ b/help/doc-config.sh @@ -1,15 +1,17 @@ title() { TMP=$(head -n 1 $1) - echo ${TMP:2} + sed "s/'/\'/" <<< "${TMP:2}" } list_dir() { + [[ "$1" == */"assets" ]] && return for a in $1/* do - if [ -d "$a" ] - then echo "$2- '$(basename $a | sed 's/[0-9][0-9]_//' | sed 's/_/ /g' | sed 's/-/ /g')':"; list_dir $a "$2 " - else echo "$a" | grep "\.md$" >/dev/null && echo "$2- $(title $a): ${a:5}" - fi + if [ -d "$a" ] + then [[ "$a" == */"assets" ]] || + echo "$2- '$(basename $a | sed 's/[0-9][0-9]_//' | sed 's/_/ /g' | sed 's/-/ /g')':"; list_dir "$a" "$2 " + else echo "$a" | grep "\.md$" >/dev/null && echo "$2- '$(title $a)': ${a:5}" + fi done } diff --git a/tests/benchmark/binary_trees.dart b/tests/benchmark/binary_trees.dart new file mode 100644 index 00000000..f7d52d5f --- /dev/null +++ b/tests/benchmark/binary_trees.dart @@ -0,0 +1,56 @@ +// Ported from the Wren version. + +class Tree { + var _item; + var _left; + var _right; + + Tree(item, depth) { + _item = item; + if (depth > 0) { + var item2 = item + item; + depth--; + _left = new Tree(item2 - 1, depth); + _right = new Tree(item2, depth); + } + } + + get check { + if (_left == null) { + return _item; + } + + return _item + _left.check - _right.check; + } +} + +main() { + var minDepth = 4; + var maxDepth = 12; + var stretchDepth = maxDepth + 1; + + print("stretch tree of depth ${stretchDepth} check: " + "${new Tree(0, stretchDepth).check}"); + + var longLivedTree = new Tree(0, maxDepth); + + // iterations = 2 ** maxDepth + var iterations = 1; + for (var d = 0; d < maxDepth; d++) { + iterations = iterations * 2; + } + + var depth = minDepth; + while (depth < stretchDepth) { + var check = 0; + for (var i = 1; i <= iterations; i++) { + check += new Tree(i, depth).check + new Tree(-i, depth).check; + } + + print("${iterations * 2} trees of depth ${depth} check: ${check}"); + iterations ~/= 4; + depth += 2; + } + + print("long lived tree of depth ${maxDepth} check: ${longLivedTree.check}"); +} diff --git a/tests/benchmark/binary_trees.gw b/tests/benchmark/binary_trees.gw new file mode 100644 index 00000000..7d8c8e30 --- /dev/null +++ b/tests/benchmark/binary_trees.gw @@ -0,0 +1,51 @@ +// Ported from the Wren version. + +class Tree { + int item; + Tree @left, right; + + fun static Tree new_Tree(int it, int depth) { + Tree t; + it => t.item; + if (depth > 0) { + it + it => int item2; + --depth; + Tree.new_Tree(item2 - 1, depth) @=> t.left; + Tree.new_Tree(item2, depth) @=> t.right; + } + return t; + } + + fun int check() { + if (!left) + return item; + return item + left.check() - right.check(); + } +} + +4 => int minDepth; +12 => int maxDepth; +maxDepth + 1 => int stretchDepth; + +<<<"stretch tree of depth ", stretchDepth, " check: ", + Tree.new_Tree(0, stretchDepth).check()>>>; + +Tree.new_Tree(0, maxDepth) @=> Tree@ longLivedTree; + +// iterations = 2 ** maxDepth +1 => int iterations; +for (int d; d < maxDepth; ++d) + 2 *=> iterations; + +minDepth => int depth; +while (depth < stretchDepth) { + int check; + for (int i; i < iterations; ++i) + Tree.new_Tree(i, depth).check() + Tree.new_Tree(-i, depth).check() +=> check; + + <<>>; + 4 /=> iterations; + 2 +=> depth; +} + +<<<"long lived tree of depth ", maxDepth, " check: ", longLivedTree.check()>>>; diff --git a/tests/benchmark/binary_trees.lua b/tests/benchmark/binary_trees.lua new file mode 100644 index 00000000..e690c270 --- /dev/null +++ b/tests/benchmark/binary_trees.lua @@ -0,0 +1,50 @@ +-- The Computer Language Benchmarks Game +-- http://shootout.alioth.debian.org/ +-- contributed by Mike Pall + +local function BottomUpTree(item, depth) + if depth > 0 then + local i = item + item + depth = depth - 1 + local left, right = BottomUpTree(i-1, depth), BottomUpTree(i, depth) + return { item, left, right } + else + return { item } + end +end + +local function ItemCheck(tree) + if tree[2] then + return tree[1] + ItemCheck(tree[2]) - ItemCheck(tree[3]) + else + return tree[1] + end +end + +local N = 12 +local mindepth = 4 +local maxdepth = mindepth + 2 +if maxdepth < N then maxdepth = N end + +do + local stretchdepth = maxdepth + 1 + local stretchtree = BottomUpTree(0, stretchdepth) + io.write(string.format("stretch tree of depth %d check: %d\n", + stretchdepth, ItemCheck(stretchtree))) +end + +local longlivedtree = BottomUpTree(0, maxdepth) + +for depth=mindepth,maxdepth,2 do + local iterations = 2 ^ (maxdepth - depth + mindepth) + local check = 0 + for i=1,iterations do + check = check + ItemCheck(BottomUpTree(1, depth)) + + ItemCheck(BottomUpTree(-1, depth)) + end + io.write(string.format("%d trees of depth %d check: %d\n", + iterations*2, depth, check)) +end + +io.write(string.format("long lived tree of depth %d check: %d\n", + maxdepth, ItemCheck(longlivedtree))) diff --git a/tests/benchmark/binary_trees.py b/tests/benchmark/binary_trees.py new file mode 100644 index 00000000..eb3a9b9a --- /dev/null +++ b/tests/benchmark/binary_trees.py @@ -0,0 +1,46 @@ +# The Computer Language Benchmarks Game +# http://shootout.alioth.debian.org/ +# +# contributed by Antoine Pitrou +# modified by Dominique Wahli +# modified by Heinrich Acker +from __future__ import print_function + +import time + +# Map "range" to an efficient range in both Python 2 and 3. +try: + range = xrange +except NameError: + pass + +def make_tree(item, depth): + if not depth: return item, None, None + item2 = item + item + depth -= 1 + return item, make_tree(item2 - 1, depth), make_tree(item2, depth) + +def check_tree(node): + item, left, right = node + if not left: return item + return item + check_tree(left) - check_tree(right) + +min_depth = 4 +max_depth = 12 +stretch_depth = max_depth + 1 + +print("stretch tree of depth %d check:" % stretch_depth, check_tree(make_tree(0, stretch_depth))) + +long_lived_tree = make_tree(0, max_depth) + +iterations = 2 ** max_depth +for depth in range(min_depth, stretch_depth, 2): + + check = 0 + for i in range(1, iterations + 1): + check += check_tree(make_tree(i, depth)) + check_tree(make_tree(-i, depth)) + + print("%d trees of depth %d check:" % (iterations * 2, depth), check) + iterations //= 4 + +print("long lived tree of depth %d check:" % max_depth, check_tree(long_lived_tree)) diff --git a/tests/benchmark/binary_trees.rb b/tests/benchmark/binary_trees.rb new file mode 100644 index 00000000..2118083c --- /dev/null +++ b/tests/benchmark/binary_trees.rb @@ -0,0 +1,49 @@ +# The Computer Language Shootout Benchmarks +# http://shootout.alioth.debian.org +# +# contributed by Jesse Millikan +# Modified by Wesley Moxam + + +def item_check(left, item, right) + return item if left.nil? + item + item_check(*left) - item_check(*right) +end + +def bottom_up_tree(item, depth) + return [nil, item, nil] unless depth > 0 + item_item = 2 * item + depth -= 1 + [bottom_up_tree(item_item - 1, depth), item, bottom_up_tree(item_item, depth)] +end + +max_depth = 12 +min_depth = 4 + +max_depth = min_depth + 2 if min_depth + 2 > max_depth + +stretch_depth = max_depth + 1 +stretch_tree = bottom_up_tree(0, stretch_depth) + +puts "stretch tree of depth #{stretch_depth} check: #{item_check(*stretch_tree)}" +stretch_tree = nil + +long_lived_tree = bottom_up_tree(0, max_depth) + +min_depth.step(max_depth + 1, 2) do |depth| + iterations = 2**(max_depth - depth + min_depth) + + check = 0 + + for i in 1..iterations + temp_tree = bottom_up_tree(i, depth) + check += item_check(*temp_tree) + + temp_tree = bottom_up_tree(-i, depth) + check += item_check(*temp_tree) + end + + puts "#{iterations * 2} trees of depth #{depth} check: #{check}" +end + +puts "long lived tree of depth #{max_depth} check: #{item_check(*long_lived_tree)}" diff --git a/tests/benchmark/binary_trees.wren b/tests/benchmark/binary_trees.wren new file mode 100644 index 00000000..2393462b --- /dev/null +++ b/tests/benchmark/binary_trees.wren @@ -0,0 +1,51 @@ +// Ported from the Python version. + +class Tree { + construct new(item, depth) { + _item = item + if (depth > 0) { + var item2 = item + item + depth = depth - 1 + _left = Tree.new(item2 - 1, depth) + _right = Tree.new(item2, depth) + } + } + + check { + if (_left == null) { + return _item + } + + return _item + _left.check - _right.check + } +} + +var minDepth = 4 +var maxDepth = 12 +var stretchDepth = maxDepth + 1 + +System.print("stretch tree of depth %(stretchDepth) check: " + + "%(Tree.new(0, stretchDepth).check)") + +var longLivedTree = Tree.new(0, maxDepth) + +// iterations = 2 ** maxDepth +var iterations = 1 +for (d in 0...maxDepth) { + iterations = iterations * 2 +} + +var depth = minDepth +while (depth < stretchDepth) { + var check = 0 + for (i in 1..iterations) { + check = check + Tree.new(i, depth).check + Tree.new(-i, depth).check + } + + System.print("%(iterations * 2) trees of depth %(depth) check: %(check)") + iterations = iterations / 4 + depth = depth + 2 +} + +System.print( + "long lived tree of depth %(maxDepth) check: %(longLivedTree.check)") diff --git a/tests/benchmark/binary_trees_gc.wren b/tests/benchmark/binary_trees_gc.wren new file mode 100644 index 00000000..803202ec --- /dev/null +++ b/tests/benchmark/binary_trees_gc.wren @@ -0,0 +1,55 @@ +// Ported from the Python version. + +class Tree { + construct new(item, depth) { + _item = item + if (depth > 0) { + var item2 = item + item + depth = depth - 1 + _left = Tree.new(item2 - 1, depth) + _right = Tree.new(item2, depth) + } + } + + check { + if (_left == null) { + return _item + } + + return _item + _left.check - _right.check + } +} + +var minDepth = 4 +var maxDepth = 12 +var stretchDepth = maxDepth + 1 + +System.print("stretch tree of depth %(stretchDepth) check: " + + "%(Tree.new(0, stretchDepth).check)") +for (i in 1...1000) System.gc() + +var longLivedTree = Tree.new(0, maxDepth) + +// iterations = 2 ** maxDepth +var iterations = 1 +for (d in 0...maxDepth) { + iterations = iterations * 2 +} + +var depth = minDepth +while (depth < stretchDepth) { + var check = 0 + for (i in 1..iterations) { + check = check + Tree.new(i, depth).check + Tree.new(-i, depth).check + } + + System.print("%(iterations * 2) trees of depth %(depth) check: %(check)") + for (i in 1...1000) System.gc() + + iterations = iterations / 4 + depth = depth + 2 +} + +System.print( + "long lived tree of depth %(maxDepth) check: %(longLivedTree.check)") +for (i in 1...1000) System.gc() -- 2.43.0