diff options
| -rw-r--r-- | graph.go | 216 | ||||
| -rw-r--r-- | main.py | 36 | ||||
| -rw-r--r-- | proof.py | 33 | ||||
| -rw-r--r-- | proof2.py | 36 | ||||
| -rw-r--r-- | test.sh | 28 |
5 files changed, 349 insertions, 0 deletions
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() +} @@ -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') @@ -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 |