为什么Math.DivRem如此低效?

38

在我的电脑上,这段代码需要17秒才能执行完1000万次:

static void Main(string[] args) {
   var sw = new Stopwatch(); sw.Start();
   int r;
   for (int i = 1; i <= 100000000; i++) {
      for (int j = 1; j <= 10; j++) {
         MyDivRem (i,j, out r);
      }
   }
   Console.WriteLine(sw.ElapsedMilliseconds);
}

static int MyDivRem(int dividend, int divisor, out int remainder) {
   int quotient = dividend / divisor;
   remainder = dividend - divisor * quotient;
   return quotient;
}

当使用 Math.DivRem 时,耗时27秒。

.NET Reflector 为我提供了 Math.DivRem 的代码:

public static int DivRem(int a, int b, out int result)
{
    result = a % b;
    return (a / b);
}

CIL

.method public hidebysig static int32 DivRem(int32 a, int32 b, [out] int32& result) cil managed
{
    .maxstack 8
    L_0000: ldarg.2
    L_0001: ldarg.0
    L_0002: ldarg.1
    L_0003: rem
    L_0004: stind.i4
    L_0005: ldarg.0
    L_0006: ldarg.1
    L_0007: div
    L_0008: ret
}

理论上来说,对于有多个核心的计算机,它可能更快,但实际上,它不需要在第一次操作中执行两个操作,因为当x86 CPU使用DIV或IDIV进行整数除法时,它会返回商和余数http://www.arl.wustl.edu/~lockwood/class/cs306/books/artofasm/Chapter_6/CH06-2.html#HEADING2-451)!


当您在非x86上运行.NET时会发生什么? - Jimmy
x64 是 x86 的超集,如果 CPU 不兼容 x86,只需要为该 CPU 使用不同的代码就可以在 .net 框架下运行。 - ggf31416
没错,但.NET也被实现为Mono,因此应该可以在其他架构上运行,例如ppc等。 - André
4
看 IL 代码无法判断这一点,需要查看 JIT 编译器生成的实际代码。 - Mehrdad Afshari
天啊,我简直不敢相信!今天我在我的应用程序中注意到调用DivRem比仅仅使用/和%要慢一点。现在我测试了你的DivRem函数,它确实比两者都快得多!(在我的电脑上约为20%。) - michalburger1
DivRem 处理负数 :) - J-16 SDiZ
11个回答

20

唉。这个函数存在的唯一原因是为了利用 CPU 的指令,但他们甚至没有这样做!


2
不行。如果他们那样做,.NET Reflector 将会告诉你这个函数在本地存根中。 - Joshua
4
即使没有CPU内置求余数和商的功能,该函数仍然很有用,因为它可以通过先计算商,将商乘以除数,再从被除数中减去得到余数。在几乎所有平台上,乘法比除法快,而在某些平台上,速度差异甚至相差一个数量级,因此使用除法、乘法和减法可能比使用两个除法快近一倍。 - supercat
5
相关的是,我认为很不幸的是,极少数语言支持乘积大小大于操作数或除数位数大于被除数的情况。可以将乘法运算的操作数扩大到结果大小,或者将除数的大小扩大到匹配被除数的大小,但许多处理器具有用于混合大小操作数的指令,不使用它们是一种浪费。 - supercat
2
@supercat 至少某些版本的 .net jitter 在你将操作数从 32 位转换为 64 位并在乘法之前立即进行强制转换时,会对 32 位 * 32 位 => 64 位进行优化。不需要语言支持。另一方面,用于保存 64 位乘法结果的 128 位类型确实缺失。 - CodesInChaos
2
即使窥孔优化器可以用硬件内部函数替换某些结构,除非一种语言标准化了某些形式,这些代码生成器强烈鼓励进行窥孔优化,否则很容易出现在两个“兼容”的编译器上编写代码的最快方法在另一个编译器上变得更慢的情况。我不喜欢程序员应该请求他们不想要的操作,以便获得他们想要的操作的想法,希望优化器将从未想过的操作省略掉。 - supercat
显示剩余4条评论

15

.NET Framework 4.6.2仍然使用次优的取模和除法,而.NET Core(CoreCLR) 目前将除法替换为减法:

    public static int DivRem(int a, int b, out int result)
    {
        // TODO https://github.com/dotnet/runtime/issues/5213:
        // Restore to using % and / when the JIT is able to eliminate one of the idivs.
        // In the meantime, a * and - is measurably faster than an extra /.

        int div = a / b;
        result = a - (div * b);
        return div;
    }

有一个未解决的问题,要么通过内置方式 专门改进DivRem,要么检测和优化RyuJIT的一般情况


他为什么在 div * b 周围加上了括号? - Anton Shepelev
@jnm2:我认为应该依靠运算符优先级,只有当意图的优先级与语言中使用的优先级不同时才使用括号... - Anton Shepelev
@Ant_222 我不同意。通常的指导是首先针对人类读者进行优化。任何使代码更清晰的东西都是可取的。 - jnm2
@jnm2:但是冗余的括号会产生混乱并阻碍理解。优先级用于减少括号的数量。 - Anton Shepelev
@Ant_222 当然这是主观的,我看不到你看到的东西,但我也支持在所有未来读者的清晰度方面出错。 - jnm2

14

哇,那看起来真的很愚蠢,不是吗?

问题在于——据Lidin所著的Microsoft Press图书《.NET IL汇编器》所述——IL rem和div算术指令确实是如此:计算余数和计算除数。

除了否定操作之外的所有算术运算都从堆栈中取两个操作数,并将结果放入堆栈中。

显然,由于IL汇编语言的设计方式,不可能有一条IL指令可以产生两个输出并将它们推送到eval栈上。鉴于这种限制,在IL汇编器中无法像x86 DIV或IDIV指令那样同时计算商和余数。

IL的设计目标是安全性、可验证性和稳定性,而不是性能。任何拥有计算密集型应用程序且主要关注性能的人都会使用本地代码,而不是.NET。

我最近参加了2008年超级计算会议,并在其中的一个技术会议上,微软计算服务器的一位布道者给出了大致的经验法则,即.NET通常是本地代码速度的一半——这正是此处情况!


10
虽然这是真的,但是没有理由不能在运行时中实现Math.DivRem并像System.Math的许多其他方法一样标记为[MethodImpl(MethodImplOptions.InternalCall), SecuritySafeCritical] - codekaizen
2
你有证据证明IL本质上无法在堆栈上产生两个值吗?我并不是说这是假的;很容易想象JITter会大量使用这个假设,但是一个合适的来源会很方便。 - Roman Starkov
1
没错,但是DivRem可以返回一个带有Div和Rem字段的单个结构体。无论如何,这似乎更快,并且没有“out”参数的方法应该更好。嗯,我认为这不是在.Net中的问题。 - Alex Zhukovskiy

3

如果我不得不猜测,我会说实现Math.DivRem的人并不知道x86处理器能够在一条指令中完成它,所以他们将其写成了两个操作。如果优化器工作正确,这并不一定是坏事,尽管这又是一个表明大多数程序员缺乏低级别知识的指标。我期望优化器将模数和除法操作合并为一条指令,编写优化器的人应该知道这些低级别的东西...


1
就像编译器或JIT应该用xxx替换Math.Pow(x,3)一样,但这似乎要求太多了... - ggf31416

2
答案可能是没有人认为这是一个优先事项 - 它已经足够好了。.NET框架的任何新版本都没有修复这个问题,这表明这种情况很少被使用 - 很可能从来没有人抱怨过。

1

这只是一条注释,但我没有足够的空间。

这里是一些使用 Math.DivRem() 的 C# 代码:

    [Fact]
    public void MathTest()
    {
        for (var i = 1; i <= 10; i++)
        {
            int remainder;
            var result = Math.DivRem(10, i, out remainder);
            // Use the values so they aren't optimized away
            Assert.True(result >= 0);
            Assert.True(remainder >= 0);
        }
    }

这是相应的IL代码:

.method public hidebysig instance void MathTest() cil managed
{
    .custom instance void [xunit]Xunit.FactAttribute::.ctor()
    .maxstack 3
    .locals init (
        [0] int32 i,
        [1] int32 remainder,
        [2] int32 result)
    L_0000: ldc.i4.1 
    L_0001: stloc.0 
    L_0002: br.s L_002b
    L_0004: ldc.i4.s 10
    L_0006: ldloc.0 
    L_0007: ldloca.s remainder
    L_0009: call int32 [mscorlib]System.Math::DivRem(int32, int32, int32&)
    L_000e: stloc.2 
    L_000f: ldloc.2 
    L_0010: ldc.i4.0 
    L_0011: clt 
    L_0013: ldc.i4.0 
    L_0014: ceq 
    L_0016: call void [xunit]Xunit.Assert::True(bool)
    L_001b: ldloc.1 
    L_001c: ldc.i4.0 
    L_001d: clt 
    L_001f: ldc.i4.0 
    L_0020: ceq 
    L_0022: call void [xunit]Xunit.Assert::True(bool)
    L_0027: ldloc.0 
    L_0028: ldc.i4.1 
    L_0029: add 
    L_002a: stloc.0 
    L_002b: ldloc.0 
    L_002c: ldc.i4.s 10
    L_002e: ble.s L_0004
    L_0030: ret 
}

这里是生成的(相关的)优化x86汇编:

       for (var i = 1; i <= 10; i++)
00000000  push        ebp 
00000001  mov         ebp,esp 
00000003  push        esi 
00000004  push        eax 
00000005  xor         eax,eax 
00000007  mov         dword ptr [ebp-8],eax 
0000000a  mov         esi,1 
        {
            int remainder;
            var result = Math.DivRem(10, i, out remainder);
0000000f  mov         eax,0Ah 
00000014  cdq 
00000015  idiv        eax,esi 
00000017  mov         dword ptr [ebp-8],edx 
0000001a  mov         eax,0Ah 
0000001f  cdq 
00000020  idiv        eax,esi 

请注意 2 次对 idiv 的调用。第一次将余数 (EDX) 存储到堆栈上的 remainder 参数中。第二次是为了确定商(EAX)。实际上,第二次调用并不是真正需要的,因为在第一次调用 idiv 后,EAX 已经具有正确的值。

1

效率可能非常依赖于所涉及的数字。您正在测试可用问题空间的微小部分,并且全部前置。您正在检查前1000万 * 10 = 10亿个连续输入组合,但实际问题空间大约为42亿平方,或1.8e19个组合。

像这样的通用库数学运算的性能需要在整个问题空间上进行摊销。我很想看到更规范化的输入分布的结果。


此外,我认为在30秒内执行10亿次运行是相当不错的,那么有什么大惊小怪的呢? - Michael Haren
1
我测试了几乎整个空间,通过增加每个变量的大质数,但Math.DivRem仍然效率低下。 - ggf31416

1

有其他人在测试时得到相反的结果吗?

Math.DivRem = 11.029 sec, 11.780 sec
MyDivRem = 27.330 sec, 27.562 sec
DivRem = 29.689 sec, 30.338 sec

顺便说一下,我正在运行Intel Core 2 Duo。

上面的数字是使用调试版本得出的...

使用发布版本:

Math.DivRem = 10.314
DivRem = 10.324
MyDivRem = 5.380

看起来,在MyDivRem中,“rem” IL命令比“mul,sub”组合不太高效。


@leppie -- 添加了发布版本数据,但是数字与调试版本一样准确。 - Austin Salonen
MyDivRem 的运行时间保持在 5 秒左右的低中水平。 - Austin Salonen

0

我猜大部分额外的成本在于静态方法调用的设置和拆卸。

至于为什么存在,我猜部分原因是为了完整性,部分原因是为了其他语言的好处,这些语言可能没有易于使用的整数除法和模运算实现。


0

这是我的数字:

15170 MyDivRem
29579 DivRem (same code as below)
29579 Math.DivRem
30031 inlined

测试稍作更改;我添加了返回值的赋值,并运行了发布版本。

Core 2 Duo 2.4

意见:

你似乎找到了一个不错的优化方法;)


网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接