Js-ipfs: 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 https://github.com/MikeMcl/bignumber.js/issues/2 and the issues linked from https://github.com/MikeMcl/bignumber.js/issues/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])

1. 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.

[hugomrdias]

@MaxGraey thank you!! problem fixed and regarding the array auto grow ill wait for the next release for now.

i pushed a new version with lots of goodies, browser support, types, umd bundle, a wasm2commonjs tool so i can just require in the browser and node.

This wasm2js tool will be extracted into a new module to be re-used, could be helpful to others if we add it to the AS wiki.

[MaxGraey]

Also I recommend use -O3 instead --optimize here

[hugomrdias]

@MaxGraey what about shinkLevel ?

[hugomrdias]

-O3z for --optimizeLevel 3 and --shrinkLevel 2 ?

[MaxGraey]

yes, -O3z is equivalent to --optimizeLevel 3 + --shrinkLevel 2
--optimize equivalent to --optimizeLevel 2 + --shrinkLevel 1

[hugomrdias]

final results show
native rabin x 0.51 ops/sec ±2.56% (7 runs sampled)
wasm rabin x 0.23 ops/sec ±2.72% (6 runs sampled)
js rabin x 0.05 ops/sec ±3.78% (5 runs sampled)

with Package size: 4.66 KB with all dependencies, minified and gzipped (inlined in a single file for easier distribution)

https://github.com/ipfs/js-ipfs-unixfs-importer/pull/31#issue-284161888

[alanshaw]

Closing this one now, thanks for all the input!

We have WASM Rabin now and long.js _might_ be slower and a bunch of work to refactor and use everywhere so lets stick with bignumber.js for now!

[lidel]

Relevant news: Firefox 68 shipped support for BigInt.
This means both Chromium 67+ and Firefox 68+ now support it.
I imagine libraries will take advantage of this at some point.

BigInt is currently in stage 3 of the ECMAScript specification.
When it makes it to stage 4 of the draft, which is the final specification, BigInt will become the second built-in numeric type in JavaScript. BigInt is slated to become the first new primitive type added to JavaScript since Symbol in ES2015.
– https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/BigInt