[.NET 6] Improving the default Random.NextInt64 performance for derived classes

[koszeggy]

Description

Consider a pre-.NET 6 library used from .NET 6 that has a derived Random class but doesn't override the NextInt64 methods (example).

As such a class has no overridden NextInt64 methods, the internal Net5CompatImpl implementation kicks in, whose private NextUInt64 method ends up calling the Next() method 8 times for each byte in the ulong sample to be generated.

Proposed fix

Please consider changing the current NextUInt64 method like this:

private unsafe ulong NextUInt64()
{
    Span<byte> resultBytes = stackalloc byte[8];
    _parent.NextBytes(resultBytes); // instead of: NextBytes(resultBytes);
    return BitConverter.ToUInt64(resultBytes);
}

The proposed change above calls the possibly overridden NextBytes(Span<byte>) overload, which gives a chance for a pre-.NET 6 class to fill up the buffer much more efficiently. If NextBytes(Span<byte>) is not overridden either, then this eventually calls the current Net5CompatImpl implementation with those repeated Next calls.

Risks

This will produce different results from the current implementation but since .NET 6 is not released yet I don't think it's a real issue.

I couldn't figure out the best area label to add to this issue. If you have write-permissions please help me learn by adding exactly one area label.

[stephentoub]

This would help the cited case (potentially significantly), but hurt multiple other cases:

• Calling NextInt64 on a new Random(seed)
• Calling NextInt64 on a new DerivedRandom() that doesn't override NextBytes(Span<byte>)

as now we're adding an additional virtual call to the parent's NextBytes. I tried it out locally, and while there's some noise, it seems to have a negative impact to the tune of around 3%. And if someone has overridden the recently introduced NextBytes(Span<byte>), then I expect there's a good chance they will also end up overriding the new methods, and so the delegation pattern won't matter.

I'm inclined to say that the current implementation is making the right tradeoffs.

Tagging subscribers to this area: @dotnet/area-system-runtime
See info in area-owners.md if you want to be subscribed.

Issue Details

---

Description

Consider a pre-.NET 6 library used from .NET 6 that has a derived Random class but doesn't override the NextInt64 methods (example).

As such a class has no overridden NextInt64 methods, the internal Net5CompatImpl implementation kicks in, whose private NextUInt64 method ends up calling the Next() method 8 times for each byte in the ulong sample to be generated.

Proposed fix

Please consider changing the current NextUInt64 method like this:

private unsafe ulong NextUInt64()
{
    Span<byte> resultBytes = stackalloc byte[8];
    _parent.NextBytes(resultBytes); // instead of: NextBytes(resultBytes);
    return BitConverter.ToUInt64(resultBytes);
}

The proposed change above calls the possibly overridden NextBytes(Span<byte>) overload, which gives a chance for a pre-.NET 6 class to fill up the buffer much more efficiently. If NextBytes(Span<byte>) is not overridden either, then this eventually calls the current Net5CompatImpl implementation with those repeated Next calls.

Risks

This will produce different results from the current implementation but since .NET 6 is not released yet I don't think it's a real issue.

Author:	koszeggy
Assignees:	-
Labels:	area-System.Runtime, tenet-performance, untriaged
Milestone:	-

[koszeggy]

Calling NextInt64 on a new Random(seed)

Actually this also could be radically improved. As a new functionality, it wouldn't break anything if it didn't always throw away 3 out of 4 generated bytes. It could just call InternalSample twice to generate a long value instead of calling the virtual Next 8 times.

[stephentoub]

That was discussed previously but dismissed due to it not providing good enough distribution.

[koszeggy]

Ah, ok. At least, I tried it. :)

I still hope that 3% degradation on the legacy path (which actually has no baseline from any previous version that could be worse) is worth for a drastic improvement. Which of course will be out of question when everyone will have released their fixed libraries with the missing overrides...

[stephentoub]

I still hope that 3% degradation on the legacy path (which actually has no baseline from any previous version that could be worse) is worth for a drastic improvement.

It's not legacy. This applies to new Random(42). A type derived from Random can address the deficiency better than we can by simply overriding the new method, and it's only an issue to begin with if it's already overridden newer methods on the type. Code using new Random(42) has no recourse.

[stephentoub]

Thank you for the suggestion.

[koszeggy]

@stephentoub: Sorry for bothering again (after the issue is closed) but suddenly an idea came to my mind, which cures also another (maybe more serious) issue: when creating a derived random instace, the legacy compatible algorithm always allocates and initializes _seedArray, even if it is never needed (eg. when all methods are overridden, and base is never used).

Net5CompatImpl is now used for two use cases:

1. When we use a seed (new Random(42))
2. When we have a derived Random class (new DerivedRandom())

Actually case 2.) could use a 3rd ImplBase implementation (eg. LazyNet5CompatImpl?), which is very similar to Net5CompatImpl, but

• Its constructor does nothing. _seedArray is initialized on demand in InternalSample
• Its NextUInt64() can call _parent.NextBytes(resultBytes) because it now has no negative impact on case 1.)

Will you reopen the issue?
Or, should I create a new one, addressing the potentially unnecessary allocation/initialization issue?
Or, should I maybe prepare a pull request and reference this issue?

[stephentoub]

I'm currently experimenting with something similar, having a dedicated implementation for the new Random(int) case, which then necessarily means there's a dedicated implementation for the new DerivedRandom(...) case. My goal is to avoid the virtual dispatch in the former, but a small tweak could likely then enable lazy-init of the _seedArray in the latter as you suggest.