The Computer Language
Benchmarks Game

binary-trees Go #9 program

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