[erlang-questions] Memory-effective queue handling

[Erik Søe Sørensen]

Den 25/07/2012 15.21 skrev "Richard Carlsson" <carlsson.richard@REDACTED>:
>
> 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 I may be assuming too much by thinking that get_value is called by a
server loop which keeps holding on to the queue. Sorry I wasn't explicit
about that; if it wasn't so, then what I said didn't make much sense.
(It's vacation time and email-by-phone time, so my editing facilities are a
bit limited...)

> 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
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://erlang.org/pipermail/erlang-questions/attachments/20120726/51225789/attachment.htm>