On Tue, Jul 19, 2011 at 6:57 AM, Allan McRae <allan@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