Repository navigation
Can "Math.DivRem" do division operation only once? #4155
Description
Currently it does division twice, but most CPUs support to get the two values by doing division only once.
Besides,this method should support uint and ulong too.
category:cq
theme:div-mod-rem
skill-level:expert
cost:large
impact:medium
Activity
jkotas commentedon Apr 21, 2015
Math.DivRem is not in the .NET Core public surface, but I agree that it would be nice for the code generators to recognize the pattern and perform the division just one.
cc @CarolEidt @cmckinsey
stephentoub commentedon Apr 21, 2015
cc: @KrzysztofCwalina, as IIRC, Krzysztof bumped up against this as a measurable cost when doing some recent fomatting/parsing experimentation.
CarolEidt commentedon Apr 21, 2015
This would not be a very difficult pattern to recognize: a div and a rem with incoming value numbers that match, though it doesn't "fit" with any existing (or other common) optimization patterns. The thing that would be challenging would be to deal with the resulting IR node that would produce two values in registers. Although that would not be all that difficult, it would require more pervasive changes.
tannergooding commentedon Apr 21, 2015
👍
In short term, couldn't
Math.DivRembe treated as a special-case (intrinsic)? I wouldn't think that this optimization wouldn't really require many changes.Long term though, adding an optimization pattern to recognize
/and%with matching value members would be great.CarolEidt commentedon Apr 21, 2015
@tannergooding - you would think that it would be simpler, but actually it requires the messiest part of the work (handling the node in the IR that produces two values), while only relieving the JIT of what is probably the more straightforward part of the implementation. It might actually be easier on x86 (32 bit) where we already have to deal with longs that occupy multiple registers.
tannergooding commentedon Jun 7, 2017
@CarolEidt, I'm actually wondering why this would require more pervasive changes?
I would think that instructions like
idivshould already document (via some metadata) that they end up writing two registers, correct? As without this being carried around by the code generator, it would potentially end up overwriting the second argument of the parameter list whenever it generates theidivinstruction.I've not looked at the code, but I would guess that various instructions do indicate what registers end up being input/output by the instruction and that the changes here would be to allow the node to actually carry the second value (which could probably be done via inheritance and type checking). I actually think this is in a similar vein to having an intrinsic that takes 3 arguments where the GenTreeOp currently only allows 2 arguments.
ygc369 commentedon Mar 29, 2020
@CarolEidt
Is there any progress about this?
ygc369 commentedon Aug 26, 2020
@tannergooding @CarolEidt
After more than five years, has this issue been solved?
tannergooding commentedon Aug 27, 2020
No, but .NET 5 brought about some register allocator changes that should (hopefully) make it simpler to support now.
caihongxu commentedon Sep 21, 2020
Before this is addressed in .NET 5, any remedies we could do ourselves. e.g. is it possible to roll our own DivRem method to achieve doing division only once?
ygc369 commentedon Feb 18, 2021
@tannergooding
From this blog Announcing .NET 6 Preview 1, I see that there will be a new overload of DivRem for .Net 6, which returns a tuple. Will this new overload be able to do division only once?
tannergooding commentedon Feb 18, 2021
The new API surface is setup in a way that would enable that optimization on x86/x64. I don't believe there is any instruction to compute quotient and remainder simultaneously on ARM32/ARM64.
Whether or not it gets enabled likely depends on prioritization and availability from the dev's familiar enough with that area of the codebase.
5 remaining items
colejohnson66 commentedon May 21, 2024
For an update, in 8.0,
DivRemonly does one division, then computes the remainder from that.https://sharplab.io/#v2:EYLgxg9gTgpgtADwGwBYA0AXEBDAzgWwB8ABAJgEYBYAKGIGYACMhgYQYG8aHunGAKAK4BLAHYYGARQEQMQ7GLQNhYhgCUY+bKIAmMKAEoGAESEA3dfkGjx2RcvHBDnaj1dMA7AwCy2DAAsAOhNzDT5bBkcAbi4eAF8aWKA=
tannergooding commentedon May 24, 2024
DivRemhas been implemented to do a division and then compute the remainder using multiplication for many releases now.On non-xarch platforms, this is the only way to compute the remainder as well, notably. There is no single instruction that computes div+rem simultaneously.
colejohnson66 commentedon May 24, 2024
Yes. So the main complaint that it performs two divisions is no longer valid.
tannergooding commentedon May 24, 2024
And the overall history of the issue, which needs to be taken into account, covers that such a change went in. This issue then still exists to track the underlying spirit of the bug which is that its doing more work than necessary on some platforms.
ygc369 commentedon May 29, 2024
@tannergooding
Using multiplication is also extra work, although maybe faster than an extra division. Isn't it possible to get div+rem at the same time just by doing division once and no other operation? Maybe this cannot be done for all platforms as some platforms do not support it by hardware. But there must be platforms that support it, so, can it be done just on supported platforms?
bazzilic commentedon May 29, 2024
it is indeed significantly faster
some comments above answer this question in great detail, e.g.: #4155 (comment)
colejohnson66 commentedon May 29, 2024
On x86, a division can take 15-30 clock cycles (sometimes over 40) and can only start one ever three or four. Multiplication, on the other hand, takes about eight and can start a new one every cycle.
tannergooding commentedon May 29, 2024
For x86/x64, yes. It isn't possible on other platforms as they don't provide such support. However, even for x86/x64 the benefit there is really using 1 instruction, it isn't actually much faster (than doing
div, mul, subexplicitly). In many cases it is actually more desirable to break it apart to avoid a dependency chain or use an alternative sequence (especially if one of the inputs is known constant).Modern CPUs (almost any in the past 12-14 years) account for these things and often have special
div/idivsupport that breaks it apart internally to what is functionallydiv, mul, subalready so that the quotient can be available prior to the remainder being available. They may even skip the internal microcode for computing the remainder in some cases if they can see its unused. The time is also often dependent on the number of significant bits in the dividend, although even newer processors have changed implementations and now it is often based on the number of significant bits in the quotient instead.Notably this very much depends on microarchitecture, whether you're doing signed or unsigned, and it has massively improved in even more recent years
idiv (32-bit)took around20-28cycles with8reciprocal throughputidiv (64-bit)took around37-101cycles with24reciprocal throughput.idiv (32-bit)took around10-15cycles with6reciprocal throughputidiv (64-bit)took around14-18cycles with10reciprocal throughput.Your multiplication info is also quite a bit off, both 32-bit and 64-bit have been
3 cycleswith1 reciprocal throughputsince the early 2000s. If you're doing abig multiplication(64x64=128) then it used to take7-9or3-10cycles for pre 2011 chips, but that's not typical.