#1682 JS: improvement performance Map.containsKey

jessevdam Wed 26 Oct 2011

This is the current implementation of containsKey

fan.sys.Map.prototype.containsKey = function(key)
{
  var hash = this.hashKey(key);
  for (var k in this.keyMap)
    if (k == hash)
      return true;
  return false;
}

I think it can be replaced with the faster code

fan.sys.Map.prototype.containsKey = function(key)
{
  var k = this.hashKey(key);
  return this.keyMap[k] != null;
}

andy Wed 26 Oct 2011

Map.containsKey is not the same thing as value == null:

fansh> x := ["foo":null]
[foo:null]
fansh> x["foo"]
null
fansh> x.containsKey("foo")
true
fansh> x.remove("foo")
null
fansh> x.containsKey("foo")
false

Though I'm sure there are optimizations all over the place to be made.

alex_panchenko Wed 26 Oct 2011

this.keyMap[k] !== undefined ?

andy Wed 26 Oct 2011

this.keyMap[k] !== undefined

Yep that should do the trick.

andy Wed 26 Oct 2011

Actually a few things we could improve in here. Will take a look when I fix up Obj.hash stuff.

qualidafial Wed 26 Oct 2011

There is also Object.hasOwnProperty(name) which is roughly equivalent to containsKey.

One thing that concerns me about this implementation, is that it appears that the hash code is being used but not equals. Per the Java Oject.equals contract, it is possible for two objects to be unequal but have the same hash code.

So while unlikely, it's possible for different maps keys to conflict.

andy Wed 26 Oct 2011

There is also Object.hasOwnProperty(name) which is roughly equivalent to containsKey.

Yeah that would work too.

So while unlikely, it's possible for different maps keys to conflict.

Yep, my intent with the initial design here is the hashKey method will actually handle generating the unique key for our internal Object "map" - which will handle collisions. We'll beef all that up when we shore up support for proper Obj.hash use.

Related - anyone have any knowledge if JS engines optimize sparse Arrays if only integer keys are used? Or do they always fall back to using string keys?

andy Wed 9 Nov 2011

Fixed - see #1485

Login or Signup to reply.