On Sun, Aug 29, 2021 at 6:54 PM Soni "They/Them" L. wrote:
would it still be in spec to have 63-bit integers, or even "big integers"
In other words, you have a C compiler supporting non-standard datatype Int63
and ask if you can build Lua by simply `#define LUA_INTEGER Int63`?
I read the question more as "would it still be standards-compliant Lua" (regardless of how much of a change to the code it would take to support it) than "will this work the way I think it will?"
If the standard already accepts to compile with various precision and ranges supported by the 'number' type (by default it uses the C/C++ type 'double', it could be 'float', or 'long double' as well, but none of them warranty a given precision that is sufficient to support a specific range of integers. However it must be a floatting point type, so it has to support negative values (including for integers), but not necessarily infinite values or NaNs; it could as well be finite precision with a fixed number of decimals (like decimal numbers with formats in COBOL or new decimal types added in C/C++ or in some math coprocessors or FPUs, possibly supported by scaled integers.
So NOTHING warranties that signed 64 integers are suppported in Lua, even on a 64-bit native system: for the simplest case, this depends on the representation of 'double' in C/C++. In fact if the C/C++ compiler just uses 64-bit IEEE floatting points for 'double', it has 53 bits of mantissa (plus the implicit high bit 1 not stored, and a sign bit; zero is represented by a specific exponent part where the bits of mantissa are not used or only used for "denormal" very small absolute values where the high bit 1 is no longer implicit but stored in the mantissa bits).
This means that such 'double' type in C/C++ actually supports only 53-bit unsigned integers, plus a sign. So at most it support signed integers up to 54-bit plus one value (the inclusive range is -2^54 to +2^54) : larger integers will be rounded (with reduced precision using larger exponents).
To support 64-bit signed integers, you would need to use 'long double' (which uses more that 64 bits of storage, so they are not necessarily atomic, except inside FPU for intermediate computation; e.g. an x64 FPU, supports "long double" types using 10 bytes, i.e. 80 bits of storage; 2 bytes are used for the base-2 exponent, 8 bytes (64 bits) for the mantissa and the sign bit: it natively supports storing the full range of 64-bit signed integers without loss of precision; these FPU also have instructions to convert this long double to 64-bit integers, by shifting the mantissa and dropping the exponent part, and special treatment of zero: this may fail for values out of the range -2^63 to +2^63-1; there's no failure and no loss of precision for the reverse conversion from 64-bit signed integers or 63-bit unsigned integers to such "long double".
63-bit positive-only integers do exist then, in the context of using these 80-bit "long double" to represent them with x64 FPU registers, with their 63-bit mantissa (plus the implicit high bit 1): the allowed range is 0 to +2^63, with one additional positive value if you compare it to the range of positive values allowed in 64-bit signed integers (which allow -2^63 to +2^63-1).
The caveat is when loading/storing theses registers to memory back to 64-bit integers (signed or unsigned): if you store the positive long double +2^63 represented on 80-bit exactly as an integer, you can get a 64-bit unsigned integer of the same value, but not a 64-bit signed integer (which would result in its opposite value, negative). But if you use 63-bit positive-only integers in the same range as allowed by 64-bit signed integers, the conversion is safe: you can use treat the additional floatting point value +2^63 and any other larger absolute values like with infinite, and then throw a runtime "out-of range" exception when converting the 80-bit long double to a 64-bit signed integer (the exception handler may decide what to do: if you want it to round the result modulo 63-bit, just return 0, then you've created a safe unsigned 63-bit arithmetic.
But you've done that at the price of using 80-bit FPU registers and FPU instructions with 80-bit "long double" for intermediate computation in the FPU, instead of using "long int" for 64-bit (signed or unsigned) integer registers and ALU instructions in the x64 CPU.
The benefit is however the fact that Lua can use a single type for 63-bit unsigned integers, and 64-bit floatting points by using 80-bit "long double" FPU instructions. Lua however will still need to use an external storage to differentiate both subtypes of "number": 63-bit "unsigned" integer, or a 64-bit "double"; or better, it can take this bit of information within the 11-bit exponent part of the double, allowing a reduced range of values (if a FPU result has a too large positive base-2 exponent, the Lua engine can convert it to an Infinite; if a FPU result has a too small negative base-2 exponent, Lua can convert it to a "denormal" value near zero, or just to zero like all other denormal values, if it chooses to not use and store any denormal values).
So finally you can represent all supported values for 'number' with the same 64-bit 'double' type: it will exactly store any 63-bit signed integer and any 63-bit doubles (i.e. 64-bit double with a reduced range of allowed exponents, and the support of signed zeroes, denormals, infinites; it will also support signed NaNs, signaling or not-signaling, and still holding 51 bits of information or signals in the 53 bit mantissa field).
- If the Lua engine chooses to normalize all NaNs to a single value (force-setting the sign bit and clearing the signal bits), then it has 51 bits of information usable for other values than numbers
- If the Lua engine chooses to normalize all denormals and zeroes to a single value (force-clearing the sign bit and the denormalized mantissa), then it also has 51 bits of information usable as well for other values than numbers
If you combine both, then you have a total of 52 bits available to store other values than numbers.
Notably you could use these 52 bits as an object identifier: it could store a pointer memory to a block aligned on 64-bit boundary in user space, and thus would allow 2^52 distinct adresses in a giant user space of 2^56 bytes! This is much more than what every modern 64-bit machine supports. So it can dedicate some parts of these 2^52 object identifiers for storing also all of these:
- C/C++ function entries could use a small amount of them: these can be handles to a table of pointers, or pointers directly if they are properly aligned or restricted in the user memory space.
- the "nil" value just needs a single of these identifier
- small strings up to 3 bytes would need at most 48 bits for these bytes, plus 2 bits for the length, they would use at most 2^50 object identifiers
- immutable strings in the shared pool: many distinct ids (these are handles: the allocation of stringbuffers in dynamic memory, and the storage of their pointer in the shared pool index associating handles to stringbuffer addresses is not stored there)
- object identifiers for tables: many distinct ids.
- object identifiers for other types (userdata, lightuserdate, thread/coroutine): many distinct ids
So in fact ALL existing types of Lua would be supported in the same single 64-bit field (using the storage capability offered by the format of IEEE NaNs). you can use 64-bit registers to hold all of them. you have to use FPU instructions for all numbers but then check bounds only for Nans (too small exponent) and Infinites (too large exponent).
In a 64-bit IEEE double, the exponent field is 11-bit wide so it stores base-2 exponents from -1022 to +1023 (assuming a mantissa normalized in [1.0..2.0) with the constant integer part not stored in bits of mantissa but replaced by the sign bit).
- The smallest exponent (-1022) is used for positive and negative zeroes (all 52 mantissa bits cleared, plus the leading sign bit) and denormalized values (52 bits including most significant bit 1 stored, and the sign bit)
- The largest exponent (+1023) is used for infinites and NaNs (both having a sign bit and 52-bit mantissa)
After computing operations on numbers you can use bound checking on one or both of these exponent values. I suggest only checking the largest exponent identifying Infinites and NaNs; if so it will just have to clear all bits of the mantissa bit and possibly the sign bit for NaN to make sure it does not "mimics" the pattern of bits used to identify all other types than 'number'.
There's in that case NO loss of precision for doubles, NO loss of allowed range, you still have signed infinites (but no other bits of info), Nan (possibly signed or signaling if you wish, but no other bits of info), signed zeroes (if you wish), dernormalized values (if you wish). You just store all other types as if they were a NaN (they all are really NOT A NUMBER!) in the 52 bits of mantissa.
The Lua type information will be fully available by first looking at the exponent field (where NaNs and Infinite are identifiable: this exponent will be constant, otherwise it's a normal number including 63-bit integers and supported floatting points or infinites with a reduced range); then it can use the highest bits in the 52 bits of mantissa (after the sign bit) to identify all other Lua types or subtypes (including small strings up to 3 bytes, not requiring any external storage)
You also optimize the storage and accelerate the handling of all small strings (up to 3 bytes)
