From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from omta36.uswest2.a.cloudfilter.net (omta36.uswest2.a.cloudfilter.net [35.89.44.35]) by sourceware.org (Postfix) with ESMTPS id A1FC83858D32 for ; Fri, 3 Nov 2023 18:54:49 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org A1FC83858D32 Authentication-Results: sourceware.org; dmarc=none (p=none dis=none) header.from=tromey.com Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=tromey.com ARC-Filter: OpenARC Filter v1.0.0 sourceware.org A1FC83858D32 Authentication-Results: server2.sourceware.org; arc=none smtp.remote-ip=35.89.44.35 ARC-Seal: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1699037699; cv=none; b=Sc06F0aRMyTfJEEwSogCUxNxyULyhd+91lfRrT8+wiqzklEcaafet6EZsqfGmYln4VxMX4E8lim3wPGfhXSOOhMqQJxAcL2o1dfN/u7yrzBI6eAx5EMNnvkVKAsRICkCU5ECuXbvhLOIc7sJ0WzVk3WqaHPCyGvNpQLMxXU9f54= ARC-Message-Signature: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1699037699; c=relaxed/simple; bh=e7hptFkL/0e4u5D8PAtg3pbHAJsACDQq8I74XJJP/9c=; h=DKIM-Signature:From:To:Subject:Date:Message-ID:MIME-Version; b=ZBFITReBnBaWsN3S8iDeCW9TxOmEM3b1sMMB1p6qcB8P0gGiRbteJe/fvbsWT4OjG8tsJEcNdb43jKoshZuf6609m1lfkIfy3I0PFI9GuJW+tPR19/wH+ReaFgLfHdVMTFHqsVaPOC0eYaGRpJAlZ4wMykU5DTteBO0wJoYrdtE= ARC-Authentication-Results: i=1; server2.sourceware.org Received: from eig-obgw-6010a.ext.cloudfilter.net ([10.0.30.248]) by cmsmtp with ESMTPS id yvecqNfWlhqFdyzJgqJoO5; Fri, 03 Nov 2023 18:54:48 +0000 Received: from box5379.bluehost.com ([162.241.216.53]) by cmsmtp with ESMTPS id yzJfqDdnoruMPyzJfqf7Nx; Fri, 03 Nov 2023 18:54:47 +0000 X-Authority-Analysis: v=2.4 cv=ZNHEJF3b c=1 sm=1 tr=0 ts=654541f7 a=ApxJNpeYhEAb1aAlGBBbmA==:117 a=ApxJNpeYhEAb1aAlGBBbmA==:17 a=OWjo9vPv0XrRhIrVQ50Ab3nP57M=:19 a=dLZJa+xiwSxG16/P+YVxDGlgEgI=:19 a=BNY50KLci1gA:10 a=Qbun_eYptAEA:10 a=6I5d2MoRAAAA:8 a=MMNsf5PQiyCB31TkeqwA:9 a=IjZwj45LgO3ly-622nXo:22 DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=tromey.com; s=default; h=Content-Type:MIME-Version:Message-ID:In-Reply-To:Date:References :Subject:Cc:To:From:Sender:Reply-To:Content-Transfer-Encoding:Content-ID: Content-Description:Resent-Date:Resent-From:Resent-Sender:Resent-To:Resent-Cc :Resent-Message-ID:List-Id:List-Help:List-Unsubscribe:List-Subscribe: List-Post:List-Owner:List-Archive; bh=/Bk+Qjs7wxYQQsgxnneAfYIuDiVYRl0INOOPAnAzzW0=; b=M9zNdbdtukpEYZyOJ0T063BCBs X9SGv9iDLxArU0zJP2N+c1y88Tu4vvMMruj0rmiFhNlkc+SSwvX0xAZIQ7k+PilSY86Z0kRmNiqp1 GnHz4rpIjtA+w1IYFKRqeS2iL; Received: from 97-122-77-73.hlrn.qwest.net ([97.122.77.73]:43490 helo=murgatroyd) by box5379.bluehost.com with esmtpsa (TLS1.2) tls TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384 (Exim 4.96.2) (envelope-from ) id 1qyzJe-000f7K-2n; Fri, 03 Nov 2023 12:54:46 -0600 From: Tom Tromey To: John Baldwin Cc: Tom Tromey , gdb-patches@sourceware.org Subject: Re: [PATCH 00/19] Add hash table to gdbsupport References: <20230407-t-robin-hood-hash-v1-0-900d93ef1510@tromey.com> <31427308-7225-4aee-7b57-25c0fd06954c@FreeBSD.org> X-Attribution: Tom Date: Fri, 03 Nov 2023 12:54:45 -0600 In-Reply-To: <31427308-7225-4aee-7b57-25c0fd06954c@FreeBSD.org> (John Baldwin's message of "Mon, 10 Apr 2023 12:45:50 -0700") Message-ID: <87h6m2is5m.fsf@tromey.com> User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/28.2 (gnu/linux) MIME-Version: 1.0 Content-Type: text/plain X-AntiAbuse: This header was added to track abuse, please include it with any abuse report X-AntiAbuse: Primary Hostname - box5379.bluehost.com X-AntiAbuse: Original Domain - sourceware.org X-AntiAbuse: Originator/Caller UID/GID - [47 12] / [47 12] X-AntiAbuse: Sender Address Domain - tromey.com X-BWhitelist: no X-Source-IP: 97.122.77.73 X-Source-L: No X-Exim-ID: 1qyzJe-000f7K-2n X-Source: X-Source-Args: X-Source-Dir: X-Source-Sender: 97-122-77-73.hlrn.qwest.net (murgatroyd) [97.122.77.73]:43490 X-Source-Auth: tom+tromey.com X-Email-Count: 14 X-Org: HG=bhshared;ORG=bluehost; X-Source-Cap: ZWx5bnJvYmk7ZWx5bnJvYmk7Ym94NTM3OS5ibHVlaG9zdC5jb20= X-Local-Domain: yes X-CMAE-Envelope: MS4xfBe1iRK+6dkq3u3l74FM7/GEANAC5D5BCn7Vi0i06WEEUziO2tPFPKNAGm+pxln1jQ03NPqKOioEuqODYkq3bil08lXH0v3oHw2VnkKjddQvxxrgbxAH nagXHy9LnTrYxcYYx/wm0rWLd9nloOx29ecwCfdRgBaoBE1NAu1xn6oNPTq/uVw/MIJ4uvGZCH2AfG8SkiGZvyw8W+QRNhIbVqw= X-Spam-Status: No, score=-3018.4 required=5.0 tests=BAYES_00,DKIM_SIGNED,DKIM_VALID,JMQ_SPF_NEUTRAL,RCVD_IN_MSPIKE_H2,SPF_HELO_NONE,SPF_PASS,TXREP,T_SCC_BODY_TEXT_LINE autolearn=no autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org List-Id: >>>>> "John" == John Baldwin writes: John> On 4/7/23 8:25 AM, Tom Tromey wrote: >> I recently read an article about hash tables and was inspired to write >> a new one for gdb. I haven't converted all the libiberty htab uses in >> gdb, but this series does change enough of them to, I think, show that >> the new implementation is workable. >> The benefits of this approach are explained in the first patch. >> Regression tested on x86-64 Fedora 36. This found a latent bug in >> one >> use of htab_t, see the typedefs patch. >> Let me know what you think. John> I just have one possibly naive question which is why not use John> std::unordered_map<> directly in the various callers? At least, I think John> it might be useful to explain why GDB includes a bespoke hash table now John> that we require C++11, it was more obvious I think when GDB was still John> written in C. std::unordered_map has some issues. They may not affect every spot using hash tables in gdb, but they probably affect some of them. unordered_map is necessarily a chained hash table, not an open addressed hash table. And, it has to allocate nodes for entries, because it promises pointer stability. So, it has higher overhead than the hash table in this series. Also, I don't think there's a way to use one type as the key in unordered_map but do lookups using a different type. gdb uses this in some places. I'll add some text to this effect to patch #1. Tom