-
Notifications
You must be signed in to change notification settings - Fork 1
/
allocator.go
124 lines (103 loc) · 3.69 KB
/
allocator.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
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
package goskip
import (
"sync/atomic"
"unsafe"
)
/*
Don't forget about cpu cache model. Write code that works with it not works against it!
Optimize for x64.
==Data Padding:
Problem:
You have a data structure that does not fit nicely into the
cache line of the machine. When you parallelize your code,
your performance suffers because of false sharing. How do
you transform your code to reduce false sharing and improve
overall performance?
Solution:
Pad your data structure with extraneous “padding” data.
Padding data do not contribute to the functionality of your
program; they only expand the size of your data structure
so that it fits into an entire cache line In effect, this grants
your data exclusivity to the entire cache line.
==Data Alignment:
Problem:
You have a data structure that could fit within a cache
line but has been allocated such that it crosses the boundary
of a cache line incurring an additional overhead.
All primitive data types (int, char, float, double) have a
natural alignment within memory
Solution:
Align your data structure so that it starts on a cache line
boundary. Similar to Data Padding, you should set the
alignment to the size of the cache line.
*/
// Default size of the node type, in bytes.
// This value will be used for allocating memory for node.
const defaultNodeSize = uint32(unsafe.Sizeof(node{}))
// 0 means nil pointer for offsets of Allocator.
const nilAllocatorOffset = uint32(0)
const initialAllocatorOffset = uint32(1)
// const cacheLineSize = 64
// const paddingLimit = 15
type Allocator struct {
// Actual memory space where we keep the data.
mem []byte
// Pointer to the beginning of available memory.
// Max addressable memory 2^32 = 4GB.
offset uint32
}
// newAllocator allocates a buffer with given size and returns a new allocator.
func newAllocator(size uint32) *Allocator {
// Set initial offset as 1 since 0 is used for nil pointers.
return &Allocator{make([]byte, size), initialAllocatorOffset}
}
// new reserves a block on memory and returns offset to it.
func (allc *Allocator) new(size uint32) uint32 {
// Multiple goroutines might modify offset value.
// We need to calculate new offset atomically.
// TODO overflow
newOffset := atomic.AddUint32(&allc.offset, size)
return newOffset - size
}
// putBytes will copy given value into mem and return offset.
func (allc *Allocator) putBytes(val []byte) uint32 {
valSize := uint32(len(val))
// Add padding for increasing cache performance.
/*padding := valSize % cacheLineSize
if padding < paddingLimit {
valSize += padding
}*/
offset := allc.new(valSize)
copy(allc.mem[offset:], val)
return offset
}
// putBytesTo will copy given value into given memory offset.
func (allc *Allocator) putBytesTo(offset uint32, val []byte) {
copy(allc.mem[offset:], val)
}
// makeNode will allocate required space for node type.
// The offset of the node in the mem is returned.
func (allc *Allocator) makeNode(truncatedSize uint32) uint32 {
// Calculate the amount of actual memory required for this node.
// Depending on the height of the node, size might be truncated.
size := defaultNodeSize - truncatedSize
/*padding := size % cacheLineSize
if padding < paddingLimit {
size += padding
}*/
return allc.new(size)
}
// getBytes returns the byte slice in mem[offset:offset+size]
func (allc *Allocator) getBytes(offset uint32, size uint32) []byte {
return allc.mem[offset : offset+size]
}
// getNode returns a pointer to the node at given offset.
func (allc *Allocator) getNode(offset uint32) *node {
if offset == nilAllocatorOffset {
return nil
}
return (*node)(unsafe.Pointer(&allc.mem[offset]))
}
func (allc *Allocator) getOffset() uint32 {
return atomic.LoadUint32(&allc.offset)
}