On Sun, Mar 04, 2007 at 08:40:38PM -0500, Dan McGee wrote:
On 3/4/07, Jürgen Hötzel <juergen@hoetzel.info> wrote:
Hi,
I'm back to pacman-dev, and just just found this out profiling pacman-cvs (pacman -Ss test):
... ----------------------------------------------- 0.12 0.00 13785/13785 alpm_list_add [7] [8] 42.9 0.12 0.00 13785 alpm_list_last [8] ----------------------------------------------- ...
alpm_list_last is eating up 42.9% CPU-time on my slow epia system. This is due the missing "last element hint" which speeded up the add operation before aaron introduced the public alpm_list type two months ago. I consider adding the "last element" member again. Any objections?
Yeah, something like this definitely needs to be done. HOWEVER, let's hold off until post-3.0.0 release. We are in bugfix-only mode for the time being, and this is more than a bugfix. If you want to patch it locally, then we can probably get it into 3.0.1, but I really want to stick with this bugfix-only mentality otherwise we will just keep finding things we want to fix and never stay quite stable enough to release.
By the way, we are thinking of changing some of the data structures used, and we have at least glanced at these things: kernel-style linked lists <http://isis.poly.edu/kulesh/stuff/src/klist/> hash-table package cache, and something along this line-
I have looked into kernel-style linked lists. I like the implementation but it has the same shortcomings like the current implementation (it doesn't allow easy access to the last element, required by frequent append operations in pacmans code). Also Judds previous implementation (using the last element in every member) is a little bit error-prone, because it doesn't distinguish between the list and list elements (think of empty lists). I prefer an implementation using sentinel nodes (storing pointer to first and last element). Jürgen