Map and Collection performance
Michael
noticed that the implementation of filter is extremely slow.
For example
function fn(item){
return false;
}
Col10k.filter(fn,this);
can take upward of 10 seconds on my computer (FF browser) for a
collection of 10 thousand items. The culprit seems to be a
combination of the strategy user for filter and the performance of
Array.splice and in this light the above test (returning false for
everything) is particularly hash.
Map uses an approach of
1) Make a copy
2) test each item, and remove those that fail
The remove operation is expensive, and may be repeated many many
times.
If instead a simple add if it passes test rule is used performance is
much improved.
base2.Map.prototype.filter = function(text,context){
var copy = this.copy();
copy.clear();
//These two steps could be combined and streamlined to prevent items
in the collection from being
//copied and then thrown away. Of even apply the test in the
initial copy
//This way however does allow for code reuse between Map and
Collection
this.forEach(function(item,itemkey){
if(test.call(context,item,itemkey,this)){
copy.put(itemkey,item);
}
},this);
return copy;
}
Now the same test take only a fraction of a second (100ms). Making
the result always return true (to include everything, (harsh test for
this implementation)), or indeed all options in the middle, still
don't slow performance to anything like the point of the start full
and remove approach.
I'm sure further optimizations could be made especially if modifying
the base2 code directly. I kinda shied away from that so I don't
loose edits later on. In addition of course it's a game of decreasing
returns and in this case a 10x speedup was sufficient.
Hope this is useful to someone. I know base2 has been tremendously
useful to me.
Dean Edwards
> I've been working with some pretty large base2.collections and have
> noticed that the implementation of filter is extremely slow.
I've been using Map and Collection quite heavily myself recently and
noticed the same issues.
The good news is that I've recently rewritten the internals of Map and
Collection and now they are lightning fast. I inlined all of the
looping so that the code no longer makes lots of function calls. The
functional approach made for very readable code but does not perform
well with large Collections.
If you are using Map and Collection a lot then can you tell me a bit
how you use them and what you like and don't like about them? In the
process of rewriting I made some changes that I wasn't sure about so
would appreciate some feedback.
I'll quickly outline the changes:
1. Map::map() now returns a new Map instead of an Array
2. Collection::map() now returns a new Collection instead of an Array
3. Map::filter and Collection::filter return a copy of the object with
the filtered items removed
4. Map::imap() iterates the values of the Map/Collection and returns an Array
5. Enumerable.map (the generic function) will return different things
depending on the type of object:
* If the object has a map() method then it will delegate to that method
* If the object is array-like then it will use Array.map
* For any other object it will return an Object with the mapped key/values.
Do you agree with these changes? If not then it is not too late to
revert. Do you have any other thoughts/ideas on how to improve
Map/Collection?
I'd be quite keen to send you the new code to play with. Bear in mind
though that base2 version 2.0 is not backwardly compatible with
version 1.0. There is only one major change which affects the Package
class. The other changes I have already mentioned. There is also a
small change to RegGrp but I think that I am the only one that uses
that class. :)
I'm going to check-in a beta of version 2.0 in the next couple of
weeks. But if anyone wants a sneak peak then shout up!
-dean
Michael
be a good thing. Its also somewhat refreshing to see that other
people are fighting the performance vs readable/maintainable battle
with similar results.I'm still looking forward to the day when browser
writers (I'm thinking MS in particular) start taking JS performace
seriously.
Most of my use of collections comes from trying to migrate C# and or
python code from the server to the client, so a lot of the work is
simple enumeration or quick lookups. I like the base2 implementation
for a number of reasons. First up, it's standards driven, and this is
a biggie for me. I'd rather change my code and requirements slightly
if it means I don't have to keep rewriting every couple of years. So
I think starting with ES4 Map at least in terms of an interface was a
great start. I also like how the Enumeration stuff plugs in, and this
often fulfils the requirement of translating simple LINQ queries.
As I do have existing code and libraries from other sources I think
it's important that any Map/Collection type objects retain the ability
to be used or easily (and quickly) converted to normal JSON style
objects (for hashes) or Arrays (Keys and Values) as these are often a
point of interchange with other code bases. It also means that where
browsers do support more recent JS implementations Array functions
like forEach,filter etc can be used, and it seems likely that going
forward these native implementations have the potential to be faster
than anything we can write in JS.
1+2) I think the map and collection returning typed objects is a good
move. Seems sensible.
3) I was under the impression that map.filter and collection.filter
already did this? I think I favor the start with empty and fill with
those things that pass approach, but this may be a result of my
application. Many of my filters return only very few objects. It
seems wasteful and memory intensive to copy everything, only to then
delete it.
4) Good - see above.
5) Sounds reasonable. I think this is something that I'd have to
actually use before commenting on.
I'd love to have a go with the latest code. I don't use Base2 package
mechanism at all, so backward compatibility won't be a problem. Send
me a copy, I'm always happy to feed back on what I find. At the
moment my fingerprint on base2 is pretty light, mainly the inheritence
stuff (originally all I intended to use it for), collections and a few
bits of the DOM stuff, but I only expect it to grow as time goes on.
I use a load on demand system with a server side on the fly packer
(similar to Ext.js if you are familiar with that library) and haven't
got this to play nicely with packages yet, but that might all change
with a version 2.
I think what I like best about base2 is that often I don't even
realise that it is being used. I just write code as it "seem right"
and often it "just works", in all browsers. Thats the appeal for me.
A library that I don't even know it's there is the best kind.
-Michael
Dean Edwards
> 1+2) I think the map and collection returning typed objects is a good
> move. Seems sensible.
That's a relief. I wasn't sure if it was a good idea or not.
> 3) I was under the impression that map.filter and collection.filter
> already did this?
Yes they do. My bad.
> 4) Good - see above.
Good!
> I'd love to have a go with the latest code.
OK. I'll email you it soon. I'm trying to fix an IE7.js bug this weekend
so it may be a few days before I can get back to base2.
> I think what I like best about base2 is that often I don't even
> realise that it is being used. I just write code as it "seem right"
> and often it "just works", in all browsers. Thats the appeal for me.
> A library that I don't even know it's there is the best kind.
Great! That's how I tried to write it. I think I need some good starter
tutorials and examples for base2 to take off. With version 2.0 I feel
quite comfortable promoting the library.
Thanks for taking the time to respond in depth. :)
-dean