From: Mike Snitzer <snitzer@redhat.com>
To: Akira Hayakawa <hayakawa@valinux.co.jp>
Cc: "masami.hiramatsu.pt@hitachi.com"
<masami.hiramatsu.pt@hitachi.com>,
dm-devel@redhat.com
Subject: Re: [PATCH 9/9] dm crypt: sort writes
Date: Tue, 1 Apr 2014 23:38:14 -0400 [thread overview]
Message-ID: <20140402033813.GA16982@redhat.com> (raw)
In-Reply-To: <20140402121936.a0a61e405771c83935b9e352@valinux.co.jp>
On Tue, Apr 01 2014 at 11:19pm -0400,
Akira Hayakawa <hayakawa@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.
next prev parent reply other threads:[~2014-04-02 3:38 UTC|newest]
Thread overview: 27+ messages / expand[flat|nested] mbox.gz Atom feed top
2014-03-28 20:11 [PATCH 0/9] dm crypt: improve cpu scalability Mike Snitzer
2014-03-28 20:11 ` [PATCH 1/9] dm crypt: fix cpu hotplug crash by removing per-cpu structure Mike Snitzer
2014-03-28 20:11 ` [PATCH 2/9] block: use kmalloc alignment for bio slab Mike Snitzer
2014-03-28 20:11 ` [PATCH 3/9] dm crypt: use per-bio data Mike Snitzer
2014-03-28 20:11 ` [PATCH 4/9] dm crypt: use unbound workqueue for request processing Mike Snitzer
2014-03-28 20:11 ` [PATCH 5/9] dm crypt: don't allocate pages for a partial request Mike Snitzer
2014-03-28 20:11 ` [PATCH 6/9] dm crypt: avoid deadlock in mempools Mike Snitzer
2014-03-28 20:11 ` [PATCH 7/9] dm crypt: remove io_pool Mike Snitzer
2014-03-28 20:11 ` [PATCH 8/9] dm crypt: offload writes to thread Mike Snitzer
2014-04-01 16:27 ` Ondrej Kozina
2014-04-01 16:32 ` Mike Snitzer
2014-04-01 18:15 ` Mikulas Patocka
2014-04-01 18:23 ` Mike Snitzer
2014-04-02 6:55 ` Ondrej Kozina
2014-04-01 18:01 ` Mikulas Patocka
2014-04-01 19:08 ` Milan Broz
2014-03-28 20:11 ` [PATCH 9/9] dm crypt: sort writes Mike Snitzer
2014-03-29 8:11 ` Milan Broz
2014-03-31 12:39 ` Mike Snitzer
2014-03-31 23:37 ` Akira Hayakawa
2014-04-01 1:01 ` Mike Snitzer
2014-04-01 17:35 ` Milan Broz
2014-04-01 20:15 ` Alasdair G Kergon
2014-04-01 23:21 ` Akira Hayakawa
2014-04-02 3:19 ` Akira Hayakawa
2014-04-02 3:38 ` Mike Snitzer [this message]
2014-04-02 4:18 ` Akira Hayakawa
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20140402033813.GA16982@redhat.com \
--to=snitzer@redhat.com \
--cc=dm-devel@redhat.com \
--cc=hayakawa@valinux.co.jp \
--cc=masami.hiramatsu.pt@hitachi.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.