From patchwork Wed Sep 12 16:18:57 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Ben Peart X-Patchwork-Id: 10598027 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 DE1131575 for ; Wed, 12 Sep 2018 16:19:42 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id CD1EB2A709 for ; Wed, 12 Sep 2018 16:19:42 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id C100F2A70C; Wed, 12 Sep 2018 16:19:42 +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 EA0D92A709 for ; Wed, 12 Sep 2018 16:19:41 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1727755AbeILVYz (ORCPT ); Wed, 12 Sep 2018 17:24:55 -0400 Received: from mail-dm3nam03on0134.outbound.protection.outlook.com ([104.47.41.134]:65110 "EHLO NAM03-DM3-obe.outbound.protection.outlook.com" rhost-flags-OK-OK-OK-FAIL) by vger.kernel.org with ESMTP id S1726792AbeILVYz (ORCPT ); Wed, 12 Sep 2018 17:24:55 -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=WCRt3OOIH+NigQ5Y5Ui1TjFLaHk2HcGXe8n6kTsGlJE=; b=PmbJ3OGq/B5i/xBEjKGfiR5RsniBaTC8O7TFIwpZ9/nKid4zp38zv9a77VDlvJrJBf6nU+ajMGV3Yik+hxNzJNFEXgaWIQtgHjuKxnQ5AiPZYgyS7YEqtQp00LP5yUvm0AeXEjghyzlRKcYVUYyu5V8RT25hoWpcCehYk93lgGE= Received: from MW2PR2101MB0970.namprd21.prod.outlook.com (52.132.146.19) by MW2PR2101MB1100.namprd21.prod.outlook.com (52.132.149.29) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.1143.7; Wed, 12 Sep 2018 16:18:58 +0000 Received: from MW2PR2101MB0970.namprd21.prod.outlook.com ([fe80::3c7b:f2aa:d871:8ae7]) by MW2PR2101MB0970.namprd21.prod.outlook.com ([fe80::3c7b:f2aa:d871:8ae7%2]) with mapi id 15.20.1164.006; Wed, 12 Sep 2018 16:18:57 +0000 From: Ben Peart To: "git@vger.kernel.org" CC: "gitster@pobox.com" , "pclouds@gmail.com" , Ben Peart Subject: [PATCH v5 4/5] read-cache.c: optimize reading index format v4 Thread-Topic: [PATCH v5 4/5] read-cache.c: optimize reading index format v4 Thread-Index: AQHUSrROIGALnenPT0WhAVvTUQA9zw== Date: Wed, 12 Sep 2018 16:18:57 +0000 Message-ID: <20180912161832.55324-5-benpeart@microsoft.com> References: <20180823154053.20212-1-benpeart@microsoft.com> <20180912161832.55324-1-benpeart@microsoft.com> In-Reply-To: <20180912161832.55324-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: DM5PR1401CA0011.namprd14.prod.outlook.com (2603:10b6:4:4a::21) 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;MW2PR2101MB1100;6:/yvEIXC1nndmO0lUWVTbIjVO4I6wJSVGULRZDRKXJSzz+wvitU0Xz8A2iS/qrqhvrF/oEaLz7vO+PsvHLy9wB0IKKxCNXOtEhgrVX6NRVqoGG/RbUZaXUa7lk7P9eY9kgdChbhoI8WnOcDS/hiyHgruTFDzV5kRz+KeTsdjo7eCOhpH7tu7wohqFMOR7H/+BQ+8Q6T6ToV9x/hyhSjGbPCeVutLwEjh3qognbj+uInEhWlLCtSIHQknlwT94/+IJr610px+SrnV+UKYPeH5xrwq4HqwYVOij0RT8K6wkwHTcb9THgd0Q0lE/Qqpw3RQt4n5k00Ffz25uNTI0ddZgWBWo0dQDJriULjWxEGe6JXgrdJKkDKDQBuDyE3+maaRNjbnwYYhlvbMWCvLWJqClNE2bTjYROftx4gLIhznPKWCId1TnmUwxQhW1X5kpc/ZoRRd+/WvuSziVMS/e2wAmgQ==;5:KLn5ue6PlvGIrODGIBQeBN/NXWpGd8QCZ0ME5nLNXyVkcUzixG+t9+JBUNYeB/cMFPdwdqrsseSE29YmfTkahrpOb5wmT65M7bRS/zbvhNjyl5CsvwQkiusKiFD5O4h74zIRDS2vj618mZ0wn0JJ1HJSU0XNwOhrZp+1cah1VD0=;7:LFY1pkWK75edxKMtwCBFKNUyyXcQZsDhwYpc2Lp9FPDemKJ2wyS1ptEilKy9/jVEtcw5raSzeAG15fpVvscJBSLiaWSHE7bqkVtpYoWMFc44lRmJfHbTYEZxQM8Lx2SFBcyI65NLoWzeJh6lKyKH6R/xsepU4QJleXDGS3BXTCbxj5EXbHUMVAOZIeZ3E+zNx7P551uBiN+mTAGAB5Tulk+J1o5HTx+8byQYjhCHFm6gE7dhRdd6NBFexuQWivHY x-ms-office365-filtering-correlation-id: ac67a0ed-b957-45c7-2a7f-08d618cb7102 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:MW2PR2101MB1100; x-ms-traffictypediagnostic: MW2PR2101MB1100: authentication-results: spf=none (sender IP is ) smtp.mailfrom=Ben.Peart@microsoft.com; x-microsoft-antispam-prvs: x-exchange-antispam-report-test: UriScan:(28532068793085)(89211679590171)(85827821059158); x-ms-exchange-senderadcheck: 1 x-exchange-antispam-report-cfa-test: BCL:0;PCL:0;RULEID:(8211001083)(6040522)(2401047)(8121501046)(5005006)(93006095)(93001095)(10201501046)(3002001)(3231344)(944501410)(52105095)(2018427008)(6055026)(149027)(150027)(6041310)(201703131423095)(201702281528075)(20161123555045)(201703061421075)(201703061406153)(20161123558120)(20161123560045)(20161123562045)(20161123564045)(201708071742011)(7699050)(76991041);SRVR:MW2PR2101MB1100;BCL:0;PCL:0;RULEID:;SRVR:MW2PR2101MB1100; x-forefront-prvs: 07935ACF08 x-forefront-antispam-report: SFV:NSPM;SFS:(10019020)(366004)(136003)(376002)(396003)(346002)(39860400002)(189003)(199004)(14444005)(14454004)(5250100002)(4326008)(107886003)(1730700003)(6916009)(102836004)(53936002)(8936002)(446003)(10090500001)(76176011)(99286004)(186003)(256004)(8676002)(1076002)(2501003)(2616005)(97736004)(39060400002)(36756003)(7736002)(305945005)(52116002)(5660300001)(26005)(81166006)(81156014)(50226002)(476003)(316002)(25786009)(6506007)(478600001)(3846002)(54906003)(86612001)(6116002)(6486002)(6436002)(386003)(11346002)(2906002)(72206003)(10290500003)(66066001)(5640700003)(106356001)(486006)(22452003)(105586002)(6512007)(2351001)(68736007)(2900100001);DIR:OUT;SFP:1102;SCL:1;SRVR:MW2PR2101MB1100;H:MW2PR2101MB0970.namprd21.prod.outlook.com;FPR:;SPF:None;LANG:en;PTR:InfoNoRecords;MX:1;A:1; received-spf: None (protection.outlook.com: microsoft.com does not designate permitted sender hosts) x-microsoft-antispam-message-info: h47l4tLKmxlCnHeRr8W/ofWAvreK216SU+u/hf9Ebr2QobGMvyAcxNjb/L+8v164YzoYOaFWO8tTGNxpkYHpuiPHU4dhaGHrGy5OPvcn3jK7Zk1JrCc0TmLmIZhZQBh0aL38jlNhke6X2lMTCsHJYdlNm49Fhroq2SWhP+aJUiZSIcZr1Iyl0CTGFDQ7d5UZCZ2NOCYKkHWG4VAXCWjO/QWUln4oPcoDavf8VwHscM05QaFpkJwUSq7XZPuGowf6aEFopwOkjWOWopKxQrHk5N1ixuqx2SNUabxL8Bjm0jB4DdKZHWkvBTVZYnWffgBBj4RxKuWISKQQoEkLcW9by1Leo2ViF1EKPdJVLJrabmU= spamdiagnosticoutput: 1:99 spamdiagnosticmetadata: NSPM Content-ID: MIME-Version: 1.0 X-OriginatorOrg: microsoft.com X-MS-Exchange-CrossTenant-Network-Message-Id: ac67a0ed-b957-45c7-2a7f-08d618cb7102 X-MS-Exchange-CrossTenant-originalarrivaltime: 12 Sep 2018 16:18:57.7430 (UTC) X-MS-Exchange-CrossTenant-fromentityheader: Hosted X-MS-Exchange-CrossTenant-id: 72f988bf-86f1-41af-91ab-2d7cd011db47 X-MS-Exchange-Transport-CrossTenantHeadersStamped: MW2PR2101MB1100 Sender: git-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org X-Virus-Scanned: ClamAV using ClamSMTP From: Nguyễn Thái Ngọc Duy Index format v4 requires some more computation to assemble a path based on a previous one. The current code is not very efficient because - it doubles memory copy, we assemble the final path in a temporary first before putting it back to a cache_entry - strbuf_remove() in expand_name_field() is not exactly a good fit for stripping a part at the end, _setlen() would do the same job and is much cheaper. - the open-coded loop to find the end of the string in expand_name_field() can't beat an optimized strlen() This patch avoids the temporary buffer and writes directly to the new cache_entry, which addresses the first two points. The last point could also be avoided if the total string length fits in the first 12 bits of ce_flags, if not we fall back to strlen(). Running "test-tool read-cache 100" on webkit.git (275k files), reading v2 only takes 4.226 seconds, while v4 takes 5.711 seconds, 35% more time. The patch reduces read time on v4 to 4.319 seconds. Signed-off-by: Nguyễn Thái Ngọc Duy Signed-off-by: Ben Peart --- read-cache.c | 132 ++++++++++++++++++++++++++------------------------- 1 file changed, 67 insertions(+), 65 deletions(-) diff --git a/read-cache.c b/read-cache.c index 880f627b4c..40dc4723b2 100644 --- a/read-cache.c +++ b/read-cache.c @@ -1721,33 +1721,6 @@ int read_index(struct index_state *istate) return read_index_from(istate, get_index_file(), get_git_dir()); } -static struct cache_entry *cache_entry_from_ondisk(struct mem_pool *mem_pool, - struct ondisk_cache_entry *ondisk, - unsigned int flags, - const char *name, - size_t len) -{ - struct cache_entry *ce = mem_pool__ce_alloc(mem_pool, len); - - ce->ce_stat_data.sd_ctime.sec = get_be32(&ondisk->ctime.sec); - ce->ce_stat_data.sd_mtime.sec = get_be32(&ondisk->mtime.sec); - ce->ce_stat_data.sd_ctime.nsec = get_be32(&ondisk->ctime.nsec); - ce->ce_stat_data.sd_mtime.nsec = get_be32(&ondisk->mtime.nsec); - ce->ce_stat_data.sd_dev = get_be32(&ondisk->dev); - ce->ce_stat_data.sd_ino = get_be32(&ondisk->ino); - ce->ce_mode = get_be32(&ondisk->mode); - ce->ce_stat_data.sd_uid = get_be32(&ondisk->uid); - ce->ce_stat_data.sd_gid = get_be32(&ondisk->gid); - ce->ce_stat_data.sd_size = get_be32(&ondisk->size); - ce->ce_flags = flags & ~CE_NAMEMASK; - ce->ce_namelen = len; - ce->index = 0; - hashcpy(ce->oid.hash, ondisk->sha1); - memcpy(ce->name, name, len); - ce->name[len] = '\0'; - return ce; -} - /* * Adjacent cache entries tend to share the leading paths, so it makes * sense to only store the differences in later entries. In the v4 @@ -1762,22 +1735,24 @@ static unsigned long expand_name_field(struct strbuf *name, const char *cp_) if (name->len < len) die("malformed name field in the index"); - strbuf_remove(name, name->len - len, len); - for (ep = cp; *ep; ep++) - ; /* find the end */ + strbuf_setlen(name, name->len - len); + ep = cp + strlen((const char *)cp); strbuf_add(name, cp, ep - cp); return (const char *)ep + 1 - cp_; } -static struct cache_entry *create_from_disk(struct mem_pool *mem_pool, +static struct cache_entry *create_from_disk(struct mem_pool *ce_mem_pool, + unsigned int version, struct ondisk_cache_entry *ondisk, unsigned long *ent_size, - struct strbuf *previous_name) + const struct cache_entry *previous_ce) { struct cache_entry *ce; size_t len; const char *name; unsigned int flags; + size_t copy_len = 0; + int expand_name_field = version == 4; /* On-disk flags are just 16 bits */ flags = get_be16(&ondisk->flags); @@ -1797,21 +1772,50 @@ static struct cache_entry *create_from_disk(struct mem_pool *mem_pool, else name = ondisk->name; - if (!previous_name) { - /* v3 and earlier */ - if (len == CE_NAMEMASK) - len = strlen(name); - ce = cache_entry_from_ondisk(mem_pool, ondisk, flags, name, len); + if (expand_name_field) { + const unsigned char *cp = (const unsigned char *)name; + size_t strip_len, previous_len; - *ent_size = ondisk_ce_size(ce); - } else { - unsigned long consumed; - consumed = expand_name_field(previous_name, name); - ce = cache_entry_from_ondisk(mem_pool, ondisk, flags, - previous_name->buf, - previous_name->len); + previous_len = previous_ce ? previous_ce->ce_namelen : 0; + strip_len = decode_varint(&cp); + if (previous_len < strip_len) { + if (previous_ce) + die(_("malformed name field in the index, near path '%s'"), + previous_ce->name); + else + die(_("malformed name field in the index in the first path")); + } + copy_len = previous_len - strip_len; + name = (const char *)cp; + } + + if (len == CE_NAMEMASK) + len = strlen(name) + copy_len; + + ce = mem_pool__ce_alloc(ce_mem_pool, len); + + ce->ce_stat_data.sd_ctime.sec = get_be32(&ondisk->ctime.sec); + ce->ce_stat_data.sd_mtime.sec = get_be32(&ondisk->mtime.sec); + ce->ce_stat_data.sd_ctime.nsec = get_be32(&ondisk->ctime.nsec); + ce->ce_stat_data.sd_mtime.nsec = get_be32(&ondisk->mtime.nsec); + ce->ce_stat_data.sd_dev = get_be32(&ondisk->dev); + ce->ce_stat_data.sd_ino = get_be32(&ondisk->ino); + ce->ce_mode = get_be32(&ondisk->mode); + ce->ce_stat_data.sd_uid = get_be32(&ondisk->uid); + ce->ce_stat_data.sd_gid = get_be32(&ondisk->gid); + ce->ce_stat_data.sd_size = get_be32(&ondisk->size); + ce->ce_flags = flags & ~CE_NAMEMASK; + ce->ce_namelen = len; + ce->index = 0; + hashcpy(ce->oid.hash, ondisk->sha1); - *ent_size = (name - ((char *)ondisk)) + consumed; + if (expand_name_field) { + memcpy(ce->name, previous_ce->name, copy_len); + memcpy(ce->name + copy_len, name, len + 1 - copy_len); + *ent_size = (name - ((char *)ondisk)) + len + 1 - copy_len; + } else { + memcpy(ce->name, name, len + 1); + *ent_size = ondisk_ce_size(ce); } return ce; } @@ -1948,7 +1952,7 @@ static void *load_index_extensions(void *_data) */ static unsigned long load_cache_entry_block(struct index_state *istate, struct mem_pool *ce_mem_pool, int offset, int nr, void *mmap, - unsigned long start_offset, struct strbuf *previous_name) + unsigned long start_offset, const struct cache_entry *previous_ce) { int i; unsigned long src_offset = start_offset; @@ -1959,10 +1963,11 @@ static unsigned long load_cache_entry_block(struct index_state *istate, unsigned long consumed; disk_ce = (struct ondisk_cache_entry *)((char *)mmap + src_offset); - ce = create_from_disk(ce_mem_pool, disk_ce, &consumed, previous_name); + ce = create_from_disk(ce_mem_pool, istate->version, disk_ce, &consumed, previous_ce); set_index_entry(istate, i, ce); src_offset += consumed; + previous_ce = ce; } return src_offset - start_offset; } @@ -1970,22 +1975,18 @@ static unsigned long load_cache_entry_block(struct index_state *istate, static unsigned long load_all_cache_entries(struct index_state *istate, void *mmap, size_t mmap_size, unsigned long src_offset) { - struct strbuf previous_name_buf = STRBUF_INIT, *previous_name; unsigned long consumed; if (istate->version == 4) { - previous_name = &previous_name_buf; mem_pool_init(&istate->ce_mem_pool, estimate_cache_size_from_compressed(istate->cache_nr)); } else { - previous_name = NULL; mem_pool_init(&istate->ce_mem_pool, estimate_cache_size(mmap_size, istate->cache_nr)); } consumed = load_cache_entry_block(istate, istate->ce_mem_pool, - 0, istate->cache_nr, mmap, src_offset, previous_name); - strbuf_release(&previous_name_buf); + 0, istate->cache_nr, mmap, src_offset, NULL); return consumed; } @@ -2007,8 +2008,7 @@ struct load_cache_entries_thread_data int offset, nr; void *mmap; unsigned long start_offset; - struct strbuf previous_name_buf; - struct strbuf *previous_name; + struct cache_entry *previous_ce; unsigned long consumed; /* return # of bytes in index file processed */ }; @@ -2021,7 +2021,7 @@ static void *load_cache_entries_thread(void *_data) struct load_cache_entries_thread_data *p = _data; p->consumed += load_cache_entry_block(p->istate, p->ce_mem_pool, - p->offset, p->nr, p->mmap, p->start_offset, p->previous_name); + p->offset, p->nr, p->mmap, p->start_offset, p->previous_ce); return NULL; } @@ -2068,20 +2068,23 @@ static unsigned long load_cache_entries_threaded(int nr_threads, struct index_st p->istate = istate; p->offset = i; p->nr = ce_per_thread < istate->cache_nr - i ? ce_per_thread : istate->cache_nr - i; + p->mmap = mmap; + p->start_offset = src_offset; /* create a mem_pool for each thread */ - if (istate->version == 4) + if (istate->version == 4) { mem_pool_init(&p->ce_mem_pool, estimate_cache_size_from_compressed(p->nr)); - else + + /* create a previous ce entry for this block of cache entries */ + if (previous_name->len) { + p->previous_ce = mem_pool__ce_alloc(p->ce_mem_pool, previous_name->len); + p->previous_ce->ce_namelen = previous_name->len; + memcpy(p->previous_ce->name, previous_name->buf, previous_name->len); + } + } else { mem_pool_init(&p->ce_mem_pool, estimate_cache_size(mmap_size, p->nr)); - - p->mmap = mmap; - p->start_offset = src_offset; - if (previous_name) { - strbuf_addbuf(&p->previous_name_buf, previous_name); - p->previous_name = &p->previous_name_buf; } if (pthread_create(&p->pthread, NULL, load_cache_entries_thread, p)) @@ -2104,7 +2107,7 @@ static unsigned long load_cache_entries_threaded(int nr_threads, struct index_st } else name = ondisk->name; - if (!previous_name) { + if (istate->version != 4) { size_t len; /* v3 and earlier */ @@ -2123,7 +2126,6 @@ static unsigned long load_cache_entries_threaded(int nr_threads, struct index_st if (pthread_join(p->pthread, NULL)) die("unable to join load_cache_entries_thread"); mem_pool_combine(istate->ce_mem_pool, p->ce_mem_pool); - strbuf_release(&p->previous_name_buf); consumed += p->consumed; }