483870 - Make a fast map abstraction (hashtable)

Status: RESOLVED DUPLICATE of bug 697479

(Core :: JavaScript Engine, defect)

Description

[David Mandelin [:dmandelin]]

Attachment: First cut JS hash & perf tester

As we all know, the map abstraction (aka dictionary, associative array, "hashtable") is essential, and JS doesn't really have one.

A common solution is to use an empty object's properties as a map. This isn't a very good solution because it runs afoul of inherited properties and it only supports string keys. A big problem is that in TM, this actually runs about 3x slower with the jit on (see attachment with jit on/off; see also bug 483457).

Another solution is simply to implement a hash table or other such data structure in pure JS. I did this 3 different ways, and they all run OK under tracing but not great. With a reasonable but probably not ideal tune, I get about 5-6x slower for put/get operations vs. the object implementation.

Running 5-6x slower than C is actually excellent for a language like JS. I found that the biggest costs were in rehashing (seems hard to avoid too much) and then in the hash function itself (which should probably be specially optimized for TM). 

Ideally, I'd like to have a highly tuned pure JS hashtable that has a 1.5x slowdown or less vs. the object implementation. That will take a while but 3x would also be a great intermediate target. I imagine this will require optimizations to both the JS hashtable implementation and TM.

Here's a summary of some scores, all total times in ms:

                  TM-nojit       TM        SFX        V8
js hash impl        180         100        120        72
object impl          16          33         16        12

Key points:

- our best-case map performance on TM is hurting right now
- we do pretty well on the js hash compared to competition but have room to improve vs. v8
- v8 somehow has faster object access

Comment 1

[Ryan VanderMeulen [:RyanVM]]

			Interp	JM	JM+TI	d8
StringHashMap fill:	141	18	12	16
StringHashMap check:	37	5	6	5
JSObjHashMap  fill:	12	12	12	6
JSObjHashMap  check:	7	6	6	4

Looks like there's still room for improvement here?

Comment 2

[David Mandelin [:dmandelin]]

Heh, I forgot about filing this bug. :-) I think it can be dup'd forward to Harmony maps.