From patchwork Thu Jun 27 10:39:53 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jonathan Wakely X-Patchwork-Id: 1953160 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@legolas.ozlabs.org Authentication-Results: legolas.ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=redhat.com header.i=@redhat.com header.a=rsa-sha256 header.s=mimecast20190719 header.b=hAdMIQSD; dkim-atps=neutral Authentication-Results: legolas.ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=gcc.gnu.org (client-ip=2620:52:3:1:0:246e:9693:128c; helo=server2.sourceware.org; envelope-from=gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=patchwork.ozlabs.org) Received: from server2.sourceware.org (server2.sourceware.org [IPv6:2620:52:3:1:0:246e:9693:128c]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature ECDSA (secp384r1) server-digest SHA384) (No client certificate requested) by legolas.ozlabs.org (Postfix) with ESMTPS id 4W8wQR6wKQz20Xg for ; Thu, 27 Jun 2024 20:53:03 +1000 (AEST) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 181C73834696 for ; Thu, 27 Jun 2024 10:53:02 +0000 (GMT) X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org 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 CFC713836E86 for ; Thu, 27 Jun 2024 10:52:24 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org CFC713836E86 Authentication-Results: sourceware.org; dmarc=pass (p=none dis=none) header.from=redhat.com Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=redhat.com ARC-Filter: OpenARC Filter v1.0.0 sourceware.org CFC713836E86 Authentication-Results: server2.sourceware.org; arc=none smtp.remote-ip=170.10.133.124 ARC-Seal: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1719485546; cv=none; b=ssTUpN1SkIaBdk8d/PcN5fRNtiRki14rU3NTz+lmviUckEx5kUygeSvm+1YtDS+FS1FaTEqYD33i8PNxuoU58fGhQjXpXRWjjCdxZ6ZsIrnzFfspfq3sFT9SEDU38dig9+NX3JkL668B/Jzg1lAuzHWnEpCxop/sUd1m9HRStxE= ARC-Message-Signature: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1719485546; c=relaxed/simple; bh=oicTPzhOTdp8+sHxNP6rcddNAqS+X47Mx/GTmgvdp40=; h=DKIM-Signature:From:To:Subject:Date:Message-ID:MIME-Version; b=cWgRkLw3DeHS0aTz6PoWJ8MhQ3mP5EgIcNH2dRfeZBjtlBfdAfGDaGw3YHYP+kyTBvyYIL3SuCBX7nPX9pp4fQcjZq1mcFIMFC5GNW88OONBKXLsX5hqivu4XN03YjoRLrkzYFz6g6fVK1KUjiIgDZzJC5cp/R9nmRyEJO4SaJ8= ARC-Authentication-Results: i=1; server2.sourceware.org DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=redhat.com; s=mimecast20190719; t=1719485544; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:mime-version:mime-version:content-type:content-type: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references; bh=FvCGq2H1gJ8nQvUmFOQaQBoPfJ5vy7tfgWZ4l8Jez3Y=; b=hAdMIQSDd7KHtoKwKJInStR11n2fGup7nNGdgLAJhLemUkmr+lzBkmbIneY1HD98DoG/XQ iVmJgBotzwR0jm3Y3sqSqKpKxrNfjLrxwgvWhDI4vw/Wh5uM6XeolBoJ6AaMRokQ9S09+S bU9Hp1XchMxJUuPasvCJ0yKcwN7FDWE= Received: from mx-prod-mc-01.mail-002.prod.us-west-2.aws.redhat.com (ec2-54-186-198-63.us-west-2.compute.amazonaws.com [54.186.198.63]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.3, cipher=TLS_AES_256_GCM_SHA384) id us-mta-534-8PxoNdP8P4StpiqKgzN7Kg-1; Thu, 27 Jun 2024 06:52:22 -0400 X-MC-Unique: 8PxoNdP8P4StpiqKgzN7Kg-1 Received: from mx-prod-int-01.mail-002.prod.us-west-2.aws.redhat.com (mx-prod-int-01.mail-002.prod.us-west-2.aws.redhat.com [10.30.177.4]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (2048 bits) server-digest SHA256) (No client certificate requested) by mx-prod-mc-01.mail-002.prod.us-west-2.aws.redhat.com (Postfix) with ESMTPS id A6BC519560B5; Thu, 27 Jun 2024 10:52:21 +0000 (UTC) Received: from localhost (unknown [10.42.28.171]) by mx-prod-int-01.mail-002.prod.us-west-2.aws.redhat.com (Postfix) with ESMTP id 19BD3300021A; Thu, 27 Jun 2024 10:52:20 +0000 (UTC) From: Jonathan Wakely To: libstdc++@gcc.gnu.org, gcc-patches@gcc.gnu.org Subject: [PATCH 2/3] libstdc++: Optimize __uninitialized_default using memset Date: Thu, 27 Jun 2024 11:39:53 +0100 Message-ID: <20240627105217.116315-2-jwakely@redhat.com> In-Reply-To: <20240627105217.116315-1-jwakely@redhat.com> References: <20240627105217.116315-1-jwakely@redhat.com> MIME-Version: 1.0 X-Scanned-By: MIMEDefang 3.4.1 on 10.30.177.4 X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com X-Spam-Status: No, score=-12.4 required=5.0 tests=BAYES_00, DKIMWL_WL_HIGH, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, RCVD_IN_DNSWL_NONE, RCVD_IN_MSPIKE_H4, RCVD_IN_MSPIKE_WL, SPF_HELO_NONE, SPF_NONE, TXREP 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.30 Precedence: list List-Id: Gcc-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org For trivial types std::__uninitialized_default (which is used by std::uninitialized_value_construct) value-initializes the first element then copies that to the rest of the range using std::fill. Tamar is working on improved vectorization for std::fill, but for this value-initialized case where we just want to fill with zeros it seems sensible to just ... fill with zeros. We can use memset to do that. Tested x86_64-linux. -- >8 -- The current optimized path for __uninitialized_default and __uninitialized_default_n will use std::fill for trivial types, but we can just use memset to fill them with zeros instead. Because these functions are not defined for C++98 at all, we can use if-constexpr to simplify them and remove the dispatching to members of class template specializations. libstdc++-v3/ChangeLog: * include/bits/stl_uninitialized.h (__uninitialized_default_1) (__uninitialized_default_n_1): Remove. (__uninitialized_default, __uninitialized_default_n): Use memset for contiguous ranges of trivial types. * testsuite/20_util/specialized_algorithms/uninitialized_value_construct_n/sizes.cc: Check negative size. --- libstdc++-v3/include/bits/stl_uninitialized.h | 159 ++++++++---------- .../uninitialized_value_construct_n/sizes.cc | 13 ++ 2 files changed, 87 insertions(+), 85 deletions(-) diff --git a/libstdc++-v3/include/bits/stl_uninitialized.h b/libstdc++-v3/include/bits/stl_uninitialized.h index a9965f26269..1216b319f66 100644 --- a/libstdc++-v3/include/bits/stl_uninitialized.h +++ b/libstdc++-v3/include/bits/stl_uninitialized.h @@ -61,6 +61,7 @@ #endif #include // copy +#include // __to_address #include // __alloc_traits #if __cplusplus >= 201703L @@ -590,89 +591,72 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION // Extensions: __uninitialized_default, __uninitialized_default_n, // __uninitialized_default_a, __uninitialized_default_n_a. - template - struct __uninitialized_default_1 - { - template - static void - __uninit_default(_ForwardIterator __first, _ForwardIterator __last) - { - _UninitDestroyGuard<_ForwardIterator> __guard(__first); - for (; __first != __last; ++__first) - std::_Construct(std::__addressof(*__first)); - __guard.release(); - } - }; +#pragma GCC diagnostic push +#pragma GCC diagnostic ignored "-Wc++17-extensions" - template<> - struct __uninitialized_default_1 + // If we can value-initialize *__first using memset then return + // std::to_address(__first), otherwise return nullptr. + template + _GLIBCXX20_CONSTEXPR + inline void* + __ptr_for_trivial_zero_init(_ForwardIterator __first) { - template - static void - __uninit_default(_ForwardIterator __first, _ForwardIterator __last) - { - if (__first == __last) - return; +#ifdef __cpp_lib_is_constant_evaluated + if (std::is_constant_evaluated()) + return nullptr; // Cannot memset during constant evaluation. +#endif - typename iterator_traits<_ForwardIterator>::value_type* __val - = std::__addressof(*__first); - std::_Construct(__val); - if (++__first != __last) - std::fill(__first, __last, *__val); - } - }; - - template - struct __uninitialized_default_n_1 - { - template - _GLIBCXX20_CONSTEXPR - static _ForwardIterator - __uninit_default_n(_ForwardIterator __first, _Size __n) - { - _UninitDestroyGuard<_ForwardIterator> __guard(__first); - for (; __n > 0; --__n, (void) ++__first) - std::_Construct(std::__addressof(*__first)); - __guard.release(); - return __first; - } - }; - - template<> - struct __uninitialized_default_n_1 - { - template - _GLIBCXX20_CONSTEXPR - static _ForwardIterator - __uninit_default_n(_ForwardIterator __first, _Size __n) - { - if (__n > 0) +#if __cpp_lib_concepts + if constexpr (!contiguous_iterator<_ForwardIterator>) + return nullptr; // Need a raw pointer for memset. +#else + if constexpr (!is_pointer<_ForwardIterator>::value) + return nullptr; +#endif + else + { + using _ValueType + = typename iterator_traits<_ForwardIterator>::value_type; + // Need value-init to be equivalent to zero-init. + using __value_init_is_zero_init + = __and_, + is_trivially_constructible<_ValueType>>; + if constexpr (__value_init_is_zero_init::value) { - typename iterator_traits<_ForwardIterator>::value_type* __val - = std::__addressof(*__first); - std::_Construct(__val); - ++__first; - __first = std::fill_n(__first, __n - 1, *__val); + using _Ptr = decltype(std::__to_address(__first)); + // Cannot use memset if _Ptr is cv-qualified. + if constexpr (is_convertible<_Ptr, void*>::value) + return std::__to_address(__first); } - return __first; } - }; + return nullptr; + } // __uninitialized_default // Fills [first, last) with value-initialized value_types. template inline void - __uninitialized_default(_ForwardIterator __first, - _ForwardIterator __last) + __uninitialized_default(_ForwardIterator __first, _ForwardIterator __last) { - typedef typename iterator_traits<_ForwardIterator>::value_type - _ValueType; - // trivial types can have deleted assignment - const bool __assignable = is_copy_assignable<_ValueType>::value; + if constexpr (__is_random_access_iter<_ForwardIterator>::__value) + if (void* __ptr = std::__ptr_for_trivial_zero_init(__first)) + { + using _ValueType + = typename iterator_traits<_ForwardIterator>::value_type; + if (auto __dist = __last - __first) + { + __glibcxx_assert(__dist > 0); + const size_t __n = __dist; + __glibcxx_assert(__n < __SIZE_MAX__ / sizeof(_ValueType)); + __builtin_memset(__ptr, 0, __n * sizeof(_ValueType)); + } + return; + } - std::__uninitialized_default_1<__is_trivial(_ValueType) - && __assignable>:: - __uninit_default(__first, __last); + _UninitDestroyGuard<_ForwardIterator> __guard(__first); + for (; __first != __last; ++__first) + std::_Construct(std::__addressof(*__first)); + __guard.release(); } // __uninitialized_default_n @@ -682,23 +666,28 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION inline _ForwardIterator __uninitialized_default_n(_ForwardIterator __first, _Size __n) { -#ifdef __cpp_lib_is_constant_evaluated - if (std::is_constant_evaluated()) - return __uninitialized_default_n_1:: - __uninit_default_n(__first, __n); -#endif + if constexpr (is_integral<_Size>::value) + if constexpr (__is_random_access_iter<_ForwardIterator>::__value) + if (void* __ptr = std::__ptr_for_trivial_zero_init(__first)) + { + using _ValueType + = typename iterator_traits<_ForwardIterator>::value_type; + if (__n <= 0) + return __first; + else if (size_t(__n) < __SIZE_MAX__ / sizeof(_ValueType)) + { + __builtin_memset(__ptr, 0, __n * sizeof(_ValueType)); + return __first + __n; + } + } - typedef typename iterator_traits<_ForwardIterator>::value_type - _ValueType; - // See uninitialized_fill_n for the conditions for using std::fill_n. - constexpr bool __can_fill - = __and_, is_copy_assignable<_ValueType>>::value; - - return __uninitialized_default_n_1<__is_trivial(_ValueType) - && __can_fill>:: - __uninit_default_n(__first, __n); + _UninitDestroyGuard<_ForwardIterator> __guard(__first); + for (; __n > 0; --__n, (void) ++__first) + std::_Construct(std::__addressof(*__first)); + __guard.release(); + return __first; } - +#pragma GCC diagnostic pop // __uninitialized_default_a // Fills [first, last) with value_types constructed by the allocator diff --git a/libstdc++-v3/testsuite/20_util/specialized_algorithms/uninitialized_value_construct_n/sizes.cc b/libstdc++-v3/testsuite/20_util/specialized_algorithms/uninitialized_value_construct_n/sizes.cc index 7705c6813e3..9c4198c1a98 100644 --- a/libstdc++-v3/testsuite/20_util/specialized_algorithms/uninitialized_value_construct_n/sizes.cc +++ b/libstdc++-v3/testsuite/20_util/specialized_algorithms/uninitialized_value_construct_n/sizes.cc @@ -52,9 +52,22 @@ test02() VERIFY( i[4] == 5 ); } +void +test03() +{ + int i[3] = { 1, 2, 3 }; + // The standard defines it in terms of a loop which only runs for positive n. + auto j = std::uninitialized_value_construct_n(i+1, -5); + VERIFY( j == i+1 ); + VERIFY( i[0] == 1 ); + VERIFY( i[1] == 2 ); + VERIFY( i[2] == 3 ); +} + int main() { test01(); test02(); + test03(); }