bignumber.js vs long.js

[achingbrain]

I was porting rabin to JavaScript to add support for rabin chunking in the browser - the c algorithm uses lots of bitwise operations on uint64_t types which JavaScript cannot do because lol JavaScript 'numbers'.

I used the long.js module to do this. A passing @olizilla said 'Why don't you use bignumber.js like all our other projects?' 'Good point' I said and started to refactor.

..but then:

Turns out the support for bitwise operations in bignumber.js is pretty poor and there's not a lot of movement to add support. There have been a few attempts but no successes - see MikeMcl/bignumber.js#2 and the issues linked from MikeMcl/bignumber.js#229

long.js has support for all bitwise operations and also in a nicer* way for those that bignumber.js does support (e.g. long.shiftLeft(8) vs big.shiftedBy(-8)).

It's also smaller - the minified versions shipped with both modules are 9.6k (long.js) vs 18k (bignumber.js).

I don't want to propose swapping bignumber.js for long.js everywhere but it doesn't make a lot of sense to have two modules for this.

Anyone got any thoughts? @ipfs/repos-javascript

* = completely subjective

[mcollina]

I would recommend a WASM implementation instead.

[hugomrdias]

Exactly! This could be a great way to test out assemblyscript. Or if you find it too time consuming a rustwasm solution. Ping if you need help.

[achingbrain]

I would recommend a WASM implementation instead

@mcollina do you have one in mind or are you suggesting implementing one?

[dignifiedquire]

I maintain a pure rust bignum library, happy to chat and help if useful :)

[dignifiedquire]

https://github.com/dignifiedquire/num-bigint

[MaxGraey]

@hugomrdias On AssemblyScript we have bignum library btw: https://github.com/MaxGraey/bignum.wasm. But it still missing some methods for u256/i256 classes but u128 fully implemented

btw long.js uses WebAssembly internally if browser / node support it

[mcollina]

How about using https://github.com/fd0/lbfs/tree/bdf4f17d23b68536e7805c88e269026c74c32d59/liblbfs like https://www.npmjs.com/package/rabin?

[achingbrain]

btw long.js uses WebAssembly internally if browser / node support it

Assuming the implementation is sensible it doesn't seem like we'd gain much from writing our own then.

[mcollina]

Moving from WebAssembly to JS and viceversa cost time. Moving back-and-forth for every number operation is going to be more costly than moving back-and-forth for each chunk of data.

I'd still explore compiling https://github.com/fd0/lbfs/tree/bdf4f17d23b68536e7805c88e269026c74c32d59/liblbfs to WebAssembly and measuring throughput.

[hugomrdias]

just got as wasm rabin working https://github.com/hugomrdias/rabin-wasm
needs a bit of cleaning up, for now its just a drop in for https://github.com/datproject/rabin so dont pay to much attention to the streams code.

@MaxGraey would be awesome if you could check if i left some performance hanging on the assemblyscript side. its my first assemblyscript project so the code can probably be improved.

[MaxGraey]

@hugomrdias LGTM. Minor tips:

1. If you want to avoid bound checking during access to array better use unchecked(expr) like:

unchecked(lengths[chunk_idx++] = <i32>this.chunk_length)
// or
let t = unchecked(arr[i])

2. here you could rewrite loop with do while for reusing degree(x) - degree(p) which calculate twice. Once in condition and second during subtraction

[hugomrdias]

@MaxGraey i get an error memory access out of bounds with the unchecked. Is unchecked only for i32[] or am i doing something wrong ?

[MaxGraey]

@hugomrdias it accept for any kind of array. About error. I saw you use "allocator/tlsf" it has some bugs in muster which cause memory corruption sometimes. But this memory issues already fixed in dev branch. Now you could try switch to arena allocator instead for now. If OOB still exists that's mean you doing something wrong in algorithm and you should recheck

For example. You allocate length buffer outside (in host): https://github.com/hugomrdias/rabin-wasm/blob/master/index.js#L16

may be better use: new Int32Array(Math.ceil(buf.length/this.min)) or

new Int32Array(Math.ceil(buf.length/(this.max - this.min)))

I'm not sure

[hugomrdias]

@MaxGraey that allocation is weird ... because i don't know before hand the size of the array so i allocate the maximum possible size and remove the extra 0s after.
i could use a normal array (which resizes automatically) in the AS side and return the pointer with a linked function or something but i couldn't figure out how to properly clean the mem. Should i go load/store manually and remove the allocator?

[MaxGraey]

You could wait new release of AS which allow usual arrays during export or you could use temporal dynamic Array<u32> with push method and copy it later to UInt32Array which actually your output.