The Computer Language
Benchmarks Game

binary-trees Go #4 program

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