From patchwork Mon Aug 1 05:18:40 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Paul Hollinsky X-Patchwork-Id: 325 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a05:6a10:b5d6:b0:2b9:3548:2db5 with SMTP id v22csp2129640pxt; Sun, 31 Jul 2022 22:22:45 -0700 (PDT) X-Google-Smtp-Source: AGRyM1uZl36wfbubL60UNrIW0TMJ9RlJBAhwgPuxOM6HbN2EpjN0nOB+oL6I+gMmMj80hJqctGyj X-Received: by 2002:a17:906:7482:b0:722:edf9:e72f with SMTP id e2-20020a170906748200b00722edf9e72fmr11021246ejl.92.1659331365380; Sun, 31 Jul 2022 22:22:45 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1659331365; cv=none; d=google.com; s=arc-20160816; b=OIxGTVJjOp1AvZOiV6VY77yHUirW7A2QoJoPMw4ECU7bu2Si1XLZGRvqjrbcpCcAyt gqCgaez6UbHbMn14A+fEuRPDbzWPYw5u4wkFnHgqUfCSHGg1zMS9ypWbeDLLhY4UzoWW ikQvbfSEBxc3D4Zq+hyW/rGMLJU8P8+BdYoYR1u54evBGu0iepiMAlSeRHzyxBsCkdR1 emUmZd/JlFiBUlp8tPV++6NxnehGLEHO5XaY1pWylDdWGZs1ihz1cQjZbVrGCaVF9Ikb Y9o6K7PT40Fl7FHwbMvFsfqw+cwbVNHWxJ7xoyHyjDRq+QZWN3hrbRoDIS71oHME1OBE wFOw== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=sender:errors-to:cc:reply-to:from:list-subscribe:list-help :list-post:list-archive:list-unsubscribe:list-id:precedence :content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:to:dmarc-filter:delivered-to:dkim-signature :dkim-filter; bh=qfYLz22emExYdDuHX1AR88LhlJLXIrp/eSxlIQO38lA=; b=mzAaHI8RtrDxx0RLmcXYJnFr6CiYnzm5N6XIDhyI+Ek1gGTWnAG8gmqtKV6l5BDi7q ZvEDrtharTSmmy0H5FhpviCj6V0BUb+oh6BarYqdVUgm8seTrGMIQA9TGCz2zbazQ9eF 6/9gt9RUVTBc3nMGJFSgcsqraGmucfbiLKtQqL8qrUYQ24Hhku80y5O7/ZN2LQB/3Nvj EYiA5Ik+m92y2xlPll5ZHKsYxl2CGrzlfqy50cL4HfPsxgi5KBzC58mF+ItkXHBwGJjZ CW2QFXqxa6002T9IA44uxMiA+KclVuUAuqwteCjAgx/OyR9mTYOFWSapkbk3riGMByui INng== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@gcc.gnu.org header.s=default header.b="Ov2XDc/I"; spf=pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 8.43.85.97 as permitted sender) smtp.mailfrom="gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org"; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=gnu.org Received: from sourceware.org (ip-8-43-85-97.sourceware.org. [8.43.85.97]) by mx.google.com with ESMTPS id v18-20020a056402349200b0043c8ac1ad11si11114700edc.618.2022.07.31.22.22.45 for (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sun, 31 Jul 2022 22:22:45 -0700 (PDT) Received-SPF: pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 8.43.85.97 as permitted sender) client-ip=8.43.85.97; Authentication-Results: mx.google.com; dkim=pass header.i=@gcc.gnu.org header.s=default header.b="Ov2XDc/I"; spf=pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 8.43.85.97 as permitted sender) smtp.mailfrom="gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org"; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=gnu.org Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 39FC338582B9 for ; Mon, 1 Aug 2022 05:22:44 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 39FC338582B9 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1659331364; bh=qfYLz22emExYdDuHX1AR88LhlJLXIrp/eSxlIQO38lA=; h=To:Subject:Date:In-Reply-To:References:List-Id:List-Unsubscribe: List-Archive:List-Post:List-Help:List-Subscribe:From:Reply-To:Cc: From; b=Ov2XDc/Ivlz0HT2L+WgFgUmS+2EOpTjvTR23yDGzAd3fucMqfP8G3V5K4IcPMDfU7 OF6VebrgFreNJSpFm9DzwOMFtBDCkLs22eUzmxjZG4X4jTqWzaXc4TwF1Wjj4+9xM/ cPcBIKxlR9k28J95dBDeSebJzMAFv6XVI4EJY7SY= X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from mail-pj1-x102f.google.com (mail-pj1-x102f.google.com [IPv6:2607:f8b0:4864:20::102f]) by sourceware.org (Postfix) with ESMTPS id DD9963858412 for ; Mon, 1 Aug 2022 05:22:00 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org DD9963858412 Received: by mail-pj1-x102f.google.com with SMTP id pm17so4064728pjb.3 for ; Sun, 31 Jul 2022 22:22:00 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc; bh=qfYLz22emExYdDuHX1AR88LhlJLXIrp/eSxlIQO38lA=; b=dnKFNQH+CBVhjaNvZUPiW2i1GcKfhqR+8xqozu/WssvV12BsfXXr8OdfGySDTrvANi /MFFOZRWCZNtn5Z+OhrhDlWAebBDcAg7NL5bfTt+b0z0eP/fuTvEAjq7HHNygq8L37nR wuZLpDO4bjThPGQtRX4QrLF+iV0r4klapZZYWtgFz/O4KA2iTwLjnTbBsptDZWoKWJga HysLbeiE/K0E49g9pjzr8V/TgisQVTMUYWb4fHUY+OxodejIgpf8iP84lyjnsLMHrPKo LxEOanP46MEl1zxyIijlsC5waRR85Atxd6j8/IVIJPdvBjBchUPamwoEgw4AyeGM6u6c X5VA== X-Gm-Message-State: ACgBeo0KaJjAzpVM6ti0kvG+x2serYzMmED7sXad51ZdSUaf/qKRUPrr b3x/DpazdSWV3TLhgLNrbs1dxijVzKYCGA== X-Received: by 2002:a17:902:f606:b0:168:ecca:44e with SMTP id n6-20020a170902f60600b00168ecca044emr15087970plg.144.1659331319203; Sun, 31 Jul 2022 22:21:59 -0700 (PDT) Received: from perseverence-linux.localdomain (76-14-114-239.rk.wavecable.com. [76.14.114.239]) by smtp.gmail.com with ESMTPSA id y15-20020a17090a16cf00b001f216a9d021sm10511345pje.40.2022.07.31.22.21.58 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sun, 31 Jul 2022 22:21:58 -0700 (PDT) To: gcc-patches@gcc.gnu.org Subject: [PATCH V2] libcpp: Optimize #pragma once with a hash table [PR58770] Date: Mon, 1 Aug 2022 05:18:40 +0000 Message-Id: <20220801051839.1454-1-paulhollinsky@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20220706230321.48041-1-paulhollinsky@gmail.com> References: <20220706230321.48041-1-paulhollinsky@gmail.com> MIME-Version: 1.0 X-Spam-Status: No, score=-12.8 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, FREEMAIL_FROM, GIT_PATCH_0, RCVD_IN_DNSWL_NONE, SPF_HELO_NONE, SPF_PASS, TXREP autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org X-BeenThere: gcc-patches@gcc.gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Gcc-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-Patchwork-Original-From: Paul Hollinsky via Gcc-patches From: Paul Hollinsky Reply-To: Paul Hollinsky Cc: Tom Tromey , Per Bothner , Paul Hollinsky Errors-To: gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org Sender: "Gcc-patches" X-getmail-retrieved-from-mailbox: =?utf-8?q?INBOX?= X-GMAIL-THRID: =?utf-8?q?1739935045480004355?= X-GMAIL-MSGID: =?utf-8?q?1739935045480004355?= Rather than traversing the all_files linked list for every include, this factors out the quick idempotency checks (modification time and size) to be the keys in a hash table so we can find matching files quickly. The hash table value type is a linked list, in case more than one file matches the quick check. The table is only built if a once-only file is seen, so include guard performance is not affected. My laptop would previously complete Ricardo's benchmark from the PR in ~1.1s using #pragma once, and ~0.35s using include guards. After this change, both benchmarks now complete in ~0.35s. I did have to randomize the modification dates on the benchmark headers so the files did not all end up in the same hash table list, but that would likely not come up outside of the contrived benchmark. I bootstrapped and ran the testsuite on x86_64 Darwin, as well as ppc64le and aarch64 Linux. libcpp/ChangeLog: PR preprocessor/58770 * internal.h: Add hash table for #pragma once * files.cc: Optimize #pragma once with the hash table Signed-off-by: Paul Hollinsky --- libcpp/files.cc | 116 +++++++++++++++++++++++++++++++++++++++++++--- libcpp/internal.h | 3 ++ 2 files changed, 112 insertions(+), 7 deletions(-) diff --git a/libcpp/files.cc b/libcpp/files.cc index 24208f7b0f8..d4ffd77578e 100644 --- a/libcpp/files.cc +++ b/libcpp/files.cc @@ -167,6 +167,33 @@ struct file_hash_entry_pool struct cpp_file_hash_entry pool[FILE_HASH_POOL_SIZE]; }; +/* A set of attributes designed to quickly identify obviously different files + in a hashtable. Just in case there are collisions, we still maintain a + list. These sub-lists can then be checked for #pragma once rather than + interating through all_files. */ +struct file_quick_idempotency_attrs +{ + file_quick_idempotency_attrs(const _cpp_file *f) + : mtime(f->st.st_mtime), size(f->st.st_size) {} + + time_t mtime; + off_t size; + + static hashval_t hash (/* _cpp_file* */ const void *p); +}; + +/* Sub-list of very similar files kept in a hashtable to check for #pragma + once. */ +struct file_sublist +{ + _cpp_file *f; + file_sublist *next; + + static int eq (/* _cpp_file* */ const void *p, + /* file_sublist* */ const void *q); + static void del (/* file_sublist* */ void *p); +}; + static bool open_file (_cpp_file *file); static bool pch_open_file (cpp_reader *pfile, _cpp_file *file, bool *invalid_pch); @@ -849,17 +876,17 @@ has_unique_contents (cpp_reader *pfile, _cpp_file *file, bool import, if (!pfile->seen_once_only) return true; - /* We may have read the file under a different name. Look - for likely candidates and compare file contents to be sure. */ - for (_cpp_file *f = pfile->all_files; f; f = f->next_file) + /* We may have read the file under a different name. We've kept + similar looking files in this lists under this hash table, so + check those more thoroughly. */ + void* ent = htab_find(pfile->pragma_once_files, file); + for (file_sublist *e = static_cast (ent); e; e = e->next) { + _cpp_file *f = e->f; if (f == file) continue; /* It'sa me! */ - if ((import || f->once_only) - && f->err_no == 0 - && f->st.st_mtime == file->st.st_mtime - && f->st.st_size == file->st.st_size) + if ((import || f->once_only) && f->err_no == 0) { _cpp_file *ref_file; @@ -895,6 +922,38 @@ has_unique_contents (cpp_reader *pfile, _cpp_file *file, bool import, return true; } +/* Add the given file to the #pragma once table so it can be + quickly identified and excluded the next time it's seen. */ +static void +update_pragma_once_table (cpp_reader *pfile, _cpp_file *file) +{ + void **slot = htab_find_slot (pfile->pragma_once_files, file, INSERT); + if (slot) + { + if (!*slot) + *slot = xcalloc (1, sizeof (file_sublist)); + + file_sublist *e = static_cast (*slot); + while (e->f) + { + if (!e->next) + { + void *new_sublist = xcalloc(1, sizeof (file_sublist)); + e->next = static_cast (new_sublist); + } + e = e->next; + } + + e->f = file; + } + else + { + cpp_error (pfile, CPP_DL_ERROR, + "Unable to create #pragma once table space for %s", + _cpp_get_file_name (file)); + } +} + /* Place the file referenced by FILE into a new buffer on the buffer stack if possible. Returns true if a buffer is stacked. Use LOC for any diagnostics. */ @@ -950,6 +1009,9 @@ _cpp_stack_file (cpp_reader *pfile, _cpp_file *file, include_type type, if (!has_unique_contents (pfile, file, type == IT_IMPORT, loc)) return false; + if (pfile->seen_once_only && file->once_only) + update_pragma_once_table (pfile, file); + if (pfile->buffer && file->dir) sysp = MAX (pfile->buffer->sysp, file->dir->sysp); @@ -1434,6 +1496,41 @@ nonexistent_file_hash_eq (const void *p, const void *q) return filename_cmp ((const char *) p, (const char *) q) == 0; } +/* Hasher for the #pragma once hash table. */ +hashval_t +file_quick_idempotency_attrs::hash (const void *p) +{ + const _cpp_file *f = static_cast (p); + file_quick_idempotency_attrs kh (f); + return iterative_hash_object (kh, 0); +} + +/* Equality checker for the #pragma once hash table. */ +int +file_sublist::eq (const void *p, const void *q) +{ + /* Just check if the file q would be in the list p. Every + file in the list should have these attributes the same, + so we don't need to traverse. */ + const file_sublist *e = static_cast (p); + const _cpp_file *f = static_cast (q); + return f->st.st_mtime == e->f->st.st_mtime + && f->st.st_size == e->f->st.st_size; +} + +/* Cleanup for a file sub-list. Does not free the _cpp_file + structures within. */ +void +file_sublist::del (void *p) +{ + file_sublist *e = static_cast (p); + if (e->next) + { + file_sublist::del (e->next); + free (e->next); + } +} + /* Initialize everything in this source file. */ void _cpp_init_files (cpp_reader *pfile) @@ -1442,6 +1539,10 @@ _cpp_init_files (cpp_reader *pfile) NULL, xcalloc, free); pfile->dir_hash = htab_create_alloc (127, file_hash_hash, file_hash_eq, NULL, xcalloc, free); + pfile->pragma_once_files = htab_create_alloc (127, + file_quick_idempotency_attrs::hash, + file_sublist::eq, file_sublist::del, + xcalloc, free); allocate_file_hash_entries (pfile); pfile->nonexistent_file_hash = htab_create_alloc (127, htab_hash_string, nonexistent_file_hash_eq, @@ -1456,6 +1557,7 @@ _cpp_cleanup_files (cpp_reader *pfile) { htab_delete (pfile->file_hash); htab_delete (pfile->dir_hash); + htab_delete (pfile->pragma_once_files); htab_delete (pfile->nonexistent_file_hash); obstack_free (&pfile->nonexistent_file_ob, 0); free_file_hash_entries (pfile); diff --git a/libcpp/internal.h b/libcpp/internal.h index badfd1b40da..9c3c46df335 100644 --- a/libcpp/internal.h +++ b/libcpp/internal.h @@ -485,6 +485,9 @@ struct cpp_reader been used. */ bool seen_once_only; + /* Optimization for #pragma once. */ + struct htab *pragma_once_files; + /* Multiple include optimization. */ const cpp_hashnode *mi_cmacro; const cpp_hashnode *mi_ind_cmacro;