From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-ed1-x535.google.com (mail-ed1-x535.google.com [IPv6:2a00:1450:4864:20::535]) by sourceware.org (Postfix) with ESMTPS id F2396383CCEA for ; Wed, 31 Aug 2022 09:37:54 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org F2396383CCEA Authentication-Results: sourceware.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=gmail.com Received: by mail-ed1-x535.google.com with SMTP id c59so11374410edf.10 for ; Wed, 31 Aug 2022 02:37:54 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112; h=cc:to:subject:message-id:date:from:in-reply-to:references :mime-version:from:to:cc; bh=YHQG0V0i+1MFDT/WpGQzVJ9ED9IDeJBvtJLCWgnqFPI=; b=c9RCwJTNkS27nO0nm+JxL9x4R7qqDAuST/tMNi5PATqUYdhcotpE5USb50yro+1uMx 8fBsmt47GLUwso9B7INYgSE0jP3dsw4F+RXJ+M0b6Y3p2d4uJRZ3FN13ZhCInNvbLEi9 JTe0yS+eBNSQV9bzWDQml98K8b5/iwGK8M7nPVFOYxN8rHzMuSoyiZdmrP+AfxNY5eof gYEo8eOX/oZqqyXD8fG7OGCYIwbYBteAiTVJoCGlZXrVF7Yp7i55PCSynfOdcICb5FmH lxpbyi56GxCqUPfcSNN0Gg39dJEBpbmXJzlnqjX2ZSseuGhjg2N3J89JNWhcpbYNO0fY tBeg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=cc:to:subject:message-id:date:from:in-reply-to:references :mime-version:x-gm-message-state:from:to:cc; bh=YHQG0V0i+1MFDT/WpGQzVJ9ED9IDeJBvtJLCWgnqFPI=; b=1I5koQoC/9fkrXCsR/jNw8Tv4vs8yuNlNMf0+TrroRtbObcqTOxZHjCUmf6p3jiNwL 1LlwyEAEblTt8IXV3iyPEZ1D1zNFQQbEVuepLyok4KBVuyktEetYI6IQdI5fNvy+KAwi jO34MVSHBqW1ns2u4cauAa6FlpDlMj+M3eNDoI+XI19gQ9Q8uuD+qSg/L5WhMkAcUb7Z X4q+n7OT3NzeZHPumG5YwTiNFZzli91zbMBt9VjgZyvm/RB2ZE1VlV50X5aBHlO6zX9V jLvgauVe4qETCuOsBxQVONOZcWUCijAQ75VNxRh4fE/65a/r2oQA5dbbnhV78Qgl4aze fZbw== X-Gm-Message-State: ACgBeo3kqx7bQulyB/fN6ygaeY87e5SmKGUdRy1dT178n5cClnL9mCGx yAbkl2UpVeahlW98ffl/TGTARpTUHZq5f0YivXI= X-Google-Smtp-Source: AA6agR5V02k1SFISBWyBI0jZJtkbP3VKIQKd7I0mriySMxe0n/fkOg65bQpdT8adufWpHfDxn+ow5wDidYcS8KKs7P8= X-Received: by 2002:a50:fc97:0:b0:449:1fd1:25ea with SMTP id f23-20020a50fc97000000b004491fd125eamr1074088edq.301.1661938673731; Wed, 31 Aug 2022 02:37:53 -0700 (PDT) MIME-Version: 1.0 References: <942GHR.WGPY8O255349@tim-lange.me> In-Reply-To: From: Jonathan Wakely Date: Wed, 31 Aug 2022 10:37:42 +0100 Message-ID: Subject: Re: Usage of the C++ stdlib unordered_map in GCC To: Marek Polacek Cc: Tim Lange , GCC Mailing List Content-Type: text/plain; charset="UTF-8" X-Spam-Status: No, score=-0.5 required=5.0 tests=BAYES_00,DKIM_SIGNED,DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,FREEMAIL_FROM,RCVD_IN_DNSWL_NONE,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 List-Id: On Tue, 30 Aug 2022 at 21:08, Marek Polacek via Gcc wrote: > > On Tue, Aug 30, 2022 at 09:57:45PM +0200, Tim Lange wrote: > > Hello, > > > > I was preparing a patch for GCC and used the unordered_map from the C++ > > stdlib in my patch. Later on, I noticed that it is used nowhere else inside > > GCC except for some files in the go frontend. > > > > I wondered, now that building GCC requires a C++11 host compiler, whether > > there is a consensus on which data structure implementation is preferred. > > Should I rather use a hash_map instead of an unordered_map or is it on my > > side to decide which one I choose? > > I think you're probably better off using a hash_map; std::unordered_map > has efficiency issues as described in > https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2020/p2028r0.pdf I assume you mean the comments on page 6. Does GCC's hash_map actually use open addressing and probing to deal with collisions? Do we want to be able to change the hash function or use per-compilation salts? (Would that break PCH?) If not, I don't see why it would be any better when considering the metrics that paper is referring to. It might be better based on other properties that benefit GCC, but the case against std::unordered_map is often overstated. If the question was whether to prefer std::unordered_map or absl::node_hash_map then I would agree that std::unordered_map is a bad choice. But that's not the question.