[erlang-questions] Memory-effective queue handling

[Richard Carlsson]

On 07/25/2012 03:01 PM, Erik Søe Sørensen wrote:
>  > increase_counter(#ch{queue=Q, counter_value=CV}=CH, Value) ->
>  >     Date = ?MODULE:get_date(),
>  >     NewQueue=queue:in({Date, Value}, Q),
>  >     CH#ch{queue=NewQueue, counter_value=CV+Value}.
>  >
>  > get_value(#ch{hist_len=HL}=CH) ->
>  >     % get the values from the queue until we reach a first element in
> the queue
>  >     % which is not older then the hist_len (e.g. not older than 15 mins)
>  >     Date = ?MODULE:get_date(),
>  >     get_younger_than(CH, Date-HL).
>  >
>  > get_younger_than(#ch{queue=Q, counter_value=CV}=CH, TargetDate) ->
>  >     case queue:out(Q) of
>  >         {empty, _} ->
>  >             0 = CV, % this is an assert, the value shall be 0
>  >             {CH, 0};
>  >         {{value, {Date, Value}}, NewQ} when Date < TargetDate ->
>  >             get_younger_than(CH#ch{queue=NewQ,
> counter_value=CV-Value}, TargetDate);
>  >         {{value, _}, _} ->
>  >             % the currently removed entry is too young, so leave that
> in the
>  >             % queue (i.e. use the parameter queue).
>  >             {CH, CV}
>  >     end.
>  >
>  > The copying is done in the queue:out call, because it returns not just
>  > the first value, but the rest of the queu (newQ) too.
> That doesn't copy the entire queue. That is, occasionally it recreates
> the *spine* of a new list the length of the entire queue, but normally
> it does way less than that.
> The problem is that the way your code works, that worst-case is every
> time, and the throwing-away of old entries is also done from the start
> each time: your get_value() does not return the pruned queue.
> A further consequence of that is that Richard's statement doesn't hold:
> because you keep a reference (apparently) to the original, unpruned
> queue, the memory will have to hold both list spines simultaneously.
> So I'd suggest you change the return value of get_value.

I might be a bit tired, but where does he still hold a reference to the 
original queue (unless somewhere outside the shown code)? And if so, is 
the problem really that he can't hold 2 copies of the queue at the same 
time? - In that case he's pushing the limits anyway. As far as I can 
see, get_value() tail calls to get_younger_than(), so no references are 
kept there, and get_younger_than() keeps tailcalling itself with the 
updated queue in its #ch-record, dropping the previous queue. The final 
#ch-record gets returned to the caller. Only the result of the last call 
to queue:out() does any wasted rewriting.

     /Richard