Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
package main
import (
"flag"
"fmt"
"log"
"os"
"runtime/pprof"
"strconv"
"sync"
"time"
)
var minDepth = 4
var n = 0
var cpuprofile = flag.String("cpuprofile", "", "write cpu profile to file")
var (
nodeBuf []Node
nodeBufIdx int32
)
type Allocator struct {
nodes []Node
idx int
}
func calcNodeCount(depth int) int {
res := 1 << (uint(depth + 1))
return res - 1
}
func NewAllocatorWithCount(cap int) *Allocator {
return &Allocator{
nodes: make([]Node, cap, cap),
idx: 0,
}
}
func (a *Allocator) PrintUnused() {
left := cap(a.nodes) - a.idx
if left > 0 {
fmt.Printf("left: %d out of %d\n", left, cap(a.nodes))
}
}
func NewAllocatorWithDepth(depth int) *Allocator {
cap := calcNodeCount(depth)
return NewAllocatorWithCount(cap)
}
func (a *Allocator) Reset() {
a.idx = 0
}
func (a *Allocator) allocNode(item int, left, right *Node) *Node {
res := &a.nodes[a.idx]
a.idx++
res.item = item
res.left = left
res.right = right
return res
}
func main() {
timeStart := time.Now()
flag.Parse()
if flag.NArg() > 0 {
n, _ = strconv.Atoi(flag.Arg(0))
}
if *cpuprofile != "" {
f, err := os.Create(*cpuprofile)
if err != nil {
log.Fatal(err)
}
pprof.StartCPUProfile(f)
defer pprof.StopCPUProfile()
}
maxDepth := n
if minDepth+2 > n {
maxDepth = minDepth + 2
}
stretchDepth := maxDepth + 1
a := NewAllocatorWithDepth(stretchDepth)
check_l := bottomUpTree(a, 0, stretchDepth).ItemCheck()
fmt.Printf("stretch tree of depth %d\t check: %d\n", stretchDepth, check_l)
a.PrintUnused()
a = NewAllocatorWithDepth(maxDepth)
longLivedTree := bottomUpTree(a, 0, maxDepth)
a.PrintUnused()
result_trees := make([]int, maxDepth+1)
result_check := make([]int, maxDepth+1)
var wg sync.WaitGroup
for depth_l := minDepth; depth_l <= maxDepth; depth_l += 2 {
wg.Add(1)
go func(depth int) {
iterations := 1 << uint(maxDepth-depth+minDepth)
check := 0
//n := calcNodeCount(depth) * 2 * iterations
//fmt.Printf("depth: %d, iterations: %d, nodes: %d\n", depth, iterations, n)
a := NewAllocatorWithDepth(depth)
for i := 1; i <= iterations; i++ {
a.Reset()
check += bottomUpTree(a, i, depth).ItemCheck()
a.Reset()
check += bottomUpTree(a, -i, depth).ItemCheck()
}
result_trees[depth] = iterations * 2
result_check[depth] = check
a.PrintUnused()
wg.Done()
}(depth_l)
}
wg.Wait()
for depth := minDepth; depth <= maxDepth; depth += 2 {
fmt.Printf("%d\t trees of depth %d\t check: %d\n",
result_trees[depth], depth, result_check[depth],
)
}
fmt.Printf("long lived tree of depth %d\t check: %d\n",
maxDepth, longLivedTree.ItemCheck(),
)
fmt.Printf("dur: %s\n", time.Since(timeStart))
}
func bottomUpTree(a *Allocator, item, depth int) *Node {
if depth <= 0 {
return a.allocNode(item, nil, nil)
}
left := bottomUpTree(a, 2*item-1, depth-1)
right := bottomUpTree(a, 2*item, depth-1)
return a.allocNode(item, left, right)
}
type Node struct {
item int
left, right *Node
}
func (self *Node) ItemCheck() int {
if self.left == nil {
return self.item
}
return self.item + self.left.ItemCheck() - self.right.ItemCheck()
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.