tests/benchmark/binarytrees.slate

   1 prototypes ensureNamespace: #benchmark &delegate: True.
   2
   3 benchmark define: #TreeNode &slots: {
   4   #left.
   5   #right.
   6   #item.
   7 }.
   8
   9 n@(benchmark TreeNode traits) bottomUpTree: i@(Integer traits) depth: d@(Integer traits)
  10 [
  11   d > 0
  12     ifTrue:
  13       [a ::= 2 * i. b ::= a - 1. c ::= d - 1.
  14        n new &left: (n bottomUpTree: b depth: c) &right: (n bottomUpTree: a depth: c) &item: i]
  15     ifFalse: [n new &left: Nil &right: Nil &item: i]
  16 ].
  17
  18 n@(benchmark TreeNode traits) new &left: l &right: r &item: i
  19 [
  20   n clone `>> [left := l. right := r. item := i. ]
  21 ].
  22
  23 n@(benchmark TreeNode traits) checkItem
  24 [
  25   n left isNil
  26     ifTrue: [n item]
  27     ifFalse: [n item + (n left checkItem - n right checkItem)]
  28 ].
  29
  30 n@(Integer traits) binaryTrees
  31 [| check iterations |
  32   minDepth ::= 4.
  33   maxDepth ::= minDepth + 2 max: n.
  34   stretchDepth ::= maxDepth + 1.
  35   check := (benchmark TreeNode bottomUpTree: 0 depth: stretchDepth) checkItem.
  36   longLivedTree ::= benchmark TreeNode bottomUpTree: 0 depth: maxDepth.
  37   minDepth upTo: maxDepth by: 2 do:
  38     [| :depth |
  39      iterations := 1 bitShift: maxDepth - depth + minDepth.
  40      check := 0.
  41      1 upTo: iterations do:
  42        [| :i |
  43         check += (benchmark TreeNode bottomUpTree: i depth: depth) checkItem.
  44         check += (benchmark TreeNode bottomUpTree: (-1 * i) depth: depth) checkItem
  45       ]
  46    ].
  47 ].