adler32 optimization

[SheetJSDev]

I've tested a few ways to optimize the 65521 mod operation. As evidenced by http://jsperf.com/mod-65521 replacing the mod with a bit-based approximation is significantly faster on safari, comparable in firefox and chrome, and about 10% faster in node 0.10.29.

Also:

// Set limit ~ twice less than 5552, to keep
// s2 in 31-bits, because we force signed ints.
// in other case %= will fail.

How did you arrive at that logic? As per my calculation, the upper threshold can be boosted to 3850 without overflowing a 31-bit integer:

(* Run this in Mathematica *)
F[n_] := Reduce[x*(x + 1)*n/2 + (x + 1)*(65521) < (2^31 - 1) && x > 0, x, Integers]
F[255] (*  x \[Element] Integers && 1 <= x <= 3854 *)

[puzrin]

5552 is limit for 32 bit int, calculated by someone clever :) . This constant exists in all implementations. I don't remember details.

Also, i can advice you to dig adler32 in native zlib sources, it has 2 unrollings. Those are stripped here as "not making sense for JS"

[SheetJSDev]

5552 is limit for 32 bit int, calculated by someone clever :)

@puzrin 5552 actually comes from the same formula (you assume the worst case):

(* Run this in Mathematica *)
(* n is the maximum value for a term -- 255 for bytes *)
(* bits is the size of the containing value -- 31 for signed 32 bit ints, 32 for unsigned *)
G[n_, bits_] :=  Reduce[x*(x + 1)*n/2 + (x + 1)*(65521) < (2^bits - 1) && x > 0, x, Integers]
G[255, 32] (* x \[Element] Integers && 1 <= x <= 5552 *)

[puzrin]

May be. There should be no noticeable difference, when this value > 1000 (benchmarked). I just quickly taken safe value and switched to another task.

[SheetJSDev]

On node, it appears the performance benefit comes from the structure of the loop:

Your loop involves two variables (n and pos), both moving in lockstep:

https://github.com/nodeca/pako/blob/master/lib/zlib/adler32.js#L19-L22

This can actually be done with one moving variable (calculate the intermediate goalpost and just increment the address):

https://github.com/SheetJS/js-adler32/blob/master/adler32.js#L27-L31

[puzrin]

May be, As i explainted in email, i have no special interest to participate in minor optimizations. If you wish - create a benchmark, that demonstrate that whole inflate/deflate can have noticeable benefits, and i'll be glad to accept pull request.

I'm not out of programming. Just have to concentrate on another tasks, like refactoring js-yaml, mincer and developping main nodeca project.

[puzrin]

Closed - timed out, not significant. When improvments, confirmed with pako benchmarcs available - just create a new ticket.