From mboxrd@z Thu Jan  1 00:00:00 1970
Return-Path: <linux-fsdevel-owner@vger.kernel.org>
Received: from imap.thunk.org ([74.207.234.97]:49800 "EHLO imap.thunk.org"
        rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP
        id S1751398AbeADHRF (ORCPT <rfc822;linux-fsdevel@vger.kernel.org>);
        Thu, 4 Jan 2018 02:17:05 -0500
Date: Thu, 4 Jan 2018 02:16:55 -0500
From: Theodore Ts'o <tytso@mit.edu>
To: Jim Meyering <jim@meyering.net>
Cc: Andreas Dilger <adilger@dilger.ca>,
        Niklas =?iso-8859-1?Q?Hamb=FCchen?= <niklas@nh2.me>,
        Linux FS-devel Mailing List <linux-fsdevel@vger.kernel.org>,
        Paul Eggert <eggert@cs.ucla.edu>,
        =?iso-8859-1?Q?P=E1draig?= Brady <P@draigbrady.com>
Subject: Re: O(n^2) deletion performance
Message-ID: <20180104071655.GG23371@thunk.org>
References: <5ca3808d-4eea-afec-75a6-2cc41f44b868@nh2.me>
 <20180102015932.GF2532@thunk.org>
 <3FF0FC46-28A8-406C-A528-6F900735BEA1@dilger.ca>
 <CA+8g5KHLx6t_naqXbXskKX-k-tG9J-Hg+cLR8EBO1cqsSLbt3g@mail.gmail.com>
 <20180102062245.GJ2532@thunk.org>
 <CA+8g5KFGDG6=R3vY4jvWuSZjap4sCxrSnK1sfTsPnjjJzbYEQw@mail.gmail.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
In-Reply-To: <CA+8g5KFGDG6=R3vY4jvWuSZjap4sCxrSnK1sfTsPnjjJzbYEQw@mail.gmail.com>
Sender: linux-fsdevel-owner@vger.kernel.org
List-ID: <linux-fsdevel.vger.kernel.org>

On Wed, Jan 03, 2018 at 08:16:58PM -0800, Jim Meyering wrote:
> 
> Still wondering how this happened... deliberate optimization for
> something else, probably.
> And wishing I'd written a relative (not absolute) test for it in 2008,
> so I would have noticed sooner.
> In 2008 when I wrote this coreutils extN performance test:
> 
>   https://git.savannah.gnu.org/cgit/coreutils.git/tree/tests/rm/ext3-perf.sh
> 
> there was no O(N^2) or even "just" O(N^1.5) component when using the
> then-just-improved rm. Many of us plotted the curves.

How high (how many files) did you plot the curves back in 2008?  Do
you remember?

> Any idea when ext4's unlink became more expensive?

Ext4's unlink hasn't really changed.  What *has* changed over time is
the block and inode allocation algorithms.  2008 is before we
optimized allocation algorithms to read/write operations to large
files more efficient, and to try to avoid free space fragmention as
the file system aged.

Given that on large / fast NVMe device everything looks linear, it's
pretty clear that what you're seeing is essentially seek time on
spinning rust, and probably SSD GC overhead on flash devices.

> I've just run a test on the spinning-disk file system mentioned above,
> and it took 75 minutes to delete 12.8M entries. That's rather nasty.

Yes, but how long did it take to *create* the 12.8M entries?  My guess
is that it was roughly comparable?

							- Ted