Performance of dict and ets

[Sean Hinde]

Hi,

I've been doing some performance comparison between the new R7B dict module
and ets which I thought I'd share.

My benchmark program creates the table/dict, stores 20,000 elements in it
with keys 1..20000, then runs through all keys again and reads then deletes
each entry.

If I store lists of varying lengths I get the following results (microsecs
per op on a 167MHz SPARC)
	
list length	ets_rd_del	ets_write	ets_tot	dict_rd_del
dict_write	Dict_tot
1	13	12	25	54	62	117
100	43	30	73	55	62	117
200	71	42	113	54	64	119
300	102	60	162	55	62	117
400	140	73	213	55	63	118

As expected dict is the same speed across the board, but ets shows linear
growth with the size of the term being stored.

Storing any less than 20,000 rows doesn't seem to make much difference.

In the write case the breakeven is at about 300 elements in the list, in the
read/delete case at about 130 elements. Overall breakeven is at 230 approx

If I store a binary it becomes a bit more interesting...

The dict module performs identically to it's lists case.

The ets module gives the startling result that almost irrespective of the
size of the binary each op takes only around 14 microsecs. This seems to
imply that storing a binary in an ets table involves no copying...

My first guess is that the copying involved in storing something in an ets
table is an instantaneous term_to_binary type operation rather than anything
inherent in transferring data to ets???

Can anyone explain this ets copying business fully?

Thanks,

- Sean

BTW while playing with this I added a couple of functions to dict which
retrieve and delete the entry in one operation. This is about 20% faster
than doing them separately (which may be worth it for someone :~) )

------Cut--------

-export([find_erase/2, fetch_erase/2]).

%% find_erase(Key, Dictionary) -> {ok, Value, Dictionary} | error

find_erase(Key, D0) ->
    Slot = get_slot(D0, Key),
    case on_bucket(fun (B0) -> find_erase_key(Key, B0) end,
		   D0, Slot) of
	{D1,error} ->
	    error;
	{D1, Val} ->
	    D2 = maybe_contract(D1, 1), % I think this is always true
	    {ok, Val, D2}
    end.
    
find_erase_key(Key, [?kv(Key,Val)|Bkt]) -> {Bkt,Val};
find_erase_key(Key, [E|Bkt0]) ->
    {Bkt1,Val} = find_erase_key(Key, Bkt0),
    {[E|Bkt1],Val};
find_erase_key(Key, []) -> {[],error}.

%% fetch_erase(Key, Dictionary) -> {Value, Dictionary}

fetch_erase(Key, D0) ->
    Slot = get_slot(D0, Key),
    {D1, Val} = on_bucket(fun (B0) -> fetch_erase_key(Key, B0) end,
			  D0, Slot),
    D2 = maybe_contract(D1, 1),
    {Val, D2}.
    
fetch_erase_key(Key, [?kv(Key,Val)|Bkt]) -> {Bkt,Val};
fetch_erase_key(Key, [E|Bkt0]) ->
    {Bkt1,Val} = fetch_erase_key(Key, Bkt0),
    {[E|Bkt1],Val}.



NOTICE AND DISCLAIMER:
This email (including attachments) is confidential.  If you have received
this email in error please notify the sender immediately and delete this
email from your system without copying or disseminating it or placing any
reliance upon its contents.  We cannot accept liability for any breaches of
confidence arising through use of email.  Any opinions expressed in this
email (including attachments) are those of the author and do not necessarily
reflect our opinions.  We will not accept responsibility for any commitments
made by our employees outside the scope of our business.  We do not warrant
the accuracy or completeness of such information.