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 D5AAD3858D1E for ; Fri, 30 Dec 2022 11:30:55 +0000 (GMT) Received: by mail-ed1-x535.google.com with SMTP id u28so25282967edd.10 for ; Fri, 30 Dec 2022 03:30:55 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112; h=to:in-reply-to:cc:references:message-id:date:subject:mime-version :from:content-transfer-encoding:from:to:cc:subject:date:message-id :reply-to; bh=7tk8BqWH9HcUwFtVG8f39rSXcfnaF9S82WvGcx0l6UE=; b=N4hDYUVbLZBVUWBMNqr6YQfmIIB2pWAo52RJBYDaju+hw5rc2SHykT7cskrc+BlvkB +VPCey8yWU9xLbUojZ4pbB9Ua0WOnavoUbXuErHynfIPWTujCgR6iwiym1mQSlRga4mO XDpEgK1ECjGpN07XxKMrjt+VE1RPIphU1MRRjzJvJneEi8EnHhgZ+Eel2sbLwzpBt8j5 vim9BII8vkzs9apH/QFbtmyDdD8AwomHu1IzQ4jyVMFFxz78H4RK6F++AF8V+cT+8FCz LcSisL2VxwaiDq+LVefOeUNxogrFkTh7YTx3TNdKUalyAOxApnR0MoCQkG9XaKvG7WqH hVsg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=to:in-reply-to:cc:references:message-id:date:subject:mime-version :from:content-transfer-encoding:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=7tk8BqWH9HcUwFtVG8f39rSXcfnaF9S82WvGcx0l6UE=; b=tFFITTsra6Uu23OrzbOFhAaZSOSYncphKpUjn/74ilhN3LZnKtSPJMFngwjsRYOzT3 P2TXp5ifcZYSbxfvLasDFIxks0ZpyDAhokOT2uWrv0LMOTNJM5x7VpyGWYyr0D95Dhn7 cXgj3sIzv6/hbEmkApJ7Zl/FKmM6UMuAmR8K8uQq8jV1ECz2/+CpbbRwRE9roVSKFTvH ArqeGyh7i2AjOLeM3vSB0E2FLBnUDZ7AL1HAuhIcq029Jyj4M3++BTmsl13Me4me0cMQ 9ocdw/AHjiuzNUjZfeLXuA81luAyNNHaj5gsbV25gV7KASRm5SGxZ+hZpPTV5v1UkAys A01A== X-Gm-Message-State: AFqh2kpanEvceGv3bfsQ1OqeQBbaTg0KEy3RcZuQvGGpBFpBs95GuvhL FaMJY1pZh9Rh6FU9gimVAGWBto0Mlbs= X-Google-Smtp-Source: AMrXdXv00KZr1j7ZH6D1NqIV8HaTHeYo4/J3Sthaqp1mTKFGThXSfZqgsK3HaYs0wdkX0gXipssmtg== X-Received: by 2002:a05:6402:7c9:b0:489:9ff5:548b with SMTP id u9-20020a05640207c900b004899ff5548bmr4951533edy.36.1672399853543; Fri, 30 Dec 2022 03:30:53 -0800 (PST) Received: from smtpclient.apple (dynamic-095-117-078-092.95.117.pool.telefonica.de. [95.117.78.92]) by smtp.gmail.com with ESMTPSA id p15-20020a056402500f00b0047eeaae9558sm9173066eda.60.2022.12.30.03.30.52 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Fri, 30 Dec 2022 03:30:52 -0800 (PST) Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: quoted-printable From: Richard Biener Mime-Version: 1.0 (1.0) Subject: Re: [17/17] check hash table insertions Date: Fri, 30 Dec 2022 12:30:41 +0100 Message-Id: References: Cc: gcc-patches@gcc.gnu.org In-Reply-To: To: Alexandre Oliva X-Mailer: iPhone Mail (20C65) X-Spam-Status: No, score=-3.0 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 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: > Am 30.12.2022 um 09:53 schrieb Alexandre Oliva : >=20 > =EF=BB=BFOn Dec 29, 2022, Richard Biener wrot= e: >=20 >>>> Am 29.12.2022 um 00:06 schrieb Alexandre Oliva : >>>=20 >>> =EF=BB=BFOn Dec 28, 2022, Richard Biener wr= ote: >>>=20 >>>> I wonder if on INSERT, pushing a DELETED marker would fix the dangling >>>> insert and search during delete problem be whether that would be >>>> better from a design point of view? (It of course requires a DELETED >>>> representation) >>>=20 >>> I'm undecided whether a design that rules out the possibility of not >>> having DELETED would qualify as unequivocally better. >>>=20 >>> Unless DELETED takes over the NULL representation, and something else is= >>> used for EMPTY, every INSERT point would have to be adjusted to look for= >>> the non-NULL DELETED representation. >=20 >> Not sure what you mean >=20 > I meant existing code tests that dereferencing the returned slot pointer > yields NULL. If we were to change the slot value during insert, we'd > have to adjust all callers. >=20 >> I think turning EMPTY (or DELETED) into >> DELETED at insert time would make the slot occupied for lookups and >> thus fix lookup during insert. >=20 > Yup. >=20 >> Of course insert during insert would >> still fail and possibly return the same slot again. >=20 > Yeah. >=20 >> So the most foolproof design would be a new INSERTING representation. >=20 > There's a glitch there: we can't expand with a pending insert. So we > might need to count inserting nodes separately, or (ideally) be able to > check quickly that insertions have completed. >=20 > But then, inserting with a pending insert ought to be caught and > reported, because an insertion invalidates previously-returned slot > pointers, including that of the pending insert. And that's how I got to > the proposed patch. >=20 >>> The one-pending-insertion strategy I implemented was the only one I >>> could find that addressed all of the pitfalls without significant >>> overhead. It caught even one case that the mere element-counting had >>> failed to catch. >=20 >> Yes, it=E2=80=99s true that this addresses all issues with just imposing >> constraints on API use. But the I wondered how you catched the >> completion of the insertion? (I=E2=80=99ll have to >> Dig into the patch to see) >=20 > Record the slot with the pending insert, and at any subsequent operation > (that could be affected by the pending insert), check and report in case > the insertion was not completed. Ah, OK, so the completion is checked at the next conflicting operation. Yea= h, that makes sense I guess. Thus OK (I think Jeff already approved the patch). Thanks and happy holidays! Richard=20 >=20 >=20 > --=20 > Alexandre Oliva, happy hacker https://FSFLA.org/blogs/lxo/ > Free Software Activist GNU Toolchain Engineer > Disinformation flourishes because many people care deeply about injustice > but very few check the facts. Ask me about