lkml.org 
[lkml]   [2011]   [Jul]   [27]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
SubjectRe: list sort
From
Date
Hi,

On Wed, 2011-07-27 at 16:45 +0200, Clemens Ladisch wrote:
> Steven Whitehouse wrote:
> > There seems to be an issue with list_sort trying to compare an object to
> > itself. [...]
> > While it appears generally harmless, since the list does appear to be
> > correctly sorted, it is doing extra work needlessly.
>
> There are sort algorithms where this happens naturally, and adding
> an additional check to avoid calling the comparison function when the
> pointers are equal would be more work overall than just calling cmp().
>
> This does not happen with list_sort()'s merge sort, but I've noticed
> the following hack in merge_and_restore_back_links():
>
> do {
> /*
> * In worst cases this loop may run many iterations.
> * Continue callbacks to the client even though no
> * element comparison is needed, so the client's cmp()
> * routine can invoke cond_resched() periodically.
> */
> (*cmp)(priv, tail->next, tail->next);
>
> tail->next->prev = tail;
> tail = tail->next;
> } while (tail->next);
>
> When there is no cond_resched() call, this is indeed needless work.
>
> However, if the list is so short that cond_resched() is not needed,
> the additional comparisons should not hurt anyway.
>
>
> Regards,
> Clemens

Ah, I see now... that makes some kind of sense I think. I didn't expect
the cmp routine to be dual purpose in that way,

Steve.




\
 
 \ /
  Last update: 2011-07-27 17:05    [W:0.032 / U:0.088 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site