[dm-devel] [PATCH 9/9] dm crypt: sort writes

[Mike Snitzer]

On Tue, Apr 01 2014 at 11:19pm -0400,
Akira Hayakawa <hayakawa at valinux.co.jp> wrote:

> But, I myself found that what I really need in my case is not the
> RB tree but a simple list sorting (list_sort()).
> 
> Will do sorting anyway.
> 
> Enabling/disabling sorting in my case is really simple if I use list_sort()
> and will do. The default should be ON because I also don't see any reason
> to turn it off except benchmarking reason.

list_sort() uses merge sort, which has O(nlog(n)) complexity;
list_sort() also suffers from "list passed to list_sort() too long for
efficiency".  But in practice I'm not sure how long a list needs to be
to hit that case.

Whereas an rb-tree has O(log(n)) complexity and is efficient for
traversal, it also doesn't have the length limits.