From the start int in Poly/ML has been arbitrary precision. After around thirty years I think it's time to make a change. The current plan is to introduce a fixed precision integer type and use that as the default int. Arbitrary precision will remain as LargeInt.int/IntInf.int.

The reason for the change is that it is becoming clear that having arbitrary precision int as the only integer type imposes restrictions on the code both as regards the integer type itself but also more widely.

The arbitrary precision type in Poly/ML is implemented using a tagged representation. Small values that will fit in 31/63 bits are represented as the value shifted one bit left and with the bottom bit set. Larger values are represented as pointers to arrays of bytes, either in the GMP format or Poly's own format. Since pointers are always word-aligned it's possible to distinguish the two forms by looking at the bottom bit. The "tag-bit" also serves another purpose. The garbage-collector can use it to distinguish pointers from non-pointers so all non-pointer values, e.g. bool, char and word, are represented using the tagged form.

Arbitrary precision operations are handled directly by the code-generator. The idea is that when the values are small, as they usually are, the machine can execute the appropriate instruction directly. For example, addition is generated as an add instruction. It is preceded by a test on the tags and followed by a test for overflow. If the arguments were not tagged or the result overflowed there is a call into the run-time system. This emulates the instruction and returns with the result in the correct register.

Emulation has limitations. Currently only (in)equality, comparison, addition and subtraction are emulated. Other operations such as multiplication and division involve calls to assembly code. This means that code that makes significant use of arithmetic incurs overheads even if it only ever uses small values. There is also a more subtle cost. Because emulating addition and subtraction could involve allocating memory on the heap for the long-format result every addition and subtraction could result in a garbage-collection. This means that the registers, which could be holding intermediate results, have to be treated as the roots for the GC. That in turn means that they must always contain either valid pointers or tagged values. This sometimes involves adding extra instructions simply to ensure this is the case. It also means that whenever the code returns from the run-time system to ML all the registers have to be loaded with known values, adding to the cost of a RTS call.

The plan is to retain the existing arbitrary precision using the current tagged values but remove emulation. All arbitrary precision operations will involve an ML function call to the assembly code. This will compute the result directly if it is short and call into the run-time system if it is long. This is actually likely to faster than the current scheme if the values are long. Some cases, for example equality between an arbitrary precision value and a short constant, can continue to be handled by the code-generator since they do not require emulation.

Fixed precision int will be based on the current short format i.e. 31 bits on 32-bit machines, 63 bits on 63-bit machines. Operations on these can be handled directly by the code-generator.

These changes are currently being tested in the FixedPrecisionInt branch. This requires at least one, preferably two, calls to "make compiler" to build a version of the compiler that generates fixed precision operations. For backwards compatibility it does not yet gain all the advantages of the change; in particular it still clears all the registers on return from the run-time system.