"Float self-tagging" paper

[jepler]

An interesting paper: https://arxiv.org/html/2411.16544v1

Abstract

Dynamic and polymorphic languages must attach information, such as types, to run time objects, and therefore adapt the memory layout of values to include space for this information. This is especially problematic in the case of IEEE754 double-precision floating-point numbers, which require exactly 64 bits, leaving no space for type information. The two main encodings in-use to this day, tagged pointers and NaN-tagging, either allocate floats on the heap or unbox them at the cost of an overhead when handling all other objects.

This paper presents self-tagging, a new approach to object tagging that can attach type information to 64-bit objects while retaining the ability to use all of their 64 bits for data. At its core, self-tagging exploits the fact that some bit sequences appear with very high probability. Superimposing tags with these frequent sequences allows encoding both 64-bit data and type within a single machine word. Implementations of self-tagging demonstrate that it unboxes all floats in practice, accelerating the execution time of float-intensive benchmarks in Scheme by 2.3×, and in JavaScript by 2.7× without impacting the performance of other benchmarks, which makes it a good alternative to both tagged pointers and NaN-tagging.

Basically, this paper proposes to box some floats, based on exponent bits. It would allow a "REPR-C" like representation but without sacrificing the lower mantissa bits for tag bits. However, it is probably more expensive code wise: a boxed float type is now required for some floats, the simplest system would reduce unboxed ints to 29 bits, and tag checking/conversion might be a bit more expensive overall.

Some doodles about a possible OBJ_REPR based on this paper:

// following the paper most closely
- eeeeeeff ffffffff ffffffff fffffs10 (float rotated 3 bits, exponent 10...)
- eeeeeeff ffffffff ffffffff fffffs01 (float rotated 3 bits, exponent 01...)
- xxxxxxxx xxxxxxxx xxxxxxxx xxxxxx00 (pointer to mp_obj_base_t or fake obj)
- iiiiiiii iiiiiiii iiiiiiii iiiii011 (29-bit signed ints)
- qqqqqqqq qqqqqqqq qqqqqqqq qqqq0111 (qstrs)
- 00000000 00000000 00000000 ssss0111 (immediate objects)

// Alternate based on same paper, preserves 31-bit signed ints
// rotated float + extra xorshift to fix lower bits (tag ^ (tag >> 1))
// unboxed float range about 1e-9 .. 1e-9
// creates new *8-byte* alignment requirement for objects
- iiiiiiii iiiiiiii iiiiiiii iiiiiii1 (31-bit signed ints)
- eeeeefff fffffff ffffffff fffffs110 (float rotated 4 bits, exponent 100..)
- eeeeefff fffffff ffffffff fffffs010 (float rotated 4 bits, exponent 011..)
- xxxxxxxx xxxxxxxx xxxxxxxx xxxxx000 (pointer to mp_obj_base_t or fake obj)
- qqqqqqqq qqqqqqqq qqqqqqqq qqqq0100 (qstrs)
- 00000000 00000000 00000000 ssss1100 (immediate objects)

// Alternative: platform provides a top byte that is never a pointer encoding
// p = poison pointer top byte, removes extra alignment requirement
- xxxxxxxx xxxxxxxx xxxxxxxx xxxxxx00 (pointer to mp_obj_base_t or fake obj)
- pppppppp qqqqqqqq qqqqqqqq qqqqq000 (qstrs)
- pppppppp 00000000 00000000 0ssss100 (immediate objects)

[bidrohini]

The compact and efficient representation makes it appealing for resource-constrained environments.