CakeML / CakeML/cakeml

Negative small-integer multiplication misses the inline fast path

Open
#1,452 3 comments 0 reactions 0 assignees View on GitHub
bug high reward performance
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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.