From patchwork Thu Dec 28 15:28:04 2017 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Timofey Titovets X-Patchwork-Id: 10134957 Return-Path: Received: from mail.wl.linuxfoundation.org (pdx-wl-mail.web.codeaurora.org [172.30.200.125]) by pdx-korg-patchwork.web.codeaurora.org (Postfix) with ESMTP id 3A3C060212 for ; Thu, 28 Dec 2017 15:28:17 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 2C6C728ADD for ; Thu, 28 Dec 2017 15:28:17 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id 20B3C2D404; Thu, 28 Dec 2017 15:28:17 +0000 (UTC) X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on pdx-wl-mail.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-6.8 required=2.0 tests=BAYES_00, DKIM_ADSP_CUSTOM_MED, DKIM_SIGNED, FREEMAIL_FROM, RCVD_IN_DNSWL_HI, T_DKIM_INVALID autolearn=ham version=3.3.1 Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id BDAE028ADD for ; Thu, 28 Dec 2017 15:28:16 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1753755AbdL1P2O (ORCPT ); Thu, 28 Dec 2017 10:28:14 -0500 Received: from mail-wr0-f193.google.com ([209.85.128.193]:45919 "EHLO mail-wr0-f193.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1753464AbdL1P2N (ORCPT ); Thu, 28 Dec 2017 10:28:13 -0500 Received: by mail-wr0-f193.google.com with SMTP id o15so7274206wrf.12 for ; Thu, 28 Dec 2017 07:28:12 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=from:to:cc:subject:date:message-id; bh=D0ZItQ/yn6Zm0RpkiWxnu1aPjnfY48PPRfJweUk89Dc=; b=RCPlie1e1ajlDOYpen+5LKBjV7YyHJQzGZMcn2L0LWrAROWST7MuzcvZTshof0vG3L TU+dlS4Xfu9vHlY/xMymW1Hwf3xKGTFxIRzd0v/5N0x9Ngr/z2ZFY/epaXcC8M18f0WE G69XImjufq3RJNVajzTyb34mDbctaq60mG5NUdwHt0NoflrHLmnbH2y4BDbE685Gk7OG vmJ4cy/truWuraj80QgCSyl+Qws600tnaYmDBXXEZH2g4ED7/rn29kx+Cz16NdF9ht8U WDmR7fgxVn1gYPSGls/uDfF/Ng7GFi4iF3w70h/O+GRkzPTWN6i8xpEnl+OzEIB5x59T Qamg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:cc:subject:date:message-id; bh=D0ZItQ/yn6Zm0RpkiWxnu1aPjnfY48PPRfJweUk89Dc=; b=PbVdAvWffvXOlYSyxsJ4fttJKERptU92rFfvdtj+dXWW90hYAoLo7+Z451NOvuhLO1 UwhWc86vkWLKQh7g4gRnQTc79unM+1RSjLQcBKG5IFONNGABIDx9cclmdZNkAu2cyEQM t/BBXMIJEWGerPGS+hHO58oLNq5lL4nKV8ebtCpD/uGaCr/P1eADZBQA8c0CnnXD1VN+ cSJFWkLqqYyI96rmczYHDDhwmW4Cp0b/0o/nMx568fFBgekCpXD+CyfI4IBeSkd0ASHV NIqq5hgqsS6cWFLJz2Kt4eSqsXsztb42O/1ziUcWJOjQIumZqKRO1H2cMMF40uHwzgrK hHyA== X-Gm-Message-State: AKGB3mLwy+z9LUV2h/Q19bsCfZ/5P17PbMT9uubXOEKbMNSV3yPiWbrQ m0PLhcw/WL3I+si60KBf2tndnQ== X-Google-Smtp-Source: ACJfBovNvZLDGGpq4U158FtGU6VRjL0SVL+j8ImnLMqrv2++RQRpfFSDTHBLkSxBiNinYzQip/F8NA== X-Received: by 10.223.139.73 with SMTP id v9mr32364554wra.77.1514474891815; Thu, 28 Dec 2017 07:28:11 -0800 (PST) Received: from titovetst-beplan.itransition.corp (nat6-minsk-pool-46-53-208-190.telecom.by. [46.53.208.190]) by smtp.gmail.com with ESMTPSA id m18sm21782235wmc.18.2017.12.28.07.28.10 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Thu, 28 Dec 2017 07:28:11 -0800 (PST) From: Timofey Titovets To: linux-btrfs@vger.kernel.org Cc: Timofey Titovets Subject: [PATCH] Btrfs: replace raid56 stripe bubble sort with insert sort Date: Thu, 28 Dec 2017 18:28:04 +0300 Message-Id: <20171228152804.4645-1-nefelim4ag@gmail.com> X-Mailer: git-send-email 2.15.1 Sender: linux-btrfs-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: linux-btrfs@vger.kernel.org X-Virus-Scanned: ClamAV using ClamSMTP Insert sort are generaly perform better then bubble sort, by have less iterations on avarage. That version also try place element to right position instead of raw swap. I'm not sure how many stripes per bio raid56, btrfs try to store (and try to sort). So, that a bit shorter just in the name of a great justice. Signed-off-by: Timofey Titovets --- fs/btrfs/volumes.c | 29 ++++++++++++----------------- 1 file changed, 12 insertions(+), 17 deletions(-) diff --git a/fs/btrfs/volumes.c b/fs/btrfs/volumes.c index 98bc2433a920..7195fc8c49b1 100644 --- a/fs/btrfs/volumes.c +++ b/fs/btrfs/volumes.c @@ -5317,29 +5317,24 @@ static inline int parity_smaller(u64 a, u64 b) return a > b; } -/* Bubble-sort the stripe set to put the parity/syndrome stripes last */ +/* Insertion-sort the stripe set to put the parity/syndrome stripes last */ static void sort_parity_stripes(struct btrfs_bio *bbio, int num_stripes) { struct btrfs_bio_stripe s; - int i; + int i, j; u64 l; - int again = 1; - while (again) { - again = 0; - for (i = 0; i < num_stripes - 1; i++) { - if (parity_smaller(bbio->raid_map[i], - bbio->raid_map[i+1])) { - s = bbio->stripes[i]; - l = bbio->raid_map[i]; - bbio->stripes[i] = bbio->stripes[i+1]; - bbio->raid_map[i] = bbio->raid_map[i+1]; - bbio->stripes[i+1] = s; - bbio->raid_map[i+1] = l; - - again = 1; - } + for (i = 1; i < num_stripes; i++) { + s = bbio->stripes[i]; + l = bbio->raid_map[i]; + for (j = i - 1; j >= 0; j--) { + if (!parity_smaller(bbio->raid_map[j], l)) + break; + bbio->stripes[j+1] = bbio->stripes[j]; + bbio->raid_map[j+1] = bbio->raid_map[j]; } + bbio->stripes[j+1] = s; + bbio->raid_map[j+1] = l; } }