source code
/* The Computer Language Benchmarks Game
* https://salsa.debian.org/benchmarksgame-team/benchmarksgame/
*
* Contributed by Alexandr Karbivnichiy
* main thread stretch tree / longLivedTree by Isaac Gouy
*/
package main
import (
"flag"
"fmt"
"sort"
"strconv"
"sync"
)
type Node struct {
next *Next
}
type Next struct {
left, right Node
}
func createTree(depth int) Node {
if depth > 1 {
return Node{&Next{createTree(depth - 1), createTree(depth - 1)}}
}
return Node{&Next{Node{}, Node{}}}
}
func checkTree(node Node) int {
sum := 1
current := node.next
for current != nil {
sum += checkTree(current.right) + 1
current = current.left.next
}
return sum
}
func main() {
n := 0
flag.Parse()
if flag.NArg() > 0 {
n, _ = strconv.Atoi(flag.Arg(0))
}
run(n)
}
func run(maxDepth int) {
const minDepth = 4
var longLivedTree Node
var group sync.WaitGroup
var messages sync.Map
if minDepth+2 > maxDepth {
maxDepth = minDepth + 2
}
messages.Store(-1, fmt.Sprintf("stretch tree of depth %d\t check: %d",
maxDepth+1, checkTree(createTree(maxDepth+1))))
longLivedTree = createTree(maxDepth)
for halfDepth := minDepth / 2; halfDepth < maxDepth/2+1; halfDepth++ {
iters := 1 << (maxDepth - (halfDepth * 2) + minDepth)
group.Add(1)
go func(depth, iters, chk int) {
for i := 0; i < iters; i++ {
chk += checkTree(createTree(depth))
}
messages.Store(depth, fmt.Sprintf("%d\t trees of depth %d\t check: %d",
iters, depth, chk))
group.Done()
}(halfDepth*2, iters, 0)
}
group.Wait()
var idxs []int
messages.Range(func(key, val interface{}) bool {
idxs = append(idxs, key.(int))
return true
})
sort.Ints(idxs)
for _, idx := range idxs {
msg, _ := messages.Load(idx)
fmt.Println(msg)
}
fmt.Printf("long lived tree of depth %d\t check: %d\n",
maxDepth, checkTree(longLivedTree))
}
notes, command-line, and program output
NOTES:
64-bit Ubuntu quad core
go version go1.16 linux/amd64
Tue, 23 Mar 2021 17:49:53 GMT
MAKE:
/opt/src/go1.16/go/bin/go build -o binarytrees.go-9.go_run binarytrees.go-9.go
2.85s to complete and log all make actions
COMMAND LINE:
./binarytrees.go-9.go_run 21
PROGRAM OUTPUT:
stretch tree of depth 22 check: 8388607
2097152 trees of depth 4 check: 65011712
524288 trees of depth 6 check: 66584576
131072 trees of depth 8 check: 66977792
32768 trees of depth 10 check: 67076096
8192 trees of depth 12 check: 67100672
2048 trees of depth 14 check: 67106816
512 trees of depth 16 check: 67108352
128 trees of depth 18 check: 67108736
32 trees of depth 20 check: 67108832
long lived tree of depth 21 check: 4194303