Negative small-integer multiplication misses the inline fast path
- Dominant language
- Standard ML
- Stars
- 1.2k
- Forks
- 104
- Avg merge
- 2d 21h
- Merged PRs (30d)
- 16
Description
## Summary
On x64-64, most nonzero multiplications involving a negative tagged small
integer leave the inline small-integer path and call the generic `_Mul` helper,
even when both operands and the result are small integers. The corresponding
positive multiplication stays inline.
The result is correct, but sign alone creates a large and surprising performance
cliff in fundamental integer arithmetic.
## Reproducer
```sml
fun multloop x y n =
if n = 0 then x else multloop (x * y) y (n - 1);
val multiplier =
case CommandLine.arguments () of
["negative"] => 0 - 1
| _ => 1;
print_int (multloop 1 multiplier 50000000);
print "\n";
```
The multiplier is selected at runtime, so this is exercising the general
integer-multiply path rather than a constant-multiplication optimization. Both
runs print `1` because the iteration count is even.
From an x64-64 build directory containing `cake` and `basis_ffi.c`:
```sh
./cake < /tmp/negative-small-int-multiplication.cml > /tmp/mult.S
cc -O2 /tmp/mult.S basis_ffi.c -lm -o /tmp/mult
# Optional timing controls used for the numbers below:
env CML_HEAP_SIZE=16 CML_STACK_SIZE=16 taskset -c 2 /tmp/mult
env CML_HEAP_SIZE=16 CML_STACK_SIZE=16 taskset -c 2 /tmp/mult negative
for i in 1 2 3 4 5; do
/usr/bin/time -f '%e' env CML_HEAP_SIZE=16 CML_STACK_SIZE=16 \
taskset -c 2 /tmp/mult >/dev/null
done
for i in 1 2 3 4 5; do
/usr/bin/time -f '%e' env CML_HEAP_SIZE=16 CML_STACK_SIZE=16 \
taskset -c 2 /tmp/mult negative >/dev/null
done
```
Five timed runs after one warm-up gave:
| Runtime multiplier | Range | Median | Relative median |
|---|---:|---:|---:|
| `1` | 0.18–0.19 s | 0.18 s | 1.0× |
| `0 - 1` | 2.46–2.60 s | 2.53 s | 14.1× |
The exact ratio varies between runs, but the order-of-magnitude cliff is stable.
The runtime measurements used CakeML
`535ff9fb8b11b2f49662e21b3f95401ea5f8ed0e`. The relevant lowering and x64
target files are unchanged at
`0fe74ee25d03a7d6d72892927edcaf5ae9677e10`.
The fast-path decision is in the shared `data_to_word` lowering, so the cause is
not inherently x64-specific. Only x64-64 has been measured here.
## Cause
CakeML small integers are represented as `4 * i`
([`Smallnum_def`](https://github.com/CakeML/cakeml/blob/0fe74ee25d03a7d6d72892927edcaf5ae9677e10/compiler/backend/data_to_wordScript.sml#L1094-L1097)).
The current multiply lowering logically shifts one operand right by one bit,
performs `LongMul`, and treats a nonzero high half as a reason to call
`Mul_location`
([`assign_Mult`](https://github.com/CakeML/cakeml/blob/0fe74ee25d03a7d6d72892927edcaf5ae9677e10/compiler/backend/data_to_wordScript.sml#L1951-L1963)).
`LongMul` is an unsigned full-width multiplication: its abstract semantics use
`w2n` for both operands
([`asmSemScript.sml`](https://github.com/CakeML/cakeml/blob/0fe74ee25d03a7d6d72892927edcaf5ae9677e10/compiler/encoders/asm/asmSemScript.sml#L84-L87)),
and x64 lowers it to unsigned `mul`
([`x64_targetScript.sml`](https://github.com/CakeML/cakeml/blob/0fe74ee25d03a7d6d72892927edcaf5ae9677e10/compiler/encoders/x64/x64_targetScript.sml#L95-L100)).
A logical right shift turns a negative tagged value into a large unsigned
integer. Multiplying that value generally produces a nonzero unsigned high
half, so `assign_Mult` selects the generic helper even though the signed result
fits the small-integer representation.
This is visible in the generated x64 code as an unsigned `mul` followed by a
high-half test and a transfer to `cml__Mul_14`. In the positive control that
slow branch is not taken; with the runtime multiplier `0 - 1`, it is taken on
the loop iterations.
## Expected behavior
If both operands are tagged small integers and their mathematical product fits
the tagged small-integer range, multiplication should remain on the inline
path, irrespective of sign. The generic helper should be needed only for a
bignum operand or a genuine small-integer overflow.
## Possible implementation direction
The fast path needs a sign-aware overflow test. On x64, one natural sequence is
to check that both operands are small, arithmetically untag one operand by two
bits, and use signed `imul` with overflow detection against the other tagged
operand. The product is then already tagged as `4 * (i * j)`. This may justify
a signed multiply-with-overflow operation in abstract ASM.
Alternatively, the compiler could keep the existing unsigned `LongMul` and
correct its high-half interpretation for negative inputs. `LongMul` should
remain unsigned for the bignum machinery; the problem is its use as the overflow
test for signed tagged arithmetic.
## Regression coverage
The regression matrix should use runtime values and include:
- positive×negative, negative×positive, and negative×negative;
- multiplication by zero and by `-1`;
- products just inside both ends of the tagged-small range;
- products just outside that range, which must still call the generic helper;
- a genuinely boxed/bignum operand.
Besides checking results, a compiler-level regression should distinguish the
inline signed-small case from the helper path so that semantic equivalence alone
does not hide the performance regression.
## Related issues
- [#246, “Add instructions for efficient Div and Mul by (powers of) 2”](https://github.com/CakeML/cakeml/issues/246), concerns constant multiplication strength reduction. This issue is the general runtime path and reproduces with a runtime-selected multiplier.
- [#1036, “Relax instruction conventions in word_alloc”](https://github.com/CakeML/cakeml/issues/1036), concerns register constraints around `LongMul`, not its unsigned overflow test for signed tagged integers.
_Written by Codex (OpenAI)._
Contributor guide
No contributing guide indexed for this repository
Research direction
Start in compiler/backend/data_to_wordScript.sml at assign_Mult and trace LongMul through compiler/encoders/asm/asmSemScript.sml and compiler/encoders/x64/x64_targetScript.sml. Run the supplied runtime-multiplier reproducer and add regression coverage for signed products, boundary overflows, and boxed operands. Done means fitting tagged-small products remain inline while genuine overflow and bignum cases still use the generic helper.
Written by the indexing model from the issue text.
Assessment
- Domain
- compilers, performance
- Issue type
- Bug
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Active
- Clarity
- Mostly clear
- Newbie friendliness
- 38/100