source code
// The Computer Language Benchmarks Game
// https://salsa.debian.org/benchmarksgame-team/benchmarksgame/
//
// contributed by Marek Safar
// concurrency added by Peperud
// fixed long-lived tree by Anthony Lloyd
// ported from F# version by Anthony Lloyd
// ported from C# version by wasmup
package main
import (
"fmt"
"os"
"sync"
)
type node struct {
next *next
}
type next struct {
left, right node
}
func create(d int) node {
if d == 1 {
return node{&next{node{}, node{}}}
}
return node{&next{create(d - 1), create(d - 1)}}
}
func (p node) check() int {
sum := 1
current := p.next
for current != nil {
sum += current.right.check() + 1
current = current.left.next
}
return sum
}
func main() {
const MinDepth = 4
const NoTasks = 4
maxDepth := 10
if len(os.Args) > 1 {
_, err := fmt.Sscan(os.Args[1], &maxDepth)
if err != nil {
panic(err)
}
if MinDepth+2 > maxDepth {
maxDepth = MinDepth + 2
}
}
longLivedTree := create(maxDepth)
stretchTreeCheck := ""
wg := new(sync.WaitGroup)
wg.Add(1)
go func() {
stretchDepth := maxDepth + 1
stretchTreeCheck = fmt.Sprintf("stretch tree of depth %d\t check: %d",
stretchDepth, create(stretchDepth).check())
wg.Done()
}()
results := make([]string, (maxDepth-MinDepth)/2+1)
for i := range results {
depth := 2*i + MinDepth
n := (1 << (maxDepth - depth + MinDepth)) / NoTasks
tasks := make([]int, NoTasks)
for t := range tasks {
wg.Add(1)
go func(t int) {
check := 0
for i := n; i > 0; i-- {
check += create(depth).check()
}
tasks[t] = check
wg.Done()
}(t)
}
wg.Wait()
check := 0
for _, v := range tasks {
check += v
}
results[i] = fmt.Sprintf("%d\t trees of depth %d\t check: %d",
n*NoTasks, depth, check)
}
fmt.Println(stretchTreeCheck)
for _, s := range results {
fmt.Println(s)
}
fmt.Printf("long lived tree of depth %d\t check: %d\n",
maxDepth, longLivedTree.check())
}
notes, command-line, and program output
NOTES:
64-bit Ubuntu quad core
go version go1.16 linux/amd64
Tue, 23 Mar 2021 17:49:07 GMT
MAKE:
/opt/src/go1.16/go/bin/go build -o binarytrees.go-4.go_run binarytrees.go-4.go
2.64s to complete and log all make actions
COMMAND LINE:
./binarytrees.go-4.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