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

[Allan McRae]

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.

Do you intend to just make filelist_operation return an array at a later 
stage?

Allan