Здравствуйте, Serginio1, Вы писали:
S>Здравствуйте, Pavel Dvorkin, Вы писали:
S> Кстати а не проще перевернуть b, получишь все премущества DDR памяти ????
А я и так ее переворачива. Почитай внимательно мое первое сообщение. И все преимущества были
S> раз он квадратный
PD>Не знаю, что он там оптимизировал, но время без изменений.
Дело в том, что в циклах при явном указании что индекс меньше размера массива, проверки на выход за границы не происходит, там где это невозможно будет происходить проверка. Поэтому ситуацию с а он оптимизировал, а с b не шмог.
temp = 0;
float[] aa=a[i];
for( k = 0; k < aa.Length; k++)
temp += аа[k] * b[k][j];
... << RSDN@Home 1.1.4 stable rev. 510>>
и солнце б утром не вставало, когда бы не было меня
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>Здравствуйте, Serginio1, Вы писали:
S>>Здравствуйте, Pavel Dvorkin, Вы писали:
S>> Кстати а не проще перевернуть b, получишь все премущества DDR памяти ????
PD>А я и так ее переворачива. Почитай внимательно мое первое сообщение. И все преимущества были
А для C++ побарабану. Странно
... << RSDN@Home 1.1.4 stable rev. 510>>
и солнце б утром не вставало, когда бы не было меня
Здравствуйте, Serginio1, Вы писали:
S> А для C++ побарабану. Странно
Веренее здесь явно должен быть лимитирующим процессом промах в кэше к b[k][i]
То даже при обращении к b[k].length (имеем два промаха) разительна такая разница между C++, т.к. там без промахов ну никак не обойтись
... << RSDN@Home 1.1.4 stable rev. 510>>
и солнце б утром не вставало, когда бы не было меня
Здравствуйте, Serginio1, Вы писали:
S>Здравствуйте, Pavel Dvorkin, Вы писали:
PD>>Извини, не согласен.
S>Для интереса смнимизируй приложение и разверни и посмотри на память до и после.
Не стоит. Свободно 400+ Мбайт, а все это занимает 16 Мб. Программа практически резидентна в памяти
S> Но для Net однозначно памяти используется больше.
Ну не знаю. Я имею в виду данный процесс, а что там кроме него...
Здравствуйте, Pavel Dvorkin, Вы писали:
S>> Но для Net однозначно памяти используется больше.
PD>Ну не знаю. Я имею в виду данный процесс, а что там кроме него...
Так не забывай про джиттер, плюс различие в менеджерах памяти (резервирование откоммиченной памяти) итд.
Кроме того, ситуация может быть иной, когда из всего приложения используется малая доля типов и соответственно приложение не полностью джиткомпилится в отличие от натива
... << RSDN@Home 1.1.4 stable rev. 510>>
и солнце б утром не вставало, когда бы не было меня
PD> for( k = 0; k < nSize; k++)
PD> temp += a[i][k] * b[k][j];
Выделенная жирным операция и для плюсов будет дорога, а для дотнета она дорога в квадрате. Связано это с несколькими факторами, от слабого оптимизатора, до райт-барьера.
Так что перепиши свой алгоритм, чтобы проходил массив последовательно. Ну, и как дополнение в for проверки лучше делать на длинну массва который фором дргается.
ЗЫ
Кстати, твой код на моей машине показывает 16 секунд. Так что более чем на треть чем на твоей плюсовый.
ЗЗЫ
Ты как раз нашел случай, где ансэйф может нихило помочь. Очень похожая задача рассматривалась вот здесь
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>Спасибо, это я понимаю. Да, собственно говоря, и результаты при расположении по столбцам вполне приличные по сранению с unmanaged code, даже очень. Мой вопрос не в этом — а именно для этого варианта что-то можно сделать ? Если не смогу я тначе хранить и не хочу все же в unsafe выходить ? Выход в unsafe — это все же, что ни говори, нарушение приличий, как мне тут долго и упорно объясняли.
+1
ЗЫ
Кстати, привел бы код продольного прохода... Думаю его можно еще ускорить.
... << RSDN@Home 1.2.0 alpha rev. 618>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, GlebZ, Вы писали:
GZ>Здравствуйте, Pavel Dvorkin, Вы писали:
GZ>А так сколько получается?
<skipped>
23 секунды для Release. В общем, сравнимо (чуть лучше), чем для прямоугольной матрицы. Но не всегда можно матрицу одним куском держать.
Я не спорю, алгоритм, что я привел, далек от оптимальности (кстати, и на С++ его тоже можно пооптимизировать). Не в этом дело, а в том, что все же поведение его несколько ненормально ИМХО.
>а для дотнета она дорога в квадрате. Связано это с несколькими факторами, от слабого оптимизатора, до райт-барьера.
А что такое райт-барьера, если не секрет ?
VD>Так что перепиши свой алгоритм, чтобы проходил массив последовательно.
Влад, то, что этот алгоритм можно переписать, чтобы массив b проходился последовательно, я прекрасно понимаю. Его еще несколькими способами можно переписать. Не в этом вопрос, а в том, что я на ровном месте обнаружил несколько необычную зависимость. А не всегда алгоритм можно так переписать. К примеру, нахождение собственных чисел и собственных векторов так легко не перепишется...
>Ну, и как дополнение в for проверки лучше делать на длинну массва который фором дргается.
Т.е вместо
for(j = 0; j < nSize; j++)
писать что-то вроде
for(j = 0; j < a[j].Length; j++)
А что это даст ?
VD>ЗЫ
VD>Кстати, твой код на моей машине показывает 16 секунд. Так что более чем на треть чем на твоей плюсовый.
Ну , с такими аргументами я спорить не могу. ИМХО где-то у нас на полке старая 386 машина пылится. Пойду сейчас, найду ее , и если она работает, зафурычу этот алгоритм в DOS на BC++ 3.1, вот тогда уж точно C# победит с фантастическим отрывом!
А если серьезнее — странно. Какая у тебя машина ?
Кстати, просьба ко всем, кто это читает и имеет 10 минут свободного времени. Пропустите мой тест (самый первую программу на С# из http://www.rsdn.ru/Forum/Message.aspx?mid=1408480&only=1
) и сообщите время, ну и характерстики PC. А то, может, у меня что-то с FrameWork не в порядке (с машиной — не может быть, тест С++ проходит нормально), а я тут глубокомысленные выводы делаю
VD>ЗЗЫ
VD>Ты как раз нашел случай, где ансэйф может нихило помочь.
Влад, если можешь — объясни, как тут unsafe применить. Я уже несколько человек просил, никто не отзывается. Только не модифицируй алгоритм, т.е. матрица b по строкам. Я не могу понять, как это сделать. Рихтер утверждает, что указатели можно применять к массивам простых типов, а здесь, черт побери, массив массивов!
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>Влад, то, что этот алгоритм можно переписать, чтобы массив b проходился последовательно, я прекрасно понимаю. Его еще несколькими способами можно переписать. Не в этом вопрос, а в том, что я на ровном месте обнаружил несколько необычную зависимость. А не всегда алгоритм можно так переписать. К примеру, нахождение собственных чисел и собственных векторов так легко не перепишется...
Позволю себе лирическое отступление. Когда я учился на 2-м курсе мехмата, то был у нас такой замечательный предмет под названием "Практикум на ЭВМ". Как раз операций над матрицами (разложения всякие, поиск собственных векторов итп) пришлось проделать на нем немало. Плюс еще под MPI переписывать. В общем, полезное было занятие Особенно было весело, когда того, чтобы задача была принята нужно было укладываться в (весьма жесткие) рамки по времени работы и точности.
Так вот, указанные приемы вроде расположения матрицы m \times n в виде линейного массива размером m*n (причем обходить элементы нужно в правильном порядке, чтобы процу не пришлось загружать по новой строке кеша на каждое обращение) -- все они очень даже помогают и их приходится применять.
В C# специфики становится больше из-за bound checks и write-barrier.
PD>Т.е вместо PD>for(j = 0; j < nSize; j++) PD>писать что-то вроде PD>for(j = 0; j < a[j].Length; j++) PD>А что это даст ?
Есть гипотеза, что в данном случае JIT распознает конструкцию прохода по массиву и сделает bound check elimination.
PD>Влад, если можешь — объясни, как тут unsafe применить. Я уже несколько человек просил, никто не отзывается. Только не модифицируй алгоритм, т.е. матрица b по строкам.
Отчего же не модифицировать? Тебе нужна скорость или что?
В общем, если бы такая задача возникла у меня на практике, то первое, что я бы сделал -- попробовал переписать бы в unsafe. Конечно, способ хранения матрицы при этом нужно избирать линейный.
PD> float[,] a, b, c;
PD> int i,j,k,nSize = 1000;
PD> float temp;
PD> DateTime nTimeStart = DateTime.Now;
PD> a = new float[nSize,nSize];
PD> for(i = 0; i < nSize; i++)
PD> for(j = 0; j < nSize; j++)
PD> a[i,j] = 1;
PD> b = new float[nSize, nSize];
PD> for(i = 0; i < nSize; i++)
PD> for(j = 0; j < nSize; j++)
PD> b[i,j] = 1;
PD> c = new float[nSize,nSize];
PD> for(i = 0; i < nSize; i++)
PD> {
PD> for(j = 0; j < nSize; j++)
PD> {
PD> temp = 0;
PD> for( k = 0; k < nSize; k++)
PD> temp += a[i,k] * b[k,j];
PD> c[i,j] = temp;
PD> }
PD> }
PD>
Что то вроде такого (ghjie ghjotybz pf jib,rb). Это же можно применть и для джагед массивов
for(i = 0; i < nSize; i++)
{
for(j = 0; j < nSize; j++)
{
temp = 0;
fixed(float* aa=&а[i],float* bb=&b[0,j])
{
for( k = 0; k < nSize; k++, аа++, b+=nSize)
temp += *aa * *b;
}
c[i,j] = temp;
}
}
... << RSDN@Home 1.1.4 stable rev. 510>>
и солнце б утром не вставало, когда бы не было меня
Здравствуйте, Mab, Вы писали:
PD>>Влад, если можешь — объясни, как тут unsafe применить. Я уже несколько человек просил, никто не отзывается. Только не модифицируй алгоритм, т.е. матрица b по строкам. Mab>Отчего же не модифицировать? Тебе нужна скорость или что?
Мне в данном случае просто хочется понять, можно ли unsafe применить в исходном коде. Больше ничего. Я не понимаю, как это сделать, вот и спросил.