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

[Ulf Wiger (TN/EAB)]

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
wonderful.

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).
{ok,slots}
2> slots:ordset(10).
{1.70000,0.600000,2}
3> slots:ordset(100).
{2.76000,0.550000,5}
4> slots:ordset(1000).
{24.2180,0.533000,45}
5> slots:ordset(10000).
{290.518,0.617900,470}


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.

BR,
Ulf W


-module(slots).

-compile(export_all).

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

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(L1,lists:reverse(L2)).

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