Status: Accepted
Owner: ----
CC: [email protected]
Labels: Type-Bug Priority-Medium
New issue 2734 by [email protected]: StringDictionary store is very slow
http://code.google.com/p/v8/issues/detail?id=2734
It's cheaper (up to 10x) to have an additional indirection than to update a
existing dictionary:
var text = ["The", "quick", "brown", "fox", "jumped", "over", "the",
"lazy", "dog", "at", "a", "restaurant", "near", "the", "lake", "of",
"a", "new", "era"],
map;
function loop1() {
for (var k = 0; k < text.length; k++) {
map[text[k]] = map[text[k]] || 0
map[text[k]]++
}
}
function loop2() {
for (var k = 0; k < text.length; k++) {
var key = text[k]
map[key] = (map[key] || 0) + 1
}
}
function loop3() {
for (var k = 0; k < text.length; k++) {
var a = map[text[k]];
if(typeof a !== 'undefined'){
a.c++;
continue;
}
map[text[k]] = { c: 1 };
}
}
function measure(cb) {
map = {};
var start = Date.now();
for (var i = 0; i < 100000; i++) cb();
print(cb.name + ': ' + (Date.now() - start) + ' ms.');
}
measure(loop1);
measure(loop2);
measure(loop3);
Results in the shell:
∮ out/ia32.release/d8 p.js
loop1: 411 ms.
loop2: 179 ms.
loop3: 19 ms.
Results in the browser:
Canary:
loop1: 482 ms.
loop2: 249 ms.
loop3: 28 ms.
WebKit nightly:
loop1: 291 ms.
loop2: 151 ms.
loop3: 56 ms.
You can see that JSC is doing better but not in the "indirection" case.
Champion of dictionary implementations is LuaJIT2, for equivalent code:
function loop1()
for k = 1, #text do
map[text[k]] = map[text[k]] or 0
map[text[k]] = map[text[k]] + 1
end
end
it produces the following extremely tight loop body IR (when the map is
completely initialized):
0023 ------ LOOP ------------
0024 p32 AREF 0011 0021
0025 > str ALOAD 0024
0026 p32 HREF 0006 0025
0027 > num HLOAD 0026
0028 num ADD 0027 +1
0029 num HSTORE 0026 0028
0030 + int ADD 0021 +1
0031 > int LE 0030 0001
0032 int PHI 0021 0030
and gets 10x better result:
loop1: 23 ms.
(notice how dictionary operations are split into cell calculation and
respective load/store which allows to eliminate redundancy)
--
You received this message because this project is configured to send all
issue notifications to this address.
You may adjust your notification preferences at:
https://code.google.com/hosting/settings
--
--
v8-dev mailing list
[email protected]
http://groups.google.com/group/v8-dev
---
You received this message because you are subscribed to the Google Groups "v8-dev" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
For more options, visit https://groups.google.com/groups/opt_out.
