From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from simark.ca (simark.ca [158.69.221.121]) by sourceware.org (Postfix) with ESMTPS id 55ABB3858D32 for ; Fri, 12 Jan 2024 02:57:02 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 55ABB3858D32 Authentication-Results: sourceware.org; dmarc=pass (p=none dis=none) header.from=simark.ca Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=simark.ca ARC-Filter: OpenARC Filter v1.0.0 sourceware.org 55ABB3858D32 Authentication-Results: server2.sourceware.org; arc=none smtp.remote-ip=158.69.221.121 ARC-Seal: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1705028225; cv=none; b=DtxxVPQgZHPzWufrX+Sq/Y7+a3a3AjFAzcy7Qr8FU0jGP0HRQUfnG+CllHtDC2zepZjk72PmL7UsQCKb26nG/OevZFePR9mqG6S0WVXr0/FkgcdddKe0MyTuTdTZNUDcjTmCLO51QXYb8vzQOwAnAHgtyNmWADxjb3JVX5TKleE= ARC-Message-Signature: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1705028225; c=relaxed/simple; bh=3ec109XjWRVHcxKJC6N/5jIArJkJSdeFPCCxL/SorBo=; h=DKIM-Signature:Message-ID:Date:MIME-Version:Subject:To:From; b=MYSrhnsfAW73gzkH++ZaB9CbR2cXFEOGHdmBlqmUtZRpQ96RxCiD0Q28QL0e3yKwa9/xO4jSrvcJCZjrtJY462FzwNeMg0QSXO+IFFvfkJEQhIscGCTTIjVl+HTKRHT3uqfvwqA1HlWGFlsllwkk2NGvB9DflYKwwT3YqCOLTnU= ARC-Authentication-Results: i=1; server2.sourceware.org DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=simark.ca; s=mail; t=1705028221; bh=3ec109XjWRVHcxKJC6N/5jIArJkJSdeFPCCxL/SorBo=; h=Date:Subject:To:Cc:References:From:In-Reply-To:From; b=jOWHOkkpqhmbVNhU4eGK67QIwg6sQFcmKkSGWhTzhUOioi0vRIPNIb9PgOa/MYjFK sgGrEBPalyRJ129GX2vFdqg4C+Mxz8V2zyHg3OLnCEBFFnIrA9wbgEv4RauCuAsOnx hrASZAheUgyssDErSeync2/PBoMtMI/LV+rD1gsg= Received: from [10.0.0.11] (modemcable238.237-201-24.mc.videotron.ca [24.201.237.238]) (using TLSv1.3 with cipher TLS_AES_128_GCM_SHA256 (128/128 bits) key-exchange X25519 server-signature ECDSA (prime256v1) server-digest SHA256) (No client certificate requested) by simark.ca (Postfix) with ESMTPSA id 8753D1E098; Thu, 11 Jan 2024 21:57:01 -0500 (EST) Message-ID: Date: Thu, 11 Jan 2024 21:57:01 -0500 MIME-Version: 1.0 User-Agent: Mozilla Thunderbird Subject: Re: [PATCH 00/19] Add hash table to gdbsupport Content-Language: en-US To: Tom Tromey Cc: gdb-patches@sourceware.org References: <20230407-t-robin-hood-hash-v1-0-900d93ef1510@tromey.com> <87jzpoft0q.fsf@tromey.com> <87v87zpwuw.fsf@tromey.com> From: Simon Marchi In-Reply-To: <87v87zpwuw.fsf@tromey.com> Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 7bit X-Spam-Status: No, score=-4.8 required=5.0 tests=BAYES_00,DKIM_SIGNED,DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,SPF_HELO_PASS,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 2024-01-11 13:07, Tom Tromey wrote: >>>>>> "Tom" == Tom Tromey writes: > > [ new hash table ] > > Tom> I'd like to move forward with this. > > Tom> I think most of the patches here are straightforward. The real question > Tom> is whether we want it. I've laid out my rationale in patch #1, with > Tom> some additions (explaining why this is better than unordered_map / > Tom> unordered_set) in a follow-up email. > > I tried converting a few more libiberty hash tables to this one. > > For a lot of things this is fine, big improvement, etc. > > However, this hash table doesn't really admit the possibility that an > element might not have a natural sentinel value. This particularly > comes up with hash maps, where if you want a std::string->whatever map, > you have to introduce some kind of explicit sentinel (in my case I chose > empty string) and also then have to write a trait class. > > So, this is one area where unordered_map has the advantage. Now, it > would be possible to handle this in some way. The hash table could > store a sentinel flag, for instance. Or, we could just accept this > drawback and use unordered_map when convenience is important. > > Anyway, I tend to think it's not an enormous issue, but I figured I'd > point it out. > > Tom I spent a bit of time reading the interface of your hash table, and that was a point I found unfortunate. The type V must have a default constructor and an "empty" state (I guess that's what you mean by sentinel), even if it doesn't make sense for the rest of the program. How do other implementations (of open addessing hash tables) typically deal with this? From what I recally, other implementations I have used in the past didn't have this requirement. And that makes me think that a question I did not see answered is: I don't want to undermine your work, but what is the rationale for implementing it ourselves? Efficient C++ hash maps is a topic that comes up all the time on various programming news sites (I found this recent blog post after a quick google search [1]), surely that's a solved problem. Is there not a popular hash map library we can use as-is? Simon [1] https://martin.ankerl.com/2022/08/27/hashmap-bench-01/