-
Notifications
You must be signed in to change notification settings - Fork 119
/
pool.ljs
236 lines (210 loc) · 6.02 KB
/
pool.ljs
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
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
extern Uint16Array;
extern Uint32Array;
extern Math;
extern undefined;
extern Object;
/**
* We cannot store references to JavaScript objects in the LLJS heap. We need a way to
* manage all the JS objects that enter the LLJS heap using some kind of reference counting
* scheme, hence this reference counted object pool.
*
* Manages a reference counted pool of objects. It maintains a bi-directional mapping of
* numeric IDs to Objects. Each object in the pool is given an unique ID that is stored
* as a property in the object. The mapping from IDs to Objects is done using a dense
* object array stored in the pool.
*
* The trick is to reuse objecet IDs so that the dense object map doesn't get too large.
* This is done using a |bit| map that keeps track of available object IDs. Searching for
* a new ID is done using a wrap-around linear scan through the bit map, starting at the
* |nextWord| position which is updated whenever an ID is freed or found.
*
* The pool provides three functions:
*
* acquire (obj) adds the |obj| to the pool, increments the reference count and returns its ID.
* release (obj) decrements the reference count and removes the object if the count is zero.
* get (id) returns the object with the given |id|.
*
*/
let Pool = (function (initialSize) {
let obj = []; /* ID to Object Map */
let ref; /* Reference Count Map */
let bit; /* Used ID Bit Map */
let size = 0;
let resizeCount = 0;
const MIN_SIZE = 1024;
function resize(newSize) {
let oldRef = ref;
ref = new Uint16Array(newSize);
if (oldRef) {
ref.set(oldRef);
}
let oldBit = bit;
bit = new Uint32Array(Math.ceil(newSize / 32));
if (oldBit) {
bit.set(oldBit);
}
size = newSize;
resizeCount ++;
}
resize(Math.max(initialSize, MIN_SIZE));
/**
* Tidy uses defineProperty to add IDs to objects when they are aquired and delete to
* remove their IDs when they are released. This is slightly slower than leaving the
* ID property behind.
*/
const tidy = false;
const OBJECT_ID_NAME = "OBJECT ID";
function bitCount(v) {
v = v - ((v >> 1) & 0x55555555);
v = (v & 0x33333333) + ((v >> 2) & 0x33333333);
return ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;
}
/**
* This is a clever bit hack that computes the first zero bit in a number.
*
* (http://skalkoto.blogspot.com/2008/01/bit-operations-find-first-zero-bit.html)
*
* v = 1010 1111
* v = ~v = 0101 0000 (1) Invert the number.
* -v = 1011 0000 (2) Compute 2's complement.
* v = v & -v = 0001 0000 (3) And (1) and (2).
*
* The result is the bit position of the 1 bit in (3) which you can compute
* by subtracting 1 and then counting bits.
*
* v - 1 = 0000 1111 4) Subtract 1, and use bitCount() to find the
* result.
*
*/
function firstZero(v) {
v = ~v;
v = (v & (-v)) - 1;
// Inlined bitCount(v).
v = v - ((v >> 1) & 0x55555555);
v = (v & 0x33333333) + ((v >> 2) & 0x33333333);
return ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;
}
let nextWord = 0;
/**
* Finds the next available ID by scanning the bit map.
*/
function nextID() {
let cur = nextWord;
let end = bit.length;
while (true) {
for (let i = cur, j = end; i < j; i++) {
let word = bit[i];
if (word === 0xFFFFFFFF) {
continue;
} else if (word === 0) {
bit[i] = 1;
nextWord = i;
return i << 5;
} else {
let fz = firstZero(word);
bit[i] |= 1 << fz;
nextWord = i;
return (i << 5) + fz;
}
}
if (end === nextWord) {
/* Double the size if we can't find a free ID */
nextWord = size;
resize(size * 2);
return nextID();
}
end = cur;
cur = 0;
}
}
/**
* Frees an ID, by clearing a bit in the bit map.
*/
function freeID(id) {
bit[id >> 5] &= ~(1 << (id & 0x1f));
nextWord = id >> 5;
}
/**
* Adds an object to the pool if it doesn't exist and increments its reference count by one.
*/
function acquire(o) {
let id = o[OBJECT_ID_NAME];
if (id === undefined) {
id = nextID();
if (tidy) {
Object.defineProperty(o, OBJECT_ID_NAME, {
value : id,
writable : false,
enumerable : false,
configurable : true
});
} else {
o[OBJECT_ID_NAME] = id;
}
obj[id] = o;
ref[id] = 1;
} else {
ref[id] ++;
}
return id;
}
/**
* Decrements an objects reference count by one, and removes it from the pool if
* the reference count is zero.
*/
function release(o) {
releaseByID(o[OBJECT_ID_NAME]);
}
function releaseByID(id) {
if (id === undefined) {
return;
}
if (--ref[id] === 0) {
freeID(id);
let o = obj[id];
obj[id] = null;
if (tidy) {
delete o[OBJECT_ID_NAME];
} else {
o[OBJECT_ID_NAME] = undefined;
}
}
}
function get(id) {
return obj[id];
}
function trace() {
function getSizeName(v) {
let KB = 1024;
let MB = 1024 * KB;
if (v / MB > 1) {
return (v / MB).toFixed(2) + " M";
} else if (v / KB > 1) {
return (v / KB).toFixed(2) + " K";
} else {
return v + " ";
}
}
trace(" ID Map: " + getSizeName(bit.length * 4) + "B");
trace(" Count Map: " + getSizeName(ref.length * 2) + "B");
trace(" Object Map: " + obj.length);
trace("Resize Count: " + resizeCount);
let count = 0;
for (let i = 0; i < bit.length; i++) {
count += bitCount(bit[i]);
}
trace("Object Map Density: " + ((count / (bit.length * 32)) * 100).toFixed(2) + " %");
}
return {
acquire: acquire,
release: release,
releaseByID: releaseByID,
trace: trace,
get: get
};
})(1024);
exports.acquire = Pool.acquire;
exports.release = Pool.release;
exports.releaseByID = Pool.releaseByID;
exports.trace = Pool.trace;
exports.get = Pool.get;