[pacman-dev] _alpm_list_add_first
Hi! In many cases we use alpm_list as a "stack", or we just use it as a set. In these cases an O(1) _alpm_list_add_first function would be more efficient (which add the new member as a first element) than the O(n) _alpm_list_add. Mostly in time "critical" parts (see my favorite sortbydeps function for example;-). Bye, ngaba
On 4/26/07, Nagy Gabor <ngaba@petra.hos.u-szeged.hu> wrote:
Hi!
In many cases we use alpm_list as a "stack", or we just use it as a set. In these cases an O(1) _alpm_list_add_first function would be more efficient (which add the new member as a first element) than the O(n) _alpm_list_add. Mostly in time "critical" parts (see my favorite sortbydeps function for example;-).
I was just thinking about something similar. Given our usage pattern, the following *might* have an effect (pseudo code): alpm_list_add returns the node that was just added, and adds AFTER the passed in node. So: a->b->c->d alpm_list_add(a,x); a->x->b->c->d alpm_list_add(c,y); a->x->b->c->y->d Returning the node that was just added would allow us to do the "add to the list" loops while maintaining a 'last' pointer, and not incurring the overhead of the last pointer on every node.
On 5/16/07, Aaron Griffin <aaronmgriffin@gmail.com> wrote:
On 4/26/07, Nagy Gabor <ngaba@petra.hos.u-szeged.hu> wrote:
Hi!
In many cases we use alpm_list as a "stack", or we just use it as a set. In these cases an O(1) _alpm_list_add_first function would be more efficient (which add the new member as a first element) than the O(n) _alpm_list_add. Mostly in time "critical" parts (see my favorite sortbydeps function for example;-).
I was just thinking about something similar. Given our usage pattern, the following *might* have an effect (pseudo code):
alpm_list_add returns the node that was just added, and adds AFTER the passed in node. So: a->b->c->d alpm_list_add(a,x); a->x->b->c->d alpm_list_add(c,y); a->x->b->c->y->d
Returning the node that was just added would allow us to do the "add to the list" loops while maintaining a 'last' pointer, and not incurring the overhead of the last pointer on every node.
I have some local code of this kind of thing, and it does lead to some dramatic speedups, the most notable being on a "pacman -Qo <file>" operation, as alpm_list_ts of files are built, and we call alpm_list_last an obscene number of times. We should find a non-hackish way of doing it, however. -Dan
participants (3)
-
Aaron Griffin
-
Dan McGee
-
Nagy Gabor