CakeML / CakeML/cakeml

Unsafe arithmetic with witnesses of "smallnumness"

Open
#1,485 0 comments 0 reactions 0 assignees View on GitHub
enhancement medium effort performance
Dominant language
Standard ML
Stars
1.2k
Forks
104
Avg merge
2d 21h
Merged PRs (30d)
16

Description

A lot of performance critical CakeML code is doing simple calculations with array indices, which are currently compiled to general-purpose integer operations. Such integer operations need to deal with tests for bignums and conditional jumps to the bignum library.

This issue is about implementing unsafe arithmetic (operations `+`, `-`, ... and comparisons `<`, `=`, ...) with witnesses that guarantee the integers are smallnums. The idea can be explained with an example: instead of doing
```
App (Arith Add IntT) [arg1; arg2]
```
we do:
```
App (UnsafeIndexArith Add) [arg1; arg2; witness]
```
where the semantics is the following:
- get integers `i1` and `i2` from `arg1` and `arg2`
- read length `len` of vector / array / byte array or even list from `witness`
- perform the arithmetic operation (in this case `Add`) on `i1` and `i2`
- check that all numbers involved (`i1` and `i2` and `i1 + i2`) satisfy `-256 * len ≤ ... ≤ 256 * len`, if not then type error

The cool thing is that operations such as `Add` then compile to a single (add) instruction.

This can be seen as a manual version of https://github.com/CakeML/cakeml/issues/367

Contributor guide

No contributing guide indexed for this repository

Research direction

Start by tracing the compiler representation shown for App (Arith Add IntT) and review the related CakeML issue #367. The work is done when the specified unsafe arithmetic and comparison operations accept smallnum witnesses, enforce the stated bounds, and compile operations such as Add to a single instruction.

Written by the indexing model from the issue text.

Assessment

Domain
compilers
Issue type
Feature
Difficulty
5/5
Estimated time
Over a week
Activity status
Active
Clarity
Mostly clear
Newbie friendliness
35/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.