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: 200987 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a05:7300:bc8a:b0:106:860b:bbdd with SMTP id dn10csp1281828dyb; Wed, 14 Feb 2024 07:14:54 -0800 (PST) X-Forwarded-Encrypted: i=3; AJvYcCW4elAsu2v1HVXcjI7s0EnFXgb/8YCfsl+BqSuNC6lvmxIZxYKzk9hhSiptBpDmceGfxEU65rtD2yW4JaAEu4M4BNnH/g== X-Google-Smtp-Source: AGHT+IHckx4gHoKVq7pTF76mO/IWRUunrOUq4hOxZKoh4OQYPRmkbNzA8ZYQ7WQHNVVBPAPrzqiw X-Received: by 2002:a0c:ab12:0:b0:68e:f3ef:d79c with SMTP id h18-20020a0cab12000000b0068ef3efd79cmr2998790qvb.13.1707923694449; Wed, 14 Feb 2024 07:14:54 -0800 (PST) ARC-Seal: i=2; a=rsa-sha256; t=1707923694; cv=pass; d=google.com; s=arc-20160816; b=uAHbC8WsLBowNVnyHo6iRdLPkLazyxN60Y1nWKgH2Tx20IUoQIZiFbTFH5be17OGU7 TRu5+Av3w8KBQnyXGvdUbWRSYr8bS5/jyAzLnmQgW3/EVSBKamcXh4cuDDN3HIQRuXja 6vy9xkUfmnc1o1y/K369rvgMJ4TrlYMreCmqoRiP3HrzrW7Phh26hatRntebjtU0xvcD jdY05zR37N1E03BoFOx9s//p9ppBe9GAZvkWKvFfr4CG62Rf4FYpjD81s/meDxdUfPvP mIxmrZhC+NLPTTurvy5ZaAr02RvCGTBXFYITg6DyDJx6Dz11sLO3EtZ2caFrjEgz6zbe LgLg== ARC-Message-Signature: i=2; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=message-id:errors-to:list-subscribe:list-help:list-post :list-archive:list-unsubscribe:list-id:precedence:mime-version :subject:to:from:date:dkim-signature:dkim-signature:dkim-signature :dkim-signature:arc-filter:dmarc-filter:delivered-to; bh=gvKxnK5lD99jLCy2LGUGlWzU9PB5LH38NB/U2kd3L1o=; fh=Iz83fh3X28IGV9J2Wouw2iSCKUw+3nVfWs3C5MZRvlc=; b=Q5E+7Wrey3WWw2tEtkgFnZ31Lul7d5cAuwRqyc1Q34O3C4V5AFqAkxvS1zlZOvJMzM DaDP4MWy8suiCYDkYkPa33FswJACAAlbuR7bkbxkVw+jCOdC5b/GEwzurjxEkPqMf9eh 1ztIZ5uaWGYZ1HGIiQpySD35WZTTFB0GDvOZ7aeQ2rU8yhV+OdKb357/gVTBzopxNNhM /ZRyj6kAzgUMujkwt9yC6sr4JdbO7Nx/x9rKPsDbYpcr8KfGhWfNryZXZl4+69wT+4Kz dw0RP86OiGowrUE4J3A0LcGZhnyLAOhiFvLsoI1uuZu3yjRSTqLShDPcLIW1HNLN45QW 2BUA==; dara=google.com ARC-Authentication-Results: i=2; mx.google.com; dkim=neutral (body hash did not verify) header.i=@suse.de header.s=susede2_rsa header.b=CFbPzdAR; dkim=neutral (no key) header.i=@suse.de header.s=susede2_ed25519; dkim=neutral (body hash did not verify) header.i=@suse.de header.s=susede2_rsa header.b=CFbPzdAR; dkim=neutral (no key) header.i=@suse.de header.s=susede2_ed25519; arc=pass (i=1); spf=pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 2620:52:3:1:0:246e:9693:128c as permitted sender) smtp.mailfrom="gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org"; dmarc=fail (p=NONE sp=NONE dis=NONE) header.from=suse.de X-Forwarded-Encrypted: i=2; AJvYcCU14KWEjCZ1+IoLBVUy1z1E8PPejUVuvlBv7YeSEmkW7/+bJbB109oPq5duPdlWofOkjYO7zSLWhpyJA/kAro1iFwaV6Q== Received: from server2.sourceware.org (server2.sourceware.org. [2620:52:3:1:0:246e:9693:128c]) by mx.google.com with ESMTPS id r4-20020a056214212400b0068cdb0d8740si6101717qvc.376.2024.02.14.07.14.54 for (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 14 Feb 2024 07:14:54 -0800 (PST) Received-SPF: pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 2620:52:3:1:0:246e:9693:128c as permitted sender) client-ip=2620:52:3:1:0:246e:9693:128c; Authentication-Results: mx.google.com; dkim=neutral (body hash did not verify) header.i=@suse.de header.s=susede2_rsa header.b=CFbPzdAR; dkim=neutral (no key) header.i=@suse.de header.s=susede2_ed25519; dkim=neutral (body hash did not verify) header.i=@suse.de header.s=susede2_rsa header.b=CFbPzdAR; dkim=neutral (no key) header.i=@suse.de header.s=susede2_ed25519; arc=pass (i=1); spf=pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 2620:52:3:1:0:246e:9693:128c as permitted sender) smtp.mailfrom="gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org"; dmarc=fail (p=NONE sp=NONE dis=NONE) header.from=suse.de Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 195CC385F012 for ; Wed, 14 Feb 2024 15:14:54 +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+ouuuleilei=gmail.com@gcc.gnu.org Message-Id: <20240214151454.195CC385F012@sourceware.org> X-getmail-retrieved-from-mailbox: INBOX X-GMAIL-THRID: 1790887795666227993 X-GMAIL-MSGID: 1790887795666227993 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; }