From patchwork Fri Oct 5 03:44:55 2012 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Theodore Ts'o X-Patchwork-Id: 189420 Return-Path: X-Original-To: patchwork-incoming@ozlabs.org Delivered-To: patchwork-incoming@ozlabs.org Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by ozlabs.org (Postfix) with ESMTP id C60BE2C00FB for ; Fri, 5 Oct 2012 17:29:33 +1000 (EST) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1752619Ab2JEH3S (ORCPT ); Fri, 5 Oct 2012 03:29:18 -0400 Received: from li9-11.members.linode.com ([67.18.176.11]:53927 "EHLO imap.thunk.org" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1752369Ab2JEH3P (ORCPT ); Fri, 5 Oct 2012 03:29:15 -0400 Received: from root (helo=closure.thunk.org) by imap.thunk.org with local-esmtp (Exim 4.72) (envelope-from ) id 1TJyqH-0002wZ-9D; Fri, 05 Oct 2012 03:44:49 +0000 Received: by closure.thunk.org (Postfix, from userid 15806) id 1B950244A0C; Thu, 4 Oct 2012 23:44:55 -0400 (EDT) From: Theodore Ts'o To: Ext4 Developers List Cc: Theodore Ts'o Subject: [PATCH 2/2] libext2fs: optimize rb_test_bit Date: Thu, 4 Oct 2012 23:44:55 -0400 Message-Id: <1349408695-11661-2-git-send-email-tytso@mit.edu> X-Mailer: git-send-email 1.7.12.rc0.22.gcdd159b In-Reply-To: <1349408695-11661-1-git-send-email-tytso@mit.edu> References: <1349408695-11661-1-git-send-email-tytso@mit.edu> X-SA-Exim-Connect-IP: X-SA-Exim-Mail-From: tytso@thunk.org X-SA-Exim-Scanned: No (on imap.thunk.org); SAEximRunCond expanded to false Sender: linux-ext4-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: linux-ext4@vger.kernel.org Optimize testing for a bit in an rbtree-based bitmap for the case where the calling application is scanning through the bitmap sequentially. Previously, we did this for a set of bits which were inside an allocated extent, but we did not optimize the case where there was a large number of bits after an allocated extents which were not in use. 1111111111111110000000000000000000 ^ optimized ^not optimized In my tests of a roughly half-filled file system, the run time of e2freefrag was halved, and the cpu time spent in userspace was during e2fsck's pass 5 was reduced by a factor of 30%. Signed-off-by: "Theodore Ts'o" --- lib/ext2fs/blkmap64_rb.c | 16 ++++++++++++++-- 1 file changed, 14 insertions(+), 2 deletions(-) diff --git a/lib/ext2fs/blkmap64_rb.c b/lib/ext2fs/blkmap64_rb.c index a83f8ac..c9006f8 100644 --- a/lib/ext2fs/blkmap64_rb.c +++ b/lib/ext2fs/blkmap64_rb.c @@ -314,8 +314,8 @@ static errcode_t rb_resize_bmap(ext2fs_generic_bitmap bmap, inline static int rb_test_bit(struct ext2fs_rb_private *bp, __u64 bit) { - struct bmap_rb_extent *rcursor; - struct rb_node *parent = NULL; + struct bmap_rb_extent *rcursor, *next_ext; + struct rb_node *parent = NULL, *next; struct rb_node **n = &bp->root.rb_node; struct bmap_rb_extent *ext; @@ -330,6 +330,18 @@ rb_test_bit(struct ext2fs_rb_private *bp, __u64 bit) return 1; } + next = ext2fs_rb_next(&rcursor->node); + if (next) { + next_ext = ext2fs_rb_entry(next, struct bmap_rb_extent, node); + if ((bit >= rcursor->start + rcursor->count) && + (bit < next_ext->start)) { +#ifdef BMAP_STATS_OPS + bp->test_hit++; +#endif + return 0; + } + } + rcursor = *bp->wcursor; if (!rcursor) goto search_tree;