From patchwork Thu May 21 10:59:49 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jan Hubicka X-Patchwork-Id: 1295108 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Authentication-Results: ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=gcc.gnu.org (client-ip=8.43.85.97; helo=sourceware.org; envelope-from=gcc-patches-bounces@gcc.gnu.org; receiver=) Authentication-Results: ozlabs.org; dmarc=none (p=none dis=none) header.from=ucw.cz Received: from sourceware.org (server2.sourceware.org [8.43.85.97]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (4096 bits) server-digest SHA256) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id 49SRTq0JJsz9sSJ for ; Thu, 21 May 2020 20:59:57 +1000 (AEST) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 84E99387086F; Thu, 21 May 2020 10:59:54 +0000 (GMT) X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from nikam.ms.mff.cuni.cz (nikam.ms.mff.cuni.cz [195.113.20.16]) by sourceware.org (Postfix) with ESMTPS id C6C903851C2F for ; Thu, 21 May 2020 10:59:50 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.3.2 sourceware.org C6C903851C2F Authentication-Results: sourceware.org; dmarc=none (p=none dis=none) header.from=ucw.cz Authentication-Results: sourceware.org; spf=none smtp.mailfrom=hubicka@kam.mff.cuni.cz Received: by nikam.ms.mff.cuni.cz (Postfix, from userid 16202) id AABD028094C; Thu, 21 May 2020 12:59:49 +0200 (CEST) Date: Thu, 21 May 2020 12:59:49 +0200 From: Jan Hubicka To: gcc-patches@gcc.gnu.org Subject: Fix hashing of prestreamed nodes Message-ID: <20200521105949.GA59676@kam.mff.cuni.cz> MIME-Version: 1.0 Content-Disposition: inline User-Agent: Mutt/1.10.1 (2018-07-13) X-Spam-Status: No, score=-25.6 required=5.0 tests=BAYES_00, GIT_PATCH_0, HEADER_FROM_DIFFERENT_DOMAINS, KAM_DMARC_STATUS, KAM_LAZY_DOMAIN_SECURITY, RCVD_IN_MSPIKE_H3, RCVD_IN_MSPIKE_WL, SPF_HELO_NONE, SPF_NONE, TXREP autolearn=ham autolearn_force=no version=3.4.2 X-Spam-Checker-Version: SpamAssassin 3.4.2 (2018-09-13) 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: , Errors-To: gcc-patches-bounces@gcc.gnu.org Sender: "Gcc-patches" Hi, this patch seems to solve basically all collisions while building cc1. From: [WPA] read 3312246 unshared trees [WPA] read 1144381 mergeable SCCs of average size 4.833785 [WPA] 8843938 tree bodies read in total [WPA] tree SCC table: size 524287, 197767 elements, collision ratio: 0.506446 [WPA] tree SCC max chain length 43 (size 1) [WPA] Compared 946614 SCCs, 775077 collisions (0.818789) to [WPA] read 3314520 unshared trees [WPA] read 1144763 mergeable SCCs of average size 4.835021 [WPA] 8849473 tree bodies read in total [WPA] tree SCC table: size 524287, 200574 elements, collision ratio: 0.486418 [WPA] tree SCC max chain length 2 (size 1) [WPA] Compared 944189 SCCs, 179 collisions (0.000190) The problem is that preloaded nodes all have hash code 0 because cache->nodes.length is not updated while streaming out. I also added an arbitrary constant to avoid clash with constant of 0 used to hash NULL pointers and 1 used to hash pointers inside SCC. Bootstrapped/regtested x86_64-linux, comitted. * tree-streamer.c (record_common_node): Fix hash value of pre-streamed nodes. diff --git a/gcc/tree-streamer.c b/gcc/tree-streamer.c index f6181fafc4c..b0afa1dc6c0 100644 --- a/gcc/tree-streamer.c +++ b/gcc/tree-streamer.c @@ -299,10 +299,11 @@ record_common_node (struct streamer_tree_cache_d *cache, tree node) if (!node) node = error_mark_node; - /* ??? FIXME, devise a better hash value. But the hash needs to be equal - for all frontend and lto1 invocations. So just use the position - in the cache as hash value. */ - streamer_tree_cache_append (cache, node, cache->nodes.length ()); + /* This hash needs to be equal for all frontend and lto1 invocations. So + just use the position in the cache as hash value. + Small integers are used by hash_tree to record positions within scc + hash. Values are not in same range. */ + streamer_tree_cache_append (cache, node, cache->next_idx + 0xc001); switch (TREE_CODE (node)) {