[erlang-questions] Performance on FIFO

[Raimo Niskanen]

On Tue, May 25, 2010 at 02:12:44PM +1200, Richard O'Keefe wrote:
> 
> 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.

And if you do not want to hack the queue module, you can
sacrifice some performance and do it with a wrapper:

lookup(Key, Q) ->
    case queue:peek(queue:filter(
		fun ({K,_}) when K =:= Key -> true;
		    (_) -> false end,
		Q)) of
	empty -> none;
	{value,KV} -> KV
    end.

The question for you to answer is how much that hurts for a
queue lenght 1000 as you mentioned, and how often that happens.

> 
> 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
> 
> ________________________________________________________________
> erlang-questions (at) erlang.org mailing list.
> See http://www.erlang.org/faq.html
> To unsubscribe; mailto:erlang-questions-unsubscribe@REDACTED

-- 

/ Raimo Niskanen, Erlang/OTP, Ericsson AB