[erlang-questions] Performance on FIFO

[Richard O'Keefe]

On May 24, 2010, at 7:56 PM, maruthavanan s wrote:

>
> Hi Again,
>
> Thanks for your valuable suggestions. I am sorry for incomplete mail.
>
> I want my system to be fast performing, robust and
> should be able to have good memory management. This data is run time  
> and the queue size can increase up to 1000
>
> My frequent operations would be insert and delete rather than lookup.

So you have a collection of {Key,Value} pairs,
where from the collection's point of view it doesn't
matter what the Values are, and all it knows is that
Keys can be compared for equality.  (This is a starting
point, not a hard limitation.)

The classic thing for fast (in the amortised sense)
insert and delete is a pair of lists, where
	a b c d e f g		A
might be represented by
	[a,b,c] [g,f,e,d]	L R
where A = L ++ reverse(R).  This way we can easily
pull things off the front, and as easily put them on
the back.

This is exactly what the queue: module gives you.

What it doesn't give you is lookup.  With no "indexing"
superstructure, it's going to be an O(N) linear scan,
but if N is small (you mentioned 20) and lookups are
rare, this is not a problem.

%% lookup(Key, Queue)
%% returns the leftmost {Key,Value} pair in Queue
%% or 'none' if there is no such 2-tuple.

lookup(Key, {Back,Front}) ->
     case lookup_front(Key, Front)
       of none -> lookup_back(Key, Back, none)
        ; Found -> Found
     end.

lookup_front(Key, [Found={Key,_}|_]) ->
     Found;
lookup_front(Key, [_|Front]) ->
     lookup_front(Key, Front);
lookup_front(_, []) ->
     none.

lookup_back(Key, [Found={Key,_}|Back], _) ->
     lookup_back(Key, Back, Found);
lookup_back(Key, [_|Back], State) ->
     lookup_back(Key, Back, State);
lookup_back(_, [], State) ->
     State.

This has received some not very thorough testing.
Make a copy of queue.erl and add this to it.
Don't forget to -export lookup/2.

Write the rest of your program.
Run some test cases to find how how often the
various operations really _are_ called, not how
often you _think_ they are called.
Then decide whether to replace your q module.


I suggest