[erlang-questions] Ets bag complexity

[Jesper Louis Andersen]

On Dec 10, 2012, at 1:20 PM, Gleb Peregud <gleber.p@REDACTED> wrote:

> As far as I can understand from paper [1] by Scott Lystic Fritchie ETS
> tables of 'bag' type are implemented as a hash table with linear
> arrays of values attached to each key?

This reminds me of this weeks funny revelation. I have an ETS duplicate_bag of the form {Key, Value}. Now I thought that I could save something by changing the code into using {Key, [Value, …]} in a set since I use lookup_element/3 on it to pick out the list of values. Surely, I can avoid the linear walk of the tuples and the gathering of the list, which would be much faster, right?

The speed was the same as before. Though I did not check the memory usage :) I guess that the price of copying the data set into the Process is around the same as before and this dwarfs the run time.

Jesper Louis Andersen
  Erlang Solutions Ltd., Copenhagen