Messages in this thread Patch in this message | | | Subject | [2.4 patch] fix O(N^2) dquot sync behaviour | From | "Stephen C. Tweedie" <> | Date | 23 Apr 2004 19:37:16 +0100 |
| |
Hi,
On Thu, 2004-04-22 at 16:18, Jan Kara wrote:
> when there are lots of dirty dquots the vfs_quota_sync() is too slow > (it has O(N^2) behaviour). Attached patch implements list of dirty > dquots for each superblock and quota type. Using this lists sync is > trivially linear. Attached patch is against 2.6.5 with journalled quota > and previous patch for hash table size. Please apply.
The O(N^2) behaviour is present on 2.4 too, but fortunately there's a simple way to bring that down to O(N) without the complexity of adding new lists and locking. This patch simply rotates the dquot list-head after each dquot write, so that the next scan walks the list starting after the entry just processed.
For 40,000 dirty dquots, this brings sync time from 7 minutes and 50 seconds down to 0.8 seconds. :-) On 2.4, we have BKL while doing this list manipulation. Jan Kara has acked this; please apply.
Cheers, Stephen
--- linux-2.4/fs/dquot.c.=K0000=.orig +++ linux-2.4/fs/dquot.c @@ -397,6 +397,10 @@ restart: wait_on_dquot(dquot); if (dquot_dirty(dquot)) sb->dq_op->write_dquot(dquot); + /* Move the inuse_list head pointer to just after the + * current dquot, so that we'll restart the list walk + * after this point on the next pass. */ + list_move(&inuse_list, &dquot->dq_inuse); dqput(dquot); goto restart; } | |