[erlang-questions] Can gen_tcp/inets store connection-specific user state?

Tony Rogvall tony@REDACTED
Tue Jul 20 19:00:43 CEST 2010


On 20 jul 2010, at 18.46, Tony Arcieri wrote:

> On Tue, Jul 20, 2010 at 5:57 AM, Tony Rogvall <tony@REDACTED> wrote:
> 
>> Why do you lose the O(1) ? ets:lookup on a set table is O(1) ?  ordered_set
>> is O(log(N)) .
>> Please enlighten me ;-)
>> 
> 
> I'm afraid you're the one who will have to enlighten me here.
> 
> My understanding is that ETS are implemented as Judy tables, which I know
> very little about and sound rather complicated.  I can't find specific
> details about the algorithmic complexity of Judy lookup, except one
> reference to it being worse case O(log_256 n).  Are you suggesting it
> is amortized O(1) or something?

ets set tables are implemented using linear hashing.
ets ordered_set tables are implemented  using avl tree.

/Tony



More information about the erlang-questions mailing list