Skip to content

Instantly share code, notes, and snippets.

@kjk
Created December 29, 2016 09:05
Show Gist options
  • Save kjk/4620bf60315d3fdd3f210e4590bdf1cb to your computer and use it in GitHub Desktop.
Save kjk/4620bf60315d3fdd3f210e4590bdf1cb to your computer and use it in GitHub Desktop.
package main
import (
"flag"
"fmt"
"log"
"os"
"runtime/debug"
"runtime/pprof"
"strconv"
"sync"
"time"
)
var minDepth = 4
var n = 0
var cpuprofile = flag.String("cpuprofile", "", "write cpu profile to file")
const nodesCount = 1024 * 32
var (
nodeBuf []Node
nodeBufIdx int32
)
type Allocator struct {
nodes []Node
idx int
cap int
}
func NewAllocatorWithCapacity(cap int) *Allocator {
return &Allocator{
nodes: make([]Node, cap, cap),
cap: cap,
idx: 0,
}
}
func NewAllocator() *Allocator {
return NewAllocatorWithCapacity(nodesCount)
}
func (a *Allocator) allocNode(item int, left, right *Node) *Node {
if a.idx >= a.cap-1 {
a.nodes = make([]Node, a.cap)
a.idx = 0
}
res := &a.nodes[a.idx]
a.idx++
res.item = item
res.left = left
res.right = right
return res
}
func main() {
//runtime.GOMAXPROCS(runtime.NumCPU() * 2)
debug.SetGCPercent(-1)
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 := NewAllocator()
check_l := bottomUpTree(a, 0, stretchDepth).ItemCheck()
fmt.Printf("stretch tree of depth %d\t check: %d\n", stretchDepth, check_l)
longLivedTree := bottomUpTree(a, 0, maxDepth)
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
a := NewAllocator()
for i := 1; i <= iterations; i++ {
check += bottomUpTree(a, i, depth).ItemCheck()
check += bottomUpTree(a, -i, depth).ItemCheck()
}
result_trees[depth] = iterations * 2
result_check[depth] = check
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