Ответ 1
Grrr. Единственная причина, по которой эта функция существует, - это воспользоваться инструкцией CPU для этого, и они даже этого не сделали!
Почему 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
}
Ответы
Ответ 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
Это отчасти в природе зверя. Насколько я знаю, нет общего быстрого способа рассчитать остаток деления. Это потребует соответственно большого количества тактовых циклов, даже с х сто миллионов транзисторов.