From patchwork Tue Aug 17 08:41:08 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Antony Polukhin X-Patchwork-Id: 1517638 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Authentication-Results: ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=gcc.gnu.org (client-ip=2620:52:3:1:0:246e:9693:128c; helo=sourceware.org; envelope-from=gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=) Authentication-Results: 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=G5mEKJVe; dkim-atps=neutral Received: from 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 RSA-PSS (4096 bits) server-digest SHA256) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id 4GpkzF6fhmz9sT6 for ; Tue, 17 Aug 2021 18:41:44 +1000 (AEST) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 391C13835C0A for ; Tue, 17 Aug 2021 08:41:42 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 391C13835C0A DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1629189702; bh=IqwdSKeZjHGaRk0WjUSeCD0DJBsr0gVU8zESicBA/vY=; h=Date:Subject:To:List-Id:List-Unsubscribe:List-Archive:List-Post: List-Help:List-Subscribe:From:Reply-To:From; b=G5mEKJVey/s1mVsKO3X5oDWr3tx9T6sS1/8hSIQCYZprs6yCPft1DTo+b2lj5SH2U AAG1KhWzhRKRxOeCXk/vdZ0SHd0HRAIOMxbd704ZYFO88lPaDn+bocgREoqSnFOliA TpbjtXvs/jEBZhN9Ppxj8hht7e01/1t/pHS0qkJg= X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from mail-qt1-x82e.google.com (mail-qt1-x82e.google.com [IPv6:2607:f8b0:4864:20::82e]) by sourceware.org (Postfix) with ESMTPS id 3C3643871018; Tue, 17 Aug 2021 08:41:20 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 3C3643871018 Received: by mail-qt1-x82e.google.com with SMTP id y9so16490671qtv.7; Tue, 17 Aug 2021 01:41:20 -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:from:date:message-id:subject:to; bh=IqwdSKeZjHGaRk0WjUSeCD0DJBsr0gVU8zESicBA/vY=; b=B3ZqV1QATKuqALTLnTlUm4RMf31BV5GzY1cgpTxcZ0UCMOB6AsKmpyUsqZ2AXhA8d6 VyYAHjncGDwDuq2jswwScqYW0QcLMp3mbklnNofxkcsGcSF2rQy34Zega4NiSzksuS51 I4/nzEwzTArs+wrVLnO4PatNgv8fgOOnqEd0fxVie0sgvnwX9JRM/h6FbK/k98a5pdFU 8+8kJbE1MZBMVBuxq/NcPqQ+PyEW9ldBjZIrRXIBYkvXFYAhajTJou9AJtWnOWc/1nSO T8guNY/32gM4CuFED88L/VYwN/dY3wNUGO1wMzNSdzl6ZJ67Pv2uZykYb2ygO5jd8TEE yxCw== X-Gm-Message-State: AOAM533zZjRgcXLk1jnjEoEPWKpypUUQXEaoMGrwOWsYpPBNPW4poQ2p 8PBKO+KYg7ZCm2l//nL2kwQiSy/nENW6ZmH1sw0anOHkJb0= X-Google-Smtp-Source: ABdhPJwIYHefgdFRAvYzyEn+gzbxSSIdYntnLpqeml6bIPoPZwqLiaiwbKzQFQf6L6Fg46YZwaCjzlJBD1nXUcVIiPc= X-Received: by 2002:a05:622a:14d3:: with SMTP id u19mr2057893qtx.258.1629189679702; Tue, 17 Aug 2021 01:41:19 -0700 (PDT) MIME-Version: 1.0 Date: Tue, 17 Aug 2021 11:41:08 +0300 Message-ID: Subject: [PATCH] Optimize seed_seq construction To: "libstdc++" , gcc-patches List X-Spam-Status: No, score=-9.7 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, FREEMAIL_FROM, GIT_PATCH_0, RCVD_IN_DNSWL_NONE, SPF_HELO_NONE, SPF_PASS, TXREP autolearn=ham autolearn_force=no version=3.4.4 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) 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: Antony Polukhin via Gcc-patches From: Antony Polukhin Reply-To: Antony Polukhin Errors-To: gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org Sender: "Gcc-patches" When std::seed_seq is constructed from random access iterators we can detect the internal vector size in O(1). Reserving memory for elements in such cases may avoid multiple memory allocations. libstdc++-v3/ChangeLog: * include/bits/random.tcc: Optimize seed_seq construction. diff --git a/libstdc++-v3/include/bits/random.tcc b/libstdc++-v3/include/bits/random.tcc index bf43970..816bfc1 100644 --- a/libstdc++-v3/include/bits/random.tcc +++ b/libstdc++-v3/include/bits/random.tcc @@ -3234,14 +3234,31 @@ namespace __detail template seed_seq::seed_seq(std::initializer_list<_IntType> __il) { + _M_v.reserve(__il.size()); for (auto __iter = __il.begin(); __iter != __il.end(); ++__iter) _M_v.push_back(__detail::__mod::__value>(*__iter)); } + template + void __reserve_if_distance_cheap(_Vector& __vec, _InputIterator __begin, + _InputIterator __end, random_access_iterator_tag) + { + __vec.reserve(__end - __begin); + } + + template + void __reserve_if_distance_cheap(_Vector&, _InputIterator, + _InputIterator, _Tag) + { + // computing the distance between __begin and __end is not O(1) + } + template seed_seq::seed_seq(_InputIterator __begin, _InputIterator __end) { + std::__reserve_if_distance_cheap(_M_v, __begin, __end, + typename iterator_traits<_InputIterator>::iterator_category()); for (_InputIterator __iter = __begin; __iter != __end; ++__iter) _M_v.push_back(__detail::__mod::__value>(*__iter));