[systemd-devel] [PATCH] Dynamically allocate bootchart logs

[Kok, Auke-jan H]

On Fri, May 3, 2013 at 9:14 AM, Lennart Poettering
<lennart at poettering.net> wrote:
> On Thu, 25.04.13 22:47, Kok, Auke-jan H (auke-jan.h.kok at intel.com) wrote:
>
>> On Wed, Apr 24, 2013 at 5:20 PM, Zbigniew Jędrzejewski-Szmek
>> <zbyszek at in.waw.pl> wrote:
>> > On Wed, Apr 24, 2013 at 04:26:12PM -0700, Nathaniel Chen wrote:
>> >> Instead of storing bootchart sample data in arrays, this patch moves
>> >> storage to linked lists so that there is no more limit on samples.
>> >
>> > How does this approach compare to greedy_realloc?
>>
>> One of the problems with the static arrays is that it was inherently
>> allocating way too much memory to begin with. Most tasks live much
>> less time than (samples * interval), the rest of the array space is
>> just wasted.
>>
>> The linked list approach drives down this memory requirement and makes
>> navigating all the data much more straightforward. I also much prefer
>> head pointers instead of having index numbers around.
>
> Still sounds like greedy_realloc() is what you want here. Storing sample
> data in a dynamically increasing array sounds much more natural than a
> linked list.

I admit I hadn't heard of greedy_realloc() unti Zbigniew mentioned it,
and I still fail to see why it would be so much better other than "you
can access members by index". You're still doing an allocation each
time you extend the array (unless you're doing tricks and
preallocate).

The arrays are also sparse: most likely ps[0]...ps[N] will never be
used since at the start (0) only very few processes exist - can
greedy_realloc() handle large unallocated parts at the start of the
array? That doesn't seem likely. Unless we re-index them where 0 means
"first sample found", but that means all sorts of extra math
determining where each sample lines up in time...

The lists are cross-linked, so even if one way we're making them an
array again, we'd be walking them as a linked list in the other way
for efficiency...

Auke