From 236b06a88f709ca6c70ce0c7adfb57f9f0b2a60d Mon Sep 17 00:00:00 2001
From: Thibaut Horel <thibaut.horel@gmail.com>
Date: Wed, 11 May 2016 22:03:53 -0400
Subject: Add final code used during experiments

---
 graph.go  | 216 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 main.py   |  36 +++++++++++
 proof.py  |  33 ++++++++++
 proof2.py |  36 +++++++++++
 test.sh   |  28 ++++++++
 5 files changed, 349 insertions(+)
 create mode 100644 graph.go
 create mode 100644 main.py
 create mode 100644 proof.py
 create mode 100644 proof2.py
 create mode 100644 test.sh

diff --git a/graph.go b/graph.go
new file mode 100644
index 0000000..92f44a1
--- /dev/null
+++ b/graph.go
@@ -0,0 +1,216 @@
+package posgraph
+
+import (
+	"encoding/binary"
+	"fmt"
+	"os"
+
+	"github.com/boltdb/bolt"
+	// "reflect"
+	// "unsafe"
+)
+
+const (
+	TYPE1 = iota
+	EGS   = iota
+	TYPE2 = iota
+)
+
+// creating another DB type so it's easier to change underlying DB later
+type DB struct {
+	db *bolt.DB
+}
+
+type Graph_ struct {
+	fn string
+	db DB
+
+	index int64
+	log2  int64
+	pow2  int64
+	size  int64
+
+	t int //type of the graph
+}
+
+type Graph interface {
+	NewNodeP(id int64, parents []int64)
+	GetParents(id int64) []int64
+	NewNodeA(id int64, adjlist []int64)
+	GetAdjacency(id int64) []int64
+	GetSize() int64
+	GetDB() DB
+	ChangeDB(DB)
+	Close()
+}
+
+// Generate a new PoS graph of index
+// Currently only supports the weaker PoS graph
+// Note that this graph will have O(2^index) nodes
+func NewGraph(t int, dir string, index int64) Graph {
+	var fn string
+	if t == TYPE1 {
+		fn = fmt.Sprintf("%s/T1-%d", dir, index)
+	} else if t == EGS {
+		fn = fmt.Sprintf("%s/EGS-%d", dir, index)
+	} else if t == TYPE2 {
+		fn = fmt.Sprintf("%s/T2-%d", dir, index)
+	}
+
+	_, err := os.Stat(fn)
+	fileExists := err == nil
+
+	var db *bolt.DB
+	if fileExists { //open it as read only
+		db, err = bolt.Open(fn, 0600, &bolt.Options{ReadOnly: true})
+	} else {
+		db, err = bolt.Open(fn, 0600, nil)
+	}
+	if err != nil {
+		panic("Failed to open database")
+	}
+
+	db.Update(func(tx *bolt.Tx) error {
+		_, err := tx.CreateBucket([]byte("Parents"))
+		if err != nil {
+			return fmt.Errorf("create bucket: %s", err)
+		}
+		return nil
+	})
+	db.Update(func(tx *bolt.Tx) error {
+		_, err := tx.CreateBucket([]byte("Adjlist"))
+		if err != nil {
+			return fmt.Errorf("create bucket: %s", err)
+		}
+		return nil
+	})
+
+	var g Graph
+	if t == TYPE1 {
+		g = NewType1Graph(t, !fileExists, index, DB{db})
+	} else if t == EGS {
+		//'index' for EGS is overloaded to be size
+		g = NewEGSGraph(t, !fileExists, index, DB{db})
+	} else if t == TYPE2 {
+		g = NewType2Graph(t, !fileExists, index, DB{db})
+	}
+
+	// a hack for testing; graph should be opened for read only after gen
+	g.Close()
+	db, err = bolt.Open(fn, 0600, &bolt.Options{ReadOnly: true})
+	if err != nil {
+		panic("Failed to open database")
+	}
+	g.ChangeDB(DB{db})
+
+	return g
+}
+
+func (g *Graph_) NewNodeP(node int64, parents []int64) {
+	// header := *(*reflect.SliceHeader)(unsafe.Pointer(&parents))
+	// header.Len *= 8
+	// header.Cap *= 8
+	// data := *(*[]byte)(unsafe.Pointer(&header))
+	// log.Println("New node:", node, parents)
+
+	key := make([]byte, 8)
+	binary.PutVarint(key, node)
+	data := make([]byte, len(parents)*8)
+	for i := range parents {
+		binary.PutVarint(data[i*8:(i+1)*8], parents[i])
+	}
+
+	g.db.db.Update(func(tx *bolt.Tx) error {
+		b := tx.Bucket([]byte("Parents"))
+		err := b.Put(key, data)
+		return err
+	})
+}
+
+func (g *Graph_) NewNodeA(id int64, adjlist []int64) {
+	// header := *(*reflect.SliceHeader)(unsafe.Pointer(&parents))
+	// header.Len *= 8
+	// header.Cap *= 8
+	// data := *(*[]byte)(unsafe.Pointer(&header))
+	// log.Println("New node:", id, parents)
+
+	key := make([]byte, 8)
+	binary.PutVarint(key, id)
+	data := make([]byte, len(adjlist)*8)
+	for i := range adjlist {
+		binary.PutVarint(data[i*8:(i+1)*8], adjlist[i])
+	}
+
+	g.db.db.Update(func(tx *bolt.Tx) error {
+		b := tx.Bucket([]byte("Adjlist"))
+		err := b.Put(key, data)
+		return err
+	})
+}
+
+func (g *Graph_) GetParents(id int64) []int64 {
+	// first pow2 nodes are srcs in TYPE1
+	if g.t == TYPE1 && id < int64(1<<uint64(g.index)) {
+		return nil
+	}
+
+	key := make([]byte, 8)
+	binary.PutVarint(key, id)
+
+	var data []byte
+	g.db.db.View(func(tx *bolt.Tx) error {
+		b := tx.Bucket([]byte("Parents"))
+		d := b.Get(key)
+		data = make([]byte, len(d))
+		copy(data, d)
+		return nil
+	})
+
+	parents := make([]int64, len(data)/8)
+	for i := range parents {
+		parents[i], _ = binary.Varint(data[i*8 : (i+1)*8])
+	}
+
+	return parents
+}
+
+func (g *Graph_) GetAdjacency(id int64) []int64 {
+	key := make([]byte, 8)
+	binary.PutVarint(key, id)
+
+	var data []byte
+	g.db.db.View(func(tx *bolt.Tx) error {
+		b := tx.Bucket([]byte("Adjlist"))
+		d := b.Get(key)
+		data = make([]byte, len(d))
+		copy(data, d)
+		return nil
+	})
+
+	adjlist := make([]int64, len(data)/8)
+	for i := range adjlist {
+		adjlist[i], _ = binary.Varint(data[i*8 : (i+1)*8])
+	}
+
+	return adjlist
+}
+
+func (g *Graph_) GetSize() int64 {
+	return g.size
+}
+
+func (g *Graph_) GetDB() DB {
+	return g.db
+}
+
+func (g *Graph_) GetType() int {
+	return g.t
+}
+
+func (g *Graph_) ChangeDB(db DB) {
+	g.db = db
+}
+
+func (g *Graph_) Close() {
+	g.db.db.Close()
+}
diff --git a/main.py b/main.py
new file mode 100644
index 0000000..c37c288
--- /dev/null
+++ b/main.py
@@ -0,0 +1,36 @@
+import numpy as np
+import matplotlib.pyplot as plt
+import seaborn
+import matplotlib
+
+seaborn.set_style("white")
+
+matplotlib.rcParams.update({'xtick.labelsize': 12})
+matplotlib.rcParams.update({'ytick.labelsize': 12})
+matplotlib.rcParams.update({'legend.fontsize': 12})
+matplotlib.rcParams.update({'axes.titlesize': 12})
+matplotlib.rcParams.update({'axes.labelsize': 12})
+
+with open("time.txt") as fh:
+    values = [line.split() for line in fh]
+
+h, post, bfs = zip(*values)
+plt.plot(h, post, label="DF")
+plt.plot(h, bfs, label="BF")
+plt.legend()
+plt.xlabel("height")
+plt.ylabel("runtime (s)")
+plt.savefig("time.pdf", bbox_inches='tight')
+
+plt.clf()
+with open("misses.txt") as fh:
+    values = [line.split() for line in fh]
+h, bfs, post = zip(*values)
+plt.plot(h, post, label="DF")
+plt.plot(h, bfs, label="BF")
+plt.legend()
+plt.xlabel("height")
+plt.ylabel("cache-misses")
+plt.savefig("misses.pdf", bbox_inches='tight')
+
+print h, post, bfs
diff --git a/proof.py b/proof.py
new file mode 100644
index 0000000..96cdd00
--- /dev/null
+++ b/proof.py
@@ -0,0 +1,33 @@
+#!/usr/bin/env python
+import numpy as np
+import matplotlib.pyplot as plt
+import matplotlib
+import seaborn
+
+seaborn.set_style("white")
+matplotlib.rcParams.update({'xtick.labelsize': 12})
+matplotlib.rcParams.update({'ytick.labelsize': 12})
+matplotlib.rcParams.update({'legend.fontsize': 12})
+matplotlib.rcParams.update({'axes.titlesize': 12})
+matplotlib.rcParams.update({'axes.labelsize': 12})
+
+N = 3
+bf = (915544, 557179, 141672)
+df = (886501, 528297, 107256)
+
+ind = np.arange(N)  # the x locations for the groups
+width = 0.25       # the width of the bars
+
+fig, ax = plt.subplots()
+rects1 = ax.bar(ind-width, df, width)
+rects2 = ax.bar(ind, bf, width, color='g')
+
+
+# add some text for labels, title and axes ticks
+ax.set_ylabel('Time per proof (ns)')
+ax.set_xlabel('# proofs')
+ax.set_xticks(ind)
+ax.set_xticklabels(('2000', '20000', '200000'))
+
+ax.legend((rects1[0], rects2[0]), ('DF', 'BF'))
+plt.savefig("proofs.pdf", bbox_inches='tight')
diff --git a/proof2.py b/proof2.py
new file mode 100644
index 0000000..7fe92d9
--- /dev/null
+++ b/proof2.py
@@ -0,0 +1,36 @@
+#!/usr/bin/env python
+import numpy as np
+import matplotlib.pyplot as plt
+import matplotlib
+import seaborn
+
+seaborn.set_style("white")
+matplotlib.rcParams.update({'xtick.labelsize': 12})
+matplotlib.rcParams.update({'ytick.labelsize': 12})
+matplotlib.rcParams.update({'legend.fontsize': 12})
+matplotlib.rcParams.update({'axes.titlesize': 12})
+matplotlib.rcParams.update({'axes.labelsize': 12})
+
+N = 3
+
+naive = (973166, 528297, 107256)
+sorte = (951139, 391564, 21161)
+explicit = (742536, 249948, 25932)
+
+ind = np.arange(N)  # the x locations for the groups
+width = 0.25       # the width of the bars
+
+fig, ax = plt.subplots()
+rects1 = ax.bar(ind-1.5*width, naive, width)
+rects2 = ax.bar(ind-0.5*width, sorte, width, color='g')
+rects3 = ax.bar(ind+0.5*width, explicit, width, color='r')
+
+
+# add some text for labels, title and axes ticks
+ax.set_ylabel('Time per proof (ns)')
+ax.set_xlabel('# proofs')
+ax.set_xticks(ind)
+ax.set_xticklabels(('2000', '20000', '200000'))
+
+ax.legend((rects1[0], rects2[0], rects3[0]), ('Naive', 'Sorted', 'Explicit'))
+plt.savefig("proofs2.pdf", bbox_inches='tight')
diff --git a/test.sh b/test.sh
new file mode 100644
index 0000000..6406091
--- /dev/null
+++ b/test.sh
@@ -0,0 +1,28 @@
+rm /mnt/data/test.db
+perf stat -e cache-misses,cache-references,instructions,faults,cycles,branches,branch-misses -o runs/bfs-22.stat ./project -db /mnt/data/test.db -mtype bfs -height 22
+rm /mnt/data/test.db
+perf stat -e cache-misses,cache-references,instructions,faults,cycles,branches,branch-misses -o runs/post-22.stat ./project -db /mnt/data/test.db -mtype post -height 22
+rm /mnt/data/test.db
+perf stat -e cache-misses,cache-references,instructions,faults,cycles,branches,branch-misses -o runs/bfs-24.stat ./project -db /mnt/data/test.db -mtype bfs -height 24
+rm /mnt/data/test.db
+perf stat -e cache-misses,cache-references,instructions,faults,cycles,branches,branch-misses -o runs/post-24.stat ./project -db /mnt/data/test.db -mtype post -height 24
+rm /mnt/data/test.db
+perf stat -e cache-misses,cache-references,instructions,faults,cycles,branches,branch-misses -o runs/bfs-25.stat ./project -db /mnt/data/test.db -mtype bfs -height 25
+rm /mnt/data/test.db
+perf stat -e cache-misses,cache-references,instructions,faults,cycles,branches,branch-misses -o runs/post-25.stat ./project -db /mnt/data/test.db -mtype post -height 25
+rm /mnt/data/test.db
+perf stat -e cache-misses,cache-references,instructions,faults,cycles,branches,branch-misses -o runs/bfs-26.stat ./project -db /mnt/data/test.db -mtype bfs -height 26
+rm /mnt/data/test.db
+perf stat -e cache-misses,cache-references,instructions,faults,cycles,branches,branch-misses -o runs/post-26.stat ./project -db /mnt/data/test.db -mtype post -height 26
+rm /mnt/data/test.db
+perf stat -e cache-misses,cache-references,instructions,faults,cycles,branches,branch-misses -o runs/bfs-27.stat ./project -db /mnt/data/test.db -mtype bfs -height 27
+rm /mnt/data/test.db
+perf stat -e cache-misses,cache-references,instructions,faults,cycles,branches,branch-misses -o runs/post-27.stat ./project -db /mnt/data/test.db -mtype post -height 27
+rm /mnt/data/test.db
+perf stat -e cache-misses,cache-references,instructions,faults,cycles,branches,branch-misses -o runs/bfs-30.stat ./project -db /mnt/data/test.db -mtype bfs -height 30
+rm /mnt/data/test.db
+perf stat -e cache-misses,cache-references,instructions,faults,cycles,branches,branch-misses -o runs/post-30.stat ./project -db /mnt/data/test.db -mtype post -height 30
+rm /mnt/data/test.db
+perf stat -e cache-misses,cache-references,instructions,faults,cycles,branches,branch-misses -o runs/bfs-31.stat ./project -db /mnt/data/test.db -mtype bfs -height 31
+rm /mnt/data/test.db
+perf stat -e cache-misses,cache-references,instructions,faults,cycles,branches,branch-misses -o runs/post-31.stat ./project -db /mnt/data/test.db -mtype post -height 31
-- 
cgit v1.2.3-70-g09d2