From patchwork Tue Sep 11 23:26:40 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Ben Peart X-Patchwork-Id: 10596469 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 F1CE3109C for ; Tue, 11 Sep 2018 23:26:51 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id D850329BF1 for ; Tue, 11 Sep 2018 23:26:51 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id CC50929BF7; Tue, 11 Sep 2018 23:26:51 +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 0091F29BF1 for ; Tue, 11 Sep 2018 23:26:50 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1726502AbeILE2X (ORCPT ); Wed, 12 Sep 2018 00:28:23 -0400 Received: from mail-eopbgr680120.outbound.protection.outlook.com ([40.107.68.120]:1880 "EHLO NAM04-BN3-obe.outbound.protection.outlook.com" rhost-flags-OK-OK-OK-FAIL) by vger.kernel.org with ESMTP id S1726179AbeILE2X (ORCPT ); Wed, 12 Sep 2018 00:28:23 -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=/9RB0AxNRWLF3uL2HSp7WExPLFenkjgS+dMWBHMWuGk=; b=bymfrhE+8kUbk2fVb4N51o3mhAZENzBlnY/XDzOODb74Czel9oyKfa/s6iA7XGHG9Fvkr6EnUY6nwnWpcJikzk9p8660gNx6G2kV+wGlx7JSorVcz+fLYKV8H4S08QH+defjoq78eP4evCGmX28AGqexYpcXxHgc5xKpUev65ME= Received: from MW2PR2101MB0970.namprd21.prod.outlook.com (52.132.146.19) by MW2PR2101MB1113.namprd21.prod.outlook.com (52.132.149.30) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.1164.5; Tue, 11 Sep 2018 23:26:40 +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; Tue, 11 Sep 2018 23:26:40 +0000 From: Ben Peart To: "git@vger.kernel.org" CC: "gitster@pobox.com" , "pclouds@gmail.com" , Ben Peart Subject: [PATCH v4 4/5] read-cache.c: optimize reading index format v4 Thread-Topic: [PATCH v4 4/5] read-cache.c: optimize reading index format v4 Thread-Index: AQHUSibksfTADAV93UWDv7xMuyp/UA== Date: Tue, 11 Sep 2018 23:26:40 +0000 Message-ID: <20180911232615.35904-5-benpeart@microsoft.com> References: <20180823154053.20212-1-benpeart@microsoft.com> <20180911232615.35904-1-benpeart@microsoft.com> In-Reply-To: <20180911232615.35904-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: CY4PR1601CA0021.namprd16.prod.outlook.com (2603:10b6:910:72::34) 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;MW2PR2101MB1113;6:kxwnhh03VExeqVzz5+xUpvzzOrqvux8TYZqDCYK+9+9D64QTO55HnNOIEy/AY4ot144ujYFvjATnkuVwwjMczG9KI+Xluuvh0tvMeBA2F2cLw1lmmaTXXlmjTTZZmAuL248ERaKrqOFnIMX1565ESs8FUAMdkUvJDCVyV1cww+cM3IChYdG5fWeAKnwayKLFMXwYpkzwocwkfeQp/L8ICgo1RqKyR5XVj1HV+Vzl0i+kPXQuCalHajk4rQHJKZIIIo5wd1d+F4P1feJzhs/xX7GYkxJWtfe0re0m9VQ32H4MhJBeS7LcHzSBgW8vhpD+FyN5n9BTruQyM8K67QqRxjL+rb5kNXgKMO974e9Eb9ZNrnDMtxEiDtDpj2olts70rH2ps2qZ/oNXaAT/dhD1mkYP859YgKNGiXmSI+/fG8AQQRxxrJzrpaMEo8/BC9c6DWmYc17rnRCRCPldAsNy3A==;5:CqdY1sovzxfc8dLau4C6Wg4y9YeKAgpnUygVXDfwsBk6eYjJGNxviqB6McrGYr6YTGpSUoKWTeEQEMbH9lK679N2bEFyTGpmu5J6BHG6IgTjJLxkUF7tpmN198Si/JO65V1A+uQvNExVEbhIeLXobq2FMZtV6H6k9/JDKYgpVfc=;7:DEIg+d9dHVOErutCBbR+ZbdNj9VWmILDVvEn8muILrGpXRbfn2btVdvwNXbXIm2quVEGwV/HMTFyQBy2BbsAp8ywfvcJv0zCvJkx3IkMERN3nTzkfRipoh3I8V+RA18kfVo+zQ/5aGYVVKRES7xRr6EV7Pe5Mil1NbvRaxODmxTOUJx8BmtTauv8NaknxH0EQ6yPjZh55m9zn2RKPbhhI9AIDSFoCgsOsZ8aVgxinh9uYVqNO5MaJ7azCc9k49xN x-ms-office365-filtering-correlation-id: 68ca8b26-e9a6-49de-5319-08d6183e0664 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:MW2PR2101MB1113; x-ms-traffictypediagnostic: MW2PR2101MB1113: 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)(3231344)(944501410)(52105095)(2018427008)(3002001)(6055026)(149027)(150027)(6041310)(201703131423095)(201702281528075)(20161123555045)(201703061421075)(201703061406153)(20161123558120)(20161123560045)(20161123562045)(20161123564045)(201708071742011)(7699050)(76991037);SRVR:MW2PR2101MB1113;BCL:0;PCL:0;RULEID:;SRVR:MW2PR2101MB1113; x-forefront-prvs: 0792DBEAD0 x-forefront-antispam-report: SFV:NSPM;SFS:(10019020)(39860400002)(346002)(366004)(376002)(396003)(136003)(199004)(189003)(386003)(6116002)(97736004)(6506007)(86612001)(7736002)(5640700003)(81156014)(81166006)(26005)(2900100001)(102836004)(6436002)(1730700003)(6346003)(305945005)(11346002)(14444005)(446003)(2616005)(476003)(486006)(3846002)(256004)(36756003)(10090500001)(66066001)(186003)(53936002)(1076002)(106356001)(105586002)(2351001)(6512007)(316002)(4326008)(54906003)(2906002)(52116002)(25786009)(5660300001)(107886003)(68736007)(22452003)(76176011)(39060400002)(6916009)(50226002)(478600001)(2501003)(99286004)(72206003)(14454004)(5250100002)(8936002)(8676002)(10290500003)(6486002);DIR:OUT;SFP:1102;SCL:1;SRVR:MW2PR2101MB1113;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: s2O0lEyBWwwyIqPECY0Uqd9Of2Bi881pWfwFp6EI76hd8pyuo45uAd7hI256C4RQPC14Zd8d4x8GhcX6flhZfQqpV5Iuw9aNX9KYjHi4fKj2oD7WQLDmHejrN577SbR3onuZrGgX0BF3RgUzcOz/Lw9N0qJMp5BkYucGdY5+uJTkhVh1keqZPQZCb9hvqsJQfokBnrvqsbYlsrNsr/+sZm1s7Z/jf6n1/1R7Coz7jJEmvIRMJUD/8m1pO98nmHJvUbPCoSxba1x9NaLTNmwwnYiLPaRHYAuijf1vW1G4whiILqWXZB2Vq36heIool1qvHuH9MmYsWEJzU5Pw/rtZ5cJl5upgoF1ltqQyb4W91k0= spamdiagnosticoutput: 1:99 spamdiagnosticmetadata: NSPM Content-ID: MIME-Version: 1.0 X-OriginatorOrg: microsoft.com X-MS-Exchange-CrossTenant-Network-Message-Id: 68ca8b26-e9a6-49de-5319-08d6183e0664 X-MS-Exchange-CrossTenant-originalarrivaltime: 11 Sep 2018 23:26:40.3312 (UTC) X-MS-Exchange-CrossTenant-fromentityheader: Hosted X-MS-Exchange-CrossTenant-id: 72f988bf-86f1-41af-91ab-2d7cd011db47 X-MS-Exchange-Transport-CrossTenantHeadersStamped: MW2PR2101MB1113 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 | 136 +++++++++++++++++++++++++++------------------------ 1 file changed, 71 insertions(+), 65 deletions(-) diff --git a/read-cache.c b/read-cache.c index c01d34a71d..d21ccb5e67 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; + int expand_name_field = version == 4; /* On-disk flags are just 16 bits */ flags = get_be16(&ondisk->flags); @@ -1797,21 +1772,54 @@ 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; + } - *ent_size = (name - ((char *)ondisk)) + consumed; + if (len == CE_NAMEMASK) { + len = strlen(name); + if (expand_name_field) + len += 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); + + if (expand_name_field) { + if (copy_len) + 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 +1956,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 +1967,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,20 +1979,16 @@ 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, istate->cache_nr * (sizeof(struct cache_entry) + CACHE_ENTRY_PATH_LENGTH)); } 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; } @@ -2005,8 +2010,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 */ }; @@ -2019,7 +2023,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; } @@ -2066,20 +2070,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)) @@ -2102,7 +2109,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 */ @@ -2121,7 +2128,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; }