-
Notifications
You must be signed in to change notification settings - Fork 6
/
sort.go
109 lines (90 loc) · 2.62 KB
/
sort.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
package main
import (
"fmt"
"hash/maphash"
"log"
"math/rand"
"sort"
)
// Arbitrary seed
const SORT_SEED = 1234
const SORT_N = 1024
// BenchSort is a sorting benchmark using the standard library facilities.
// Items
type BenchSort struct {
array []SortItem
r *rand.Rand
h uint64
hseed maphash.Seed
}
// SortItem includes local and remote memory. We sort the structures using strings and integers.
// The size of the structure is not trivial to put a bit more pressure on memory.
type SortItem struct {
firstname string
lastname string
id int
blob [128]byte
}
// ByFirst enforces firstname order
type ByFirst []SortItem
func (a ByFirst) Len() int { return len(a) }
func (a ByFirst) Swap(i, j int) { a[i], a[j] = a[j], a[i] }
func (a ByFirst) Less(i, j int) bool { return a[i].firstname < a[j].firstname }
// ByLast enforces lastname order
type ByLast []SortItem
func (a ByLast) Len() int { return len(a) }
func (a ByLast) Swap(i, j int) { a[i], a[j] = a[j], a[i] }
func (a ByLast) Less(i, j int) bool { return a[i].lastname < a[j].lastname }
// ById enforces id order
type ById []SortItem
func (a ById) Len() int { return len(a) }
func (a ById) Swap(i, j int) { a[i], a[j] = a[j], a[i] }
func (a ById) Less(i, j int) bool { return a[i].id < a[j].id }
// NewBenchSort creates a new sorting benchmark
func NewBenchSort() *BenchSort {
// Fill the structures with pseudo-random (but seeded) data
r := rand.New(rand.NewSource(SORT_SEED))
items := make([]SortItem, SORT_N)
for i := 0; i < len(items); i++ {
x := &(items[i])
x.firstname = fmt.Sprintf("%016x", r.Int63())
x.lastname = fmt.Sprintf("%016X", r.Int63())
x.id = i
if n, err := r.Read(x.blob[:]); err != nil || n != 128 {
log.Fatal("Wrond rand read")
}
}
res := &BenchSort{
array: items,
r: r,
hseed: maphash.MakeSeed(),
}
// Calculate a hash corresponding to all the records in id order
res.h = res.sortHash()
return res
}
// Run the sorting benchmark
func (b *BenchSort) Run() {
// Shuffle the slice of records
b.r.Seed(SORT_SEED)
b.r.Shuffle(SORT_N, func(i, j int) {
b.array[i], b.array[j] = b.array[j], b.array[i]
})
// Sort in various orders
sort.Sort(ByFirst(b.array))
sort.Sort(ByLast(b.array))
sort.Sort(ById(b.array))
// We should be back in the initial order (by id), so calculate a hash and check
if b.sortHash() != b.h {
log.Fatal("Hash discrepancy")
}
}
// sortHash calculate a hash code of all the records
func (b *BenchSort) sortHash() uint64 {
var h maphash.Hash
h.SetSeed(b.hseed)
for i := range b.array {
h.Write(b.array[i].blob[:])
}
return h.Sum64()
}