From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from us-smtp-delivery-124.mimecast.com (us-smtp-delivery-124.mimecast.com [170.10.133.124]) by sourceware.org (Postfix) with ESMTPS id 7DD183858403 for ; Fri, 26 Aug 2022 14:25:15 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 7DD183858403 Authentication-Results: sourceware.org; dmarc=pass (p=none dis=none) header.from=redhat.com Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=redhat.com DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=redhat.com; s=mimecast20190719; t=1661523914; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:cc:mime-version:mime-version:content-type:content-type: in-reply-to:in-reply-to:references:references; bh=7GBzXvG2pPAaWbpzIIXigDiPhGbFR8G0l3ut67ZtzMI=; b=cEb82wGlnebz+aBPT9of7UmoPjNmBXoXQku6miF7ga4VVpNqFJguehHl9GSpUmfky6U2Hk hMKL61RfdOxqV3jbsk2HeYf65AjHNMHcGwOrGz370v8s1f44BgWvLzPEb9u4X0Bs3GvYZp dL+MF5G2YAFVfetgy3UMEjMwKeSYpgs= Received: from mail-qt1-f200.google.com (mail-qt1-f200.google.com [209.85.160.200]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.3, cipher=TLS_AES_128_GCM_SHA256) id us-mta-600-4ID5qxflNiOdoKOSVGUkow-1; Fri, 26 Aug 2022 10:25:14 -0400 X-MC-Unique: 4ID5qxflNiOdoKOSVGUkow-1 Received: by mail-qt1-f200.google.com with SMTP id v13-20020a05622a188d00b00343794bd1daso1380133qtc.23 for ; Fri, 26 Aug 2022 07:25:13 -0700 (PDT) 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=7GBzXvG2pPAaWbpzIIXigDiPhGbFR8G0l3ut67ZtzMI=; b=vXa7i0AhCQSPYuFQeXtz69vYWzDi8Y4Ye+tx+ddrEBT/lbKGd3RXlBOBrxwOJ2UwHT KdxiM2kr0GEC23xnvA1jCU3J5BATyxncGOmQHm8NMoA4L5xfuBtrbXkVdb+xtbWjzhU0 YF2yiV0l5WhPxAujl1VjE5EdvMHJItmDrY8d/XvhE9rByJ1b9HTA35Tei0op450J6lZd 8HdnT6QncIeKrvaa1Xr0a/kKFofCdPdaWw/Djg7BEbVerTWI945UmzjFBliswxTQjMta l4AeWYe3RnnlHXAgdTLn7DH7+xfjPtuQ7S1vZgWm8U9OYP1LZQv8EO10TFMjRIQ9iZGp RY9A== X-Gm-Message-State: ACgBeo0bO/5XCn80/PqHkw1i154XC58TBYL+6QKgCFZmoGfG4czEKQ3g qhsuqvvg1FH3h+gISTY4wTkKkMfBa9ryfGLTyhRLJtziq1ET+5eJxzJ/Dbzdm3NVBcaO90Ll6Jo ld9axd2GthCp7XE9eJNv/TZcnc25XR+g= X-Received: by 2002:a37:4452:0:b0:6bb:fb52:5c75 with SMTP id r79-20020a374452000000b006bbfb525c75mr6822657qka.638.1661523913533; Fri, 26 Aug 2022 07:25:13 -0700 (PDT) X-Google-Smtp-Source: AA6agR4fwDvQpaL/KplRo8K1RdzLN/XcRKeckkFN5POn9nFgG4NQ182g8lokyFu9OhaqiPzHG/0z0FgB787vCdQV44E= X-Received: by 2002:a37:4452:0:b0:6bb:fb52:5c75 with SMTP id r79-20020a374452000000b006bbfb525c75mr6822648qka.638.1661523913277; Fri, 26 Aug 2022 07:25:13 -0700 (PDT) MIME-Version: 1.0 References: <20220824194013.2035464-1-ppalka@redhat.com> <1096f2fe-28df-ad54-8f74-95a12a32c79d@idea> In-Reply-To: <1096f2fe-28df-ad54-8f74-95a12a32c79d@idea> From: Jonathan Wakely Date: Fri, 26 Aug 2022 15:25:02 +0100 Message-ID: Subject: Re: [PATCH] libstdc++: Optimize std::con/disjunction, __and_/__or_, etc To: Patrick Palka Cc: libstdc++@gcc.gnu.org, gcc-patches@gcc.gnu.org X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Type: text/plain; charset="UTF-8" X-Spam-Status: No, score=-6.2 required=5.0 tests=BAYES_00,DKIMWL_WL_HIGH,DKIM_SIGNED,DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,RCVD_IN_DNSWL_NONE,SPF_HELO_NONE,SPF_NONE,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 Fri, 26 Aug 2022 at 14:45, Patrick Palka via Libstdc++ wrote: > > On Wed, 24 Aug 2022, Patrick Palka wrote: > > > The internal type-level logical operations __and_ and __or_ are > > currently quite slow to compile for a couple of reasons: > > > > 1. They are drop-in replacements for std::con/disjunction, which > > are rigidly specified to form a type that derives from the first > > type argument that caused the overall computation to short-circuit. > > In practice this inheritance property seems to be rarely needed; > > usually all we care about is the value of the overall expression. > > 2. Their recursive implementations instantiate up to ~N class templates > > and form up to a depth ~N inheritance chain. > > > > This patch does away with this inheritance property of __and_ and __or_ > > (which seems to be unneeded in the library except indirectly by > > std::con/disjunction) and redefines them as alias templates that yield > > either false_type or true_type via SFINAE and overload resolution of a > > pair of function templates. > > Another difference between this implementation of __and_/__or_ and > std::con/disjunction is the handling of invalid/non-"truthy" operands. > The standard makes this ill-formed ([meta.logical]/4), whereas this > implementation of __and_/__or_ silently treats such an operand as if > it were false_type/true_type respectively. > > Thus e.g. std::conjunction_v and std::disjunction_v are both > ill-formed The standard probably *should* make it ill-formed, but currently it makes it undefined, because it just says "shall be". Violating that rule has undefined behaviour, so isn't required to be ill-formed. Our implementations make it ill-formed, because that's just what happens if we try to access Bi::value outside a SFINAE context, but I think > whereas __and_v/__or_v are false/true respectively > with this implementation (somewhat nonsensically). Which is actually fine for something that the standard says is undefined. Ill-formed is more user-friendly for the standardized std::{con,dis}junction APIs than (potentially unbounded) UB, but "somewhat nonsensical, but entirely well-defined" is perfectly fine for our own internal helpers. > Though I'm not sure > if this corner case is relevant for our current internal uses of > __and_/__or_, which all seem to pass in "truthy" operands. Yes, I *think* it's the case that we always pass sensible types into them. There's a small risk in that I've sometimes used __and_ where the standard requires conjunction, just because it saved one class template instantiation to do so. But I think even in those cases, all the type args are traits like is_assignable, which will always be truthy. We should keep this edge case difference in mind for the future though, and use std::{con,dis}junction if the difference might matter. The new implementations of __and_ and __or_ are very impressive. The patch is OK for trunk, thanks! Yesterday you mentioned changing conjunction_v to be defined in terms of the cheaper __and_v in stead of conjunction::value. If we decide there are some edge cases that would make that not equivalent, what we could do is: template inline constexpr conjunction_v = __detail::__conjunction_impl::value; i.e. skip the step of instantiating std::conjunction::type and just use that type directly. But I think we should be able to just define it as __and_v because [meta.logical]/4 makes that equivalent to conjunction::value.