From mboxrd@z Thu Jan  1 00:00:00 1970
Return-Path: <gcc-patches-return-426453-listarch-gcc-patches=gcc.gnu.org@gcc.gnu.org>
Received: (qmail 43075 invoked by alias); 3 May 2016 12:39:08 -0000
Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm
Precedence: bulk
List-Id: <gcc-patches.gcc.gnu.org>
List-Archive: <http://gcc.gnu.org/ml/gcc-patches/>
List-Post: <mailto:gcc-patches@gcc.gnu.org>
List-Help: <mailto:gcc-patches-help@gcc.gnu.org>
Sender: gcc-patches-owner@gcc.gnu.org
Received: (qmail 42439 invoked by uid 89); 3 May 2016 12:39:07 -0000
Authentication-Results: sourceware.org; auth=none
X-Virus-Found: No
X-Spam-SWARE-Status: No, score=-1.6 required=5.0 tests=AWL,BAYES_00,FREEMAIL_FROM,RCVD_IN_DNSWL_NONE,SPF_PASS autolearn=ham version=3.3.2 spammy=positions, Hx-languages-length:794
X-Spam-User: qpsmtpd, 2 recipients
X-HELO: mail-yw0-f181.google.com
Received: from mail-yw0-f181.google.com (HELO mail-yw0-f181.google.com) (209.85.161.181) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with (AES128-GCM-SHA256 encrypted) ESMTPS; Tue, 03 May 2016 12:38:57 +0000
Received: by mail-yw0-f181.google.com with SMTP id t10so18621216ywa.0;        Tue, 03 May 2016 05:38:56 -0700 (PDT)
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;        d=1e100.net; s=20130820;        h=x-gm-message-state:mime-version:in-reply-to:references:date         :message-id:subject:from:to:cc;        bh=Oyhk+zkJFKU4HaqNy5jPgi6jyW2WJr3pI54Nwl89CgA=;        b=XWLglOeuzReA+n5vxNnW0dx7ayZOwnQ/wEkDWCYUfClgb9nRpTB20HcN8u4xU2gu/h         eUMaOlVNd/kDyPAZEIbDgYZEudMOUIg+h6odyhkQs+JuZ+oTDaarA9ZYnM6QoIVcCpz/         /l6ZMk6teU1Sph4uH3V6erXeZqSRguydgwzOf6UZySPAKgW9jq7EIL+Uj6XfgckLw9s0         2QdjUpFIAnmC4R4/3ixUhOW5VJftp26oSjOjqGrVEkOWVeui4YAf9XsiaczLrFTYty1+         iVbLrNqkKH6unMfv9QTCAxVV+9oXLGH6IjCF2wtw6RIG2Q6vGGEk+lbnPnTQgHgIXWBU         1PGQ==
X-Gm-Message-State: AOPr4FVnwMOHS9npG+cgXizGlWGw4R6emUG+b3Dw4SDCFqF8DTBZRI2OMjdqoyOdOJBq08ZHx0Q6FELNER8xZQ==
MIME-Version: 1.0
X-Received: by 10.129.154.79 with SMTP id r76mr1082941ywg.86.1462279135165; Tue, 03 May 2016 05:38:55 -0700 (PDT)
Received: by 10.37.198.131 with HTTP; Tue, 3 May 2016 05:38:55 -0700 (PDT)
In-Reply-To: <ng53cl$4iu$2@ger.gmane.org>
References: <ng536o$4iu$1@ger.gmane.org>	<ng53cl$4iu$2@ger.gmane.org>
Date: Tue, 03 May 2016 12:39:00 -0000
Message-ID: <CAH6eHdTnASg7A5USA_sTAHXPfUFmkrZvF27tZUJhj5ywwDVDag@mail.gmail.com>
Subject: Re: [patch, libstdc++] std::shuffle: Generate two swap positions at a time if possible
From: Jonathan Wakely <jwakely.gcc@gmail.com>
To: Eelis <eelis@eelis.net>
Cc: "libstdc++" <libstdc++@gcc.gnu.org>, gcc-patches <gcc-patches@gcc.gnu.org>
Content-Type: text/plain; charset=UTF-8
X-SW-Source: 2016-05/txt/msg00202.txt.bz2

ENOPATCH

On 1 May 2016 at 15:21, Eelis <eelis@eelis.net> wrote:
> Sorry, forgot to include the libstdc++ list.
>
> On 2016-05-01 16:18, Eelis wrote:
>>
>> Hi,
>>
>> The attached patch optimizes std::shuffle for the very common case
>> where the generator range is large enough that a single invocation
>> can produce two swap positions.
>>
>> This reduces the runtime of the following testcase by 37% on my machine:
>>
>>      int main()
>>      {
>>          std::mt19937 gen;
>>
>>          std::vector<int> v;
>>          v.reserve(10000);
>>          for (int i = 0; i != 10000; ++i)
>>          {
>>              v.push_back(i);
>>              std::shuffle(v.begin(), v.end(), gen);
>>          }
>>
>>          std::cout << v.front() << '\n';
>>      }
>>
>> Thoughts?
>>
>> Thanks,
>>
>> Eelis
>>
>
>