What about backing cid.Set by a sorted slice rather than a map?

[aboodman]

It's pretty common when using cid.Set to want them to remain sorted. For example, if you're going to compare two sets, you need them to be sorted. If you're going to compute a hash representing the set, you need to do it over a sorted set, otherwise two hashes for equal sets won't be equal.

We could introduce a new cid.SortedSet for this use case, but I think it is worth considering making cid.Set always sorted and backing it by a sorted slice rather than a map.

I can't recall the exact details but I think insertion and lookup in a sorted slice in Go is negligibly different performance than into a map. More importantly, with a slice, you have the option of using a stack allocated array as the backing buffer, eliminating a heap allocation, reducing gc pressure.

[Stebalien]

I'm fine with that but I'd benchmark it. At the moment, it'll probably be faster as you'll be able to compare CIDs without allocating (while we currently end up allocating a string for the key). We've discussed using a string to back the CID (I believe there's an open PR) but this would probably require a bit of refactoring.

[dignifiedquire]

string pr is in #47

[anorth]

As reference, go-filecoin implements an immutable sorted CID set in a slice as TipSetKey.