5-кратное увеличение производительности с Parallel.For… на двухъядерном процессоре?
Ради интереса я проводил экспериментальные расчеты, когда наткнулся на интересный результат:
Completed 1024x1024 pixels with 700 points in...
For Loop (Inline): 19636ms
For Loop: 12612ms
Parallel.For Loop: 3835ms
Это не то, что я ожидал.
Система :Windows 7 64, i3 2120 [двухъядерный, 4 потока], Visual Studio 2010.
Сборка :Оптимизация включена, режим выпуска [без отладчика], 32 бит.
Второстепенный интерес вызывает разочаровывающая 64-битная производительность. Хотя это больше соответствует тому, что я ожидал с точки зрения соотношения, оно достигает этого, будучи медленнее по всем направлениям.
Completed 1024x1024 pixels with 700 points in...
For Loop (Inline): 23409ms
For Loop: 24373ms
Parallel.For Loop: 6839ms
Расчет прост :Для индексов x и y найдите ближайший Vector3 и сохраните его в двумерном массиве.
Вопрос, если вы осмелитесь, состоит в том, чтобы попытаться объяснить, почему встроенный цикл for такой медленный. Бонусные баллы за объяснение низкой производительности 64-битных версий.
using System;
using System.Diagnostics;
using System.Threading.Tasks;
namespace TextureFromPoints
{
class Program
{
const int numPoints = 700;
const int textureSize = 1024;
static Random rnd = new Random();
static void Main(string[] args)
{
while (true)
{
Console.WriteLine("Starting");
Console.WriteLine();
var pointCloud = new Vector3[numPoints];
for (int i = 0; i < numPoints; i++)
pointCloud[i] = new Vector3(textureSize);
var result1 = new Vector3[textureSize, textureSize];
var result2 = new Vector3[textureSize, textureSize];
var result3 = new Vector3[textureSize, textureSize];
var sw1 = Stopwatch.StartNew();
for (int x = 0; x < textureSize; x++)
for (int y = 0; y < textureSize; y++)
{
var targetPos = new Vector3(x, y, 0);
var nearestV3 = pointCloud[0];
var nearestV3Distance = nearestV3.DistanceToPoint(targetPos);
for (int i = 1; i < numPoints; i++)
{
var currentV3 = pointCloud[i];
var currentV3Distance = currentV3.DistanceToPoint(targetPos);
if (currentV3Distance < nearestV3Distance)
{
nearestV3 = currentV3;
nearestV3Distance = currentV3Distance;
}
}
result1[x, y] = nearestV3;
}
sw1.Stop();
var sw2 = Stopwatch.StartNew();
for (int x = 0; x < textureSize; x++)
for (int y = 0; y < textureSize; y++)
Computation(pointCloud, result2, x, y);
sw2.Stop();
var sw3 = Stopwatch.StartNew();
Parallel.For(0, textureSize, x =>
{
for (int y = 0; y < textureSize; y++)
Computation(pointCloud, result3, x, y);
});
sw3.Stop();
Console.WriteLine("Completed {0}x{0} pixels with {1} points in...", textureSize, numPoints);
Console.WriteLine("{0}: {1}ms", "For Loop (Inline)", sw1.ElapsedMilliseconds);
Console.WriteLine("{0}: {1}ms", "For Loop", sw2.ElapsedMilliseconds);
Console.WriteLine("{0}: {1}ms", "Parallel.For Loop", sw3.ElapsedMilliseconds);
Console.WriteLine();
Console.Write("Verifying Data: ");
Console.WriteLine(CheckResults(result1, result2) && CheckResults(result1, result3) ? "Valid" : "Error");
Console.WriteLine(); Console.WriteLine();
Console.ReadLine();
}
}
private static bool CheckResults(Vector3[,] lhs, Vector3[,] rhs)
{
for (int x = 0; x < textureSize; x++)
for (int y = 0; y < textureSize; y++)
if (!lhs[x, y].Equals(rhs[x, y]))
return false;
return true;
}
private static void Computation(Vector3[] pointCloud, Vector3[,] result, int x, int y)
{
var targetPos = new Vector3(x, y, 0);
var nearestV3 = pointCloud[0];
var nearestV3Distance = nearestV3.DistanceToPoint(targetPos);
for (int i = 1; i < numPoints; i++)
{
var currentV3 = pointCloud[i];
var currentV3Distance = currentV3.DistanceToPoint(targetPos);
if (currentV3Distance < nearestV3Distance)
{
nearestV3 = currentV3;
nearestV3Distance = currentV3Distance;
}
}
result[x, y] = nearestV3;
}
struct Vector3
{
public float x;
public float y;
public float z;
public Vector3(float x, float y, float z)
{
this.x = x;
this.y = y;
this.z = z;
}
public Vector3(float randomDistance)
{
this.x = (float)rnd.NextDouble() * randomDistance;
this.y = (float)rnd.NextDouble() * randomDistance;
this.z = (float)rnd.NextDouble() * randomDistance;
}
public static Vector3 operator -(Vector3 a, Vector3 b)
{
return new Vector3(a.x - b.x, a.y - b.y, a.z - b.z);
}
public float sqrMagnitude()
{
return x * x + y * y + z * z;
}
public float DistanceToPoint(Vector3 point)
{
return (this - point).sqrMagnitude();
}
}
}
}
ОБНОВЛЕНИЕ :Благодаря усилиям Дрю Марша теперь у нас есть супероптимизированная версия, в которой встроены все операции V3.
using System;
using System.Diagnostics;
using System.Threading.Tasks;
namespace TextureFromPoints
{
class RevisedProgram
{
const int numPoints = 700;
const int textureSize = 1024;
static Random rnd = new Random();
static void Main(string[] args)
{
while (true)
{
Console.WriteLine("Starting REVISED");
Console.WriteLine();
var pointCloud = new Vector3[numPoints];
for (int i = 0; i < numPoints; i++)
pointCloud[i] = new Vector3(textureSize);
var result1 = new Vector3[textureSize, textureSize];
var result2 = new Vector3[textureSize, textureSize];
var result3 = new Vector3[textureSize, textureSize];
var sw1 = Inline(pointCloud, result1);
var sw2 = NotInline(pointCloud, result2);
var sw3 = Parallelized(pointCloud, result3);
Console.WriteLine("Completed {0}x{0} pixels with {1} points in...", textureSize, numPoints);
Console.WriteLine("{0}: {1}ms", "For Loop (Inline)", sw1.ElapsedMilliseconds);
Console.WriteLine("{0}: {1}ms", "For Loop", sw2.ElapsedMilliseconds);
Console.WriteLine("{0}: {1}ms", "Parallel.For Loop", sw3.ElapsedMilliseconds);
Console.WriteLine();
Console.Write("Verifying Data: ");
Console.WriteLine(CheckResults(result1, result2) && CheckResults(result1, result3) ? "Valid" : "Error");
Console.WriteLine();
Console.WriteLine();
Console.ReadLine();
}
}
private static Stopwatch Parallelized(Vector3[] pointCloud, Vector3[,] result3)
{
var sw3 = Stopwatch.StartNew();
Parallel.For(0, textureSize, x =>
{
for (int y = 0; y < textureSize; y++)
Computation(pointCloud, result3, x, y);
});
sw3.Stop();
return sw3;
}
private static Stopwatch NotInline(Vector3[] pointCloud, Vector3[,] result2)
{
var sw2 = Stopwatch.StartNew();
for (int x = 0; x < textureSize; x++)
for (int y = 0; y < textureSize; y++)
Computation(pointCloud, result2, x, y);
sw2.Stop();
return sw2;
}
private static Stopwatch Inline(Vector3[] pointCloud, Vector3[,] result1)
{
var sw1 = Stopwatch.StartNew();
for (int x = 0; x < textureSize; x++)
for (int y = 0; y < textureSize; y++)
{
var targetPos = new Vector3(x, y, 0);
var nearestV3 = pointCloud[0];
Vector3 temp1 = new Vector3(nearestV3.x - targetPos.x, nearestV3.y - targetPos.y, nearestV3.z - targetPos.z);
var nearestV3Distance = temp1.x * temp1.x + temp1.y * temp1.y + temp1.z * temp1.z;
for (int i = 1; i < numPoints; i++)
{
var currentV3 = pointCloud[i];
Vector3 temp2 = new Vector3(currentV3.x - targetPos.x, currentV3.y - targetPos.y, currentV3.z - targetPos.z);
var currentV3Distance = temp2.x * temp2.x + temp2.y * temp2.y + temp2.z * temp2.z;
if (currentV3Distance < nearestV3Distance)
{
nearestV3 = currentV3;
nearestV3Distance = currentV3Distance;
}
}
result1[x, y] = nearestV3;
}
sw1.Stop();
return sw1;
}
private static bool CheckResults(Vector3[,] lhs, Vector3[,] rhs)
{
for (int x = 0; x < textureSize; x++)
for (int y = 0; y < textureSize; y++)
if (!lhs[x, y].Equals(rhs[x, y]))
return false;
return true;
}
private static void Computation(Vector3[] pointCloud, Vector3[,] result, int x, int y)
{
var targetPos = new Vector3(x, y, 0);
var nearestV3 = pointCloud[0];
Vector3 temp1 = new Vector3(nearestV3.x - targetPos.x, nearestV3.y - targetPos.y, nearestV3.z - targetPos.z);
var nearestV3Distance = temp1.x * temp1.x + temp1.y * temp1.y + temp1.z * temp1.z;
for (int i = 1; i < numPoints; i++)
{
var currentV3 = pointCloud[i];
Vector3 temp2 = new Vector3(currentV3.x - targetPos.x, currentV3.y - targetPos.y, currentV3.z - targetPos.z);
var currentV3Distance = temp2.x * temp2.x + temp2.y * temp2.y + temp2.z * temp2.z;
if (currentV3Distance < nearestV3Distance)
{
nearestV3 = currentV3;
nearestV3Distance = currentV3Distance;
}
}
result[x, y] = nearestV3;
}
struct Vector3
{
public float x;
public float y;
public float z;
public Vector3(float x, float y, float z)
{
this.x = x;
this.y = y;
this.z = z;
}
public Vector3(float randomDistance)
{
this.x = (float)rnd.NextDouble() * randomDistance;
this.y = (float)rnd.NextDouble() * randomDistance;
this.z = (float)rnd.NextDouble() * randomDistance;
}
}
}
}
И это дает следующие результаты:
x86
Completed 1024x1024 pixels with 700 points in...
For Loop (Inline): 3820ms
For Loop: 3962ms
Parallel.For Loop: 1681ms
x64
Completed 1024x1024 pixels with 700 points in...
For Loop (Inline): 10978ms
For Loop: 10924ms
Parallel.For Loop: 3073ms
Итак, хорошая новость заключается в том, что мы можем резко увеличить производительность этого кода -и заставить однопоточную версию работать со скоростью, несколько соответствующей ее параллельной версии.
Плохая новость заключается в том, что это означает полный и ручной отказ от x64 в -с подкладкой всей математики.
На данном этапе я очень разочарован производительностью компиляторов -Я ожидал, что они будут намного лучше.
Заключение
Это глупо и грустно... и хотя мы действительно не знаем, почему мы можем сделать обоснованное предположение, что это вызвано глупым компилятором/компиляторами. 24 с до 3,8 с, просто изменив компилятор с x64 на x86 и выполнив некоторую ручную подкладку -- это не то, что я ожидал. Однако я закончил доказательство концепции, которую писал, и благодаря простому пространственному хешу я могу вычислить изображение 1024 на 1024 с 70 000 «точек» за 0,7 с-~На 340 000 % быстрее, чем в моем исходном сценарии x64, и без многопоточности или выравнивания -. Таким образом, я принял ответ -, что насущная необходимость отпала, хотя я все еще буду изучать этот вопрос.
Код доступен здесь и здесь-он генерирует хорошую диаграмму Вороного как побочный эффект :P