[pacman-dev] [PATCH] Convert package filelists to an array instead of linked list

[Dan McGee]

On Tue, Jul 19, 2011 at 6:57 AM, Allan McRae <allan at archlinux.org> wrote:
> On 19/07/11 20:01, Dan McGee wrote:
>>
>> This accomplishes quite a few things with one rather invasive change.
>>
>> 1. Iteration is much more performant, due to a reduction in pointer
>>    chasing and linear item access.
>> 2. Data structures are smaller- we no longer have the overhead of the
>>    linked list as the file struts are now laid out consecutively in
>>    memory.
>> 3. Memory allocation has been massively reworked. Before, we would
>>    allocate three different pieces of memory per file item- the list
>>    struct, the file struct, and the copied filename. What this resulted
>>    in was massive fragmentation of memory when loading filelists since
>>    the memory allocator had to leave holes all over the place. The new
>>    situation here now removes the need for any list item allocation;
>>    allocates the file structs in contiguous memory (and reallocs as
>>    necessary), leaving only the strings as individually allocated. Tests
>>    using valgrind (massif) show some pretty significant memory
>>    reductions on the worst case `pacman -Ql>  /dev/null` (366387 files
>>    on my machine):
>>
>>    Before:
>>      Peak heap:   54,416,024 B
>>         Useful heap: 36,840,692 B
>>         Extra heap:  17,575,332 B
>>
>>    After:
>>      Peak heap:   38,004,352 B
>>         Useful heap: 28,101,347 B
>>         Extra heap:   9,903,005 B
>>
>> Several small helper methods have been introduced, including a list to
>> array conversion helper as well as a filelist merge sort that works
>> directly on arrays.
>>
>
>
> Minor comments:
>
> Maybe want to look at consistency between the two places where file lists
> are read (local_db_read, _alpm_pkg_load_internal).  e.g. starting with size
> 4 vs 8, freeing excess memory at the end.
It actually starts with 8 in both cases, it just does it in different
ways. Look closer at it, but I agree it isn't all that clear, more
cleaver than necessary.

> Do you intend to just make filelist_operation return an array at a later
> stage?
I contemplated doing that, as it is the only user of the list_to_array
method right now. The tricky part there is the unknown size in advance
bit- we could have a list ranging anywhere in size from 0 to
max(len(lista), len(listb)).

-Dan