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 [216.205.24.124]) by sourceware.org (Postfix) with ESMTP id C96A9383303A for ; Fri, 18 Jun 2021 21:19:24 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org C96A9383303A Received: from mail-wr1-f72.google.com (mail-wr1-f72.google.com [209.85.221.72]) (Using TLS) by relay.mimecast.com with ESMTP id us-mta-475-0CFpnmeJPM-EHDdj3OKgJg-1; Fri, 18 Jun 2021 17:19:23 -0400 X-MC-Unique: 0CFpnmeJPM-EHDdj3OKgJg-1 Received: by mail-wr1-f72.google.com with SMTP id v9-20020a5d4a490000b029011a86baa40cso500269wrs.7 for ; Fri, 18 Jun 2021 14:19:23 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to:cc; bh=12rmgeLQ/+qpc1biYqkRODYmfhyFldrKpke2T9OLydA=; b=MQn1V28KtdEv4pL/DOBJTcjKcJfqu8svRHpwjjTSBW5UctfxS3MOrIFTIMeDFI4tIv nwEuef9M51xdegWytq0Alr7OtQvwn/JTHWnWhf3Ku0rnJjvckB17OMQl6SsJ6cTvNyaC BaddXRSC1teYUFWVLy+uPSvT0Z0tQIf2tdM2vBrGGrmcdCZc2Zo72G6lzegSzwnD54Mm XACyAYNKMFbUX9I2vIfxUCzNQo8u12SL/ifXh5Llcvi23yTeH1XDYPh/Nou13fngnzY6 uwGSv9sl8ZZZjNGtCn91r+gHkMgaiZAQ5LhrYNMBsxlceqOKAhg0GnRqaQFgOIV5KDAD BePg== X-Gm-Message-State: AOAM532pcwcFToRwgg8G9JPfyLqkDXjgh3f+msjYCiNuDdBc6bVnBhKO MF1gNSZxlcsuD1DcLBLcl2PJ7VD+ZX2rCR0jSqX4UE5Ad5bKW0t0bPfmK1Y+tB+dq3Jd8K4MAJJ //cEBsveBmpmWHODTG6Zh7cUmqHIa6MQK5w== X-Received: by 2002:a1c:2601:: with SMTP id m1mr11665965wmm.185.1624051162310; Fri, 18 Jun 2021 14:19:22 -0700 (PDT) X-Google-Smtp-Source: ABdhPJxeTt6Odo8sPEjFBjc5tTGZHaz+o2Eu5LNubDur0hgQXBwxA0GNsyG1eBk7OrvP/9kA5MjA2FD85vyP1zaKtaI= X-Received: by 2002:a1c:2601:: with SMTP id m1mr11665957wmm.185.1624051162074; Fri, 18 Jun 2021 14:19:22 -0700 (PDT) MIME-Version: 1.0 References: <20210505014220.1216746-1-ppalka@redhat.com> <20210505093931.GP3008@redhat.com> <8ecb8845-8f8d-393d-15eb-8eb9c6bc8a73@idea> <42b07719-808a-3a3d-2a27-8310a2562f5b@idea> <5ac36fdc-c7f0-b9a5-d89-34b730d3e765@idea> In-Reply-To: <5ac36fdc-c7f0-b9a5-d89-34b730d3e765@idea> From: Jonathan Wakely Date: Fri, 18 Jun 2021 22:19:10 +0100 Message-ID: Subject: Re: [PATCH] libstdc++: Reduce ranges::minmax/minmax_element comparison complexity To: Patrick Palka Cc: gcc Patches , "libstdc++" 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_LOW, RCVD_IN_MSPIKE_H4, RCVD_IN_MSPIKE_WL, SPF_HELO_NONE, SPF_PASS, TXREP autolearn=ham autolearn_force=no version=3.4.2 X-Spam-Checker-Version: SpamAssassin 3.4.2 (2018-09-13) on server2.sourceware.org X-BeenThere: gcc-patches@gcc.gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Gcc-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Fri, 18 Jun 2021 21:19:26 -0000 On Fri, 18 Jun 2021 at 18:44, Patrick Palka wrote: > > Ping; here's the same patch with the above comment corrected. > > -- >8 -- > > Subject: [PATCH] libstdc++: Reduce ranges::minmax/minmax_element comparison > complexity > > This rewrites ranges::minmax and ranges::minmax_element so that it > performs at most 3*N/2 many comparisons, as required by the standard. > In passing, this also fixes PR100387 by avoiding a premature std::move > in ranges::minmax and in std::shift_right. > > Tested on x86_64-pc-linux-gnu, does this look OK for trunk and perhaps > 10/11? OK, for all branches, thanks.