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.