From: "Niklas Hambüchen" <niklas@nh2.me>
To: linux-fsdevel@vger.kernel.org
Cc: "Paul Eggert" <eggert@cs.ucla.edu>,
"Jim Meyering" <jim@meyering.net>,
"Pádraig Brady" <P@draigbrady.com>
Subject: O(n^2) deletion performance
Date: Tue, 2 Jan 2018 01:21:32 +0100 [thread overview]
Message-ID: <5ca3808d-4eea-afec-75a6-2cc41f44b868@nh2.me> (raw)
Hello filesystem hackers,
Over in coreutils issue https://bugs.gnu.org/29921 we have found that
unlink()ing `n` many files seems to take in general O(n²) wall time.
So far me and others (in CC) have benchmarked `rm -r` and other methods
of unlink()ing multiple files and we've found approximately quadratic
performance across:
* ext4, XFS and zfs-on-linux on spinning disks
* ext4 on SSDs
* the other combinations were not tested yet
Please find the exact numbers https://bugs.gnu.org/29921.
So far we've observed apparently linear deletion time on:
* XFS on NVMe
It would be great to hear any kind of insights you may have regarding
this issue, implementation details that might be relevant here, or even
some quick benchmarks on your systems to confirm or refute our findings.
Unless instructed otherwise, I would also go ahead and file bugs for the
respective filesystem types, as quadratic deletion time makes for a bad
user experience and lots of sysadmin tears.
Happy new year,
Niklas
next reply other threads:[~2018-01-02 0:29 UTC|newest]
Thread overview: 11+ messages / expand[flat|nested] mbox.gz Atom feed top
2018-01-02 0:21 Niklas Hambüchen [this message]
2018-01-02 1:20 ` O(n^2) deletion performance Niklas Hambüchen
2018-01-02 1:59 ` Theodore Ts'o
2018-01-02 2:49 ` Andreas Dilger
2018-01-02 4:27 ` Jim Meyering
2018-01-02 6:22 ` Theodore Ts'o
2018-01-04 4:16 ` Jim Meyering
2018-01-04 7:16 ` Theodore Ts'o
2018-01-04 11:42 ` Dave Chinner
2018-01-02 4:33 ` Theodore Ts'o
2018-01-02 4:54 ` Dave Chinner
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=5ca3808d-4eea-afec-75a6-2cc41f44b868@nh2.me \
--to=niklas@nh2.me \
--cc=P@draigbrady.com \
--cc=eggert@cs.ucla.edu \
--cc=jim@meyering.net \
--cc=linux-fsdevel@vger.kernel.org \
/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 a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).