From patchwork Sun Jun 18 18:27:37 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jan Hubicka X-Patchwork-Id: 1796263 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@legolas.ozlabs.org Authentication-Results: legolas.ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=gcc.gnu.org (client-ip=8.43.85.97; helo=sourceware.org; envelope-from=gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=) Authentication-Results: legolas.ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org header.a=rsa-sha256 header.s=default header.b=ehzOl5ta; dkim-atps=neutral Received: from sourceware.org (server2.sourceware.org [8.43.85.97]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature ECDSA (P-384) server-digest SHA384) (No client certificate requested) by legolas.ozlabs.org (Postfix) with ESMTPS id 4QkhGT46dGz20WT for ; Mon, 19 Jun 2023 04:28:01 +1000 (AEST) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 3505C3858D33 for ; Sun, 18 Jun 2023 18:27:59 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 3505C3858D33 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1687112879; bh=q/Z12/fcWxiT3kEhuxn3IbT2Kazi/0ZOXWb6DKbHd+U=; h=Date:To:Subject:List-Id:List-Unsubscribe:List-Archive:List-Post: List-Help:List-Subscribe:From:Reply-To:From; b=ehzOl5taHbVJjFXT7n/vDQqynAQnv4amg7UKZXMe/nJU9xkJP+a4wtyArnf2VmZfr WOTtZs+HPWYgjHsqRUYIAMuQPuvlktnRaG6sfv6CeWZ7vnRgYLqSHEtHmCsLtmkViv /gugYe6ymSCI3mR9Ma1sXgP7t9QYUvcVB8xzV+JQ= X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from nikam.ms.mff.cuni.cz (nikam.ms.mff.cuni.cz [195.113.20.16]) by sourceware.org (Postfix) with ESMTPS id E808A3858D28 for ; Sun, 18 Jun 2023 18:27:38 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org E808A3858D28 Received: by nikam.ms.mff.cuni.cz (Postfix, from userid 16202) id B91FC28AEC3; Sun, 18 Jun 2023 20:27:37 +0200 (CEST) Date: Sun, 18 Jun 2023 20:27:37 +0200 To: gcc-patches@gcc.gnu.org, jwakely@redhat.com Subject: [libstdc++] Improve M_check_len Message-ID: MIME-Version: 1.0 Content-Disposition: inline X-Spam-Status: No, score=-11.1 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, GIT_PATCH_0, HEADER_FROM_DIFFERENT_DOMAINS, RCVD_IN_MSPIKE_H3, 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 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-Patchwork-Original-From: Jan Hubicka via Gcc-patches From: Jan Hubicka Reply-To: Jan Hubicka Errors-To: gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org Sender: "Gcc-patches" 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)) + && __builtin_constant_p (__n) + && sizeof (ptrdiff_t) >= 8 + && __n < max_size () / 2) + 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.