Re: [PATCH 9/9] dm crypt: sort writes

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

 



On Tue, Apr 01 2014 at 11:19pm -0400,
Akira Hayakawa <hayakawa@xxxxxxxxxxxxx> 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.

--
dm-devel mailing list
dm-devel@xxxxxxxxxx
https://www.redhat.com/mailman/listinfo/dm-devel




[Index of Archives]     [DM Crypt]     [Fedora Desktop]     [ATA RAID]     [Fedora Marketing]     [Fedora Packaging]     [Fedora SELinux]     [Yosemite Discussion]     [KDE Users]     [Fedora Docs]

  Powered by Linux