Possibility of non-u128 implementation of BigInteger

[weikengchen]

In ZPrize submission for the WASM tracks, people have been using different ways to improve the WASM efficiency. There is a common thesis: people use other languages, such as C or JS, to implement 30-bit limbs.

One possible reason: is it a side effect of using u128 if the target is WASM?
Note: uint128 even in x86-64 always is complied into a few instructions over uint64.

We need more experiments to see if the use of u128 as the intermediate is the issue.

[weikengchen]

And it seems that, even if two backends support u64 natively, whether or not they have "carry" would make things different.

[Pratyush]

We can implement a new arithmetic backend for our prime field elements which should make different backend possible.

[piotr-roslaniec]

Hello. I found that using u128 leads to generating a __multi3 WASM function that causes a large performance penalty. Please see a reproduction here: https://github.com/piotr-roslaniec/wasm32-u32-u128

Edit: I just realized that there is a possible mitigation awaiting to be released:

algebra/ff/src/biginteger/arithmetic.rs

Lines 92 to 103 in b33df5c

	#[cfg(target_family = "wasm")]
	{
	let a_lo = a as u32 as u64;
	let a_hi = a >> 32;
	let b_lo = b as u32 as u64;
	let b_hi = b >> 32;
	let lolo = (a_lo * b_lo) as u128;
	let lohi = ((a_lo * b_hi) as u128) << 32;
	let hilo = ((a_hi * b_lo) as u128) << 32;
	let hihi = ((a_hi * b_hi) as u128) << 64;
	(lolo | hihi) + (lohi + hilo)

[Pratyush]

Yes, we need to make a release with the new code!

[TalDerei]

Yes, we need to make a release with the new code!

this is great! what's the status of upstreaming these changes?