use a small, fast-to-iterate implementation of Map, MultiMap
Submitted by Simon McVittie
Assigned to fol..@..e.bugs
Link to original bug (#697379)
Description
Similar to Bug #653239, many of Folks' uses of Map and MultiMap have few keys and few values.
I've prototyped a C implementation similar to Folks.SmallSet, implemented in terms of a GArray<struct{void *, void *}>. It cuts 10% off my performance benchmark's time, but doesn't have proper test coverage, and probably still has implementation bugs (tests/eds/im-details fails).
Efficient things:
-
Quite memory-efficient (could be made better by not storing unnecessary callbacks)
-
Read-only views are about as efficient as they're going to get
-
get_keys() on "single" maps is O(n) C code, returning a SmallSet
-
map_iterator() is fast C code, although it still has to create a GObject per use, so it still accounts for about 3%
Inefficient things:
-
Membership testing scales up poorly: it's O(n)
-
As a result, adding/removing items is typically also O(n)
-
Adding/removing items from a multi-map can be as bad as O(n**2) because it keeps entries with the same key together in iteration order
-
Map.entries, Map.iterator() and Map.foreach() are never going to be efficient anyway, because they construct one GObject per item: I implemented Entry, entries and iterator() in Vala
-
Map.values, MultiMap.values, MultiMap.all_keys are also Vala code, although they don't account for many calls anyway
Possible future enhancements:
- get_key_at(int i), get_value_at(int i) are not implemented yet: they won't have syntax support, but could be used anyway in hot paths
I don't think I'm going to be able to finish this immediately, so I'm attaching my work-in-progress here.
Version: git master