From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: <9front-bounces@9front.inri.net> X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on inbox.vuxu.org X-Spam-Level: X-Spam-Status: No, score=-0.6 required=5.0 tests=DKIM_INVALID,DKIM_SIGNED, HEADER_FROM_DIFFERENT_DOMAINS,MAILING_LIST_MULTI autolearn=ham autolearn_force=no version=3.4.4 Received: from 9front.inri.net (9front.inri.net [168.235.81.73]) by inbox.vuxu.org (Postfix) with ESMTP id 4065F229A4 for ; Fri, 29 Mar 2024 13:40:27 +0100 (CET) Received: from wopr.sciops.net ([216.126.196.60]) by 9front; Fri Mar 29 08:39:09 -0400 2024 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=sciops.net; s=20210706; t=1711715923; 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; bh=2Bn8qBkDQ4LqbfCQpmeMX/ehx7D9wMsUUBfzQZPPgZI=; b=CP50n9+N6pmAMFDYkHpTUt4zY1j6zEJOgpRqzz7up3yMfHxu4DHAfYLD8dfT3WaIt0PydF 0AvS6LaO+ftrZOBZgMckspN2jDl5ekjOvcJsT/VwPK4XHtz0faSS7eT+QEtVLaD6gdGbIJ kQ9k4eJPU2iIofTwhGHX2gwswNB5UOQ= Received: by wopr.sciops.net (OpenSMTPD) with ESMTPSA id a8f7d262 (TLSv1.2:ECDHE-RSA-CHACHA20-POLY1305:256:NO) for <9front@9front.org>; Fri, 29 Mar 2024 05:38:42 -0700 (PDT) Message-ID: <505C905934B3CDB74EC21F69ADF03150@wopr.sciops.net> Date: Fri, 29 Mar 2024 13:39:03 +0100 From: qwx@sciops.net To: 9front@9front.org In-Reply-To: <3LHKTP1HB4DYE.2X5KUF9RIVGEC@e55-lap.my.domain> MIME-Version: 1.0 Content-Type: text/plain; charset="US-ASCII" Content-Transfer-Encoding: 7bit List-ID: <9front.9front.org> List-Help: X-Glyph: ➈ X-Bullshit: framework XMPP over HTTP CSS CMS-oriented layer Subject: Re: [9front] [PATCH] libc: replace lrand's algorithm Reply-To: 9front@9front.org Precedence: bulk On Fri Mar 29 09:19:39 +0100 2024, eolien55@disroot.org wrote: > Hello, > > The current lrand's algorithm is quite suboptimal. > After benchmarking, we find: > Current algorithm: > repeated srand with different values: 820.740000 > repeated lrand: 643.880000 > > Proposed algorithm (PCG32-XSH-RR[1]): > repeated srand with different valudes: 1.920000 > repeated lrand: 600.590000 Hello, I'm a bit puzzled by both the results and the implementation. If I look at the site you point to, the download page [1] has this snippet: typedef struct { uint64_t state; uint64_t inc; } pcg32_random_t; uint32_t pcg32_random_r(pcg32_random_t* rng) { uint64_t oldstate = rng->state; // Advance internal state rng->state = oldstate * 6364136223846793005ULL + (rng->inc|1); // Calculate output function (XSH RR), uses old state for max ILP uint32_t xorshifted = ((oldstate >> 18u) ^ oldstate) >> 27u; uint32_t rot = oldstate >> 59u; return (xorshifted >> rot) | (xorshifted << ((-rot) & 31)); } Here `state' is 64-bit, whereas in your code, it's a ulong, ie. 32-bit, which seems to break everything. Furthermore, your code seems to have flipped part of the last statement and return the equivalent of: return (xorshifted >> ((-rot) & 31)) | (xorshifted << rot); Is that intentional? Moreover, for the benchmark itself, while seeding is significantly faster, actually calling lrand barely is; the new code is only 1.07x faster than the old. The scale is also minuscule, around 42 seconds for circa 4.3 billion calls (you're looping on a signed long from 0 to -1). Am I misreading? lrand is used by rand(2) itself and is used throughout the system and elsewhere, and who knows what impact changing it might have. Applications which need guarantees about distribution or performance are not supposed to use rand(2) to begin with. Therefore, these numbers alone do not justify, in my opinion, replacing the current implementation. Cheers, qwx [1] https://www.pcg-random.org/download.html