From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-wr1-x42d.google.com (mail-wr1-x42d.google.com [IPv6:2a00:1450:4864:20::42d]) by sourceware.org (Postfix) with ESMTPS id 8437F385AC1C for ; Wed, 7 Sep 2022 04:53:28 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 8437F385AC1C Authentication-Results: sourceware.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=gmail.com Received: by mail-wr1-x42d.google.com with SMTP id bj14so5220076wrb.12 for ; Tue, 06 Sep 2022 21:53:28 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112; h=in-reply-to:content-language:references:cc:to:subject:from :user-agent:mime-version:date:message-id:from:to:cc:subject:date; bh=AaTtbZZucNIOEi4YCAAUWJHY+VOJHmH1ScFruPgp3hs=; b=oCC6xJREfIlhI2qeYvNZv/PtyJOpIqCOw4D6OIv+pgqDn9Sw+sKBHohGF0sH+WnCcW FyIUM4bluSHG4s059BekYYzlvFCBLbqIAhdj93b98UiBLR8smTvcE6Rk+Yv89PTP4jJT 1kfUUecr/3OoKtrH8IN11Pn20jbZBnFq9H4dhnPWE5kIzKMn/AE+dng1j5IJ8QJM7TOI FltOTsuT3xKkHqAswZDItnkgvHtB0eLzpyosCzyQLyr5kFAcM41KHCcTvnEC9vo6jx7V tz1P3INAdXjYWj2dy0OXFZdPtRIoijwMJCNbMvBvVwRrYoAvGz5TwY6ZDKemzLAGcNWJ YLjQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=in-reply-to:content-language:references:cc:to:subject:from :user-agent:mime-version:date:message-id:x-gm-message-state:from:to :cc:subject:date; bh=AaTtbZZucNIOEi4YCAAUWJHY+VOJHmH1ScFruPgp3hs=; b=Jz6D0jkFVK6RKfEmfxUq6JW5dQleMZLf+p/+r5uzduwtPC2Cl3KRpw+mm2wWO2N6zw wwNkkU3veahMrfZg/1FGhuSniT+18o2GTHdIHWTZvL/P1TwH5epBqKFkhI+iCiXNerYf T4FWeIpQgjxIY14GgQNF9d1/7DkDB7hSzJIjbgJtmKJtCCW+BBCFYdaDw2zBkYygNvUO SFN5w87QDfqKl1D4oEJEHR1JYFZIKAp6b0gQDS0Qk+v3hHVg2ZTERWMmISMq//a/ygEA QnRWMr82g+XVxIbazvfzlpRCpK6Z8e18uAALRQZaEJ0wpU+8FNomdCCzOjIsVLX6VQel T+Uw== X-Gm-Message-State: ACgBeo1A6Ld027oConaq23WBB7t4VB22syzKptf0s8U/ZYfglbT8l9L+ Q2gWWRIFTonSq1CDVMOwwD4= X-Google-Smtp-Source: AA6agR4LEyFoNZes9gQfX22ZjUxZQB0pPd/1dLn0Wh6cWSoO7US288vanU27CspJ2V/EB9DipxopUQ== X-Received: by 2002:a05:6000:1568:b0:226:e2d0:abcb with SMTP id 8-20020a056000156800b00226e2d0abcbmr845087wrz.456.1662526407120; Tue, 06 Sep 2022 21:53:27 -0700 (PDT) Received: from [10.40.0.59] ([109.190.253.11]) by smtp.googlemail.com with ESMTPSA id e7-20020a05600c4e4700b003a60f0f34b7sm17777552wmq.40.2022.09.06.21.53.25 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Tue, 06 Sep 2022 21:53:26 -0700 (PDT) Content-Type: multipart/mixed; boundary="------------FRqJQWevbiU6LbmmylF18utN" Message-ID: Date: Wed, 7 Sep 2022 06:53:24 +0200 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:91.0) Gecko/20100101 Thunderbird/91.11.0 From: =?UTF-8?Q?Fran=c3=a7ois_Dumont?= Subject: Re: Add three way lower_bound To: Jonathan Wakely Cc: libstdc++ References: Content-Language: en-US In-Reply-To: X-Spam-Status: No, score=-4.2 required=5.0 tests=BAYES_00,BODY_8BITS,DKIM_SIGNED,DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,FREEMAIL_FROM,HTML_MESSAGE,NICE_REPLY_A,RCVD_IN_BARRACUDACENTRAL,RCVD_IN_DNSWL_NONE,SPF_HELO_NONE,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: This is a multi-part message in MIME format. --------------FRqJQWevbiU6LbmmylF18utN Content-Type: multipart/alternative; boundary="------------VjgFTGSnbUsQiPtoBC1KLtTS" --------------VjgFTGSnbUsQiPtoBC1KLtTS Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit On 01/09/22 08:47, Jonathan Wakely wrote: > > > On Wed, 23 Jun 2021, 21:34 François Dumont via Libstdc++, > > wrote: > > Hi > > Following the message to propose an alternative lower_bound and the > reply to use three way comparison I try to implement this. > > Before going further I wonder if this is something possible ? > > The purpose of the: > > if constexpr (three_way_comparable<>) > > is to make sure that we use it only if there is a proper <=> operator > defined. Afai understood what is in we can have the > __synth3way for any type as long as < exist. But I think that if > <=> is > implemented in terms of < then it might be too expensive, the actual > lower_bound might already be implemented this way. > > My main concerns is of course Standard conformity, could it be ok ? > > > > I don't think so. For a built-in type like int I don't think using <=> > will be faster. I could not believe it so I wrote the small bench attached and it turns out that indeed, performance are very bad. In pre- <=> mode: lower_bound.cc-thread        lower_bound (int)             657r 657u    0s         0mem    0pf With <=> support: lower_bound.cc-thread        lower_bound (int)            8621r 8620u    0s         0mem    0pf Now I wonder if it is <=> implementation that is making it so bad, I'll try to find out. Thanks for the feedback François --------------VjgFTGSnbUsQiPtoBC1KLtTS-- --------------FRqJQWevbiU6LbmmylF18utN Content-Type: text/x-c++src; charset=UTF-8; name="lower_bound.cc" Content-Disposition: attachment; filename="lower_bound.cc" Content-Transfer-Encoding: base64 I2luY2x1ZGUgPGFsZ29yaXRobT4KI2luY2x1ZGUgPHRlc3RzdWl0ZV9wZXJm b3JtYW5jZS5oPgoKaW50IG1haW4oKQp7CiAgdXNpbmcgbmFtZXNwYWNlIF9f Z251X3Rlc3Q7CiAgdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCiAgdGltZV9jb3Vu dGVyIHRpbWU7CiAgcmVzb3VyY2VfY291bnRlciByZXNvdXJjZTsKCiAgaW50 IGlhcnJbMTAwMDAwMF07CiAgZm9yIChpbnQgaSA9IDA7IGkgIT0gMTAwMDAw MDsgKytpKQogICAgaWFycltpXSA9IGk7CgogIGludCBqZm91bmQgPSAwOwog IHN0YXJ0X2NvdW50ZXJzKHRpbWUsIHJlc291cmNlKTsKICBmb3IgKGludCBq ID0gMDsgaiAhPSAxMDA7ICsraikKICAgIHsKICAgICAgaW50IGZvdW5kID0g MDsKICAgICAgZm9yIChpbnQgaSA9IDA7IGkgIT0gMTAwMDAwMDsgKytpKQoJ Zm91bmQgKz0gbG93ZXJfYm91bmQoaWFyciArIDAsIGlhcnIgKyAxMDAwMDAw LCBpKSA9PSBpYXJyICsgaTsKICAgICAgamZvdW5kICs9IGZvdW5kID09IDEw MDAwMDA7CiAgICB9CgogIHN0b3BfY291bnRlcnModGltZSwgcmVzb3VyY2Up OwoKICByZXBvcnRfcGVyZm9ybWFuY2UoX19GSUxFX18sICJsb3dlcl9ib3Vu ZCAoaW50KSIsIHRpbWUsIHJlc291cmNlKTsKICByZXR1cm4gamZvdW5kID09 IDEwMDAgPyAwIDogMTsKfQo= --------------FRqJQWevbiU6LbmmylF18utN--