[pacman-dev] alpm_list: missing quick access to last element

[Jürgen Hötzel]

On Sun, Mar 04, 2007 at 08:40:38PM -0500, Dan McGee wrote:
> On 3/4/07, Jürgen Hötzel <juergen at 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
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 189 bytes
Desc: not available
URL: <http://archlinux.org/pipermail/pacman-dev/attachments/20070305/5f6d4bb1/attachment.pgp>