ipfs / ipfs/go-cid

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

Open
#45 3 comments 0 reactions 0 assignees View on GitHub
Dominant language
Go
Stars
171
Forks
50
PR merge metrics
No merged PRs in 30d

Description

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.

Contributor guide

No contributing guide indexed for this repository

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.