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
|
Growing data structures in arenas
=================================
Solution 1
----------
Put "the" growing allocation at the beginning, and non-growing allocations
at the end. There can only be one growing structure per arena block
(otherwise we need to allocate another block)
+ Memory efficient for grow-only structures
- Causes fragmentation is the structure can shrink also
- Requires a separate block for each growing structure.
- There is a maximum size (block size - non-growing allocations).
After this maximum size is reached, we need to either deny the allocation or move it.
Solution 2
----------
Use plain malloc/realloc for growing structures.
+ Memory efficient when there are many growing structures.
- Will cause fragmentation when structures grow and get moved
around (or if malloc is smart enough to spread them out)
- May cause copying of memory.
Solution 3
----------
Hybrid of 1 and 2.
There should perhaps also be a way of freezing a growable structure,
when it is known that no more growth will occur.
Solution 4
----------
Special list data structure (does not allow indexed access):
struct { capacity_in_chunk, count_in_chunk, next_chunk_ptr, data... }
When the list (including its elements) is the last item in the arena,
we can simply grow it and put the next element last.
For efficient access, perhaps there should be some kind of flag in the beginning?
- if chunks are always 16+ bit aligned, then we could use a bit in the pointer
- the bit would indicate the layout of the struct (to allow a compact layout)
How to interleave lists efficiently?
Solution 5
----------
Chunks of growing (power of 2)? sizes.
type List<T> = struct { size length; ref struct ListChunk<T> first_chunk; }
# FIXME how to specify length here?
type ListChunk<T> = struct { ref struct ListChunk<T> next; []T data; }
We would probably need some kind of data parameter for the type (a.k.a. dependent types):
type List<T> = struct { size length; ref struct ListChunk<T,16> first_chunk; }
type ListChunk<T, int L> = struct { ref struct ListChunk<T,2*L> next; [L]T data; }
Solution 6
----------
Add a "standalone" free-list structure to the arena system, and do new
allocations when necessary. Either:
1. the free-list can be unordered, without merging,
2. we could have some kind of lookup structure to find next/previous blocks, or
3. we could look at the adjacent machine words, bounds check, and continue
until we find either a "root" (first or last entry) or some invalid pointer
(including a pointer that goes in the wrong direction).
|
