proposal for efficient 64-bit arithmetic without value objects
Vyacheslav Egorov
me at mrale.ph
Wed Oct 30 08:43:35 PDT 2013
Hi,
There are algorithms that require 64-bit arithmetic, however currently
JavaScript does not provide any efficient way to perform it.
Similar to Math.imul which was added for the purposes of efficient
32-bit multiplication I propose extending Math object with a family of
operations Math.<s>64<op> where <s> is one of {i, u} and <op> is one
of { sub, add, mul, div, neg }
These functions are specified as follows for <op> in { sub, add, mul, div }:
Math.<s>64<op>
1. accepts 4 arguments al, ah, bl, bh
2. x' = ToUint32(x), for x in {al, ah, bl, bh }
3. pairs (al', ah') and (bl', bh') are interpreted as 64-bit signed
(if <s> == i) or unsigned (if <s> == u) integer values with first
member of the pair containing low bits and second - high bits.
4. Result is computed as a standard overflowing operation on 64-bit
values and is decomposed into two int32 values (cl', ch') = (al', ah')
<op> (bl', bh')
5. A one shot property Math.H is created that returns ch' on the first
access and deletes itself.
6. Return cl'
Unary operation is specified in a similar straightforward fashion.
Here is addition of three unsigned 64bit integers using described functions:
var al, ah, bl, bh, cl, ch, dl, dh;
dl = Math.u64add(Math.u64add(al, ah, bl, bh), Math.H, cl, ch);
dh = Math.H;
This API is designed purposefully to allow good optimizations of the
resulting code, e.g. optimizing compiler knowing one shot semantics of
H property can eradicate any memory traffic and keep things in
registers even collocating (dl, dh) to a single 64-bit register on
64-bit platform.
I think such API has many advantages:
- can greatly improve performance of numeric algorithms relying on 64-bit math;
- easily polyfillable in the current JavaScript;
- does not depend on any complicated language changes (e.g. value objects);
- simple to implement and optimize on any platform (including 32bit ones);
--
Vyacheslav Egorov
More information about the es-discuss
mailing list