From patchwork Thu Sep 6 21:03:53 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Ben Peart X-Patchwork-Id: 10591035 Return-Path: Received: from mail.wl.linuxfoundation.org (pdx-wl-mail.web.codeaurora.org [172.30.200.125]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id C42845A4 for ; Thu, 6 Sep 2018 21:04:00 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id B006B2AEAF for ; Thu, 6 Sep 2018 21:04:00 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id A2EFC2B229; Thu, 6 Sep 2018 21:04:00 +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=-8.0 required=2.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,MAILING_LIST_MULTI,RCVD_IN_DNSWL_HI 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 14CEA2AEAF for ; Thu, 6 Sep 2018 21:04:00 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1730153AbeIGBlM (ORCPT ); Thu, 6 Sep 2018 21:41:12 -0400 Received: from mail-eopbgr720129.outbound.protection.outlook.com ([40.107.72.129]:59840 "EHLO NAM05-CO1-obe.outbound.protection.outlook.com" rhost-flags-OK-OK-OK-FAIL) by vger.kernel.org with ESMTP id S1729281AbeIGBlM (ORCPT ); Thu, 6 Sep 2018 21:41:12 -0400 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=microsoft.com; s=selector1; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-SenderADCheck; bh=XJKScN529+c8IlmCp2dAYGhvU1VsZbkczKRVcM/bP1w=; b=QPnmO/lzXtD158f9ZSnO/XTYYik+ToVYnJaWUCnG0oX+faPGyaaHl5w0d05U8O6cuIKUTBSFGhGcDquJQShmtJacgDxcJRADZchmyEyc5wsv30wD2R0UL6YmaHJ4LaZ02jZ59+IFJHsH4jS5Gzc8B3E5mFOQ0DXOp9OmgAiuUPw= Received: from MW2PR2101MB0970.namprd21.prod.outlook.com (52.132.146.19) by MW2PR2101MB0908.namprd21.prod.outlook.com (52.132.152.28) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.1143.6; Thu, 6 Sep 2018 21:03:53 +0000 Received: from MW2PR2101MB0970.namprd21.prod.outlook.com ([fe80::d41c:2bea:5b2d:a858]) by MW2PR2101MB0970.namprd21.prod.outlook.com ([fe80::d41c:2bea:5b2d:a858%4]) with mapi id 15.20.1143.008; Thu, 6 Sep 2018 21:03:53 +0000 From: Ben Peart To: "git@vger.kernel.org" CC: "gitster@pobox.com" , "pclouds@gmail.com" , Ben Peart Subject: [PATCH v3 0/4] read-cache: speed up index load through parallelization Thread-Topic: [PATCH v3 0/4] read-cache: speed up index load through parallelization Thread-Index: AQHURiUeuqYsZcpx30WX9+14gyVQOA== Date: Thu, 6 Sep 2018 21:03:53 +0000 Message-ID: <20180906210227.54368-1-benpeart@microsoft.com> References: <20180823154053.20212-1-benpeart@microsoft.com> In-Reply-To: <20180823154053.20212-1-benpeart@microsoft.com> Accept-Language: en-US Content-Language: en-US X-MS-Has-Attach: X-MS-TNEF-Correlator: x-originating-ip: [70.33.148.227] x-mailer: git-send-email 2.18.0.windows.1 x-clientproxiedby: DM5PR1101CA0021.namprd11.prod.outlook.com (2603:10b6:4:4c::31) To MW2PR2101MB0970.namprd21.prod.outlook.com (2603:10b6:302:4::19) x-ms-exchange-messagesentrepresentingtype: 1 x-ms-publictraffictype: Email x-microsoft-exchange-diagnostics: 1;MW2PR2101MB0908;6:foDfm1/4Mc+6pjkfVi3Mw4FB1o4C/DZ5JcZhK0ZWiGKt0KirtISaf4RsY+2hTM13u4FR3Rh/p8V/ma9j6V2CKVot23C520ssfdPU+h+CYh+mP6C/79lRMSnpFkAoPJUmSiPujjScRORl8l4FCD1lq3PdLja5fMId8G12+mWklKv3kwz/8yUepXWkai6RlYy2BMHjPIeYAtiGdxQH/nxSyDRtH+0XVauvgLjta3w9wHF4zqxJEN1pR2DqifXdi2Hq4G6DHksN+Fu9nEE0kq/2PsHYPIJc4QYn3mJHuAEXgU2cPP67EZJPk3EAXNhxe1qsYM7O6aT5qgEXsX7A5j9cIhUTsxytE3ElZD6EZ5qFcONMdjns+qINDqzSvTn8nLcEWHbe+S2aGbauv7gXqCvM/a4pa8UM4/8FvrrdCI2uyi2dcwjCQ8wzsLllVJfzw5eC0HKc5dCAkTEcYZx70er+EQ==;5:MZl/JAaiVCBu3EO4tTslK4rKWFg74jMddRqBSpV2tfxPWYtMNuuCKcrRO/wXX/pc7AgeUkTKeRjtXBqA3CdWZPPyTjc06Gyde3zwXbs83rCw9uroYaLqqtslQltL8mEtlLm49FXhvEYJs48VEkUZABVUgdsmfjVnTNR+ak4IttQ=;7:F6G62kcg4Pvl/l1CzOzxn03RlekiKZCrAEwGeiHqa0dpHPgzrt3lJLDWLn0IaZPJGenFTJGTMWSNbx/d09TCLHbxHZwX0DZ2tevmLtrR616Ec+bdoVTCbkcsIu1SfzZPW8a189G257smjws+R/i+JVER1vlOzE3S71zywK0JYKZf9XLlQsj0z3GPcRcsdA5/w3/W5xHF7mCrPWdoOShbxg0Q6F2NqZbobcIwrHc0vRvjt4t1wRF6Nb96mWOuOoaB x-ms-office365-filtering-correlation-id: b7cbb417-8d9b-45cd-1ece-08d6143c4011 x-ms-office365-filtering-ht: Tenant x-microsoft-antispam: BCL:0;PCL:0;RULEID:(7020095)(4652040)(8989137)(4534165)(4627221)(201703031133081)(201702281549075)(8990107)(5600074)(711020)(4618075)(2017052603328)(7193020);SRVR:MW2PR2101MB0908; x-ms-traffictypediagnostic: MW2PR2101MB0908: x-microsoft-antispam-prvs: x-exchange-antispam-report-test: UriScan:(28532068793085)(166708455590820)(211936372134217); x-ms-exchange-senderadcheck: 1 x-exchange-antispam-report-cfa-test: BCL:0;PCL:0;RULEID:(8211001083)(6040522)(2401047)(8121501046)(5005006)(3002001)(10201501046)(3231344)(944501410)(52105095)(2018427008)(93006095)(93001095)(6055026)(149027)(150027)(6041310)(201703131423095)(201702281528075)(20161123555045)(201703061421075)(201703061406153)(20161123560045)(20161123558120)(20161123562045)(20161123564045)(201708071742011)(7699049)(76991033);SRVR:MW2PR2101MB0908;BCL:0;PCL:0;RULEID:;SRVR:MW2PR2101MB0908; x-forefront-prvs: 0787459938 x-forefront-antispam-report: SFV:NSPM;SFS:(10019020)(366004)(396003)(39860400002)(346002)(136003)(376002)(199004)(189003)(68736007)(316002)(25786009)(72206003)(50226002)(97736004)(10290500003)(478600001)(14454004)(966005)(256004)(5640700003)(6306002)(99286004)(53936002)(486006)(52116002)(6486002)(54906003)(1076002)(8676002)(14444005)(76176011)(22452003)(305945005)(7736002)(5660300001)(6916009)(6512007)(26005)(6346003)(106356001)(575784001)(105586002)(86612001)(2616005)(6436002)(2351001)(102836004)(3846002)(6116002)(446003)(11346002)(186003)(10090500001)(476003)(36756003)(2906002)(81156014)(1730700003)(81166006)(66066001)(2900100001)(8936002)(386003)(561924002)(2501003)(5250100002)(107886003)(4326008)(6506007)(39060400002);DIR:OUT;SFP:1102;SCL:1;SRVR:MW2PR2101MB0908;H:MW2PR2101MB0970.namprd21.prod.outlook.com;FPR:;SPF:None;LANG:en;PTR:InfoNoRecords;A:1;MX:1; received-spf: None (protection.outlook.com: microsoft.com does not designate permitted sender hosts) authentication-results: spf=none (sender IP is ) smtp.mailfrom=Ben.Peart@microsoft.com; x-microsoft-antispam-message-info: fbBZjMQUS9WJ3SZDCE6fIp6mMl/r+FnQq2QwlJnWo9VmZyJ5PTI5GljAS1+We5rqFVNbkkLGa0ISQfAcGq5dwIaAEV7sWnnBfXzZ/6H+NnRd3MPBBwxodtfBFDJ3jrI7eQoSqJe0GyhuZdWz7/lT550Pp9ydbkWhH+JIu8ISUPa3xOhY1bDoA8Dk1KDi9fb9XQM2aZqDEZND4ji8k42ORkzsBH7FTNlngevitGRykZl3bYbnd2JSC30BwfIfjzrs7F8puhyv6VUftdtLb/2CcA1ziIhglIWUkX7mZcclAccvDNWEm4mpXtcw9NbVPS2oIloJopDZRq0zmijff191hcZ/GPIyulvT+5J23A4/0ZI= spamdiagnosticoutput: 1:99 spamdiagnosticmetadata: NSPM Content-ID: <4B8E2F74EB58CC44BDE55EC93C3955E5@namprd21.prod.outlook.com> MIME-Version: 1.0 X-OriginatorOrg: microsoft.com X-MS-Exchange-CrossTenant-Network-Message-Id: b7cbb417-8d9b-45cd-1ece-08d6143c4011 X-MS-Exchange-CrossTenant-originalarrivaltime: 06 Sep 2018 21:03:53.6211 (UTC) X-MS-Exchange-CrossTenant-fromentityheader: Hosted X-MS-Exchange-CrossTenant-id: 72f988bf-86f1-41af-91ab-2d7cd011db47 X-MS-Exchange-Transport-CrossTenantHeadersStamped: MW2PR2101MB0908 Sender: git-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org X-Virus-Scanned: ClamAV using ClamSMTP On further investigation with the previous patch, I noticed that my test repos didn't contain the cache tree extension in their index. After doing a commit to ensure they existed, I realized that in some instances, the time to load the cache tree exceeded the time to load all the cache entries in parallel. Because the thread to read the cache tree was started last (due to having to parse through all the cache entries first) we weren't always getting optimal performance. To better optimize for this case, I decided to write the EOIE extension as suggested by Junio [1] in response to my earlier multithreading patch series [2]. This enables me to spin up the thread to load the extensions earlier as it no longer has to parse through all the cache entries first. The big changes in this iteration are: - add the EOIE extension - update the index extension worker thread to start first The absolute perf numbers don't look as good as the previous iteration because not loading the cache tree at all is a lot faster than loading it in parallel. These were measured with a V4 index that included a cache tree extension. I used p0002-read-cache.sh to generate some performance data on how the three performance patches help: p0002-read-cache.sh w/100,000 files Baseline expand_name_field() Thread extensions Thread entries --------------------------------------------------------------------------------------- 22.34(0.01+0.12) 21.14(0.03+0.01) -5.4% 20.71(0.03+0.03) -7.3% 13.93(0.04+0.04) -37.6% p0002-read-cache.sh w/1,000,000 files Baseline expand_name_field() Thread extensions Thread entries ------------------------------------------------------------------------------------------- 306.44(0.04+0.07) 295.42(0.01+0.07) -3.6% 217.60(0.03+0.04) -29.0% 199.00(0.00+0.10) -35.1% This patch conflicts with Duy's patch to remove the double memory copy and pass in the previous ce instead. The two will need to be merged/reconciled once they settle down a bit. [1] https://public-inbox.org/git/xmqq1sl017dw.fsf@gitster.mtv.corp.google.com/ [2] https://public-inbox.org/git/20171109141737.47976-1-benpeart@microsoft.com/ Base Ref: master Web-Diff: https://github.com/benpeart/git/commit/325ec69299 Checkout: git fetch https://github.com/benpeart/git read-index-multithread-v3 && git checkout 325ec69299 ### Patches Ben Peart (4): read-cache: optimize expand_name_field() to speed up V4 index parsing. eoie: add End of Index Entry (EOIE) extension read-cache: load cache extensions on a worker thread read-cache: speed up index load through parallelization Documentation/config.txt | 6 + Documentation/technical/index-format.txt | 23 ++ config.c | 18 + config.h | 1 + read-cache.c | 476 ++++++++++++++++++++--- t/README | 11 + t/t1700-split-index.sh | 1 + 7 files changed, 487 insertions(+), 49 deletions(-) base-commit: 29d9e3e2c47dd4b5053b0a98c891878d398463e3