[erlang-questions] ETS bag performance characteristics

[Sverker Eriksson]

Kris Rasmussen wrote:
> Hi,
>
> I am currently using the ETS bag table type to store a list of PIDs
> associated with a given key. I'm concerned that the bag implementation may
> require a linear traversal to remove (and possibly also add) elements to the
> bag. Does anyone know how ETS bags are implemented? Ideally, I'd like to
> have constant lookups by key as well as constant adds/contains/removals. If
> I were to implement this outside of erlang I would use a Map<String, Set>
> type data structure.
>   
All ETS tables, except ordered_set, are hash tables with separate 
chaining to resolve collisions.

On average constant time for insert/lookup/removal of scattered keys. A 
bag with lots of identical keys
may give bad performance as that will result in linear searches between 
objects with the same key
(and others that happen to hash to the same bucket).

ordered_set is implented as a binary AVL tree.

/Sverker, Erlang/OTP Ericsson