Подтвердить что ты не робот

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

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

Ответ 1

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

Ответ 2

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

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

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

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

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

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

Ответ 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.

Ответ 4

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

Ответ 5

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

Ответ 6

Кто-нибудь другой обращается к этому при тестировании?

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" combo в MyDivRem.

Ответ 7

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

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

Ответ 8

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

Вот несколько С#, используя 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.

Ответ 9

Вот мои номера:

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

Тест слегка изменился; Я добавил назначение к возвращаемому значению и выполнял сборку выпуска.

Core 2 Duo 2.4

Мнение:

Кажется, вы нашли хорошую оптимизацию;)

Ответ 10

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

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

Ответ 11

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