6 ms·

Evolving the Go Standard Library with math/rand/v2

156 points by spacey 2y ago

38 2y ago
If both are now crypto secure, what's the point of having both? Also seems like they've made math/rand slower, not a win in my book.
Smaug123 2y ago
Nice - I wish .NET would be more willing to condemn chunks of the standard library and replace them with something better!
- akira2501 2y ago
  That's precisely what I was thinking when I was reading this. The go module transition was not awesome, but if the result is being able to "step" the standard library forward like this without a corresponding major language release, then I take back all the bad things I ever said about it.
  - parhamn 2y ago
    What this have to do with go modules? Any standard lib should have the ability add a new builtin module under a different namespace regardless of how third-party packages of managed, right?
    - lowmagnet 2y ago
      The standard lib was considered core code and to make even the smallest change can have a huge impact. It was more a matter of, "if we're going to do a v2 language, what would we fix?" And, as it turns out this required no regression of existing core language code.
- oneepic 2y ago
  Not the same, but I wanted to say that when I was upgrading apps from .NET Framework to Core and above, I was surprised how many Framework packages not only had upgrades, but were deprecated entirely and replaced by a new package. We had a difficult time migrating. (This was at MSFT btw)
- tempest_ 2y ago
  Rust has rand in a separate crate which felt weird at first but makes sense for reasons like this thread.
  - josephg 2y ago
    Yeah. "Why should / shouldn't code be put in the standard library" is a really interesting question that I think people don't think about enough. I think a lot of the benefit of putting stuff in the standard library is interoperability. It seems obvious but - having a string and list type in std means you can pass strings and lists between packages. I think a lot of standard stuff that acts as "glue" should be in std. For example, in nodejs the standard library includes HTTP request and response types because of how useful they are in their ecosystem. Notably, unlike swift, rust doesn't have an "inlined string" type in std. There's a lot of crates that implement small strings, but most interfaces that need to pass an actual string buffer use std::String - and thats way less efficient. (Thankfully, &str is more common at interface boundaries). Rust also doesn't have much support for futures in std - which upsets a lot of people, because tokio ends up being included by a lot of programs. Anyway, when it comes to crates like rand where interoperability isn't important, I think its fine to keep this stuff out of std. Code can evolve much more easily when it lives as a 3rd party library.
- giancarlostoro 2y ago
  At least .NET is very capable of allowing you to support third party libraries. Heck, even ASP .NET Core isn't built-in anymore, you get it through NuGet. So you're not stuck with the standard libraries.
  - wiseowise 2y ago
    “Don’t you guys have internet?” What happened to batteries-included support?
    - giancarlostoro 2y ago
      ASP isnt included OOTB anymore, so if you want to do web dev in .NET you have to install it, they decoupled a ton of things from the core of the language.
      - neonsunset 2y ago
        You don’t get it through NuGet. You get it by specifying the sdk type in the project. https://learn.microsoft.com/en-us/dotnet/core/project-sdk/overview https://learn.microsoft.com/en-us/dotnet/core/project-sdk/ov...
        giancarlostoro 2y ago
        Used to be this way for .NET Core, I guess with modern .NET they changed it? https://www.nuget.org/profiles/aspnet https://www.nuget.org/profiles/aspnet Some projects listed were last updated in 2022.
      - metaltyphoon 2y ago
        ASP comes included in SDK. All you need is to specify in the csproj that you want a Web project
  - Smaug123 2y ago
    But when you're replacing, like, much of the standard library, you have to be a bit sad about all the interop work that falls on the user. It should instead fall on the makers of the bad standard library.
skitter 2y ago
Related, this article discusses difference generators and tradeoffs for Go using them as Source: https://zephyrtronium.github.io/articles/randomness.html https://zephyrtronium.github.io/articles/randomness.html
infogulch 2y ago
> In 2018, Daniel Lemire found an algorithm that avoids the divisions nearly all the time (see also his 2019 blog post). In math/rand, adopting Lemire’s algorithm would make Intn(1000) 20-30% faster... I recently found a super simple algorithm that appears to produce a number in the interval [0,N] with a branchless expression with a single multiplication in an extended number size. (Sorry I don't have a reference.) Say you want to generate a number, G, in interval [0,N] where N<=UInt32Max. The algorithm is: G = uint32( uint64(N)*uint64(rand.UInt32())>>32 ) It seems like this should select a number in the range with no bias. Is there something I missed?
- fanf2 2y ago
  Your algorithm is the first step of Lemire’s algorithm, without the followup check to debias the result. https://dotat.at/@/2020-10-29-nearly-divisionless-random-numbers.html https://dotat.at/@/2020-10-29-nearly-divisionless-random-num...
- baruz 2y ago
  Your results will be biased. It is tiny with small values of N, and absent when N is a power of two, but the skew becomes more obvious when your N is 2^31 + 2^30 + 1, for example.
- funny_falcon 2y ago
  Lemire uses your found but corrects its biases.
- Someone 2y ago
  > It seems like this should select a number in the range with no bias. Is there something I missed? Yes. There are many values of N that aren’t divisors of UInt32Max. As the article says: “However, no algorithm can convert 2⁶³ equally likely values into n equally likely values unless 2⁶³ is a multiple of n: otherwise some outputs will necessarily happen more often than others. (As a simpler example, try converting 4 equally likely values into 3.)”
  - infogulch 2y ago
infogulch 2y ago
I like the Principles section. Very measured and practical approach to releasing new stdlib packages. https://go.dev/blog/randv2#principles https://go.dev/blog/randv2#principles The end of the post they mention that an encoding/json/v2 package is in the works: https://github.com/golang/go/discussions/63397 https://github.com/golang/go/discussions/63397
- physicles 2y ago
  > Second, all changes must be rooted in respect for existing usage and users This is one of the reasons I love working in Go. I feel that the language maintainers understand that people using Go have more important work to do than update their code to whatever the new hotness is this month. Basically the opposite of this: https://steve-yegge.medium.com/dear-google-cloud-your-deprecation-policy-is-killing-you-ee7525dc05dc https://steve-yegge.medium.com/dear-google-cloud-your-deprec...
  - pjmlp 2y ago
    A long tradition in the Java, C and C++ ecosystems.
lifthrasiir 2y ago
> Ideally, the v2 package should be able to do everything the v1 package could do, and when v2 is released, the v1 package should be rewritten to be a thin wrapper around v2. And even more ideally, as many v1 usages should be automatically fixed as possible by `go fix` or similar tools. Allowing this to all user packages would be a major improvement over the status quo.
- rsc 2y ago
  > Allowing this to all user packages would be a major improvement over the status quo. We have plans to get there. https://github.com/golang/go/issues/32816 https://github.com/golang/go/issues/32816
rollulus 2y ago
As often I’m impressed by the quality of all of this. The amount of thinking that went into this, this excellent written blog post. I love the Go blog.
- JetSetIlly 2y ago
  Agreed. I admire the clarity of Cox's writing, as much as his thoughtful restraint on adding new features to the language.
  - dekhn 2y ago
    Rob Pike called Russ Cox "future winner of the Kyoto prize". My favorite is https://research.swtch.com/qart https://research.swtch.com/qart (see also: https://spinroot.com/pico/pjw.html https://spinroot.com/pico/pjw.html)

156 points by spacey 2y ago

38 2y ago

If both are now crypto secure, what's the point of having both? Also seems like they've made math/rand slower, not a win in my book.

Smaug123 2y ago

Nice - I wish .NET would be more willing to condemn chunks of the standard library and replace them with something better!

akira2501 2y ago
That's precisely what I was thinking when I was reading this. The go module transition was not awesome, but if the result is being able to "step" the standard library forward like this without a corresponding major language release, then I take back all the bad things I ever said about it.
- parhamn 2y ago
  What this have to do with go modules? Any standard lib should have the ability add a new builtin module under a different namespace regardless of how third-party packages of managed, right?
  - lowmagnet 2y ago
    The standard lib was considered core code and to make even the smallest change can have a huge impact. It was more a matter of, "if we're going to do a v2 language, what would we fix?" And, as it turns out this required no regression of existing core language code.
oneepic 2y ago
Not the same, but I wanted to say that when I was upgrading apps from .NET Framework to Core and above, I was surprised how many Framework packages not only had upgrades, but were deprecated entirely and replaced by a new package. We had a difficult time migrating. (This was at MSFT btw)
tempest_ 2y ago
Rust has rand in a separate crate which felt weird at first but makes sense for reasons like this thread.
- josephg 2y ago
  Yeah. "Why should / shouldn't code be put in the standard library" is a really interesting question that I think people don't think about enough. I think a lot of the benefit of putting stuff in the standard library is interoperability. It seems obvious but - having a string and list type in std means you can pass strings and lists between packages. I think a lot of standard stuff that acts as "glue" should be in std. For example, in nodejs the standard library includes HTTP request and response types because of how useful they are in their ecosystem. Notably, unlike swift, rust doesn't have an "inlined string" type in std. There's a lot of crates that implement small strings, but most interfaces that need to pass an actual string buffer use std::String - and thats way less efficient. (Thankfully, &str is more common at interface boundaries). Rust also doesn't have much support for futures in std - which upsets a lot of people, because tokio ends up being included by a lot of programs. Anyway, when it comes to crates like rand where interoperability isn't important, I think its fine to keep this stuff out of std. Code can evolve much more easily when it lives as a 3rd party library.
giancarlostoro 2y ago
At least .NET is very capable of allowing you to support third party libraries. Heck, even ASP .NET Core isn't built-in anymore, you get it through NuGet. So you're not stuck with the standard libraries.
- wiseowise 2y ago
  “Don’t you guys have internet?” What happened to batteries-included support?
  - giancarlostoro 2y ago
    ASP isnt included OOTB anymore, so if you want to do web dev in .NET you have to install it, they decoupled a ton of things from the core of the language.
    - neonsunset 2y ago
      You don’t get it through NuGet. You get it by specifying the sdk type in the project. https://learn.microsoft.com/en-us/dotnet/core/project-sdk/overview https://learn.microsoft.com/en-us/dotnet/core/project-sdk/ov...
      - giancarlostoro 2y ago
        Used to be this way for .NET Core, I guess with modern .NET they changed it? https://www.nuget.org/profiles/aspnet https://www.nuget.org/profiles/aspnet Some projects listed were last updated in 2022.
    - metaltyphoon 2y ago
      ASP comes included in SDK. All you need is to specify in the csproj that you want a Web project
- Smaug123 2y ago
  But when you're replacing, like, much of the standard library, you have to be a bit sad about all the interop work that falls on the user. It should instead fall on the makers of the bad standard library.

skitter 2y ago

Related, this article discusses difference generators and tradeoffs for Go using them as Source: https://zephyrtronium.github.io/articles/randomness.html https://zephyrtronium.github.io/articles/randomness.html

infogulch 2y ago

> In 2018, Daniel Lemire found an algorithm that avoids the divisions nearly all the time (see also his 2019 blog post). In math/rand, adopting Lemire’s algorithm would make Intn(1000) 20-30% faster... I recently found a super simple algorithm that appears to produce a number in the interval [0,N] with a branchless expression with a single multiplication in an extended number size. (Sorry I don't have a reference.) Say you want to generate a number, G, in interval [0,N] where N<=UInt32Max. The algorithm is: G = uint32( uint64(N)*uint64(rand.UInt32())>>32 ) It seems like this should select a number in the range with no bias. Is there something I missed?

fanf2 2y ago
Your algorithm is the first step of Lemire’s algorithm, without the followup check to debias the result. https://dotat.at/@/2020-10-29-nearly-divisionless-random-numbers.html https://dotat.at/@/2020-10-29-nearly-divisionless-random-num...
baruz 2y ago
Your results will be biased. It is tiny with small values of N, and absent when N is a power of two, but the skew becomes more obvious when your N is 2^31 + 2^30 + 1, for example.
funny_falcon 2y ago
Lemire uses your found but corrects its biases.
Someone 2y ago
> It seems like this should select a number in the range with no bias. Is there something I missed? Yes. There are many values of N that aren’t divisors of UInt32Max. As the article says: “However, no algorithm can convert 2⁶³ equally likely values into n equally likely values unless 2⁶³ is a multiple of n: otherwise some outputs will necessarily happen more often than others. (As a simpler example, try converting 4 equally likely values into 3.)”
- infogulch 2y ago

infogulch 2y ago

I like the Principles section. Very measured and practical approach to releasing new stdlib packages. https://go.dev/blog/randv2#principles https://go.dev/blog/randv2#principles The end of the post they mention that an encoding/json/v2 package is in the works: https://github.com/golang/go/discussions/63397 https://github.com/golang/go/discussions/63397

physicles 2y ago
> Second, all changes must be rooted in respect for existing usage and users This is one of the reasons I love working in Go. I feel that the language maintainers understand that people using Go have more important work to do than update their code to whatever the new hotness is this month. Basically the opposite of this: https://steve-yegge.medium.com/dear-google-cloud-your-deprecation-policy-is-killing-you-ee7525dc05dc https://steve-yegge.medium.com/dear-google-cloud-your-deprec...
- pjmlp 2y ago
  A long tradition in the Java, C and C++ ecosystems.

lifthrasiir 2y ago

> Ideally, the v2 package should be able to do everything the v1 package could do, and when v2 is released, the v1 package should be rewritten to be a thin wrapper around v2. And even more ideally, as many v1 usages should be automatically fixed as possible by `go fix` or similar tools. Allowing this to all user packages would be a major improvement over the status quo.

rsc 2y ago
> Allowing this to all user packages would be a major improvement over the status quo. We have plans to get there. https://github.com/golang/go/issues/32816 https://github.com/golang/go/issues/32816

rollulus 2y ago

As often I’m impressed by the quality of all of this. The amount of thinking that went into this, this excellent written blog post. I love the Go blog.

JetSetIlly 2y ago
Agreed. I admire the clarity of Cox's writing, as much as his thoughtful restraint on adding new features to the language.
- dekhn 2y ago
  Rob Pike called Russ Cox "future winner of the Kyoto prize". My favorite is https://research.swtch.com/qart https://research.swtch.com/qart (see also: https://spinroot.com/pico/pjw.html https://spinroot.com/pico/pjw.html)