Skip to content

Commit d0e9ff9

Browse files
SheetJSDevSheetJSDev
committed
version bump 0.2.0: safari performance
On Safari, bit twiddling is 50% faster than directly evaluating mod 65521
1 parent b53334d commit d0e9ff9

File tree

6 files changed

+88
-51
lines changed

6 files changed

+88
-51
lines changed

‎README.md

Lines changed: 11 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -51,6 +51,17 @@ decisions in the code).
5151

5252
[js-crc](http://git.io/crc32) has more performance notes
5353

54+
Bit twiddling is much faster than taking the mod on Safari and older Firefoxes.
55+
Instead of taking the literal mod 65521, it is faster to keep it in the integers
56+
by bit-shifting: `65536 ~ 15 mod 65521` so for nonnegative integer `a`:
57+
58+
```
59+
a = (a >>> 16) * 65536 + (a & 65535) [equality]
60+
a ~ (a >>> 16) * 15 + (a & 65535) mod 65521
61+
```
62+
63+
The mod is taken at the very end, since the intermediate result may exceed 65521
64+
5465
## Magic Number
5566

5667
The magic numbers were chosen so as to not overflow a 31-bit integer:

‎adler32.js

Lines changed: 13 additions & 13 deletions
Original file line numberDiff line numberDiff line change
@@ -10,29 +10,29 @@ function adler32_bstr(bstr) {
1010
if(bstr.length > 32768) if(use_buffer) return adler32_buf(Buffer(bstr));
1111
var a = 1, b = 0, L = bstr.length, M;
1212
for(var i = 0; i < L;) {
13-
M = Math.min(L-i, 3854);
14-
for(;M>0;--M) {
15-
a += bstr.charCodeAt(i++);
13+
M = Math.min(L-i, 3850)+i;
14+
for(;i<M;i++) {
15+
a += bstr.charCodeAt(i);
1616
b += a;
1717
}
18-
a %= 65521;
19-
b %= 65521;
18+
a = (15*(a>>>16)+(a&65535))
19+
b = (15*(b>>>16)+(b&65535))
2020
}
21-
return b > 32767 ? (((b - 65536) * 65536) | a) : ((b * 65536) | a);
21+
return ((b%65521) << 16) | (a%65521);
2222
}
2323

2424
function adler32_buf(buf) {
2525
var a = 1, b = 0, L = buf.length, M;
2626
for(var i = 0; i < L;) {
27-
M = Math.min(L-i, 3854);
28-
for(;M>0;--M) {
29-
a += buf[i++];
27+
M = Math.min(L-i, 3850)+i;
28+
for(;i<M;i++) {
29+
a += buf[i];
3030
b += a;
3131
}
32-
a %= 65521;
33-
b %= 65521;
32+
a = (15*(a>>>16)+(a&65535))
33+
b = (15*(b>>>16)+(b&65535))
3434
}
35-
return b > 32767 ? (((b - 65536) * 65536) | a) : ((b * 65536) | a);
35+
return ((b%65521) << 16) | (a%65521);
3636
}
3737

3838
/* much much faster to intertwine utf8 and adler */
@@ -61,7 +61,7 @@ function adler32_str(str) {
6161
a %= 65521;
6262
b %= 65521;
6363
}
64-
return b > 32767 ? (((b - 65536) * 65536) | a) : ((b * 65536) | a);
64+
return (b << 16) | a;
6565
}
6666
ADLER32.bstr = adler32_bstr;
6767
ADLER32.buf = adler32_buf;

‎bits/40_adler.js

Lines changed: 13 additions & 13 deletions
Original file line numberDiff line numberDiff line change
@@ -5,29 +5,29 @@ function adler32_bstr(bstr) {
55
if(bstr.length > 32768) if(use_buffer) return adler32_buf(Buffer(bstr));
66
var a = 1, b = 0, L = bstr.length, M;
77
for(var i = 0; i < L;) {
8-
M = Math.min(L-i, 3854);
9-
for(;M>0;--M) {
10-
a += bstr.charCodeAt(i++);
8+
M = Math.min(L-i, 3850)+i;
9+
for(;i<M;i++) {
10+
a += bstr.charCodeAt(i);
1111
b += a;
1212
}
13-
a %= 65521;
14-
b %= 65521;
13+
a = (15*(a>>>16)+(a&65535))
14+
b = (15*(b>>>16)+(b&65535))
1515
}
16-
return b > 32767 ? (((b - 65536) * 65536) | a) : ((b * 65536) | a);
16+
return ((b%65521) << 16) | (a%65521);
1717
}
1818

1919
function adler32_buf(buf) {
2020
var a = 1, b = 0, L = buf.length, M;
2121
for(var i = 0; i < L;) {
22-
M = Math.min(L-i, 3854);
23-
for(;M>0;--M) {
24-
a += buf[i++];
22+
M = Math.min(L-i, 3850)+i;
23+
for(;i<M;i++) {
24+
a += buf[i];
2525
b += a;
2626
}
27-
a %= 65521;
28-
b %= 65521;
27+
a = (15*(a>>>16)+(a&65535))
28+
b = (15*(b>>>16)+(b&65535))
2929
}
30-
return b > 32767 ? (((b - 65536) * 65536) | a) : ((b * 65536) | a);
30+
return ((b%65521) << 16) | (a%65521);
3131
}
3232

3333
/* much much faster to intertwine utf8 and adler */
@@ -56,5 +56,5 @@ function adler32_str(str) {
5656
a %= 65521;
5757
b %= 65521;
5858
}
59-
return b > 32767 ? (((b - 65536) * 65536) | a) : ((b * 65536) | a);
59+
return (b << 16) | a;
6060
}

‎ctest/adler32.js

Lines changed: 13 additions & 13 deletions
Original file line numberDiff line numberDiff line change
@@ -10,29 +10,29 @@ function adler32_bstr(bstr) {
1010
if(bstr.length > 32768) if(use_buffer) return adler32_buf(Buffer(bstr));
1111
var a = 1, b = 0, L = bstr.length, M;
1212
for(var i = 0; i < L;) {
13-
M = Math.min(L-i, 3854);
14-
for(;M>0;--M) {
15-
a += bstr.charCodeAt(i++);
13+
M = Math.min(L-i, 3850)+i;
14+
for(;i<M;i++) {
15+
a += bstr.charCodeAt(i);
1616
b += a;
1717
}
18-
a %= 65521;
19-
b %= 65521;
18+
a = (15*(a>>>16)+(a&65535))
19+
b = (15*(b>>>16)+(b&65535))
2020
}
21-
return b > 32767 ? (((b - 65536) * 65536) | a) : ((b * 65536) | a);
21+
return ((b%65521) << 16) | (a%65521);
2222
}
2323

2424
function adler32_buf(buf) {
2525
var a = 1, b = 0, L = buf.length, M;
2626
for(var i = 0; i < L;) {
27-
M = Math.min(L-i, 3854);
28-
for(;M>0;--M) {
29-
a += buf[i++];
27+
M = Math.min(L-i, 3850)+i;
28+
for(;i<M;i++) {
29+
a += buf[i];
3030
b += a;
3131
}
32-
a %= 65521;
33-
b %= 65521;
32+
a = (15*(a>>>16)+(a&65535))
33+
b = (15*(b>>>16)+(b&65535))
3434
}
35-
return b > 32767 ? (((b - 65536) * 65536) | a) : ((b * 65536) | a);
35+
return ((b%65521) << 16) | (a%65521);
3636
}
3737

3838
/* much much faster to intertwine utf8 and adler */
@@ -61,7 +61,7 @@ function adler32_str(str) {
6161
a %= 65521;
6262
b %= 65521;
6363
}
64-
return b > 32767 ? (((b - 65536) * 65536) | a) : ((b * 65536) | a);
64+
return (b << 16) | a;
6565
}
6666
ADLER32.bstr = adler32_bstr;
6767
ADLER32.buf = adler32_buf;

‎package.json

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,6 +1,6 @@
11
{
22
"name": "adler-32",
3-
"version": "0.1.0",
3+
"version": "0.2.0",
44
"author": "sheetjs",
55
"description": "Pure-JS ADLER-32",
66
"keywords": [ "adler32", "checksum" ],

‎perf/bstr.js

Lines changed: 37 additions & 11 deletions
Original file line numberDiff line numberDiff line change
@@ -1,5 +1,3 @@
1-
var table = require('../').table;
2-
31
function sheetjs1(bstr) {
42
var a = 1, b = 0, L = bstr.length;
53
for(var i = 0; i < L;) {
@@ -14,7 +12,21 @@ function sheetjs1(bstr) {
1412
function sheetjs2(bstr) {
1513
var a = 1, b = 0, L = bstr.length, M;
1614
for(var i = 0; i < L;) {
17-
M = Math.min(L-i, 3854);
15+
M = Math.min(L-i, 3850)+i;
16+
for(;i<M;i++) {
17+
a += bstr.charCodeAt(i);
18+
b += a;
19+
}
20+
a = (15*(a>>>16)+(a&65535))
21+
b = (15*(b>>>16)+(b&65535))
22+
}
23+
return ((b%65521) << 16) | (a%65521);
24+
}
25+
26+
function sheetjs3(bstr) {
27+
var a = 1, b = 0, L = bstr.length, M;
28+
for(var i = 0; i < L;) {
29+
M = Math.min(L-i, 5552);
1830
for(;M>0;--M) {
1931
a += bstr.charCodeAt(i++);
2032
b += a;
@@ -25,14 +37,28 @@ function sheetjs2(bstr) {
2537
return (b << 16) | a;
2638
}
2739

28-
var foobar = "foobarbazqux";
29-
for(var i = 0; i != 11; ++i) foobar += " " + foobar;
40+
var foobar = [255,255,255,255,255,255].map(function(x) { return String.fromCharCode(x); }).join("");
41+
foobar += foobar;
42+
foobar += foobar;
43+
foobar += foobar;
44+
foobar += foobar;
45+
foobar += foobar;
46+
foobar += foobar;
47+
foobar.charCodeAt(0);
48+
var m = 2048;
3049
var assert = require('assert');
31-
assert.equal(sheetjs1(foobar), sheetjs2(foobar));
32-
3350
var BM = require('./bm');
34-
var suite = new BM('binary string');
51+
for(var i = 0; i != 14; ++i) {
52+
foobar += foobar;
53+
foobar.charCodeAt(0);
54+
assert.equal(sheetjs1(foobar), sheetjs3(foobar));
55+
assert.equal(sheetjs1(foobar), sheetjs2(foobar));
56+
//for(var j = 0; j != 200; ++j) assert.equal(sheetjs2(foobar), sheetjs3(foobar));
57+
var suite = new BM('binary string (' + foobar.length + ')');
3558

36-
suite.add('sheetjs 1', function() { for(var j = 0; j != 1000; ++j) sheetjs1(foobar); });
37-
suite.add('sheetjs 2', function() { for(var j = 0; j != 1000; ++j) sheetjs2(foobar); });
38-
suite.run();
59+
if(i<3) suite.add('sheetjs 1', function() { for(var j = 0; j != m; ++j) sheetjs1(foobar); });
60+
suite.add('sheetjs 2', function() { for(var j = 0; j != m; ++j) sheetjs2(foobar); });
61+
suite.add('sheetjs 3', function() { for(var j = 0; j != m; ++j) sheetjs3(foobar); });
62+
suite.run();
63+
m>>>=1; if(m < 10) m = 10;
64+
}

0 commit comments

Comments
 (0)