GNOME Bugzilla – Bug 697379
use a small, fast-to-iterate implementation of Map, MultiMap
Last modified: 2018-09-21 16:02:02 UTC
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.
Created attachment 240775 [details] [review] WiP: add and use FolksSmallMap, FolksSmallMultiMap
-- GitLab Migration Automatic Message -- This bug has been migrated to GNOME's GitLab instance and has been closed from further activity. You can subscribe and participate further through the new bug through this link to our GitLab instance: https://gitlab.gnome.org/GNOME/folks/issues/60.