From issues-return-73160-archive-asf-public=cust-asf.ponee.io@commons.apache.org Tue Apr 2 11:51:06 2019 Return-Path: X-Original-To: archive-asf-public@cust-asf.ponee.io Delivered-To: archive-asf-public@cust-asf.ponee.io Received: from mail.apache.org (hermes.apache.org [140.211.11.3]) by mx-eu-01.ponee.io (Postfix) with SMTP id 689CF180668 for ; Tue, 2 Apr 2019 13:51:06 +0200 (CEST) Received: (qmail 49198 invoked by uid 500); 2 Apr 2019 11:51:05 -0000 Mailing-List: contact issues-help@commons.apache.org; run by ezmlm Precedence: bulk List-Help: List-Unsubscribe: List-Post: List-Id: Reply-To: issues@commons.apache.org Delivered-To: mailing list issues@commons.apache.org Received: (qmail 49187 invoked by uid 99); 2 Apr 2019 11:51:05 -0000 Received: from mailrelay1-us-west.apache.org (HELO mailrelay1-us-west.apache.org) (209.188.14.139) by apache.org (qpsmtpd/0.29) with ESMTP; Tue, 02 Apr 2019 11:51:05 +0000 Received: from jira-lw-us.apache.org (unknown [207.244.88.139]) by mailrelay1-us-west.apache.org (ASF Mail Server at mailrelay1-us-west.apache.org) with ESMTP id A7DA3E00CC for ; Tue, 2 Apr 2019 11:51:04 +0000 (UTC) Received: from jira-lw-us.apache.org (localhost [127.0.0.1]) by jira-lw-us.apache.org (ASF Mail Server at jira-lw-us.apache.org) with ESMTP id 5652F24422 for ; Tue, 2 Apr 2019 11:51:04 +0000 (UTC) Date: Tue, 2 Apr 2019 11:51:04 +0000 (UTC) From: "Alex D Herbert (JIRA)" To: issues@commons.apache.org Message-ID: In-Reply-To: References: Subject: [jira] [Resolved] (RNG-87) MultiplyWithCarry256 MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: quoted-printable X-JIRA-FingerPrint: 30527f35849b9dde25b450d4833f0394 [ https://issues.apache.org/jira/browse/RNG-87?page=3Dcom.atlassian.ji= ra.plugin.system.issuetabpanels:all-tabpanel ] Alex D Herbert resolved RNG-87. ------------------------------- Resolution: Implemented In master. > MultiplyWithCarry256 > -------------------- > > Key: RNG-87 > URL: https://issues.apache.org/jira/browse/RNG-87 > Project: Commons RNG > Issue Type: Improvement > Components: core > Affects Versions: 1.3 > Reporter: Alex D Herbert > Assignee: Alex D Herbert > Priority: Minor > Labels: performance > Attachments: MWC_256.jpg, MWC_256_2.jpg, MWC_256_3.jpg, MWC_256_3= .png, Shuffle.jpg, big.jpg, small.jpg > > Time Spent: 50m > Remaining Estimate: 0h > > The {{MultiplyWithCarry256}}=C2=A0currently uses a length 256 array for i= nternal state. This is cycled through continuously. The current implementat= ion refills the state every 256 calls to next: > {code:java} > public int next() { > if (index =3D=3D Q_SIZE) { // Whole state used up. > // Refill. > for (int i =3D 0; i < Q_SIZE; i++) { > final long t =3D A * (state[i] & 0xffffffffL) + carry; > carry =3D (int) (t >> 32); > state[i] =3D (int) t; > } > // Reset current index. > index =3D 0; > } > return state[index++]; > } > {code} > This can be changed to continuously update the state for only a single in= dex on each call to next: > {code:java} > public int next() { > // Produce an index in the range 0-255 > final int i =3D index++ & 0xFF; > final long t =3D A * (state[i] & 0xffffffffL) + carry; > carry =3D (int) (t >> 32); > return state[i] =3D (int) t; > } > {code} > This avoids an {{if}} statement check and *marginally* improves performan= ce. It has the advantage of not advancing the state further ahead than nece= ssary. > MWC_256B is the new version. JMH results from the GenerationPerformance b= enchmark. > {noformat} > openjdk version "1.8.0_191" > OpenJDK Runtime Environment (build 1.8.0_191-8u191-b12-2ubuntu0.16.04.1-b= 12) > OpenJDK 64-Bit Server VM (build 25.191-b12, mixed mode) > {noformat} > ||numValues||randomSourceName||Method||Score||Error||Median|| > |1|SPLIT_MIX_64|nextInt|0.00478|4.45e-05|0.00477| > |1|MWC_256|nextInt|0.00521|1.69e-05|0.00521| > |1|MWC_256B|nextInt|0.00519|0.000321|0.00512| > |100|SPLIT_MIX_64|nextInt|0.421|0.0131|0.418| > |100|MWC_256|nextInt|0.452|0.000968|0.452| > |100|MWC_256B|nextInt|0.443|0.00183|0.442| > |10000|SPLIT_MIX_64|nextInt|41.7|0.0725|41.7| > |10000|MWC_256|nextInt|44.5|2.25|43.9| > |10000|MWC_256B|nextInt|42.6|0.037|42.6| > |1000000|SPLIT_MIX_64|nextInt|3.77e+03|21.2|3.77e+03| > |1000000|MWC_256|nextInt|4.16e+03|12.8|4.16e+03| > |1000000|MWC_256B|nextInt|3.98e+03|120|3.96e+03| > {noformat} > java version "11.0.2" 2019-01-15 LTS > Java(TM) SE Runtime Environment 18.9 (build 11.0.2+9-LTS) > Java HotSpot(TM) 64-Bit Server VM 18.9 (build 11.0.2+9-LTS, mixed mode) > {noformat} > ||numValues||randomSourceName||Method||Score||Error||Median|| > |1|SPLIT_MIX_64|nextInt|0.00469|4.98e-06|0.00469| > |1|MWC_256|nextInt|0.00553|2.09e-05|0.00553| > |1|MWC_256B|nextInt|0.00493|4.32e-05|0.00492| > |100|SPLIT_MIX_64|nextInt|0.435|0.000624|0.435| > |100|MWC_256|nextInt|0.467|0.00284|0.466| > |100|MWC_256B|nextInt|0.455|0.00105|0.455| > |10000|SPLIT_MIX_64|nextInt|43|4.94|41.9| > |10000|MWC_256|nextInt|45.8|0.132|45.8| > |10000|MWC_256B|nextInt|43|0.033|43| > |1000000|SPLIT_MIX_64|nextInt|3.7e+03|7.88|3.7e+03| > |1000000|MWC_256|nextInt|4.17e+03|45.3|4.15e+03| > |1000000|MWC_256B|nextInt|4.12e+03|4.76|4.12e+03| -- This message was sent by Atlassian JIRA (v7.6.3#76005)