[PATCH] lib/list_sort: introduce list_sort_nonatomic() and remove dummy cmp() calls

[Richard Weinberger]

----- Ursprüngliche Mail -----
> Von: "Kuan-Wei Chiu" <visitorckw at gmail.com>
> Historically, list_sort() implemented a hack in merge_final():
>    if (unlikely(!++count))
>        cmp(priv, b, b);
> 
> This was designed specifically so that callers could periodically
> invoke cond_resched() within their comparison functions when merging
> highly unbalanced lists.
> 
> However, an audit of the kernel tree reveals that only fs/ubifs/ relies
> on this mechanism. For the vast majority of list_sort() users (such as
> block layer IO schedulers and file systems), this results in completely
> wasted function calls. In the worst-case scenario (merging an already
> sorted list where 'a' is exhausted quickly), this results in
> approximately (N/2)/256 unnecessary cmp() calls.

Why isn't this a problem for other users of list_sort()?
Are the lists they sort guaranteed to be short?

Or did nobody test hard enough on slow machines without preempt? ;-)

Thanks,
//richard