From: Daniel Phillips <phillips@bonn-fries.net>
To: Alexander Viro <viro@math.psu.edu>, Andrew Morton <andrewm@uow.edu.au>
Cc: lkml <linux-kernel@vger.kernel.org>
Subject: Re: [patch] truncate_inode_pages
Date: Sun, 10 Jun 2001 00:53:36 +0200 [thread overview]
Message-ID: <01061000533601.03897@starship> (raw)
In-Reply-To: <Pine.GSO.4.21.0106091331120.19361-100000@weyl.math.psu.edu>
In-Reply-To: <Pine.GSO.4.21.0106091331120.19361-100000@weyl.math.psu.edu>
On Saturday 09 June 2001 19:40, Alexander Viro wrote:
> > takes 45 seconds CPU time due to the O(clean * dirty) algorithm in
> > truncate_inode_pages(). The machine is locked up for the duration.
> > The patch reduces this to 20 milliseconds via an O(clean + dirty)
> > algorithm.
>
> Unfortunately, it's _not_ O(clean + dirty).
>
> > + while (truncate_list_pages(&mapping->clean_pages, start,
> > &partial)) { + spin_lock(&pagecache_lock);
> > + complete = 0;
> > + }
>
> Cool. Now think what happens if pages with large indices are in the
> very end of list. Half of them. You skip clean/2 pages on each of
> clean/2 passes. Hardly a linear behaviour - all you need is a
> different program to trigger it.
>
> Now, having a separate pass that would reorder the pages on list,
> moving the to-kill ones in the beginning might help.
This is easy, just set the list head to the page about to be truncated.
--
Daniel
next prev parent reply other threads:[~2001-06-09 22:51 UTC|newest]
Thread overview: 10+ messages / expand[flat|nested] mbox.gz Atom feed top
2001-06-09 15:51 [patch] truncate_inode_pages Andrew Morton
2001-06-09 17:40 ` Alexander Viro
2001-06-09 22:53 ` Daniel Phillips [this message]
2001-06-10 1:31 ` Andrew Morton
2001-06-10 16:40 ` Daniel Phillips
2001-06-11 12:45 ` Andrew Morton
2001-06-11 13:13 ` Daniel Phillips
2001-06-11 13:28 ` Andrew Morton
2001-06-11 2:22 Dieter Nützel
[not found] ` <200106112252.AAA19615@mail.bonn-fries.net>
[not found] ` <01061214324600.00879@starship>
2001-06-12 16:32 ` Dieter Nützel
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=01061000533601.03897@starship \
--to=phillips@bonn-fries.net \
--cc=andrewm@uow.edu.au \
--cc=linux-kernel@vger.kernel.org \
--cc=viro@math.psu.edu \
/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).