From patchwork Wed Feb 14 15:14:08 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Richard Biener X-Patchwork-Id: 1898972 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@legolas.ozlabs.org Authentication-Results: legolas.ozlabs.org; dkim=fail reason="signature verification failed" (1024-bit key; unprotected) header.d=suse.de header.i=@suse.de header.a=rsa-sha256 header.s=susede2_rsa header.b=CFbPzdAR; dkim=fail reason="signature verification failed" header.d=suse.de header.i=@suse.de header.a=ed25519-sha256 header.s=susede2_ed25519 header.b=BVGSfnRJ; dkim=fail reason="signature verification failed" (1024-bit key) header.d=suse.de header.i=@suse.de header.a=rsa-sha256 header.s=susede2_rsa header.b=CFbPzdAR; dkim=neutral header.d=suse.de header.i=@suse.de header.a=ed25519-sha256 header.s=susede2_ed25519 header.b=BVGSfnRJ; dkim-atps=neutral Authentication-Results: legolas.ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=gcc.gnu.org (client-ip=8.43.85.97; helo=server2.sourceware.org; envelope-from=gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=patchwork.ozlabs.org) Received: from server2.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 ECDSA (secp384r1) server-digest SHA384) (No client certificate requested) by legolas.ozlabs.org (Postfix) with ESMTPS id 4TZhZ12MwFz23j8 for ; Thu, 15 Feb 2024 02:14:33 +1100 (AEDT) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 1391C3860002 for ; Wed, 14 Feb 2024 15:14:31 +0000 (GMT) X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from smtp-out1.suse.de (smtp-out1.suse.de [195.135.223.130]) by sourceware.org (Postfix) with ESMTPS id 8930F38582B9 for ; Wed, 14 Feb 2024 15:14:09 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 8930F38582B9 Authentication-Results: sourceware.org; dmarc=pass (p=none dis=none) header.from=suse.de Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=suse.de ARC-Filter: OpenARC Filter v1.0.0 sourceware.org 8930F38582B9 Authentication-Results: server2.sourceware.org; arc=none smtp.remote-ip=195.135.223.130 ARC-Seal: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1707923651; cv=none; b=b/mdr/cFQlVBaerJEvVw9Kd7sq+3P0DV1k8lRjc35Ppra2CUK26R6R6SlRMv6z9TANcMP9xsNqkZIOZhXio5vBrAnSoai/MwiJRKV2cVw0Bq8I4BY+J51vv0DR+5ZScM3kFM4hEdMg1K3m+6q+UK+KNtGFBvpL3piiJG8j+W9Zg= ARC-Message-Signature: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1707923651; c=relaxed/simple; bh=JR8gohII7wtKQs8wX9uFxS9j8es4NEaaxU/s3SvnFpA=; h=DKIM-Signature:DKIM-Signature:DKIM-Signature:DKIM-Signature:Date: From:To:Subject:MIME-Version; b=TWLqqVYaIDb4TZzcLqum7NKV6YbKy2mm33f5tOWz2m7ehWK73ubQAR+uTYmXlEGAX788qCLJFcA5FNzGWoJZLA7gFp3CyNT6wqb1990GY5uhz+UGUCOjncb/Babf32slrElpMOPyre0RqrsY9QgeSeaLuzb4MXLvDd5AIaw01T0= ARC-Authentication-Results: i=1; server2.sourceware.org Received: from [10.168.4.150] (unknown [10.168.4.150]) (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 smtp-out1.suse.de (Postfix) with ESMTPS id 56A38220DD for ; Wed, 14 Feb 2024 15:14:08 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=suse.de; s=susede2_rsa; t=1707923648; h=from:from:reply-to:date:date:to:to:cc:mime-version:mime-version: content-type:content-type; bh=a8nnJwW7AG/bqCPgNxH2jD2eTckKuGnVGQRMK06+I5o=; b=CFbPzdARkSSYUrbBx9yxRxWgsI/nWb2fRzqOFIsx4g0AoInYX+uDTZ3nHKmBQyKmABF2Jd AwbyNc3lIe1XP8fZv1edLTcpG3dCD+i7PjajrwQ2/cVl4ZlEZxEzGQPL+rYInjp4kD2pCT VW8/TwsUVFCBZ+TVu0cYjg/kSTtfto8= DKIM-Signature: v=1; a=ed25519-sha256; c=relaxed/relaxed; d=suse.de; s=susede2_ed25519; t=1707923648; h=from:from:reply-to:date:date:to:to:cc:mime-version:mime-version: content-type:content-type; bh=a8nnJwW7AG/bqCPgNxH2jD2eTckKuGnVGQRMK06+I5o=; b=BVGSfnRJCpC3QgKdVbPCqnFAKoG23O728uxsXVR7mTXKW+qHKQJS3Qh4LYH5qrWZzo9C5P vPu0XjX8VSEVTcCA== DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=suse.de; s=susede2_rsa; t=1707923648; h=from:from:reply-to:date:date:to:to:cc:mime-version:mime-version: content-type:content-type; bh=a8nnJwW7AG/bqCPgNxH2jD2eTckKuGnVGQRMK06+I5o=; b=CFbPzdARkSSYUrbBx9yxRxWgsI/nWb2fRzqOFIsx4g0AoInYX+uDTZ3nHKmBQyKmABF2Jd AwbyNc3lIe1XP8fZv1edLTcpG3dCD+i7PjajrwQ2/cVl4ZlEZxEzGQPL+rYInjp4kD2pCT VW8/TwsUVFCBZ+TVu0cYjg/kSTtfto8= DKIM-Signature: v=1; a=ed25519-sha256; c=relaxed/relaxed; d=suse.de; s=susede2_ed25519; t=1707923648; h=from:from:reply-to:date:date:to:to:cc:mime-version:mime-version: content-type:content-type; bh=a8nnJwW7AG/bqCPgNxH2jD2eTckKuGnVGQRMK06+I5o=; b=BVGSfnRJCpC3QgKdVbPCqnFAKoG23O728uxsXVR7mTXKW+qHKQJS3Qh4LYH5qrWZzo9C5P vPu0XjX8VSEVTcCA== Date: Wed, 14 Feb 2024 16:14:08 +0100 (CET) From: Richard Biener To: gcc-patches@gcc.gnu.org Subject: [PATCH][RFC] tree-optimization/113910 - improve bitmap_hash MIME-Version: 1.0 Authentication-Results: smtp-out1.suse.de; none X-Spamd-Result: default: False [2.40 / 50.00]; ARC_NA(0.00)[]; FROM_HAS_DN(0.00)[]; TO_MATCH_ENVRCPT_ALL(0.00)[]; MIME_GOOD(-0.10)[text/plain]; TO_DN_NONE(0.00)[]; RCPT_COUNT_ONE(0.00)[1]; MISSING_MID(2.50)[]; DKIM_SIGNED(0.00)[suse.de:s=susede2_rsa,suse.de:s=susede2_ed25519]; FUZZY_BLOCKED(0.00)[rspamd.com]; RCVD_COUNT_ZERO(0.00)[0]; FROM_EQ_ENVFROM(0.00)[]; MIME_TRACE(0.00)[0:+] X-Spam-Score: 2.40 X-Spam-Status: No, score=-9.3 required=5.0 tests=BAYES_00, DKIM_INVALID, DKIM_SIGNED, GIT_PATCH_0, KAM_DMARC_STATUS, MISSING_MID, SPF_HELO_NONE, SPF_PASS, TXREP, T_SCC_BODY_TEXT_LINE 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.30 Precedence: list List-Id: Gcc-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org Message-Id: <20240214151431.1391C3860002@sourceware.org> The following tries to improve the actual hash function for hashing bitmaps. We're still getting collision rates as high as 23 for the testcase in the PR. The following improves this by properly mixing in the bitmap element starting bit number. This brings down the collision rate below 1.4, improving compile-time by 25% for the testcase but at the expense of bringing bitmap_hash into the profile at around 5% of the samples as collected by perf. When you actually mix each set bit number collisions are virtually non-existent but hashing is then taking 35% of the compile time. Any better ideas? PR tree-optimization/113910 * bitmap.cc (bitmap_hash): Improve hash function by mixing the bitmap element index rather than XORing it. XOR individual elements into the hash. --- gcc/bitmap.cc | 12 ++++++++---- 1 file changed, 8 insertions(+), 4 deletions(-) diff --git a/gcc/bitmap.cc b/gcc/bitmap.cc index 459e32c1ad1..80e185d5146 100644 --- a/gcc/bitmap.cc +++ b/gcc/bitmap.cc @@ -2695,18 +2695,22 @@ hashval_t bitmap_hash (const_bitmap head) { const bitmap_element *ptr; - BITMAP_WORD hash = 0; + hashval_t hash = 0; int ix; gcc_checking_assert (!head->tree_form); for (ptr = head->first; ptr; ptr = ptr->next) { - hash ^= ptr->indx; + hash = iterative_hash_hashval_t (ptr->indx, hash); + BITMAP_WORD bits = 0; for (ix = 0; ix != BITMAP_ELEMENT_WORDS; ix++) - hash ^= ptr->bits[ix]; + bits ^= ptr->bits[ix]; + if (sizeof (bits) == 8 && sizeof (hashval_t) == 4) + bits ^= bits >> 32; + hash ^= (hashval_t)bits; } - return iterative_hash (&hash, sizeof (hash), 0); + return hash; }