diff options
Diffstat (limited to 'doc/0/0-value.md')
| -rw-r--r-- | doc/0/0-value.md | 145 |
1 files changed, 77 insertions, 68 deletions
diff --git a/doc/0/0-value.md b/doc/0/0-value.md index f9f01c4..4dbd44a 100644 --- a/doc/0/0-value.md +++ b/doc/0/0-value.md @@ -2,7 +2,11 @@ <!--TOC--> -Zisp uses NaN-packing for a uniform 64-bit Value representation. +Zisp uses NaN-packing for a uniform 64-bit Zisp Value representation. + +When we speak of a 64-bit Value that is either a Zisp double or NaN-packed Zisp +value, we use the term "Value" with a capital 'V'. In other words, a Value is +either a Zisp double, or the NaN-packed representation of any other Zisp value. The format of a binary64 floating-point number, in big-endian notation, is: @@ -10,8 +14,8 @@ The format of a binary64 floating-point number, in big-endian notation, is: When the 11 exponent bits are all set, it's either a NaN or an Infinity. -For value packing, the remaining 53 bits are available, giving us `2^53` values, -minus the following four bit patterns: +For non-double packing, the remaining 53 bits are available, giving us `2^53` +values, minus the following four bit patterns which *are* doubles: *** FORBIDDEN BIT-PATTERNS *** @@ -31,20 +35,20 @@ zero makes it the *canonical* quiet NaN for the given sign value. The positive and negative cqNaN are the *only* NaN values that can actually be returned by FP operations. This is convenient, because it means we can simply -use them to represent themselves in Zisp. +use them to represent themselves in Zisp as doubles. Infinity values may also be returned by FP operations, and we want them to also -exist in Zisp, so they also represent themselves. +exist as doubles in Zisp, so they also represent themselves. Beyond those four bit patterns, all values with a maximum exponent (all bits -set) are fair game for representing other values, so `2^53 - 4` possibilities. +set) are fair game for representing other Values, so `2^53 - 4` possibilities. We split those `2^53 - 4` available values into four groups, each allowing for -`2^51 - 1` different values to be encoded. (51-bit values excluding zero.) +`2^51 - 1` different values (51-bit values excluding zero) for Value coding: - sign = 1, quiet = 1 :: Negative Fixnum from -1 to -2^51+1 + sign = 1, quiet = 1 :: Negative Fixnums from -1 to -2^51+1 - sign = 1, quiet = 0 :: Positive Fixnum from 0 to 2^51-2 + sign = 1, quiet = 0 :: Positive Fixnums from 0 to 2^51-2 sign = 0, quiet = 1 :: Pointers and other immediates @@ -55,11 +59,11 @@ We split those `2^53 - 4` available values into four groups, each allowing for Negative fixnums actually represent themselves, without needing to go through any transformation. Only the smallest 52-bit signed negative, `-2^51`, cannot -be represented, as it would step on Forbidden Value #1, Negative cqNaN. +be represented, as it would step on Forbidden Pattern #1, Negative cqNaN. Positive fixnums go through a bitsiwe NOT (which can be implemented as an XOR mask combining it with removal of NaN-related high bits) to avoid the all-zero -payload value, which would step on Forbidden Value #2, Negative Infinity. +payload value, which would step on Forbidden Pattern #2, Negative Infinity. ## Pointers and immediates @@ -67,11 +71,11 @@ payload value, which would step on Forbidden Value #2, Negative Infinity. This region of 51-bit values is divided as follows, based on the three highest bits, providing a payload value of 48 bits for each. - 000 :: Pointer to list values + 000 :: Pointer to list (code) - 001 :: Pointer to heap object + 001 :: Pointer to heap - 010 :: Pointer to istr object + 010 :: Pointer to istr 011 :: Immediate short string @@ -93,48 +97,59 @@ bits, providing a payload value of 48 bits for each. (etc.) -Pointers are actually indexes into one of two regions of virtual memory: The -main heap of 32 GiB, which is addressed in 64-bit (8-byte) units; and another -region of 4 GiB for `istr` objects which are byte-addressed. Both regions can -thus be addressed via 32-bit index/offset values. +Zisp splits the native program heap provided by the platform into three regions +of virtual memory: The code heap of 32 GiB, addressed in 64-bit (8-byte) units; +the main heap of 32 GiB, also addressed in 64-bit units; and the 4 GiB heap for +`istr` objects (interned strings) which is addressed in bytes. Each region can +thus be addressed via 32-bit indices instead of larger direct pointers. ### List pointers -In Zisp, a list is a contiguous array of a fixed number of Value elements. +In Zisp, a list is a contiguous array of a fixed number of Values. These may +reside in the main heap or the code heap; this pointer type here is used to +represent lists in the code heap specifically. + +These code lists are allocated with no or little padding, and with no metadata +headers, to achieve optimal memory density and cache locality of code. As such, +we must encode the length of the list directly in the pointer itself. -For a maximally dense representation of code, lists of up to 255 Value elements -are allocated in blocks without any padding or metadata headers, using some of -the bits of the NaN-packed pointer to immediately encode the length. +The exact layout of the 48-bit payload is as follows: -The lower 32 bits of the payload are an index into the main heap region, while -the higher 16 bits are divided into 8 high bits for the length and 8 low bits -for garbage collector metadata. +The low 32 bits are an index into the code heap, while the higher 16 bits are +divided into 8 high bits for the length, and 8 low bits for garbage collector +metadata. The length bits cannot be zero. The empty list is represented by a different bit pattern to provide a minor benefit during garbage collection: Zero-length -lists don't needlessly trigger the code branch that handles list pointers. +lists can't needlessly trigger the code branch that handles list pointers. + +The 8-bit length field means we can only encode lists of up to 255 elements +using this Value type. However, this doesn't mean that source code cannot +contain longer lists: -Lists of arbitrary length can be allocated as regular heap objects of the array -type; the difference is invisible when using the generic list API. +Lists of arbitrary length can be allocated as regular heap objects of the Array +type; the difference is hidden when using a generic list API. This means that +*some* parts of source code may actually end up on the main heap, though lists +of greater than 255 elements should be extremely rare, typically only used to +embed static data arrays in source code anyway. -Forbidden Value #3, Positive cqNaN, is avoided thanks to the fact that the high -8 bits of the payload, encoding the length, cannot be zero. +Forbidden Pattern #3, Positive cqNaN, is avoided thanks to the fact that the +high 8 bits of the payload, encoding the list length, cannot be zero. ### Heap pointers -Regular heap objects are represented by this pointer type, which also uses a -32-bit index into the main heap, in the lower portion of the 48-bit payload. +Regular heap objects are represented by this index type, which uses a 32-bit +index into the main heap, in the lower portion of the 48-bit payload. Of the 16 high bits of the payload, the upper 8 are used to immediately encode the type of the heap object, and the remaining 8 are used for garbage collector metadata. -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. +This means our 64-bit Values can be checked against heap types by comparing the +24 high bits to a combined constant: the 16 high bits that indicate it's a main +heap index, plus 8 more bits encoding a specific heap type. -### Interned strings +### String pointers An `istr` is a string of up to 255 arbitrary bytes, that is typically interned, fulfilling a similar purpose to symbols in Lisp and Scheme. If uninterned, we @@ -195,7 +210,7 @@ highest byte has its MSb set, then the 14 non-MSb bits of the two high bytes define the type, and each has a 32-bit payload; and so on. Unicode code points need 21 bits, so we use a 24-bit type for the Character -type. Miscellaneous values like True, False, EOF, etc. are placed in an 8-bit +type. Miscellaneous Values like True, False, EOF, etc. are placed in an 8-bit type, since there will never be that many of them; this is also where the empty list bit pattern is located. @@ -204,7 +219,7 @@ with small payload values here: There is room for over 268 Million 16-bit types (28-bit type tag) and over 34 Billion 8-bit types (35-bit type tag). -## Internal use values +## Internal use Values The final 51-bit range is used for various internal purposes by the interpreter, mostly related to transparent code optimization. These could also be viewed as @@ -218,49 +233,43 @@ a sort of instruction set for a tree-walking virtual machine. 011 :: Short string as constant - 100 :: Pointer to opcodes in list values + 100 :: Pointer to opcodes in code list - 101 :: Pointer to opcodes in heap object + 101 :: Pointer to opcodes in heap list 110 :: Local variable reference index 111 :: Lexical capture reference index -### Constant values +### Constant Values The first four categories simply mirror those of the previous 51-bit range, but -mark the values as being constants rather than code to evaluate. This way, we +mark the Value as being a constant rather than code to evaluate. This way, we can inject constant data into the AST without needing to worry about it being confused for code to evaluate, and without needing the `(quote ...)` wrapper. -Forbidden Value #4, Positive Infinity, is avoided thanks to the fact that list -pointers always have non-zero length bits. +Forbidden Pattern #4, Positive Infinity, is avoided thanks to the fact that +pointers to lists always have non-zero length bits. ### Opcode array pointers -These pointer types are derived from regular list pointers and heap pointers by -flipping 2 bits. In the case of a heap pointer, the heap type will be an array -of values, i.e., a list of length greater than 255; this should be exceedingly -rare, given that code expressions almost never have such length, but we support -it just in case. - -Either way, what this means is that the list has been pre-evaluated to ensure -it's a well-formed code expression, and the first element has been transformed -into something other than a Value: Its new layout as a 64-bit structure is that -the low 8 bits are an opcode, and the high 56 bits a payload value. - -For example, a `CALL` opcode may use 48 bits for the direct memory address of a -function to call. An opcode like `CALL_LOCAL` may indicate that a heap index -should be read from the local variables array (see below) to locate a function -or closure in the main heap. - -A `CALL_EVAL` opcode may indicate that the payload contains a 32-bit heap index -to another expression to evaluate to generate the address of a function to call; -this might result from a code form such as: `((if x fn1 fn2) arg1 arg2)` - -Various special forms like if, let, lambda, etc. can have their own opcode, and -one for user-defined macro calls, in case macros should be expanded on every -evaluation to help during iterative development of macro code. +These types are derived from the regular code list pointers (length <= 255) and +heap list pointers (length > 255) by flipping 2 bits. + +A heap list pointer of this kind would result from a list of longer than 255 +that represents actual code to execute. (Had it been a quoted list, it would +have become a "pointer to heap as constant" instead.) This will be exceedingly +rare, given that regular code expressions almost never have such length, but we +must support it. It might have resulted, for example, from heavy macro use or +otherwise machine-generated source code. + +Either way, what this means is that a list has been analyzed to ensure it's a +well-formed code expression, and transformed into an optimized form: + +The first element is transformed into something other than a Value: It is now a +64-bit structure whose low 8 bits are an opcode, and the high 56 bits a payload +value. Other elements may also have been transformed into VM instructions, but +only of the above listed Value types. ### Local variable index |