[erlang-questions] ets:slot() on ordered_set

Ulf Wiger (TN/EAB) ulf.wiger@REDACTED
Tue Sep 4 16:45:13 CEST 2007

I had reason to look into the behaviour of ets:slot/2
on ordered_set tables.

It's either really cool, or really bad, depending on
what you want to do with it.

The thing is that erl_db_tree.c caches the slot position
from the previous operation, and the function db_slot()
traverses the tree from the cached position to the new
position. This is wonderful if the slot asked for is
adjacent to the previous slot; otherwise - not so

Consider the sloppy benchmark below. It creates a
table, and fills it with data. It then reads each
slot, once in order, and once with the positions
shuffled about.

Eshell V5.5.5  (abort with ^G)
1> c(slots).
2> slots:ordset(10).
3> slots:ordset(100).
4> slots:ordset(1000).
5> slots:ordset(10000).

The values are {TimeShuffled, TimeOrdered, Ratio},
and it's very obvious that jumping about using slot()
in a large ordered_set table is a very bad idea.

Ulf W



s([A|B],T) ->
     ets:slot(T, A),
s([],_) ->

ordset(N) -> go(ordered_set,N).

go(Type,N) ->
     T = ets:new(t,[Type]),
     L = lists:seq(1,N),
     [ets:insert(T, {N1}) || N1 <- lists:seq(1,N)],
     L1 = shuffle(L),
     {T1,ok} = timer:tc(?MODULE,s,[L1,T]),
     {T2,ok} = timer:tc(?MODULE,s,[L,T]),
     {T1/N, T2/N, T1 div T2}.

shuffle(L) ->
     Mid = length(L) div 2,
     L1 = lists:sublist(L,1,Mid),
     L2 = lists:nthtail(Mid,L),

splice([H|T],[H1|T1]) ->
     [H,H1 | splice(T,T1)];
splice([],[H]) -> [H];
splice([H],[]) -> [H];
splice([], []) ->

More information about the erlang-questions mailing list