Optimise Rng::gen on arrays?

I noticed that Rng::gen and Rng::fill don't do the same thing on arrays and have different results when the element size is small:

rng.gen() essentially does [rng.gen(), rng.gen(), ..., rng.gen()]
rng.fill(&mut buf) casts buf to &mut [u8] then uses RngCore::fill_bytes — more efficient, and only implemented for integer arrays/slices

We likely want to keep the current behaviour for rng.gen() when the element type is f32/f64/complex types, but for integer types can we optimise to use fill_bytes?

Perhaps fill and try_fill should only work on byte slices and other arrays can just use distributions?

Perhaps fill and try_fill should only work on byte slices and other arrays can just use distributions?

That is how they work right now 😄.

This issue asks the question if we can/should optimise the rng.gen() implementation for integer arrays to also use fill like it is a slice.

Actually fill also works on integer slices/arrays; it's fill_bytes which is restricted to byte slices.

The point is that you can write let x: [u32; 32] = rng.gen(); in the current rand, but it would be much faster to write the following (and also have different result, but statistically equivalent):

let mut x = [0u32; 32];
rng.fill(&mut x);

Well, the current gen() (aka Standard) implementation for arrays is actually very fast:

test gen_1k_fill                     ... bench:         377 ns/iter (+/- 16) = 2716 MB/s
test gen_1k_gen_array                ... bench:         261 ns/iter (+/- 5) = 3923 MB/s
test gen_1k_gen_iter                 ... bench:         633 ns/iter (+/- 20) = 1617 MB/s
test gen_1k_iter_repeat              ... bench:         383 ns/iter (+/- 11) = 2673 MB/s
test gen_1k_sample_iter              ... bench:         390 ns/iter (+/- 8) = 2625 MB/s

... for u64 elements, at least.

I found a way to make gen() use fill on arrays:

// Specialized implementation:
impl<T> Distribution<T> for Standard where T: AsByteSliceMut+Default {
    #[inline]
    fn sample<R: Rng + ?Sized>(&self, _rng: &mut R) -> T {
        let mut result: T = Default::default();
        _rng.fill(&mut result);
        result
    }
}

The problems are (1) that it conflicts with other implementations (even using #![feature(specialization)] on nightly, all versions I've tried appear to conflict), and (2) that for u64 at least this version actually hurts performance.

If we can sort out the specialisation (when Rust supports it on stable, or alternatively negative trait bounds), and we restrict to small types (u8, i8, probably also u16 and i16), then this may work:

// within array_impl macro:
        // Specialized implementation:
        impl<u8> Distribution<[u8; $n]> for Standard where [u8; $n]: AsByteSliceMut+Default {
            #[inline]
            fn sample<R: Rng + ?Sized>(&self, _rng: &mut R) -> [u8; $n] {
                let mut result: [u8; $n] = Default::default();
                _rng.fill(&mut result);
                result
            }
        }

For now, I believe the best option is to do nothing (we can actually implement this instead of the generic Distribution<[T; $n]> support, but of course that restricts users since any array type not specifically implemented will cease to be supported — e.g. currently [[u64; 32]; 4] is supported).

I propose we close this with documentation only (provided in #812) since although using specialisation as above might be possible in the future, value-stability is important and this specialisation would yield different values for many types (with actual behaviour depending on the RNG).

It appears that specialization will not be available in the near future: tracking issue. Would we want to make a value-breaking change when it becomes available?

Also, any such implementation would have to make a fixed choice about which types to use the fill "optimisation" for, while the fastest method may depend on RNG and platform.

This might be a better option:

diff --git a/src/distributions/other.rs b/src/distributions/other.rs
index 2295f79..883b332 100644
--- a/src/distributions/other.rs
+++ b/src/distributions/other.rs
@@ -137,10 +137,13 @@ macro_rules! array_impl {
     {$n:expr, $t:ident, $($ts:ident,)*} => {
         array_impl!{($n - 1), $($ts,)*}
 
-        impl<T> Distribution<[T; $n]> for Standard where Standard: Distribution<T> {
+        impl<T> Distribution<[T; $n]> for Standard
+        where Standard: Distribution<T>, [T]: crate::AsByteSliceMut, T: Default {
             #[inline]
-            fn sample<R: Rng + ?Sized>(&self, _rng: &mut R) -> [T; $n] {
-                [_rng.gen::<$t>(), $(_rng.gen::<$ts>()),*]
+            fn sample<R: Rng + ?Sized>(&self, rng: &mut R) -> [T; $n] {
+                let mut a = Default::default();
+                rng.fill(&mut a);
+                a
             }
         }
     };

The Distribution<T> requirement is not needed, but it avoids implementing the trait for potentially unwanted types. This does not work for [[u64; 32]; 4], but arguably that is not very important and could be fixed by implementing AsByteSliceMut for nested arrays.

Of course, this is still a regression for types that don't implement AsByteSliceMut.

This doesn't work for many types, e.g. [f32; 3]. Is byte-buffer gen performance more important than being able to generate arrays of other types?

Fair enough. However, it would be nice if fill could support floats. I think it is fine to close this issue, following your argumentation in #269 (comment).

Perhaps we got the design of AsByteSliceMut wrong), and instead we should have:

pub trait Fill {
    fn try_fill<R: Rng + ?Sized>(&mut self, rng: &mut R) -> Result<(), Error>;
}

With that, we could implement support for float slices; also we could support gen for any type supporting Fill + Default (so long as we avoided overlapping implementations) which would allow this optimisation and make arr = rng.gen() and rng.fill(&mut arr) value-equivalent on arrays.

Possibly this was not done because fill_bytes and try_fill_bytes are not guaranteed to be semantically equivalent, so correct implementation of both would require two implementations (at least, for everything using byte filling internally). Now that we have a simpler Error type it is hard to see try_fill_bytes(buf).unwrap() being different to fill_bytes(buf), although technically it's still possible.

I agree that Fill seems like the better abstraction. Maybe it's better to do that for 0.8 though.

I would not worry too much about fill_bytes vs. try_fill_bytes, we have similar problems with next_u32 and next_u64.

Fill is now implemented and documented, including support for floats.

Navigation Menu

Repository navigation

Optimise `Rng::gen` on arrays? #269

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Optimise Rng::gen on arrays? #269

Description

Activity

clarfonthey commented on Mar 8, 2018

pitdicker commented on Mar 8, 2018

dhardy commented on Mar 8, 2018

dhardy commented on Jun 2, 2018

dhardy commented on Jun 3, 2019

vks commented on Jun 3, 2019

dhardy commented on Jun 3, 2019

vks commented on Jun 3, 2019

dhardy commented on Jun 3, 2019

vks commented on Jun 3, 2019

vks commented on Sep 15, 2021

Metadata

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Issue actions

Optimise `Rng::gen` on arrays? #269