The primary application of this library is to track user names or user principals inside a service canister and to assign permanent numerical user ids to them.
Enumeration is an add-only set which keeps track of the order in which elements were added. Efficient lookups are provided in both ways, from an element to its order number and from an order number to the element.
For example, when user principals sign up for a service then they get a numerical user id in the order in which they signed up. We want to resolve a principal to a user id and vice versa. This is what Enumeration allows - a two-way lookup. The assumption is that user ids and principals are stored forever, never deleted.
The underlying implementation is an array plus a red-black tree. The two are interwoven to optimize for memory efficiency. We benchmarked the library against other comparable maps such as btree, RBTree from base and map (v7 and v8). It performs well in comparison even though it provides more functionality by being a two-way map instead of a one-way map. The benchmarking results can be found in the README.
Memory-wise Enumeration is close to the leader btree (it uses 3 bytes more than btree per entry). For example, storing 32-byte blobs (what principals need) in Enumeration requires 68 bytes per entry.
Time-wise Enumeration is slightly slower than RBTree from base, which is the result of a trade-off made for higher memory efficiency. However, it should be noted that in practice the use of Enumeration should result in saving time. The idea is to write the service canister entirely around numerical ids as user identifiers. This saves time and memory compared to using principals as user identifiers by storing user data in simple arrays. The only place where principals occur is in Enumeration, i.e. the use of principals is confined to one place. The lookup from principal → user id happens once at the beginning of a call and never again during the same call because all subsequent data access is based on user id. It is cheaper to do one lookup with Enumeration than doing multiple lookups with any of the other map data structures.