Доброго времени суток!
Пытаюсь соптимизировать умножение небольшой (40*40) матрицы из float на вектор.
Понятно, что с развернутым в одну строку массивом (и развернутым циклом) получается немного быстрее, чем какие-то извращения с jagged (код под катом):
Скрытый текст
public static void Main()
{
int N = 40;
int T = 1000000;
long start, stop;
double elapsed;
var A = new float[N*N];
var B = new float[N];
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
A[i*N+j] = Math.Abs(i-j);
for (int i = 0; i < N; i++)
B[i] = i;
var C = new float[N];
start = DateTime.Now.Ticks;
for (int l = 0; l < T; l++)
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j+=4)
{
C[i] += A[i*N+j] * B[j];
C[i] += A[i*N+j+1] *B[j+1];
C[i] += A[i*N+j+2] *B[j+2];
C[i] += A[i*N+j+3] *B[j+3];
}
stop = DateTime.Now.Ticks;
elapsed = (stop - start) / 1000.0 / 10000;
Console.WriteLine("Single line unfolded: " + elapsed + " seconds");
}
А вот реализация Mono.Simd относительно предыдущего варианта дает всего порядка 10% ускорения (код под катом, запускать под Mono, добавить reference на Mono.Simd.dll). Мб я что-то делаю не так? С SIMD на Intel знаком только в общих чертах.
Скрытый текст
public static void Main()
{
int N = 40;
int T = 1000000;
long start, stop;
double elapsed;
start = DateTime.Now.Ticks;
var n = N/4;
var A = new Vector4f[N*n];
var B = new Vector4f[n];
for (int i = 0; i < N; i++)
for (int j = 0; j < n; j++)
{
A[i*n+j][0] = Math.Abs(i-j*4);
A[i*n+j][1] = Math.Abs(i-j*4-1);
A[i*n+j][2] = Math.Abs(i-j*4-2);
A[i*n+j][3] = Math.Abs(i-j*4-3);
}
for (int i = 0; i < n; i++)
{
B[i][0] = i*4;
B[i][1] = i*4+1;
B[i][2] = i*4+2;
B[i][3] = i*4+3;
}
var C = new Vector4f[n];
start = DateTime.Now.Ticks;
for (int l = 0; l < T; l++)
{
var v = new Vector4f[N];
for (int i = 0; i < N; i++)
{
for (int j = 0; j < n; j++)
v[i] += A[i*n+j]*B[j];
}
// HorzontalAdd(a,b) := { a[0]+a[1], a[2]+a[3], b[0]+b[1], b[2]+b[3] }, вроде как одна инструкция SSE3for (int i = 0; i<N; i+=4)
C[i>>2] = VectorOperations.HorizontalAdd(VectorOperations.HorizontalAdd(v[i],v[i+1]),VectorOperations.HorizontalAdd(v[i+2],v[i+3]));
}
stop = DateTime.Now.Ticks;
elapsed = (stop - start) / 1000.0 / 10000;
Console.WriteLine("SIMD: " + elapsed + " seconds");
}
P.S. OS — Mac OS X; с unmanaged-вставками я не знаю стоит ли возиться, не выйдет ли маршалинг этой матрицы с вектором дороже, чем само умножение.
Скорость нужна, т.к. эти умножения (правда, с разными матрицами и разными векторами) программой будут проводиться почти подряд и в огромном числе.
CPU поддерживает вплоть до SSSE3.
Утро вечера мудренее... Вот таким образом получается более чем в 2 раза быстрее, чем предыдущий вариант, хотя и все равно в 2 раза медленнее чем на C. Интересно, нельзя ли это еще ускорить без значительной потери читабельности и, желательно, без потери безопасности?
for (int l = 0; l < T; l++)
{
Vector4f v0,v1,v2,v3;
for (int i = 0; i < N; i+=4)
{
v0 = v1 = v2 = v3 = Vector4f.Zero;
for (int j = 0; j < n; j++)
{
v0 += A[i*n+j]*B[j];
v1 += A[(i+1)*n+j]*B[j];
v2 += A[(i+2)*n+j]*B[j];
v3 += A[(i+3)*n+j]*B[j];
}
C[i>>2] = VectorOperations.HorizontalAdd(VectorOperations.HorizontalAdd(v0,v1),VectorOperations.HorizontalAdd(v2,v3));
}
}
Здравствуйте, Saidai no, Вы писали:
SN>Утро вечера мудренее... Вот таким образом получается более чем в 2 раза быстрее, чем предыдущий вариант, хотя и все равно в 2 раза медленнее чем на C. Интересно, нельзя ли это еще ускорить без значительной потери читабельности и, желательно, без потери безопасности?
Ты не правильно тему назвал. Надо было написать что то типа "С# фуфло, С++ рулез. Или история о том как C++ уделывает C#". Тогда бы народ точно набежал и принялся все жестоко оптимизировать
Сорри что не помог конкретно по теме.
Думаю стоит заменить массив на структуру описывающую матрицу.
Взятие и присвоение через индекстатор в дотнете медленнее чем в С, так как там идёт проверка на соответствие типу.
Доступ к полю быстрее.
«История жизни – это, по существу, развитие сознания, которое завуалировано морфологией.» Пьер Тейяр де Шарден
Здравствуйте, Rival, Вы писали:
Синтаксис Mono.Simd не помню, но в таком стиле.
public class/struct Matrix4
{
public float M11, M12, M13, M14,
M21, M22, M23, M23,
M31, M32, M33, M34,
M41, M42, M43, M44
}
// код перемножения
{
var row1 = new Vector4f(matrix1.M11,matrix1.M12,matrix1.M13,matrix1.M14) * new Vector4f(matrix1.M11,matrix1.M21,matrix1.M31,matrix1.M41);
var row2 = new Vector4f(matrix1.M21,matrix1.M22,matrix1.M23,matrix1.M24) * new Vector4f(matrix1.M12,matrix1.M22,matrix1.M32,matrix1.M42);
var row3 = new Vector4f(matrix1.M31,matrix1.M32,matrix1.M33,matrix1.M34) * new Vector4f(matrix1.M13,matrix1.M23,matrix1.M33,matrix1.M43);
var row4 = new Vector4f(matrix1.M41,matrix1.M42,matrix1.M43,matrix1.M44) * new Vector4f(matrix1.M14,matrix1.M24,matrix1.M34,matrix1.M44);
var returnMat = new Matrix4();
returnMat.M11 = row1.X;returnMat.M12 = row1.Y;returnMat.M13 = row1.Z;returnMat.M14 = row1.W;
// и т.д.
...
}
P.S.
сам хотел поиграться с этим делом(Mono.Simd), как раз активно матрицы множу в проекте.
Так что сообщи пожалуйста о результатах, но тут думаю дело в доступе к массивам. На тестах у меня как раз доступ к полю был быстрее раза в два.
«История жизни – это, по существу, развитие сознания, которое завуалировано морфологией.» Пьер Тейяр де Шарден
Здравствуйте, Rival, Вы писали:
R>Здравствуйте, Rival, Вы писали: R>Синтаксис Mono.Simd не помню, но в таком стиле.
Мм, ну для совсем маленьких матриц так мб удобно, но вот матрицу 32х32 так захардкодить не особо хочется =( С другой стороны, если писать для матрицы 32х32 с полностью раскрытым внутренним циклом, то выходит у меня чуть быстрее, чем обычный сишный код с развернутым на 4 эл-та строки циклом (1 млн. примерно за 1.48 и 1.57 сек. соответственно на моей машине). Если честно, думаю на этом остановиться, жаль только не нашел код на C с руками вставленным SSE...
R>P.S. R>сам хотел поиграться с этим делом(Mono.Simd), как раз активно матрицы множу в проекте. R>Так что сообщи пожалуйста о результатах, но тут думаю дело в доступе к массивам. На тестах у меня как раз доступ к полю был быстрее раза в два.
Вообще у меня была идея для этой цели использовать Nemerle с его макросами, а также посмотреть заметен ли выигрыш если сделать такой макрос, что инлайнит все векторные и матричные перемножения.
«История жизни – это, по существу, развитие сознания, которое завуалировано морфологией.» Пьер Тейяр де Шарден
Мм.. забыл добавить, хоть у меня задачи и иные, и матрицы маленькие, но
для себя планирую в дальнейшем попробовать переделать на Mono.Simd и Nemerle,
Simd — ускорит математику, а макросы Nemerle позволят более тонко контролировать отдельные операции, как раз в таких случаях. Как видите при раскрытии скорость абсолютно сопоставимая, проблема лишь в массивах дотнета, если у С индекс, это всего лишь смещение от начала, то в дотнете там ещё идут проверки на тип, что замедляет скорость, поэтому при переводе кода с С или С++ я всегда стараюсь при возможности, если производительность критична, делать значения полями, а не массивами и запись
Vector4 constrainVectors[4];
перевожу в
Vector4 constrainVector0;
Vector4 constrainVector1;
Vector4 constrainVector2;
Vector4 constrainVector3;
Естественно это не всегда такое возможно, но по идее Nemerle может убрать этот недостаток.
«История жизни – это, по существу, развитие сознания, которое завуалировано морфологией.» Пьер Тейяр де Шарден
Здравствуйте, Rival, Вы писали:
R>Взятие и присвоение через индекстатор в дотнете медленнее чем в С, так как там идёт проверка на соответствие типу.
Проверяется не тип, а попадание индекса в допустимый диапазон.
... << RSDN@Home 1.2.0 alpha 4 rev. 1305>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Здравствуйте, Saidai no, Вы писали:
SN>Мм, ну для совсем маленьких матриц так мб удобно, но вот матрицу 32х32 так захардкодить не особо хочется =(
Если под моно есть expressions — можно генерить.
P.S. Novell что, допилили рантайм? Mono SIMD Tests
Отстал от жизни.
P.P.S.Забавный топик на тему "нафига я всё это затеял" — в конце-концов "оптимизированный" вариант сливал в 20 раз. Оптимизация такая оптимизация...
P.S. Вообще-то моно производительностью не блещет, по крайней мере полгода назад моновская числодробилка под win (без simd) слегка сливала. Может, аналог
// С другой стороны, если писать для матрицы 32х32 с полностью раскрытым внутренним циклом, то выходит у меня чуть быстрее, чем обычный сишный код с развернутым на 4 эл-та строки циклом (1 млн. примерно за 1.48 и 1.57 сек. соответственно на моей машине). Если честно, думаю на этом остановиться, жаль только не нашел код на C с руками вставленным SSE...
R>>P.S. R>>сам хотел поиграться с этим делом(Mono.Simd), как раз активно матрицы множу в проекте. R>>Так что сообщи пожалуйста о результатах, но тут думаю дело в доступе к массивам. На тестах у меня как раз доступ к полю был быстрее раза в два.
Здравствуйте, Rival, Вы писали:
R>Здравствуйте, St.Rush Co., Вы писали:
SRC>>Только Unmanaged code спасет человечество!!! SRC>>Вот тут про то как давать стране угля.
R>Дать ссылку на статью где перемножают на SSE двухмерные матрицы, когда человеку нужно на managed матрицы разного размера. Бесценно!
Может таки за человека еще код написать?
Или у вас с экстраполяцией проблемы?
И вы уважаемый изначальный пост читали?
Там написано в частности: Доброго времени суток!
Пытаюсь соптимизировать умножение небольшой (40*40) матрицы из float на вектор.
Или 40*40 это уже не двухмерная матрица?
Хой вэй сафсэм забыл... там еще было слово оптимизация...
А если серьезно если во главу угла проблемы ставится оптимизация по скорости выполнения — то только unmanaged code.
За сим усе.
There are 10 kind of people who understands binary system and who don't.
Здравствуйте, St.Rush Co., Вы писали:
R>>Дать ссылку на статью где перемножают на SSE двухмерные матрицы, когда человеку нужно на managed матрицы разного размера. Бесценно!
SRC>Может таки за человека еще код написать? SRC>Или у вас с экстраполяцией проблемы?
Cразу столько вопросов.
SRC>И вы уважаемый изначальный пост читали? SRC>Там написано в частности: SRC>Доброго времени суток! SRC>Пытаюсь соптимизировать умножение небольшой (40*40) матрицы из float на вектор. SRC>
Вы тут видите форум какой? Какие вопросы? Вы тут видите в титуле топика Mono.Simd? Cи код у топикстартера уже был и гуглить он явно умеет не хуже вас.
SRC>Или 40*40 это уже не двухмерная матрица?
Вы неправильно поняли, или я неверно написал. Матрицей 2 на 2 описываются трансформации в двухмерном пространстве. В примере она для этого и используется. Хотя, конечно, это не совсем верно называть её двухмерной. Прошу прощения.
SRC>Хой вэй сафсэм забыл... там еще было слово оптимизация...
Скажите вы всегда, словно бэтмен, если человек зашёл на форум и спрашивает про оптимизацию, пихаете ему статью про ассемблер? Оно конечно средство универсальное, но...
SRC>А если серьезно если во главу угла проблемы ставится оптимизация по скорости выполнения — то только unmanaged code.
Why so serious?) Ваше мнение бесценно, вы всё сказали?
SRC>За сим усе.
Вот с самого начала бы так. Идёте в правильную сторону.
«История жизни – это, по существу, развитие сознания, которое завуалировано морфологией.» Пьер Тейяр де Шарден
Здравствуйте, Rival, Вы писали:
R>Здравствуйте, St.Rush Co., Вы писали:
R>>>Дать ссылку на статью где перемножают на SSE двухмерные матрицы, когда человеку нужно на managed матрицы разного размера. Бесценно!
SRC>>Может таки за человека еще код написать? SRC>>Или у вас с экстраполяцией проблемы?
R>Cразу столько вопросов.
SRC>>И вы уважаемый изначальный пост читали? SRC>>Там написано в частности: SRC>>Доброго времени суток! SRC>>Пытаюсь соптимизировать умножение небольшой (40*40) матрицы из float на вектор. SRC>>
R>Вы тут видите форум какой? Какие вопросы? Вы тут видите в титуле топика Mono.Simd? Cи код у топикстартера уже был и гуглить он явно умеет не хуже вас.
SRC>>Или 40*40 это уже не двухмерная матрица?
R>Вы неправильно поняли, или я неверно написал. Матрицей 2 на 2 описываются трансформации в двухмерном пространстве. В примере она для этого и используется. Хотя, конечно, это не совсем верно называть её двухмерной. Прошу прощения.
А что так сложно из умножения матрицы 2х2 на вектор сделать умножение матрицы NxN? на подходящий вектор?
Да и афинные преобразования на плоскости описываются матрицей 3 на 3...
SRC>>Хой вэй сафсэм забыл... там еще было слово оптимизация...
R>Скажите вы всегда, словно бэтмен, если человек зашёл на форум и спрашивает про оптимизацию, пихаете ему статью про ассемблер? Оно конечно средство универсальное, но...
Вот именно, что позволено ассемблеру не позволено C# но...? .Net вас на столько изнежил?
SRC>>А если серьезно если во главу угла проблемы ставится оптимизация по скорости выполнения — то только unmanaged code.
R>Why so serious?) Ваше мнение бесценно, вы всё сказали?
SRC>>За сим усе. R>Вот с самого начала бы так. Идёте в правильную сторону.
"Ты такой умный, тебе череп не жмет?" Цитата.
There are 10 kind of people who understands binary system and who don't.
Здравствуйте, St.Rush Co., Вы писали:
R>>Скажите вы всегда, словно бэтмен, если человек зашёл на форум и спрашивает про оптимизацию, пихаете ему статью про ассемблер? Оно конечно средство универсальное, но... SRC>Вот именно, что позволено ассемблеру не позволено C# но...? .Net вас на столько изнежил?
Справедлива, кстати, и обратное: что позволено C# не позволено многим другим языкам...
Здравствуйте, MxMsk, Вы писали:
MM>Здравствуйте, St.Rush Co., Вы писали:
R>>>Скажите вы всегда, словно бэтмен, если человек зашёл на форум и спрашивает про оптимизацию, пихаете ему статью про ассемблер? Оно конечно средство универсальное, но... SRC>>Вот именно, что позволено ассемблеру не позволено C# но...? .Net вас на столько изнежил? MM>Справедлива, кстати, и обратное: что позволено C# не позволено многим другим языкам...
Эт например что?
There are 10 kind of people who understands binary system and who don't.
Здравствуйте, St.Rush Co., Вы писали:
SRC>>>Вот именно, что позволено ассемблеру не позволено C# но...? .Net вас на столько изнежил? MM>>Справедлива, кстати, и обратное: что позволено C# не позволено многим другим языкам... SRC>Эт например что?
Уверен, ты слышал, что такое GC, и какие проблемы он решает.
Здравствуйте, MxMsk, Вы писали:
MM>Здравствуйте, St.Rush Co., Вы писали:
SRC>>>>Вот именно, что позволено ассемблеру не позволено C# но...? .Net вас на столько изнежил? MM>>>Справедлива, кстати, и обратное: что позволено C# не позволено многим другим языкам... SRC>>Эт например что? MM>Уверен, ты слышал, что такое GC, и какие проблемы он решает.
Ну начнем с того что C# имеет такое же отношение к GC как я к балету — то есть какое-то отношение имеется, но очень далекое. (Я примерно представляю что такое балет)
GC — фича платформы .Net и managed кода и все отношение C# к GC это то что все что написано на C# исполняется в среде с наличием GC.
Исходя из выше сказанного ваш довод — палец в небо.
There are 10 kind of people who understands binary system and who don't.