Pointer->Integer->Pointer

← →
alertus © (2005-05-27 17:36) [0]

Подскажите, пожалуйста, если я пишу так:

a:^real; p:^real; .... getmem(a,100*sizeof(real)); p:=pointer(integer(a)+0); p^:=0.347; p:=pointer(integer(a)+8); p^:=0.764; p:=pointer(integer(a)+16); p^:=0.764; ....

Похоже ли это на работу динамического массива и какова будет разница в скорости??

← →
Digitman © (2005-05-27 17:41) [1]

> Похоже ли это на работу динамического массива

нет, не похоже.

> какова будет разница в скорости

в связи с чем тебя озадачила "скорость" ?

← →
-=XP=- © (2005-05-27 17:45) [2]

Похоже. Но и только.

Лучше использовать не +0, +8, а +SizeOf(pointer) * ItemIndex

А зачем так изголяться? Чем динамические массивы не подошли?
Или конструкция типа:

{$RANGECHECKS OFF} type PRealArray = ^TRealArray; TRealArray = array[0..0] of real; var A: PRealArray; begin GetMem(A, 100 * SizeOf(real)); A^[2] := 0.764; ...

← →
alertus © (2005-05-27 17:47) [3]

Почему не похоже, ведь у меня получился массив из 100 элементов типа real, к каждому из которых я имею доступ.
И если я изначально не знаю размер массива, то я могу его задать в ходе выполнения программы (после мне его менятьт не потребуется).

Я столкнулся с программированием на Matlab, там перемножение двух матриц 300x700 элементов real занимает около 1/4 секунды, а у меня на Delphi с использованием динамических массивов - 4 сек.
Matlab написан на C++, там динамические массивы объявляются так:
float *a.

В общем я хочу ускорить операции с динамическими массивами, судя по Matlab"у это возможно.

Может быть кто-нибудь знает как это запрограммировано на Matlab"е??

← →
Digitman © (2005-05-27 17:50) [4]

> Почему не похоже

по кочану.

любой дин.тип данных предусматривает упр.структуру ... она у тебя ГДЕ ?

← →
alertus © (2005-05-27 17:50) [5]

> Лучше использовать не +0, +8, а +SizeOf(real) * ItemIndex

Да, я так и хотел сделать в дальнейшем.

А как насчет скорости или другой реализации??

← →
alertus © (2005-05-27 17:52) [6]

> любой дин.тип данных предусматривает упр.структуру ... она
> у тебя ГДЕ ?

Меня беспокоит то, что любая управляющая структура уменьшает скорость, я специально делаю все на наиболее низком уровне, хочу попробовать на asm"е это сделать...

← →
-=XP=- © (2005-05-27 17:54) [7]

Тут проблема не с динамическими массивами.
Скорее всего, у Вас алгоритм другой, нежели в MathLab.

← →
Digitman © (2005-05-27 17:58) [8]

> Меня беспокоит то, что любая управляющая структура уменьшает
> скорость

при обращении по чтению - ровно на одну-две маш.инструкции.

мизер.

> специально делаю все на наиболее низком уровне

начинать нужно со своего менеджера памяти (адаптированного под конкр.задачи), а не с динамических структур, иначе все твои усилия будут сведены на нет

> хочу попробовать на asm"е это сделать

попробуй.
тем более что садомазо нынче в моде)

← →
Lin7 (2005-05-27 18:11) [9]

> alertus © (27.05.05 17:47) [3]
> Я столкнулся с программированием на Matlab, там перемножение
> двух матриц 300x700 элементов real занимает около 1/4 секунды,
> а у меня на Delphi с использованием динамических массивов
> - 4 сек.

Может приведёшь свой код? Дело в том, что в MatLab"е интерпретатор и у меня Matlab работает медленнее, чем тот же код переписанный на Delphi, причём в разы. В новых версиях Mаtlab"а появился встроенный компилятор, но он позволяет (если не ошибаюсь) компилить matlab"овские функции в только dll.

← →
alertus © (2005-05-27 18:12) [10]

А что насчет менеджера памяти, я так понимаю, есть такой тип TMemoryManeger, он создается вместе с приложением (TApplication).
Он управляет всей памятью, которая требуется приложению, в том числе и динамическими массивами, но он проверяет не превышены ли текущие границы динамического массива и т.п.
Это, как я понимаю и есть управляющая структура, а я хочу ее обойти или поменьше использовать.
Я совсем не уверен что это все правильно, но я ищу способы ускорить мою программу.

> Скорее всего, у Вас алгоритм другой, нежели в MathLab.

Я думаю, что для перемножения матриц другого алгоритма просто не существует в природе (возможно я не прав). Я использую такой:

var m1:array[1..2,1..3] of real; m2:array[1..3,1..2] of real; mr:array[1..2,1..2] of real; temp:real; begin for i:=1 to 2 do begin for j:=1 to 2 do begin temp:=0; for k:=1 to 3 do begin temp:=temp+m1[i,k]*m2[k,j]; end; mr[i,j]:=temp; end; end; end;

Я реализовал свою небольшую прогараммку:

procedure TForm1.Button1Click(Sender: TObject); var i,j,k:integer; temp:real; t1,t2:real; pt:^real; off:integer; begin m1.w:=400; m1.h:=800; getmem(m1.pint,400*800*sizeof(real)); m2.w:=800; m2.h:=400; getmem(m2.pint,800*400*sizeof(real)); mr.w:=400; mr.h:=400; getmem(mr.pint,400*400*sizeof(real)); for i:=1 to 400 do begin for j:=1 to 400 do begin temp:=0; for k:=1 to 800 do begin pt:=pointer(integer(m1.pint)+(i-1+(k-1)*m1.w)); t1:=pt^; pt:=pointer(integer(m2.pint)+(k-1+(i-1)*m1.h)); t2:=pt^; temp:=temp+t1*t2; end; pt:=pointer(integer(mr.pint)+(i-1+(j-1)*m1.h)); pt^:=temp; end; end; end;

Она длится 2.7 секунды, уже лучше чем 4, да и размер матриц больше, только это не объективно, потому что я на другом компьютере, хотя процессоры почти одинаковые.

← →
MBo © (2005-05-27 18:16) [11]

Какой процессор?

← →
alertus © (2005-05-27 18:17) [12]

> В новых версиях Mаtlab"а появился встроенный компилятор,
> но он позволяет (если не ошибаюсь) компилить matlab"овские
> функции в только dll.

Да, это так, но, как я понимаю, если я напишу на матлабе функцию перемножения матриц и сделаю dll, то этой dll нужна другая, где реализовано само умножения, я с трудом понимаю где ее искать, и я не знаю точно как передавать параметры.

Ну и, в конце концов, я хочу написать свою функцию на Dephi.

> Дело в том, что в MatLab"е интерпретатор и у меня Matlab
> работает медленнее, чем тот же код переписанный на Delphi,
> причём в разы.

Да, это абсолютно так для циклов и программ, но если взять отдельно функцию перемножения матриц, то ситуация резко меняется в противоположную сторону.

← →
alertus © (2005-05-27 18:18) [13]

> Какой процессор?

Дома Athlon 1000, а на работе, где я сейчас - Athlon 800.

← →
Digitman © (2005-05-27 18:23) [14]

> хочу написать свою функцию на Dephi

это похвально.
и перевешивает любые иные аргументы.

размер матрицы-результата тебе известен ?

думаю - да.

а если да, то дин.структуры нафих не нужны - один раз распределил память и заполняй ее сколь угоднго "эффективно", хоть на асме, хоть на хрясме)

← →
MBo © (2005-05-27 18:41) [15]

Кроме канонического алгоритма вычисления произведения матриц, существуют и более сложные - Винограда, Штрассена. На порядок они выигрыша не дадут, а в пару раз при твоих размерах - возможно. Кроме того, с точки зрения оптимизации работы с памятью может быть эффективно предварительно транспонировать одну из матриц, чтобы обращение к памяти шло подряд, а не скачками. И еще - использование SSE-иструкций современных процессоров - при программировании на ASM или использовании соответствующих компиляторов - може привести к ускорению еще в несколько раз.

← →
begin...end © (2005-05-27 18:50) [16]

> -=XP=- © (27.05.05 17:45) [2]

> Лучше использовать не +0, +8, а +SizeOf(pointer) * ItemIndex

А причём тут SizeOf(pointer)?

← →
Verg © (2005-05-27 18:52) [17]

> Она длится 2.7 секунды, уже лучше чем 4,

Это логично. Она (вторая функция) - реализована неверно. Экономия времени достигнута отсутствием требуемого умножения смещения от указателя на sizeof(real). Реально вычисляются адреса ячеек, как будь-то они размером 1 (байт).
А вообще задумайся - обход столбца одной матрицы и строки другой делаются строго последовательно. Т.о. если уж так хочется оптимизировать, то надо от прямого индексирования, сопровождающегося "в лоб" вычислением адреса через i,j и умножением на sizeof(real) на каждом шаге, переходить на суммирование индексных смещений (наращивание на каждом шаге). Т.о. ты избавишься от операций умножения для вычислений физического адреса ячейки матрицы.

← →
-=XP=- © (2005-05-27 18:55) [18]

А причём тут SizeOf(pointer)?

Типа опечатка. Там дальше написано: SizeOf(real)

:)

← →
alertus © (2005-05-27 19:03) [19]

> а если да, то дин.структуры нафих не нужны - один раз распределил
> память и заполняй ее сколь угоднго "эффективно", хоть на
> асме, хоть на хрясме)

Размеры матриц изначально не известны на первой, ни второй, ни ризультата, но в ходе программы они не меняются.

> Она (вторая функция) - реализована неверно.

Да, я теперь заметил, торопился когда писал.

> Кроме того, с точки зрения оптимизации работы с памятью
> может быть эффективно предварительно транспонировать одну
> из матриц.

Вообще если говорить о моей программе, то у меня вторая матрица - это транспонированная первая (это аппроксимация алгоритма Ньютона для нахождения производной функции нескольких переменных от по двум переменным), а что, если используются близкие адреса, то это будет быстрее??

Всем огромное спасибо, попробую совместить все советы.

← →
begin...end © (2005-05-27 19:06) [20]

> alertus © (27.05.05 19:03) [19]

> а что, если используются близкие адреса, то это будет быстрее??

Дело не столько в близких адресах, сколько в облегчении вычисления индексов. И об этом я уже говорил Вам в предыдущей ветке.

var
a: Pointer;
p: ^Real;
begin
GetMem(a, 100 * sizeof(Real));
p := a;
p^ := 0.347;
Inc(p);
p^ := 0.764;
Inc(p);
p^ := 0.764;
...
end.

← →
Defunct © (2005-05-27 19:08) [21]

Verg © (27.05.05 18:52) [17]

Допускается же умножение индексного регистра при адресации массивов. пример:

mov EAX, [EBX + ESI*8]

← →
begin...end © (2005-05-27 19:10) [22]

> Defunct © (27.05.05 19:08) [21]

Ну и что? Речь-то не о возможности, а о скорости.

← →
Anatoly Podgoretsky © (2005-05-27 19:12) [23]

p:=pointer(integer(a)+8);
Так не допустимо, размер Real не 8, а величина переменная, но даже если бы и постоянно, то это все равно выглядит некрасиво.

← →
alertus © (2005-05-27 19:41) [24]

Да, я согласен, я думал, что sizeof(real) тормозит программу, но это как-бы константа, поэтому лучше писать
p:=pointer(integer(a)+sizeof(real));

> begin...end © (27.05.05 19:06) [20]

насчет наращивания адреса, похоже, очень дельный совет.

А еще такой вопрос:
если я по очереди обращаюсь к нескольким элементам памяти, зависит ли скорость от расстояния между этими физическими адресами??

← →
Defunct © (2005-05-27 19:48) [25]

begin...end © (27.05.05 19:10) [22]

Ну и ничего,
прежде чем сразу спорить возьми и проверь по скорости

mov eax, [ebx + ecx]
и
mov eax, [ebx + ecx*8]

оно рульно будет (С) begin...end

← →
begin...end © (2005-05-27 19:53) [26]

> Defunct © (27.05.05 19:48) [25]

А Вы, надо полагать, уже проверили?

type
TElemType = Integer;
PElemType = ^TElemType;
const
ElemsCount = 10000000;
var
a: Pointer;
p: PElemType;
T1, T2, I: Cardinal;
begin
GetMem(a, ElemsCount * sizeof(TElemType));
p := a;
T1 := GetTickCount;
for I := 0 to Pred(ElemsCount) do
PElemType(Integer(p) + I * sizeof(TElemType))^ := 1;
T1 := GetTickCount - T1;
p := a;
T2 := GetTickCount;
for I := 0 to Pred(ElemsCount) do
begin
p^ := 1;
Inc(p)
end;
T2 := GetTickCount - T2;
Caption := Format("Умножение: %d; сложение: %d", [T1, T2]);
FreeMem(a)
end.

"Чуешь Тайд?" (c) Defunct

← →
Defunct © (2005-05-27 19:55) [27]

> begin...end
> сколько в облегчении вычисления индексов.

Вот например это вообще теряет смысл, если проц. и так умеет перемножать индексные регистры непосредственно при адресации элемента массива.

т.е. доступно даже такое

mov eax, [CONST + ebx + ecx*8]
и эта команда будет выполняться одинаково быстро с командой
mov eax, [ebx]

← →
Defunct © (2005-05-27 19:57) [28]

begin...end © (27.05.05 19:53) [26]

Да я уже проверил, а тот код который вы приводите я не понимаю. Это какой-то набор значков. Не знаю что вы там в нем меряли.

function test:integer; var a : array[0..100] of byte; asm xor ecx, ecx mov eax, [ESP + ECX*8] end; function test2:integer; var a : array[0..100] of byte; asm xor ecx, ecx mov eax, [ESP + ECX] end; procedure TForm1.rClick(Sender: TObject); var i : integer; E1, E2 : Integer; begin T1 := Now; for i := 0 to 2000*1000*1000 do begin E1 := Test; end; E2 := E1; T3 := E2*T1; T2 := Now; ShowMessage("С умножением "+ FormatDateTime("nn:ss:zzz", T2 - T1)); T1 := Now; for i := 0 to 2000*1000*1000 do begin E1 := Test2; end; E2 := E1; T2 := Now; ShowMessage( "Без умножения "+ FormatDateTime("nn:ss:zzz", T2 - T1)); T2 := E2*T2; end;

Чего результаты то не привел, ну зачем же каждому компилировать. Кроме того тест желательно оптимизировать, что бы уменьши погрешность от цикла и команд вызова/возврата. это делается так

mov eax, [ESP + ECX*8]
... повторения строки от 100 раз и более
mov eax, [ESP + ECX*8]

Anatoly Podgoretsky © (27.05.05 20:12) [29]

Спасибо за метод устранения ошибки.

В общем картина такая.
1. выключил оптимизацию.

2. функция test
приняла такой вид:

xor ecx, ecx
mov eax, [0 + ESP + ECX*8]
...
mov eax, [99 + ESP + ECX*8]

3. Функция test2 такой:
xor ecx, ecx
mov eax, [ESP]
...
mov eax, [ESP]

по сотне команд в обеих функциях. Циклы остались такими же - по 2млрд итераций.

Результаты выполнения теста на P4:

1-й запуск: с умножением без умножения 44.581с 44.565с 2-й запуск с умножением без умножения 44.518с 44.518с 3-й запуск с умножением без умножения 44.518с 44.518с

Выводы постоите сами ;>

> Defunct © (27.05.05 19:57) [28]

> тот код который вы приводите я не понимаю

Сорри, но я ничего не могу с этим поделать.

> Это какой-то набор значков.

LOL. Любой листинг программного кода -- это набор значков.

> Не знаю что вы там в нем меряли.

Времена выполнения двух вариантов кода.

Ваш код я видоизменил: вместо ламерского способа измерения времени выполнения кода функцией использовал GetTickCount, хотя это тоже не лучший способ.

var i : integer; T1, T2, T3: Cardinal; E1, E2 : Integer; begin T1 := GetTickCount; for i := 0 to 2000*1000*1000 do begin E1 := Test; end; E2 := E1; T3 := E2*T1; T2 := GetTickCount; ShowMessage("С умножением: "+ IntToStr(T2 - T1)); T1 := GetTickCount; for i := 0 to 2000*1000*1000 do begin E1 := Test2; end; E2 := E1; T2 := GetTickCount; ShowMessage( "Без умножения: "+ IntToStr(T2 - T1)); T2 := E2*T2; end

Кстати, обратите внимание на количество хинтов компилятора, указывающих на выкинутые им строчки. Это свидетельствует о том, что бессмысленных значков в Вашем коде намного больше, чем в моём.

Результаты проверки таковы (на Pentium 3):

С умножением -- 30304 Без умножения -- 25947

Чуда не произошло, что мной и ожидалось.

> времени выполнения кода функцией

времени выполнения кода функцией Now

Наваял такую программу:

function writems:string; var t:TDateTime; h,m,s,ms:word; begin t:=Time; DecodeTime(t, h, m, s, ms); result:=inttostr(s)+"."+inttostr(ms); end; procedure TForm1.Button5Click(Sender: TObject); var a:^real; //311x700 b:^real; //700x311 c:^real; //311x311 i,j,k:integer; p:^real; pa,pb,pc:^real; temp:real; begin getmem(a,311*700*sizeof(real)); getmem(b,311*700*sizeof(real)); getmem(c,311*311*sizeof(real)); memo1.lines.add(writems); for i:=1 to 311 do begin for j:=1 to 311 do begin temp:=0; p:=integer(0); for k:=1 to 700 do begin pa:=pointer(integer(a)+(i-1)*311+integer(p)); pb:=pointer(integer(b)+(j-1)*311+integer(p)); temp:=temp+pa^*pb^; inc(p); end; pc:=pointer(integer(c)+(i-1+(j-1)*311)*sizeof(real)); pc^:=temp; end; end; memo1.lines.add(writems); end;

Время умножения - 1.2 с, прежний метод 3.2 с, метод с использованием a:array[0..0] - 3.0 с (до этого про 4.0 было неверно, я брал другой размер матрицы и перепутал).

т.к. у меня в программе матрица 1 это транспонированная матрица 2, то, я думаю, можно сократить еще время, т.к. у матрицы-результата под нижней диагональю зеркальное отражение того, что над верхней диагональю, но время сократиться еще не более чем в 2 раза.

Очень помогли советы
MBo © (27.05.05 18:41) [15] и
begin...end © (27.05.05 19:06) [20], всем огромное спасибо.

begin...end © (27.05.05 20:58) [31]

Я прекрасно знаю насколько объективно, именно Вы относитесь к моим постам, но в этот раз ничего у Вас не выйдет. LOL оставьте себе, раз забыли выключить оптимизацию.

> Кстати, обратите внимание на количество хинтов компилятора
Обратил - ни одного hint"a либо warning"a.

begin...end © (27.05.05 20:58) [31]

> Ваш код я видоизменил: вместо ламерского способа измерения времени выполнения кода функцией использовал GetTickCount,

Вам не стыдно такое писать?

> Defunct © (27.05.05 21:05) [34]

> Я прекрасно знаю насколько объективно, именно Вы относитесь
> к моим постам

Вы своими постами заслужили такое отношение. Поэтому смело можете сказать спасибо зеркалу.

> забыли выключить оптимизацию

Не совсем понятно, каким образом опция оптимизации может повлиять на код самих asm-функций, но, раз уж Вы об этом упомянули, я повторил тест с отключённой оптимизацией.

Результаты таковы:

С умножением -- 37974 Без умножения -- 34750

Уж и не знаю, что нужно сделать, чтобы вариант с умножением выиграл. Может, с бубном возле компьютера поплясать?

> > Кстати, обратите внимание на количество хинтов компилятора
> Обратил - ни одного hint"a либо warning"a.

Это у Вас что-то с компилятором. А может быть, Вы просто отключили показ хинтов? Приведу список хинтов, возникших на Delphi 7 (конечно, с первого раза код [28] откомпилировать не удалось -- пришлось добавить объявления перменных T1, T2 и T3):

[Hint] Unit1.pas(75): Value assigned to "T2" never used [Hint] Unit1.pas(70): Value assigned to "E2" never used [Hint] Unit1.pas(67): Value assigned to "E1" never used [Hint] Unit1.pas(58): Value assigned to "T3" never used [Hint] Unit1.pas(56): Value assigned to "E2" never used [Hint] Unit1.pas(54): Value assigned to "E1" never used

Если выключить оптимизацию, то количество хинтов уменьшается до двух, но они есть.

> Defunct © (27.05.05 21:10) [35]

Не стыдно.

Воспользовался "методом устранения ошибки" из [30]. Теперь функции содержат по 100 команд MOV: в Test -- команды вида mov eax, [I + ESP + ECX*8], где I -- целочисленные константы от 0 до 99, а в Test2 -- mov eax, [ESP + ECX].

В связи с малой производительностью процессора пришлось уменьшить число итераций до 200 миллионов, иначе я бы заснул в ожидании результатов. А результаты впечатляют:

С умножением -- 84520 Без умножения -- 46480

"Выводы построите сами" (c) Defunct

Вот оно влияние цикла, вызова и возврата из подпрограммы. А казалось бы безобидный с виду тест.

Anatoly Podgoretsky © (27.05.05 22:27) [38]

Нет скорее это не влияние цикла вызова и возврата а особенность работы P3, для которого более сложная иструкция (читать более большая), тратит больше времени на погдотовку, потому что за результат [30] я ручаюсь со всей ответственностью.

begin...end © (27.05.05 21:37) [36]
Промолчу, если вы заметили, я уже стараюсь с вами не спорить.

begin...end © (27.05.05 22:12) [37]

Предполагаю, что на P3 тормозит не умножение индекса, а наличие постоянной константы, которое значительно раздувает размер команды. Для получение объективного результата проверьте в равных условиях команды

mov eax, [I + ESP + ECX*8]
и
mov eax, [I + ESP + ECX]

т.е. сугубо наличие умножения индекса.

> Defunct © (27.05.05 21:10) [35] [Новое
>сообщение][Ответить]
>begin...end © (27.05.05 20:58) [31]
>
> > Ваш код я видоизменил: вместо ламерского способа
> измерения времени выполнения кода функцией использовал
>GetTickCount,
>
> Вам не стыдно такое писать?

Действительно ламерство. Если б ты предложил QueryPerformanceTimer, то это дело. Но TDateTime с сопутствующими - истинная черепаха.
Твоя проблема, ИМХО, в том, что глубочайшие знания у тебя соседствуют с пробелами чуть ли не в табличке умножения.

Pointer->Integer->Pointer Найти похожие ветки