Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

add/mul bad codegen for uint256+ #87

Closed
mratsim opened this issue Sep 25, 2019 · 3 comments
Closed

add/mul bad codegen for uint256+ #87

mratsim opened this issue Sep 25, 2019 · 3 comments
Labels
bug Something isn't working good first issue Good for newcomers Performance

Comments

@mratsim
Copy link
Contributor

mratsim commented Sep 25, 2019

Seen with @arnetheduck.

for uint128, stint properly generates add + adc (see #10)

But for uint256+, the way carry is done will loop multiple time on the low half

func `+`*(x, y: UintImpl): UintImpl {.inline.}
# Forward declaration
func `+=`*(x: var UintImpl, y: UintImpl) {.inline.}=
## In-place addition for multi-precision unsigned int
type SubTy = type x.lo
x.lo += y.lo
x.hi += (x.lo < y.lo).toSubtype(SubTy) + y.hi # This helps the compiler produce ADC (add with carry)
func `+`*(x, y: UintImpl): UintImpl {.inline.}=
# Addition for multi-precision unsigned int
result = x
result += y

Important for WASM codesize optimization.

@mratsim mratsim added bug Something isn't working Performance labels Sep 25, 2019
@arnetheduck
Copy link
Member

the issue here is that we lack an func addWithCarry(a, b: T): tuple[v: T, overflow: bool] operation - both for normal integers and for this library - with such an operation one can write a recursive version of the algorithm that lines up the operations and carries in a single pass instead of the current inefficient comparison+add

@arnetheduck arnetheduck added the good first issue Good for newcomers label Oct 23, 2019
@mratsim
Copy link
Contributor Author

mratsim commented Oct 23, 2019

Implementation can follow recint which also uses recursive high/low limbs: https://github.com/linbox-team/givaro/blob/v4.1.1/src/kernel/recint/ruadd.h#L170

@mratsim
Copy link
Contributor Author

mratsim commented Sep 28, 2023

Closed by array backend refactoring

@mratsim mratsim closed this as completed Sep 28, 2023
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
bug Something isn't working good first issue Good for newcomers Performance
Projects
None yet
Development

No branches or pull requests

2 participants