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
|
# List array optimization
_2026 June_
Currently, I use pointers with a 3-bit tag to denote lists of up to 7
elements, with the value 0 meaning it instead has a terminator at the
end.
This requires a small complication in the interpreter, where it needs
to check if the tag value is 0 or not, and branch based off of that.
It also makes lists of 8+ elements waste 8 bytes of memory for the
termination marker, and makes checking the length require a linear
scan through memory.
Here's an idea for the future:
* Map a 32 GiB virtual memory region for list arrays.
* When the high 16 bits of a NaN-packed value say "list pointer" then
the next 16 bits are a length, and the low 32 bits an "address" or
index into the list array memory region.
* A memory access like `base + index*8` is equally as cheap as just
`base + offset` on modern CPUs, so we lose no performance to the
fact that we use the address as an index.
* Maximum list length is 65535 elements, which is good enough.
* Length 0 with a canonical null address can denote `()` aka `nil` as
the empty list singleton; no need for a separate singleton value
making type checks and such awkward.
This is very clean and consistent, and should offer a slight boost to
interpreter performance, thanks to less branching, no wasted 64-bit
slots in the list array pool, and so on.
I've said for the future, but this idea seems so attractive that I'm
thinking of implementing it right away. I just haven't touched mmap
so far and don't know how to do it in Zig but it should be easy.
## For the regular heap as well?
So far I've held steadfast to the idea that I want to support a full
48-bit address range for regular heap pointers, but it's honestly not
necessary.
If I ever implement a modern and advanced GC algorithm like ZGC, I'll
probably need to sacrifice some bits to that anyway.
A 32-bit index value can support a 64 GiB heap by taking advantage of
the fact that heap objects are 16-byte aligned. Higher alignment may
increase that further; for example, align to entire cache lines (64
bytes) and you can support a 256 GiB heap. This could be a setting,
to accommodate for different needs.
This time we can't make use of the fact that modern CPUs allow direct
index value multiplication, because those only go up to 8. However,
since we use exactly the lower 32 bits of a register, no masking or
"shifting back and forth" is needed on x86-64, since we can use the
virtual register feature to extract the low half directly. I think
there's similar tricks available on AArch64. Then you just multiply
by a multiple of 8, which is just a left-shift instruction.
This gives us 16 bits for the heap type tag and GC-related metadata.
Even Generational ZGC, the most bit-hungry GC design, only uses 9 in
total (despite having 17 more in reserve) so all is well. Note: I've
not fact-checked this; it comes straight out of Google Gemini. But I
know that it uses 4 bits for coloring, and "a few more" for the newer
generational algorithm. Documentation doesn't specify how many and I
don't want to dive into the code; in any case, I'm sure that the 16
bits I have will be more than enough, using e.g. 4 bits for the heap
type tag, and up to 12 bits for GC metadata.
Heck, having heap type tags directly on pointers really isn't that
important, because in almost all cases you will actually access the
heap value after ensuring it's the correct type, and a type mismatch
leading to an exception is a cold branch anyway. So having the type
tags on the heap object itself works well enough, meaning I could use
all 16 bits for GC metadata if I really needed that for some reason.
Anyway, I'm getting ahead of myself. For now, I think I'll move to a
design where list pointers are partitioned as 16/16/32, and regular
heap pointers as 16/4/12/32, with a static 16-byte alignment allowing
up to 64 GiB of regular (non-list) heap objects for now.
And if one day someone writes a program in Zisp (lol) that needs more
heap data then that, we'll see. In most cases, having hundreds of GiB
of data probably means you just have some enormous mapped files or so,
for which you could just use handle objects and index values, so the
actual heap pointers of the runtime don't need to be able to represent
those addresses. Dog knows what corporations do with Java that makes
them want a GC algorithm that can handle terabytes of heap data.
|
