diff options
Diffstat (limited to 'doc/0/0-value.md')
| -rw-r--r-- | doc/0/0-value.md | 78 |
1 files changed, 43 insertions, 35 deletions
diff --git a/doc/0/0-value.md b/doc/0/0-value.md index c2810d8..2b9a858 100644 --- a/doc/0/0-value.md +++ b/doc/0/0-value.md @@ -95,70 +95,78 @@ bits, providing a payload value of 48 bits for each. ### Interned strings -An istr is an interned string of up to 65,535 arbitrary bytes. These are very -similar to symbols in Lisp and Scheme. Of the 48-bit payload value, the lower -32 bits are an offset into a virtual memory region dedicated to this type, and -the higher 16 bits encode the length of the string, which cannot be zero. The -empty string has a different representation; see immediate short strings. +An `istr` is an interned string of up to 255 arbitrary bytes, fulfilling a +similar purpose to symbols in Lisp and Scheme. -Using a 32-bit offset value means that interned strings can occupy a total -maximum of 4 GiB of memory, which should be comfortably sufficient. +Of the 48-bit payload value, the lower 32 bits are an offset into a dedicated +virtual memory region for this type only, bounding total memory use to 4 GiB, +which is more than enough for interned strings. + +The higher 16 bits of the payload are divided in two halves. The upper 8 bits +directly encode the length, which cannot be zero; the lower 8 bits are used for +garbage collection metadata. + +The empty string is represented as an immediate short string; see below. Forbidden Value #3, Positive cqNaN, is avoided thanks to the fact that the high -16 bits of the payload value cannot be zero. +8 bits of the payload, encoding the length, cannot be zero. ### List pointers Lists are arrays of Value objects, allocated without any padding, for efficient source code representation and traversal by the interpreter. -They are also allocated within a dedicated virtual memory region, but using a -32-bit index value, treating the region as an array of 64-bit Value slots, so +They are allocated within a dedicated virtual memory region as well, but use a +32-bit index value that treats the region as an array of 64-bit slots, meaning they can occupy a total maximum of 32 GiB of memory. -The upper 16 bits of the payload encode the length (element count) meaning that -a list can contain up to 65,535 elements. +The higher 16 bits of the 48-bit payload are once again divided into length and +garbage collector metadata. This limits element count to 255, but a fall-back +heap type is used to make this limitation invisible to programs. The empty list is canonically represented with a null payload value, i.e., zero -length, and zero offset. +length, cleared GC metadata bits, and zero index value. -There is a separate heap object type for arbitrary-length arrays; this type is -intended only for the representation of lists in source code, and no more; it's -handled differently by the garbage collector as well and should not be used for -arbitrary heap storage. +Lists of this type can double as generic *tuple* types since they are packed in +a maximally efficient way. For instance, a *box* type of a single explicitly +heap-allocated Value, a *pair* type of exactly two Values, and a variety of +*struct* types of fixed Value counts could be implemented by this type. ### Heap pointers Other heap objects are allocated within their own virtual memory region, using -the low 32 bits of the payload for an index value as well, meaning that this -region can also span up to 32 GiB of memory. +the low 32 bits of the payload as an index value as well, meaning this region +can occupy another 32 GiB of memory. -Objects in this main heap may have an alignment of greater than 8 bytes, which -could be exploited to increase the implicit multiplier of the index value, for -example to 16, to support a greater maximum heap size, such as 64 GiB. This is -not currently implemented, since heaps that large are rarely needed, and modern -CPUs are optimized for indexing into arrays of up to 8-byte elements. +Objects in the main heap may have an alignment greater than 8 bytes. We could +exploit this to support larger heaps, treating the heap as, for instance, slots +of 16 bytes (128 bits) or more. However, this is not implemented, since heaps +that large are rarely needed, and modern CPUs are optimized for indexing 64-bit +array elements. (Both the x86-64 and AArch64 architectures can directly use a value as an index into an array of 64-bit values, making the multiplication by 8 implicit, while greater multipliers need an explicit transform of the index.) -Of the remaining upper 16 bits of the 48-bit payload value, the highest 4 are -used to immediately encode the type of the heap object, and the remaining 12 -bits are reserved for garbage collector metadata. +Of the remaining upper 16 bits of the 48-bit payload, the upper 8 are used to +immediately encode the type of the heap object, and the remaining 8 bits are +once again used for garbage collector metadata. -Thus, a value can be checked against a specific heap object type by comparing -the 20 high bits to a combined constant value: The 16 highest bits indicating -that it's a heap pointer, and the 4 bits after that denoting the heap type. +This means that a full 64-bit NaN-packed value can be checked against a heap +type by comparing the highest 24 bits to a combined constant: the highest 16 +bits indicating that it's a regular heap pointer, and 8 bits encoding the +specific heap type being checked against. ### Immediate short strings -This 48-bit range is used for strings of zero to six bytes. These are NUL -terminated unless exactly six bytes, meaning that a literal NUL byte cannot -appear in them, but otherwise they allow arbitrary byte values. +This 48-bit range is used for strings of zero to six bytes in length. + +They are NUL-terminated unless exactly six bytes, meaning that a literal NUL +byte cannot appear in them, but otherwise they allow arbitrary byte values. +When a NUL-terminator appears, the remaining bytes *must* be NUL as well; +otherwise the strings could not be tested for equality as easily. -This type is used to represent the empty string, with a null payload, which -indicates a length of zero due to the first byte immediately being a NUL. +The empty string is represented with an all-NUL payload. NOTE: The order of bytes may depend on the endianness of the platform. |