Почему 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)!
11 ответов
Хмм. Единственная причина существования этой функции - использовать для этого инструкцию процессора, а они даже этого не сделали!
Хотя.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.
Вау, это действительно выглядит глупо, не так ли?
Проблема заключается в том, что, согласно книге Microsoft Press ".NET IL Assembler" Лидина, атимметические инструкции IL rem и div именно таковы: вычислить остаток и вычислить делитель.
Все арифметические операции, кроме операции отрицания, берут два операнда из стека и помещают результат в стек.
По-видимому, так, как спроектирован язык ассемблера IL, невозможно иметь инструкцию IL, которая создает два вывода и помещает их в стек eval. Учитывая это ограничение, вы не можете иметь инструкцию деления в IL-ассемблере, которая вычисляет так, как это делают инструкции x86 DIV или IDIV.
IL был разработан для безопасности, проверяемости и стабильности, а не для производительности. Любой, кто имеет приложение, интенсивно использующее вычислительные ресурсы и который в основном занимается производительностью, будет использовать собственный код, а не.NET.
Недавно я посетил Supercomputing '08, и на одном из технических заседаний евангелист для Microsoft Compute Server дал грубое эмпирическое правило о том, что.NET, как правило, вдвое медленнее нативного кода - что именно здесь и происходит!
Если бы мне пришлось сделать дикое предположение, я бы сказал, что тот, кто внедрил Math.DivRem, не знал, что процессоры x86 способны сделать это в одной инструкции, поэтому они записали это как две операции. Это не обязательно плохо, если оптимизатор работает правильно, хотя это еще один показатель того, что в наши дни программистам не хватает знаний низкого уровня. Я ожидал бы, что оптимизатор свернет модуль и затем разделит операции на одну инструкцию, и люди, которые пишут оптимизаторы, должны знать такие вещи низкого уровня...
Ответ, вероятно, заключается в том, что никто не считал это приоритетом - это достаточно хорошо. Тот факт, что это не было исправлено ни в одной новой версии.NET Framework, является показателем того, как редко это используется - скорее всего, никто никогда не жаловался.
Эффективность может очень хорошо зависеть от числа участвующих. Вы тестируете крошечную часть доступного проблемного пространства и все загружается с фронта. Вы проверяете первые 1 миллион * 10 = 1 миллиард смежных входных комбинаций, но фактическая проблемная область составляет приблизительно 4,2 миллиарда в квадрате, или 1,8e19 комбинаций.
Производительность таких общих математических операций библиотеки нужно амортизировать по всему проблемному пространству. Мне было бы интересно увидеть результаты более нормализованного распределения входных данных.
Кто-нибудь еще получает противоположность при тестировании этого?
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
Похоже, команда IL "rem" менее эффективна, чем комбо "mul, sub" в MyDivRem.
Это действительно просто комментарий, но мне не хватает места.
Вот немного 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 параметр в стеке. 2-й, чтобы определить частное (EAX). Этот 2-ой звонок на самом деле не нужен, так как EAX имеет правильное значение после первого вызова idiv,
Вот мои номера:
15170 MyDivRem
29579 DivRem (same code as below)
29579 Math.DivRem
30031 inlined
Тест был немного изменен; Я добавил присваивание возвращаемому значению и выполнял сборку релиза.
Core 2 Duo 2.4
Мнение:
Вы, кажется, нашли хорошую оптимизацию;)
Я полагаю, что большая часть добавленной стоимости заключается в установке и удалении статического вызова метода.
Что касается того, почему он существует, я бы предположил, что это отчасти для полноты и частично для других языков, которые могут не иметь простых в использовании реализаций целочисленного деления и вычисления модуля.
Это отчасти в природе зверя. Насколько мне известно, нет общего быстрого способа подсчитать остаток от деления. Это займет соответственно большое количество тактов, даже с сотнями миллионов транзисторов.