Help with storing data in memory

[Max Lapshin-2]

Erlyvideo has got a timeshift feature. It means, that last 10 minutes
of videostream are stored in stream_media gen_server.
When client want to seek back in live stream, it starts to read from
timeshift buffer just like from plain file.

43000 frames take about 1,5MB in ets table. They are stored as tuples
with float timestamp as a key.

Once in 5 seconds message clean_timeshift is received by stream_media
and it deletes all expired frames from this ets table.
When deletion doesn't work, erlyvideo takes about 10% CPU per several
clients. When I turn it on, it raises to 17%CPU.

I don't know what to do. When I works the same feature on ObjectiveC,
there was a ring buffer in memory, but Erlang isn't suitable for
such structures.

Currently I have an idea to keep two ets tables: when first entry from
first table comes to timeshift limit, I add second table and begin
to track from which table to take frames. When first entry from second
table comes to timeshift limit, I drop first table.
So I eliminate ets:select_delete call

________________________________________________________________
erlang-questions (at) erlang.org mailing list.
See http://www.erlang.org/faq.html
To unsubscribe; mailto:[hidden email]

[Bob Ippolito]

Why ets and not a gen_server with a queue (or queue-like) data
structure? Sending big enough binaries around should be cheap since
it's by reference.

On Tue, Mar 23, 2010 at 5:27 AM, Max Lapshin <[hidden email]> wrote:

> Erlyvideo has got a timeshift feature. It means, that last 10 minutes
> of videostream are stored in stream_media gen_server.
> When client want to seek back in live stream, it starts to read from
> timeshift buffer just like from plain file.
>
> 43000 frames take about 1,5MB in ets table. They are stored as tuples
> with float timestamp as a key.
>
> Once in 5 seconds message clean_timeshift is received by stream_media
> and it deletes all expired frames from this ets table.
> When deletion doesn't work, erlyvideo takes about 10% CPU per several
> clients. When I turn it on, it raises to 17%CPU.
>
> I don't know what to do. When I works the same feature on ObjectiveC,
> there was a ring buffer in memory, but Erlang isn't suitable for
> such structures.
>
> Currently I have an idea to keep two ets tables: when first entry from
> first table comes to timeshift limit, I add second table and begin
> to track from which table to take frames. When first entry from second
> table comes to timeshift limit, I drop first table.
> So I eliminate ets:select_delete call
>
> ________________________________________________________________
> erlang-questions (at) erlang.org mailing list.
> See http://www.erlang.org/faq.html
> To unsubscribe; mailto:[hidden email]
>
>

________________________________________________________________
erlang-questions (at) erlang.org mailing list.
See http://www.erlang.org/faq.html
To unsubscribe; mailto:[hidden email]

[Adam Kelly-2]

On 23 March 2010 09:27, Max Lapshin <[hidden email]> wrote:
> Currently I have an idea to keep two ets tables: when first entry from
> first table comes to timeshift limit, I add second table and begin
> to track from which table to take frames. When first entry from second
> table comes to timeshift limit, I drop first table.
> So I eliminate ets:select_delete call

I'm guessing that you are using one of the hash map table types, in
which case lookups by time range are going to be O(N)? You've already
hit one solution, build an index and use the index to delete entries
from the main table.   You should also be able to get the performance
you need by changing your table type to ordered_set, presuming ets is
smart about that comparison operator.

Adam.

________________________________________________________________
erlang-questions (at) erlang.org mailing list.
See http://www.erlang.org/faq.html
To unsubscribe; mailto:[hidden email]

[Max Lapshin-2]

ets is of type ordered_set, because each client can read by Key from
its own place in ets table and it needs to know ets:next for each Key.

So, queue doesn't fit, because I need random access to frame list.
Also, I'm afraid that array will not fit: when client seeks back in
timeshift table, I need to find closest frame, with conditions:
#video_frame{type = video, frame_type = keyframe, decoder_config =
false, dts = DTS} when DTS =< RequestedDTS

If use array, I will have to perform lookup through 40K of entries.
However, maybe it is not bad? I need to test.

________________________________________________________________
erlang-questions (at) erlang.org mailing list.
See http://www.erlang.org/faq.html
To unsubscribe; mailto:[hidden email]

[Bernard Duggan-2]

On 23/03/2010 8:27 PM, Max Lapshin wrote:
> I don't know what to do. When I works the same feature on ObjectiveC,
> there was a ring buffer in memory, but Erlang isn't suitable for
> such structures.
I implemented a ring buffer just the other day using the array module.
Seems to work fine, though I don't claim to have benchmarked the
performance, and I know access isn't exactly O(1) as it is in a "real"
array.  Still, it may be suitable for what you need.

Cheers,

Bernard

________________________________________________________________
erlang-questions (at) erlang.org mailing list.
See http://www.erlang.org/faq.html
To unsubscribe; mailto:[hidden email]

[Max Lapshin-2]

On Tue, Mar 23, 2010 at 2:04 PM, Bernard Duggan <[hidden email]> wrote:
> On 23/03/2010 8:27 PM, Max Lapshin wrote:
>> I don't know what to do. When I works the same feature on ObjectiveC,
>> there was a ring buffer in memory, but Erlang isn't suitable for
>> such structures.
> I implemented a ring buffer just the other day using the array module.
> Seems to work fine, though I don't claim to have benchmarked the
> performance, and I know access isn't exactly O(1) as it is in a "real"
> array.  Still, it may be suitable for what you need.
>

Ok, I will benchmark. I'm going also to test what overhead takes ets
to copy each binary.

________________________________________________________________
erlang-questions (at) erlang.org mailing list.
See http://www.erlang.org/faq.html
To unsubscribe; mailto:[hidden email]

[Bob Ippolito]

On Tue, Mar 23, 2010 at 6:54 AM, Max Lapshin <[hidden email]> wrote:

> ets is of type ordered_set, because each client can read by Key from
> its own place in ets table and it needs to know ets:next for each Key.
>
> So, queue doesn't fit, because I need random access to frame list.
> Also, I'm afraid that array will not fit: when client seeks back in
> timeshift table, I need to find closest frame, with conditions:
> #video_frame{type = video, frame_type = keyframe, decoder_config =
> false, dts = DTS} when DTS =< RequestedDTS
>
> If use array, I will have to perform lookup through 40K of entries.
> However, maybe it is not bad? I need to test.

Use a binary search! Since it's used as a ring you'll have to slightly
modify the standard algorithm but all of the data is sorted and you
have cheap random access so there is no good reason to do a sequential
scan.

-bob

________________________________________________________________
erlang-questions (at) erlang.org mailing list.
See http://www.erlang.org/faq.html
To unsubscribe; mailto:[hidden email]

[Max Lapshin-2]

What cost array:nth is?

________________________________________________________________
erlang-questions (at) erlang.org mailing list.
See http://www.erlang.org/faq.html
To unsubscribe; mailto:[hidden email]

[Dave Smith-10]

It is O log n, if my chemo brain serves me correctly. The best you can
hope for in a purely functional language implementation of arrays. I
strongly recommend Okaski's book on functional data structures.

http://www.amazon.com/Purely-Functional-Structures-Chris-Okasaki/dp/0521663504/ref=sr_1_1?ie=UTF8&s=books&qid=1269350406&sr=8-1

D.

On Tue, Mar 23, 2010 at 7:03 AM, Max Lapshin <[hidden email]> wrote:
> What cost array:nth is?
>
> ________________________________________________________________
> erlang-questions (at) erlang.org mailing list.
> See http://www.erlang.org/faq.html
> To unsubscribe; mailto:[hidden email]
>
>

________________________________________________________________
erlang-questions (at) erlang.org mailing list.
See http://www.erlang.org/faq.html
To unsubscribe; mailto:[hidden email]

[Evans, Matthew]

I agree with this. Implement it as a binary with offsets in the binary block as pointers marking the MPEG GOP boundaries.



You could then use gb_trees to find the closest offset when provided with a requested DTS. So given a DTS query to gb_trees it would return the byte offset in the binary structure (MPEG data) that is closest to the requested DTS. You would actually need to modify gb_trees so that it returns the closest match, but this should be trivial. For example:





lookup_closest(Key, {_, T}) ->

    lookup_closest1(Key, T, 0).



lookup_closest1(Key, {Key1, Value, Smaller, _}, _OldValue) when Key < Key1 ->

    lookup_closest1(Key, Smaller, Value);

lookup_closest1(Key, {Key1, _Value, _, Bigger}, OldValue) when Key > Key1 ->

    lookup_closest1(Key, Bigger, OldValue);

lookup_closest1(_, {_, Value, _, _},_OldValue) ->

    {value, Value};

lookup_closest1(_, nil, Value) ->

    {closest, Value}.





Then you could use split_binary to remove the head of the binary structure to simulate a circular buffer.







-----Original Message-----
From: [hidden email] [mailto:[hidden email]] On Behalf Of Bob Ippolito
Sent: Tuesday, March 23, 2010 8:15 AM
To: Max Lapshin
Cc: Adam Kelly; Erlang-Questions Questions
Subject: Re: [erlang-questions] Help with storing data in memory



On Tue, Mar 23, 2010 at 6:54 AM, Max Lapshin <[hidden email]> wrote:

> ets is of type ordered_set, because each client can read by Key from

> its own place in ets table and it needs to know ets:next for each Key.

>

> So, queue doesn't fit, because I need random access to frame list.

> Also, I'm afraid that array will not fit: when client seeks back in

> timeshift table, I need to find closest frame, with conditions:

> #video_frame{type = video, frame_type = keyframe, decoder_config =

> false, dts = DTS} when DTS =< RequestedDTS

>

> If use array, I will have to perform lookup through 40K of entries.

> However, maybe it is not bad? I need to test.



Use a binary search! Since it's used as a ring you'll have to slightly

modify the standard algorithm but all of the data is sorted and you

have cheap random access so there is no good reason to do a sequential

scan.



-bob



________________________________________________________________

erlang-questions (at) erlang.org mailing list.

See http://www.erlang.org/faq.html

To unsubscribe; mailto:[hidden email]

[Max Lapshin-2]

But that means that I will copy megabytes of data each 5 seconds...
Also, video frame is a complicated structure. I will need to serialize
it.

________________________________________________________________
erlang-questions (at) erlang.org mailing list.
See http://www.erlang.org/faq.html
To unsubscribe; mailto:[hidden email]

[Max Lapshin-2]

As I'm very disappointed of working with ets, tried to use fixed size
array. There are about 80 frames per second, so need to store
80*seconds entries.
In an hour server used all memory =))

Best thing will be dirty updatable tuple with 400K elements.

________________________________________________________________
erlang-questions (at) erlang.org mailing list.
See http://www.erlang.org/faq.html
To unsubscribe; mailto:[hidden email]

[Bob Ippolito]

You might need to tune the frequency of garbage collection or make
manual calls to erlang:garbage_collect(). You should also make sure
you are using the latest Erlang VM, the garbage collection strategy
for binaries has been significantly improved in recent versions.

On Thu, Mar 25, 2010 at 12:12 PM, Max Lapshin <[hidden email]> wrote:

> As I'm very disappointed of working with ets, tried to use fixed size
> array. There are about 80 frames per second, so need to store
> 80*seconds entries.
> In an hour server used all memory =))
>
> Best thing will be dirty updatable tuple with 400K elements.
>
> ________________________________________________________________
> erlang-questions (at) erlang.org mailing list.
> See http://www.erlang.org/faq.html
> To unsubscribe; mailto:[hidden email]
>
>

________________________________________________________________
erlang-questions (at) erlang.org mailing list.
See http://www.erlang.org/faq.html
To unsubscribe; mailto:[hidden email]

[Max Lapshin-2]

On Fri, Mar 26, 2010 at 1:10 AM, Bob Ippolito <[hidden email]> wrote:
> You might need to tune the frequency of garbage collection or make
> manual calls to erlang:garbage_collect(). You should also make sure
> you are using the latest Erlang VM, the garbage collection strategy
> for binaries has been significantly improved in recent versions.
>

R13B4. There is one question:

f({a, b, A}) ->
  g({e,f, A}).

Will the A element be copied twice or compiler is smart enought to
keep it untouched?
I.e. when I set element number 405450 in array, is the whole array
recreated or maybe just small part of it?

________________________________________________________________
erlang-questions (at) erlang.org mailing list.
See http://www.erlang.org/faq.html
To unsubscribe; mailto:[hidden email]

[Bob Ippolito]

On Thursday, March 25, 2010, Max Lapshin <[hidden email]> wrote:

> On Fri, Mar 26, 2010 at 1:10 AM, Bob Ippolito <[hidden email]> wrote:
>> You might need to tune the frequency of garbage collection or make
>> manual calls to erlang:garbage_collect(). You should also make sure
>> you are using the latest Erlang VM, the garbage collection strategy
>> for binaries has been significantly improved in recent versions.
>>
>
> R13B4. There is one question:
>
> f({a, b, A}) ->
>   g({e,f, A}).
>
> Will the A element be copied twice or compiler is smart enought to
> keep it untouched?
> I.e. when I set element number 405450 in array, is the whole array
> recreated or maybe just small part of it?
>

There is no copying of A, but there is a new tuple created {e, f, A} of course.

-bob

________________________________________________________________
erlang-questions (at) erlang.org mailing list.
See http://www.erlang.org/faq.html
To unsubscribe; mailto:[hidden email]

[Max Lapshin-2]

I thought, that hipe_bifs:array_update should help me, but it can
store only immediate values =(

________________________________________________________________
erlang-questions (at) erlang.org mailing list.
See http://www.erlang.org/faq.html
To unsubscribe; mailto:[hidden email]