[erlang-questions] Performance with large queues

[黃耀賢 (Yau-Hsien Huang)]

Giving one cent quickly, I think that a large queue can be optimized
by implementing it using two stacks.

enque(Data, {InStack, OutStack}) when length(InStack) < 50000 ->
    {[Data|InStack], OutStack};
enque(Data, {InStack, OutStack}) ->
    enque(Data, {[], OutStack ++ lists:reverse(InStack)}).

deque({[], []}) ->
    [];
deque({InStack, [Data|OutStack]}) ->
    {Data, {InStack, OutStack}};
deque({InStack, []}) ->
    deque({[], lists:reverse(InStack)}).

Then, the cost of accessing a queue goes O(1) in general while
sometimes it goes O(N).


On Sat, Mar 20, 2010 at 9:05 AM, Bernard Duggan <bernie@REDACTED> wrote:

> So, my theory: I realised that, even though our code doesn't explicitly
> do a selective receive (and so can always just grab the first message on
> the queue) mnesia probably /does/ do one to get locks and that, in all
> likelihood, the cost of a selective receive goes O(N) with the length of
> the queue.  I imagine that once the queue has passed a certain point
> those selective receives increase the load on our process to the point
> that it can't keep up.  By the time the input load has died back down at
> night, the queue is so long (~1M messages) that it's taking a serious
> amount of time to traverse it, meaning that even over many hours the
> queue isn't significantly shrunk down (a queue of one million messages
> being processed at one message per second is still going to take 277
> hours to clear).
>
>