Почему локальный массив быстрее, чем статический для чтения/записи?
Я писал несколько тестов бенчмаркинга, чтобы выяснить, почему подобный чистый алгоритм (не С++ lib/.net, построенный в классах) работал быстрее на С++, чем на С#, даже если учитывал ожидаемые отличия функций. И, делая это, я наткнулся на эти 2 теста, которые сбивали меня с толку, есть ли у кого-нибудь представление о том, почему он существенно медленнее, чем другой? Единственное отличие во втором (что занимает 51 мс против 88 на моей машине) состоит в том, что 2 массива объявляются локально в методе вместо внешнего. В обоих случаях массивы создаются до начала отсчета времени.
const int Runs = 100;
const int Width = 5000;
const int Height = 5000;
const int Size = Width * Height;
static int[] Input = Enumerable.Range(0, Size).ToArray();
static int[] Output = new int[Size * 2];
static int SimpleTest()
{
// Removing those 2 lines and using the static arrays instead give substantially slower performance, nearly half the speed!
int[] Input = Enumerable.Range(0, Size).ToArray();
int[] Output = new int[Size * 2];
Stopwatch sw = new Stopwatch();
sw.Start();
for (int run = 0; run < Runs; run++)
{
int InputIndex = 0;
for (int x = 0; x < Width; x++)
{
for (int y = 0; y < Height; y++)
{
int pixel = Input[InputIndex];
var OutputIndex = InputIndex * 2;
Output[OutputIndex] = pixel;
Output[OutputIndex + 1] = pixel;
InputIndex++;
}
}
}
sw.Stop();
return (int)(sw.ElapsedMilliseconds / Runs);
}
Ответы
Ответ 1
Когда переменные являются локальными, компилятор знает, что Input и Output никогда не изменятся, что открывает множество оптимизаций.
- Значение переменных
Input и Output может храниться в регистрах.
-
Input.Length и Output.Length можно вычислить один раз и кэшировать.
- Компилятор может доказать, что
Input[InputIndex] и Output[OutputIndex] никогда не приведут к тому, что индекс массива окажется за пределами границ, поэтому проверка границ может быть оптимизирована.
- Компилятор может заметить, что результаты
Input и Output никогда не используются, поэтому он может оптимизировать петли до нуля!
Если вы используете статические версии, компилятор не может выполнить эти оптимизации. Компилятор должен перезагрузить Input и Output при каждом доступе и должен выполнить проверку границ в каждой операции индекса массива, на всякий случай, если другой поток изменен Input или Output.
Например, если другой поток выполняет Input = new int[Size], тогда все будущие вычисления должны начинаться с этого альтернативного Input. И если другой поток имеет Output = new int[1], тогда код должен поднять IndexOutOfRangeException.
Ответ 2
С 32-битным JIT я считаю, что виновником является, как заметил Раймонд Чен, что вход и выход можно хранить в регистрах, когда они являются местными, но их нужно перезагружать каждый раз, когда они не являются. Сгенерированная сборка:
Для локальных жителей:
007426F0 mov eax,dword ptr [ebp-18h]
007426F3 mov edi,dword ptr [eax+4]
int pixel = Input[InputIndex];
007426F6 mov eax,dword ptr [ebp-18h]
007426F9 cmp edx,edi
007426FB jae 0074276E
007426FD mov ecx,dword ptr [eax+edx*4+8]
Для статики:
011C2718 mov dword ptr [ebp-18h],edx
011C271B mov esi,dword ptr ds:[3BB7E90h]
011C2721 mov eax,dword ptr [esi+4]
011C2724 mov dword ptr [ebp-1Ch],eax
int pixel = Input[InputIndex];
011C2727 mov eax,dword ptr [ebp-1Ch]
011C272A cmp ecx,eax
011C272C jae 011C27A2
011C272E mov edi,dword ptr [esi+ecx*4+8]
Как вы можете видеть, mov esi,dword ptr ds:[3BB7E90h] обращается к сегменту данных.
Как вы можете видеть, проверка границ происходит в обоих случаях (cmp-jae), так что не имеет значения, и петли на самом деле не оптимизированы ни к чему.
Как 64-разрядный JIT избегает этой проблемы, находится вне меня.
Здесь полная разборка для обоих случаев:
Быстрая версия:
for (int x = 0; x < Width; x++) {
007426EB mov dword ptr [ebp-14h],edx
for (int y = 0; y < Height; y++) {
007426EE xor ebx,ebx
007426F0 mov eax,dword ptr [ebp-18h]
007426F3 mov edi,dword ptr [eax+4]
int pixel = Input[InputIndex];
007426F6 mov eax,dword ptr [ebp-18h]
007426F9 cmp edx,edi
007426FB jae 0074276E
007426FD mov ecx,dword ptr [eax+edx*4+8]
var OutputIndex = InputIndex * 2;
00742701 mov esi,edx
00742703 add esi,esi
Output[OutputIndex] = pixel;
00742705 mov eax,dword ptr [ebp-1Ch]
00742708 cmp esi,dword ptr [eax+4]
0074270B jae 0074276E
0074270D mov dword ptr [eax+esi*4+8],ecx
Output[OutputIndex + 1] = pixel;
00742711 inc esi
00742712 mov eax,dword ptr [ebp-1Ch]
00742715 cmp esi,dword ptr [eax+4]
00742718 jae 0074276E
0074271A mov dword ptr [eax+esi*4+8],ecx
InputIndex++;
0074271E inc edx
for (int y = 0; y < Height; y++) {
0074271F inc ebx
for (int y = 0; y < Height; y++) {
00742720 cmp ebx,1388h
00742726 jl 007426F6
for (int x = 0; x < Width; x++) {
00742728 inc dword ptr [ebp-14h]
0074272B cmp dword ptr [ebp-14h],1388h
00742732 jl 007426EE
Медленная версия:
for (int x = 0; x < Width; x++) {
011C2713 mov dword ptr [ebp-14h],ecx
for (int y = 0; y < Height; y++) {
011C2716 xor edx,edx
011C2718 mov dword ptr [ebp-18h],edx
011C271B mov esi,dword ptr ds:[3BB7E90h]
011C2721 mov eax,dword ptr [esi+4]
011C2724 mov dword ptr [ebp-1Ch],eax
int pixel = Input[InputIndex];
011C2727 mov eax,dword ptr [ebp-1Ch]
011C272A cmp ecx,eax
011C272C jae 011C27A2
011C272E mov edi,dword ptr [esi+ecx*4+8]
var OutputIndex = InputIndex * 2;
011C2732 mov ebx,ecx
011C2734 add ebx,ebx
Output[OutputIndex] = pixel;
011C2736 mov edx,dword ptr ds:[3BB7E94h]
011C273C cmp ebx,dword ptr [edx+4]
011C273F jae 011C27A2
011C2741 mov dword ptr [edx+ebx*4+8],edi
Output[OutputIndex + 1] = pixel;
011C2745 inc ebx
011C2746 cmp ebx,dword ptr [edx+4]
011C2749 jae 011C27A2
011C274B mov dword ptr [edx+ebx*4+8],edi
InputIndex++;
011C274F inc ecx
for (int y = 0; y < Height; y++) {
011C2750 inc dword ptr [ebp-18h]
011C2753 cmp dword ptr [ebp-18h],1388h
011C275A jl 011C2727
for (int x = 0; x < Width; x++) {
011C275C inc dword ptr [ebp-14h]
011C275F cmp dword ptr [ebp-14h],1388h
011C2766 jl 011C2716
Ответ 3
Интересно, может ли это быть похоже на разницу в производительности между статическими и функциями-членами? Вызов статических методов не проверяется с нулевым значением, тогда как вызовы функций экземпляра имеют нулевое значение.
Кроме того, я вижу разные результаты, чем вы. Статические массивы имеют более короткое время работы на моей машине. 64.x мс за ход против около 75.x мс.
Вот полная программа, которую я использовал. Выполняется на Mono С#, на OSX.
using System;
using System.Diagnostics;
using System.Linq;
using System.Collections.Generic;
using System.Text;
namespace ConsoleApplication1
{
class Program
{
static void Main(string[] args)
{
Console.WriteLine("Time per run was: " + SimpleTest());
}
const int Runs = 10;
const int Width = 5000;
const int Height = 5000;
const int Size = Width * Height;
static int[] Input = Enumerable.Range(0, Size).ToArray();
static int[] Output = new int[Size * 2];
static float SimpleTest()
{
// Removing those 2 lines and using the static arrays instead give substantially slower performance, nearly half the speed!
//int[] Input = Enumerable.Range(0, Size).ToArray();
//int[] Output = new int[Size * 2];
Stopwatch sw = new Stopwatch();
sw.Start();
for (int run = 0; run < Runs; run++)
{
int InputIndex = 0;
for (int x = 0; x < Width; x++)
{
for (int y = 0; y < Height; y++)
{
int pixel = Input[InputIndex];
var OutputIndex = InputIndex * 2;
Output[OutputIndex] = pixel;
Output[OutputIndex + 1] = pixel;
InputIndex++;
}
}
}
sw.Stop();
return (sw.ElapsedMilliseconds / (float)Runs);
}
}
}
