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 E7A773858D28 for ; Mon, 19 Jun 2023 10:12:32 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org E7A773858D28 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=1687169552; 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=BZaiOpnUuBKf+T68p2RCEOiCoPT/QYK3O8h0COCCh6U=; b=cUHcmSRA59JHwp5gjMNBMb4+oKBmjada1SGA51l+WdR0wi+MLr9GbC2h9yITBnPqm+Uf5Q aVNVL82gKGorHFQhUm/uxIG3VWhoidk5fD36dJre0nXzoO6PeScNOoQ0Ftbgy6TpqcKnPs zOzJ+r5ys/FVE6QJjKI3N5xSUOpLBjY= Received: from mail-lj1-f200.google.com (mail-lj1-f200.google.com [209.85.208.200]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.3, cipher=TLS_AES_256_GCM_SHA384) id us-mta-264-6kvkR3p_NnadNtrdOWbAJA-1; Mon, 19 Jun 2023 06:12:30 -0400 X-MC-Unique: 6kvkR3p_NnadNtrdOWbAJA-1 Received: by mail-lj1-f200.google.com with SMTP id 38308e7fff4ca-2b337a245b7so22870721fa.3 for ; Mon, 19 Jun 2023 03:12:30 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1687169549; x=1689761549; h=cc:to:subject:message-id:date:from:in-reply-to:references :mime-version:x-gm-message-state:from:to:cc:subject:date:message-id :reply-to; bh=BZaiOpnUuBKf+T68p2RCEOiCoPT/QYK3O8h0COCCh6U=; b=T5VGKQzXZd3lZn4rdToSkOUcbRV7OVYscnYjrCA9/GV3ixECOxqyoxON7vLCDhf4sI Q5oTa0e6xAzWDRBxCtttqicgtfnr1An9eMUv9bHnRQOmUdl7wkbEna3IsogX8XWpxKal c3lPwWbyDIw/zBUddSOfirAFIRMrkpwYnIW6HE8SFJNtrJ6qjWVSql5xqMVxHm5eEITQ JN6KtaDvJ4tFj9MtzeHaDvIiPYFWK/4KOyzlwFhJ2Xa1Vwmw2YrlshosW3Bque4drRjR ypoxh4jsfCBWHoM1GQgXbuDqwULViN9EynscdhbRq9U3VTe8se7zo4D9qZaRC9FPqA4D 5GpQ== X-Gm-Message-State: AC+VfDz+pwGAggR8wdRw/P0rqHskTr4PZXVnIvXxQjftcPiFQaomExq9 mgRdQnD2WCfWl21Ywie1X0q7xbmhqDJLzlbgjcc4shaRaE7pJaTIgiYqYvUYMrp90lmi5asf8XO 0OSzmW7osz4RHm1+p6JBcY60HqsGV2svrrA== X-Received: by 2002:a2e:9b08:0:b0:2b1:be84:5496 with SMTP id u8-20020a2e9b08000000b002b1be845496mr5588951lji.12.1687169549342; Mon, 19 Jun 2023 03:12:29 -0700 (PDT) X-Google-Smtp-Source: ACHHUZ56UVQilcRM9/bedRWjr1DaKaHwhWDFs6rA4lEmtngbJvvQaY3qw5brS+rGeEPKOP3fLEmJvyWVLup1lPDa7I8= X-Received: by 2002:a2e:9b08:0:b0:2b1:be84:5496 with SMTP id u8-20020a2e9b08000000b002b1be845496mr5588941lji.12.1687169549040; Mon, 19 Jun 2023 03:12:29 -0700 (PDT) MIME-Version: 1.0 References: In-Reply-To: From: Jonathan Wakely Date: Mon, 19 Jun 2023 11:12:20 +0100 Message-ID: Subject: Re: [libstdc++] Improve M_check_len To: Jan Hubicka Cc: gcc-patches@gcc.gnu.org X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Type: multipart/alternative; boundary="000000000000a5977b05fe78c533" X-Spam-Status: No, score=-12.1 required=5.0 tests=BAYES_00,DKIMWL_WL_HIGH,DKIM_SIGNED,DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,GIT_PATCH_0,HTML_MESSAGE,RCVD_IN_DNSWL_NONE,RCVD_IN_MSPIKE_H5,RCVD_IN_MSPIKE_WL,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: --000000000000a5977b05fe78c533 Content-Type: text/plain; charset="UTF-8" On Sun, 18 Jun 2023 at 19:37, Jan Hubicka wrote: > Hi, > _M_check_len is used in vector reallocations. It computes __n + __s but > does > checking for case that (__n + __s) * sizeof (Tp) would overflow ptrdiff_t. > Since we know that __s is a size of already allocated memory block if __n > is > not too large, this will never happen on 64bit systems since memory is not > that > large. This patch adds __builtin_constant_p checks for this case. This > size > of fully inlined push_back function that is critical for loops that are > controlled by std::vector based stack. > > With the patch to optimize std::max and to handle SRA candidates, we > fully now inline push_back with -O3 (not with -O2), however there are still > quite few silly things for example: > > // _78 is original size of the allocated vector. > > _76 = stack$_M_end_of_storage_177 - _142; > _77 = _76 /[ex] 8; > _78 = (long unsigned int) _77; > _79 = MAX_EXPR <_78, 1>; > _80 = _78 + _79; // this is result of _M_check_len doubling the > allocated vector size. > if (_80 != 0) // result will always be non-zero. > goto ; [54.67%] > else > goto ; [45.33%] > > [local count: 30795011]: > if (_80 > 1152921504606846975) // doubling succesfully allocated > memmory will never get so large. > goto ; [10.00%] > else > goto ; [90.00%] > > [local count: 3079501]: > if (_80 > 2305843009213693951) // I wonder if we really want to have > two different throws > goto ; [50.00%] > else > goto ; [50.00%] > > [local count: 1539750]: > std::__throw_bad_array_new_length (); > > [local count: 1539750]: > std::__throw_bad_alloc (); > > [local count: 27715510]: > _108 = _80 * 8; > _109 = operator new (_108); > > Maybe we want to add assumption that result of the function is never > greater than max_size to get rid of the two checks above. However this > will still be recongized only after inlining and will continue confusing > inliner heuristics. > > Bootstrapped/regtested x86_64-linux. I am not too familiar with libstdc++ > internals, > so would welcome comments and ideas. > > libstdc++-v3/ChangeLog: > > PR tree-optimization/110287 > * include/bits/stl_vector.h: Optimize _M_check_len for constantly > sized > types and allocations. > > diff --git a/libstdc++-v3/include/bits/stl_vector.h > b/libstdc++-v3/include/bits/stl_vector.h > index 70ced3d101f..3ad59fe3e2b 100644 > --- a/libstdc++-v3/include/bits/stl_vector.h > +++ b/libstdc++-v3/include/bits/stl_vector.h > @@ -1895,11 +1895,22 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER > size_type > _M_check_len(size_type __n, const char* __s) const > { > - if (max_size() - size() < __n) > - __throw_length_error(__N(__s)); > + // On 64bit systems vectors of small sizes can not > + // reach overflow by growing by small sizes; before > + // this happens, we will run out of memory. > + if (__builtin_constant_p (sizeof (_Tp)) > This shouldn't be here, of course sizeof is a constant. No space before the opening parens, libstdc++ doesn't follow GNU style. > + && __builtin_constant_p (__n) > + && sizeof (ptrdiff_t) >= 8 > + && __n < max_size () / 2) > This check is not OK. As I said in Bugzilla just now, max_size() depends on the allocator, which could return something much smaller than PTRDIFF_MAX. You can't make this assumption for all specializations of std::vector. If Alloc::max_size() == 100 and this->size() == 100 then this function needs to throw length_error for *any* n. In the general case you cannot remove size() from this condition. For std::allocator it's safe to assume that max_size() is related to PTRDIFF_MAX/sizeof(T), but this patch would apply to all allocators. > + return size() + (std::max)(size(), __n); > + else > + { > + if (max_size() - size() < __n) > + __throw_length_error(__N(__s)); > > - const size_type __len = size() + (std::max)(size(), __n); > - return (__len < size() || __len > max_size()) ? max_size() : __len; > + const size_type __len = size() + (std::max)(size(), __n); > + return (__len < size() || __len > max_size()) ? max_size() : > __len; > + } > } > > // Called by constructors to check initial size. > > --000000000000a5977b05fe78c533--