From patchwork Wed Dec 4 22:17:39 2013 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Filipe Manana X-Patchwork-Id: 3285471 Return-Path: X-Original-To: patchwork-linux-btrfs@patchwork.kernel.org Delivered-To: patchwork-parsemail@patchwork2.web.kernel.org Received: from mail.kernel.org (mail.kernel.org [198.145.19.201]) by patchwork2.web.kernel.org (Postfix) with ESMTP id 0274FC0D4A for ; Wed, 4 Dec 2013 22:18:01 +0000 (UTC) Received: from mail.kernel.org (localhost [127.0.0.1]) by mail.kernel.org (Postfix) with ESMTP id 1F8EE20504 for ; Wed, 4 Dec 2013 22:18:00 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by mail.kernel.org (Postfix) with ESMTP id 3A41220501 for ; Wed, 4 Dec 2013 22:17:59 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1756076Ab3LDWRz (ORCPT ); Wed, 4 Dec 2013 17:17:55 -0500 Received: from mail-wi0-f171.google.com ([209.85.212.171]:55217 "EHLO mail-wi0-f171.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1753613Ab3LDWRy (ORCPT ); Wed, 4 Dec 2013 17:17:54 -0500 Received: by mail-wi0-f171.google.com with SMTP id ca18so9006021wib.4 for ; Wed, 04 Dec 2013 14:17:53 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=from:to:cc:subject:date:message-id; bh=ucQtNky9ZN9SqnZ2UyKIabfsJ1awPc0uHkw/aNoX2jM=; b=DjJB/CufgwFJyN66/ea6zDt4VjwNMLoa1g6XbEskPISOqXyQp7/t33DShCDpDdcs55 toVdkXCIO81LDLKiDqzjl6h+T/yzBqO3RC/WLb6pDgGZBYvHIahi+oWxf7rbULmCgfxh /HvDbWJ0cyMi2MB7GfUELsn5oAOfXwcNjMo3OdVIMdAD08O48Sm31Ul7SiB+D2pZxvlG ymvlatECubI1xi+LyHfHD+9x4YHOKaqeFtOxP5byiQY3dIfvMKLdXoiksGpmHzx1Uq+Z ZXxUjIcRkrmQkn/i0rBbobw/iWQ8acxBEEt8c9AjhYjtqjjkujIJFj1xx5gWPIJYviYm dqXg== X-Received: by 10.180.79.38 with SMTP id g6mr9112661wix.60.1386195473446; Wed, 04 Dec 2013 14:17:53 -0800 (PST) Received: from storm-desktop.lan (bl5-4-1.dsl.telepac.pt. [82.154.4.1]) by mx.google.com with ESMTPSA id s20sm204900wib.1.2013.12.04.14.17.52 for (version=TLSv1.1 cipher=ECDHE-RSA-RC4-SHA bits=128/128); Wed, 04 Dec 2013 14:17:52 -0800 (PST) From: Filipe David Borba Manana To: linux-btrfs@vger.kernel.org Cc: Filipe David Borba Manana Subject: [PATCH] Btrfs: more efficient push_leaf_right Date: Wed, 4 Dec 2013 22:17:39 +0000 Message-Id: <1386195459-15523-1-git-send-email-fdmanana@gmail.com> X-Mailer: git-send-email 1.7.9.5 Sender: linux-btrfs-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: linux-btrfs@vger.kernel.org X-Spam-Status: No, score=-6.8 required=5.0 tests=BAYES_00, DKIM_ADSP_CUSTOM_MED, DKIM_SIGNED, FREEMAIL_FROM, RCVD_IN_DNSWL_HI, RP_MATCHES_RCVD, T_DKIM_INVALID, UNPARSEABLE_RELAY autolearn=ham version=3.3.1 X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on mail.kernel.org X-Virus-Scanned: ClamAV using ClamSMTP Currently when finding the leaf to insert a key into a btree, if the leaf doesn't have enough space to store the item we attempt to move off some items from our leaf to its right neighbor leaf, and if this fails to create enough free space in our leaf, we try to move off more items to the left neighbor leaf as well. When trying to move off items to the right neighbor leaf, if it has enough room to store the new key but not not enough room to move off at least one item from our target leaf, __push_leaf_right returns 1 and we have to attempt to move items to the left neighbor (push_leaf_left function) without touching the right neighbor leaf. For the case where the right leaf has enough room to store at least 1 item from our leaf, we end up modifying (and dirtying) both our leaf and the right leaf. This is non-optimal for the case where the new key is greater than any key in our target leaf because it can be inserted at slot 0 of the right neighbor leaf and we don't need to touch our leaf at all nor to attempt to move off items to the left neighbor leaf. Therefore this change just selects the right neighbor leaf as our new target leaf if it has enough room for the new key without modifying our initial target leaf - we do this only if the new key is higher than any key in the initial target leaf. While running the following test, push_leaf_right was called by split_leaf 4802 times. Out of those 4802 calls, for 2571 calls (53.5%) we hit this special case (right leaf has enough room and new key is higher than any key in the initial target leaf). Test: sysbench --test=fileio --file-num=512 --file-total-size=5G \ --file-test-mode=[seqwr|rndwr] --num-threads=512 --file-block-size=8192 \ --max-requests=100000 --file-io-mode=sync [prepare|run] Results: sequential writes Throughput before this change: 65.71Mb/sec (average of 10 runs) Throughput after this change: 66.58Mb/sec (average of 10 runs) random writes Throughput before this change: 10.75Mb/sec (average of 10 runs) Throughput after this change: 11.56Mb/sec (average of 10 runs) Signed-off-by: Filipe David Borba Manana Reviewed-by: Liu Bo --- fs/btrfs/ctree.c | 13 +++++++++++++ 1 file changed, 13 insertions(+) diff --git a/fs/btrfs/ctree.c b/fs/btrfs/ctree.c index 11f9a18..a57507a 100644 --- a/fs/btrfs/ctree.c +++ b/fs/btrfs/ctree.c @@ -3613,6 +3613,19 @@ static int push_leaf_right(struct btrfs_trans_handle *trans, struct btrfs_root if (left_nritems == 0) goto out_unlock; + if (path->slots[0] == left_nritems && !empty) { + /* Key greater than all keys in the leaf, right neighbor has + * enough room for it and we're not emptying our leaf to delete + * it, therefore use right neighbor to insert the new item and + * no need to touch/dirty our left leaft. */ + btrfs_tree_unlock(left); + free_extent_buffer(left); + path->nodes[0] = right; + path->slots[0] = 0; + path->slots[1]++; + return 0; + } + return __push_leaf_right(trans, root, path, min_data_size, empty, right, free_space, left_nritems, min_slot); out_unlock: