Почему Math.DivRem неэффективен?

Question

В моем компьютере этот код занимает 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);
}

КСС

.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 возвращают как частное, так и остаток , когда они целочисленное деление с использованием DIV или IDIV (http://www.arl.wustl.edu/~lockwood/class/cs306/books/artofasm/Chapter_6/CH06-2.html#HEADING2-451)!

Answer 1

Grrr. Единственная причина существования этой функции - использовать для этого команду процессора, а они даже этого не сделали!

Answer 2

Ого, это действительно выглядит глупо, не так ли?

Проблема заключается в том, что, согласно книге Microsoft Press ".NET IL Assembler" Лидина, атимметические инструкции IL rem и div именно такие: вычислить остаток и вычислить делитель.

Все арифметические операции, кроме операции отрицания, берут два операнда из стека и помещают результат в стек.

По-видимому, так, как спроектирован язык ассемблера IL, невозможно иметь инструкцию IL, которая выдает два вывода и помещает их в стек eval. Учитывая это ограничение, вы не можете иметь инструкцию деления в ассемблере IL, которая вычисляет так, как это делают инструкции x86 DIV или IDIV.

IL был разработан для безопасности, проверяемости и стабильности, НЕ для производительности. Любой, кто имеет приложение с интенсивными вычислениями и озабочен в первую очередь производительностью, будет использовать собственный код, а не .NET.

Недавно я посетил Supercomputing '08, и на одном из технических заседаний евангелист для Microsoft Compute Server дал грубое эмпирическое правило о том, что .NET, как правило, вдвое медленнее нативного кода - что именно здесь и происходит! .

Answer 3

В то время как .NET Framework 4.6.2 по-прежнему использует субоптимальный модуль и деление, .NET Core (CoreCLR) в настоящее время заменяет деление на вычитание:

    public static int DivRem(int a, int b, out int result) {
        // TODO https://github.com/dotnet/coreclr/issues/3439:
        // 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.

Answer 4

Если бы мне пришлось делать какие-то предположения, я бы сказал, что тот, кто внедрил Math.DivRem, не знал, что процессоры x86 способны сделать это в одной инструкции, поэтому они записали это как две операции. Это не обязательно плохо, если оптимизатор работает правильно, хотя это еще один показатель того, что в наши дни программистам не хватает знаний низкого уровня. Я ожидал бы, что оптимизатор свернет модуль и затем разделит операции на одну инструкцию, и люди, которые пишут оптимизаторы, должны знать такие вещи низкого уровня ...

Answer 5

Ответ, вероятно, заключается в том, что никто не считал это приоритетом - это достаточно хорошо. Тот факт, что это не было исправлено ни в одной новой версии .NET Framework, является показателем того, как редко это используется - скорее всего, никто никогда не жаловался.

Answer 6

Эффективность может очень хорошо зависеть от числа участвующих. Вы тестируете крошечную часть доступного проблемного пространства и все загружается с фронта. Вы проверяете первые 1 миллион * 10 = 1 миллиард смежных входных комбинаций, но фактическая проблемная область составляет приблизительно 4,2 миллиарда в квадрате или 1,8e19 комбинаций.

Производительность таких общих математических операций библиотеки нужно амортизировать по всему проблемному пространству. Мне было бы интересно увидеть результаты более нормализованного входного распределения.

Answer 7

Кто-нибудь еще получает обратное при тестировании этого?

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

FWIW, я использую Intel Core 2 Duo.

Числа выше были с отладочной сборкой ...

С выпуском сборки:

Math.DivRem = 10.314
DivRem = 10.324
MyDivRem = 5.380

Похоже, что команда "rem" IL менее эффективна, чем комбо "mul, sub" в MyDivRem.

Answer 8

Это действительно просто комментарий, но мне не хватает места.

Вот немного C # с использованием Math.DivRem():

    [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). Этот второй вызов на самом деле не нужен, поскольку EAX имеет правильное значение после первого вызова idiv.

Answer 9

Я бы предположил, что большая часть добавленной стоимости приходится на установку и разбор статического вызова метода.

Что касается того, почему оно существует, я бы предположил, что это частично для полноты и частично для других языков, которые могут не иметь простых в использовании реализаций целочисленного деления и вычисления модуля.

Answer 10

Это отчасти в природе зверя. Насколько мне известно, нет общего быстрого способа подсчитать остаток от деления. Это займет соответственно большое количество тактов, даже с сотнями миллионов транзисторов.