| Форумы
ЧАТ |
Орешник |
|
| Форумы -» | Основная («Начинающим»)/ Базы / WinAPI / Компоненты / Сети / Media / Игры / Corba и COM / KOL / FreePascal / .Net / Прочее / RSDN.ORG |
|
| ||
|
|
Новости |
Поиск |
FAQ |
Статьи |
Книги |
Новости VCL
| | Форумы ЧАТ |
Орешник |
|
| |||
| |||
| |||
« предыдущая ветвь | форум | следующая ветвь »
Быстрый Swap,
main © (2008-11-15 20:02:00)Нужна максимально быстрая процедура, которая меняет местами содержимое блоков памяти. Что-то вроде:
procedure QuickSwap( Source,Dest :pointer; count :integer );
begin
???
end;
Почему такой процедуры нет среди стандартных? О_о
Германн (2008-11-18 03:44:00) [21]
> main © (18.11.08 03:35) [50]
>
> О спасибо! Я все понял! Наконец-то до меня дошло, что лучше
> сортировать указатели или индексы а не данные!
>
Да не за что.
P.S. Все прочие высказывания оставь себе. Может быть позже поймёшь их суть!
main (2008-11-18 03:35:00) [22]О спасибо! Я все понял! Наконец-то до меня дошло, что лучше сортировать указатели или индексы а не данные!
Нет, ну что за снобизм, а? Знаете, это напоминает ситуацию с goto. Мудрый дядя преподаватель когда-то там сказал на 1 курсе - goto зло, и вот извращаются, придумывают как не использывать этот самый goto. Никто им и не пользуется этим goto, но иногда ж все-таки бывает, ведь так?
Все вот эти приссказки и ПЫСЫ, про то что лучше тусовать указатели, были вовсе и не обязательны, не бойтесь, никто про вас плохо не подумает.
Я там выше писал, что "редко, но иногда бывает необходимо ...", если быть точнее, это вовсе и не необходимость какая-нибудь. Это такая фича, что если данные расположить определенным образом, то становятся доступны некие новые оптимизации. Ну например, если выровнить данные по 16 байт, то можно использывать инструкции SSE. Если пару зависимых юнитов расположить последовательно в памяти, то можно получить доступ к полям др. юнита как к своим. Например, командир - его отряд, охранник - то что он охраняет, расса - все юниты этой рассы, и т.д. ... ( юнит - это какой-то солдатик в игре )
Это я сейчас написал просто так, чисто пофлеймить ...
:)))
Servy (2008-11-17 03:30:00) [23]Еще немного мыслей по поводу того, что без swap'а можно обойтись практически всегда.
> Ну вот допустим реальный и понятный пример, загрузил картинку
> ( 2024х2024 ), нужно ее перевернуть - верх/низ. Построчно
> меняю данные, размер строки 2024 * 4 байта, и так 1024 обмена.
1. Если загрузка в видеопамять, то можно преобразовать текстурные координаты при отображении картинки таким образом, чтобы она отображалась вверх тормашками.
2. Можно изменить процесс загрузки, и сразу читать очередную строку в нужную область памяти.
3. Если 1 и 2 по каким-то причинам отклонены, то выделить память еще под одну такую картинку, и скопировать туда строки в нужном порядке, и уничтожить первую картинку; очевидно, это будет быстрее, чем Swap с помощью 3х Move на каждую строку с промежуточным буфером (если пренебречь временем на выделение нового участка памяти); возможно, это будет быстрее, чем разнообразные ассемблерные извращения, к тому же, здесь сложнее ошибиться, и остается видимость переносимости.
sniknik (2008-11-17 02:37:00) [24]> Для сравнения на моём ПК:
и у тебя наверняка интел, т.к. на моем AMD все наоборот
1 способ (xor) 437мс
2 способ (move) 360мс
3 способ (с char) 250мс
4 другое (ниже) 203мс
> Честно говоря, не могу придумать, где разница в обработке в памяти сотни мегабайт в 100мсек может быть критичной.
аналогично. тем более, что эта разница может из выигрышной легко стать проигрышной...
и ещё более, "тем более" что при выборе другого пути решения задачи вся эта фигня может стать совсем не нужной.
немного модифицированный 3 вариант, сделано из расчёта чтобы обрабатывались "родные" 32битные значения (для 64 разрядной операционки очевидно будут быстрее 64битные)
procedure TForm1.Button4Click(Sender: TObject);
const
size=1024*1024*10*10;
var
t1, t2: Cardinal;
p1, p2: PChar;
i: integer;
w1: array of dword absolute p1;
w2: array of dword absolute p2;
w3: dword;
begin
GetMem(p1,size);
GetMem(p2,size);
FillChar(p1[0],Size,1);
FillChar(p2[0],Size,2);
t1 := GetTickCount;
for i:= (Size-1) div 4 downto 0 do
begin
w3 := w1[i];
w1[i]:= w2[i];
w2[i]:= w3;
end;
t2 := GetTickCount;
Label4.Caption := IntToStr(t2-t1);
FreeMem(p1);
FreeMem(p2);
end;
main (2008-11-17 02:36:00) [25]Упс, про смайлики забыл совсем. :)
main (2008-11-17 02:33:00) [26]
procedure qSwap64( PData1,PData2 :pointer; Count : Integer );
asm
dd $DF03E9C1,$DF2ADF28,$833ADF38,$C28308C0,$EF774908
end;
procedure TForm1.Button4Click(Sender: TObject);
const
size=1024*1024*10*10;
var
t1,t2: Cardinal;
p1,p2: PChar;
p3: Char;
i: integer;
begin
GetMem(p1,size);
GetMem(p2,size);
FillChar(p1[0],Size,1);
FillChar(p2[0],Size,2);
t1:= GetTickCount;
qSwap64( p1 , p2 , Size );
t2:= GetTickCount;
Label1.Caption:= IntToStr(t2-t1);
FreeMem(p1);
FreeMem(p2);
end;
main (2008-11-17 02:25:00) [27]Мой вариант:
procedure qSwap64( PData1,PData2 :pointer; Count : Integer );
asm
dd $DF03E9C1,$DF2ADF28,$833ADF38,$C28308C0,$EF774908
end;
Count должено быть кратным 8.
Тын-Дын (2008-11-17 01:50:00) [28]Честно говоря, не могу придумать, где разница в обработке в памяти сотни мегабайт в 100мсек может быть критичной.
Тын-Дын (2008-11-17 01:47:00) [29]
> sniknik © (17.11.08 00:34) [42]
Ну не знаю.
Для сравнения на моём ПК:
1 способ (xor) 218мс
2 способ (move) 343мс
3 способ (с char) 234мс
sniknik (2008-11-17 00:34:00) [30]Тын-Дын © (16.11.08 23:34) [41]
а стоит ли "мудрить"? у меня простейшее
procedure TForm1.Button4Click(Sender: TObject);
const
size=1024*1024*10*10;
var
t1,t2: Cardinal;
p1,p2: PChar;
p3: Char;
i: integer;
begin
GetMem(p1,size);
GetMem(p2,size);
FillChar(p1[0],Size,1);
FillChar(p2[0],Size,2);
t1:= GetTickCount;
for i:= (Size-1) downto 0 do
begin
p3 := p1[i];
p1[i]:= p2[i];
p2[i]:= p3;
end;
t2:= GetTickCount;
Label1.Caption:= IntToStr(t2-t1);
FreeMem(p1);
FreeMem(p2);
end;
дает лучшие результаты...
насколько лучше зависит от range checking, ну и наверное, подозреваю, от типа процессора, но это уже проверить не могу.
Тын-Дын (2008-11-16 23:34:00) [31]
> main ©
Попробуй метод, реализованный в Button2Click.
procedure TForm1.Button2Click(Sender: TObject);
const
size=1024*1024*10*10;
var
t1,t2: Cardinal;
p1,p2: PChar;
pInt1,pInt2: pInteger;
i: integer;
begin
GetMem(p1,size);
GetMem(p2,size);
FillChar(p1[0],Size,1);
FillChar(p2[0],Size,2);
pInt1 := Pointer(p1);
pInt2 := Pointer(p2);
t1 := GetTickCount;
for i := 0 to (Size-1) div 4 do
begin
pInt1^ := pInt1^ xor pInt2^;
pInt2^ := pInt1^ xor pInt2^;
pInt1^ := pInt1^ xor pInt2^;
pInt1 := Pointer(Integer(pInt1)+4);
pInt2 := Pointer(Integer(pInt2)+4);
end;
t2 := GetTickCount;
Label1.Caption := IntToStr(t2-t1);
FreeMem(p1);
FreeMem(p2);
end;
Тоже самое, но с move:
procedure TForm1.Button3Click(Sender: TObject);
const
size=1024*1024*10*10;
var
t1,t2: Cardinal;
p1,p2: PChar;
p3: PChar;
begin
GetMem(p1,size);
GetMem(p2,size);
FillChar(p1[0],Size,1);
FillChar(p2[0],Size,2);
t1 := GetTickCount;
GetMem(p3,size);
Move(p1[0],p3[0],Size);
Move(p2[0],p1[0],Size);
Move(p3[0],p2[0],Size);
t2 := GetTickCount;
Label1.Caption := IntToStr(t2-t1);
FreeMem(p1);
FreeMem(p2);
FreeMem(p3);
end;
tesseract (2008-11-16 21:46:00) [32]
> хранить указатели на данные, их же и сортировать.
См Связанный двунаправленный список . ИМХО его ты и пытаешься реализовать.
Sapersky (2008-11-16 17:16:00) [33]Посмотрите, какие оптимизации используются в FastCode Move Challenge:
http://fastcode.sourceforge.net/challenge_content/Move.html
Задача-то в общем сходная.
Если у вас BDS2006 или более новая версия, оптимизированный вариант Move с FastCode должен быть уже встроен в system.pas.
Хотя, конечно, если производительность упирается в move или swap - в консерватории что-то не так...
Ruzzz (2008-11-16 15:59:00) [34]procedure QuickSwap(PData1,PData2 :pointer; count :integer );
begin
???
end;
а так не пойдет? :)
procedure QuickSwap(var PData1, PData2 :pointer);
var
temp: pointer;
begin
temp := PData1;
PData1 := PData2;
PData2 := temp;
end;
я имею ввиду, что сожет пересмотреть логику программы? хранить указатели на данные, их же и сортировать.
sniknik (2008-11-16 15:12:00) [35]> Как раз задача - оптимизировать процесс.
видимо я по другому понимаю что такое задача.
вот например задача - "перейти улицу". это задача. более общая для которой первая будет подзадачей это - "сходить за хлебом в булочную на другой стороне улицы". и ещё более общая - "сделать что то, чтобы хлеб к обеду был на столе".
а вот - "перебежать улицу на красный свет в неположенном месте", это уже путь решения, и "сделать перебег безопасным, и занимающим минимум времени" т.е. оптимизировать процесс это уже не задача, это уже поиск алгоритма для выполнения этого выбранного пути.
т.е. разница между "перейти улицу" и "перебежать на красный" в том что одно это цель(задача), а другое реализация(путь решения).
и да, конечно, можно и "оптимизировать процесс" рассматривать как задачу, но только для решения основной ("перейти улицу"/"сходить за хлебом"/"хлеб на столе") она довольно бессмысленна, вот будешь ты тут рассчитывать время выхода, скорость движения, чтобы попасть не в час пик, т.е. удобное время для "перебега" и т.д. т.е. сокращать время которое для него потребуется, а ведь можно пойти вообще другим путём, и например заказать хлеб по интернету... сократив своё время похода до 0, и сделав вообще ненужными все подзадачи.
Тын-Дын (2008-11-16 14:05:00) [36]
> это вообще не задача,
Ну почему не задача? Как раз задача - оптимизировать процесс.
> main © (16.11.08 05:32) [32]
Обрати внимание - как сказал MBo в [33] для оптимизации нужны точные условия. В общем случае задача не решается.
Хитрий Лис (2008-11-16 13:23:00) [37]Давненько в одной ветке столько голубых значков небыло :) зацепило таки...
sniknik (2008-11-16 11:29:00) [38]> Не понимаю я. Вроде ясно написал, отсортировать по определенным приоритетам массив рекордов.
> Что, это разве не "конкретная задача"?
это вообще не задача, это путь решения, твой путь, возможно неверный (почему никто и не хочет его "разрабатывать").
задача это то что делается, а не каким образом, и возможно, именно для задачи, не только сортировка но и вообще массив рекордов не понадобится... при другом алгоритме решения.
MBo (2008-11-16 10:39:00) [39]Всё-таки давай конкретное условие задачи с типом записей и их примерным количеством, тогда посмотрим, как можно оптимизировать
main (2008-11-16 05:32:00) [40]
> Германн © (16.11.08 01:03) [26]
>
> > ... но ... редко но бывает что нужно именно данные обменять
>
> > ( ну бывает такое ).
>
> Тогда проясни "твою конкретную задачу". Словосочетания типа
> "редко но бывает что нужно" не способствуют получению наилучшего
> ответа-решения.
Не понимаю я. Вроде ясно написал, отсортировать по определенным приоритетам массив рекордов. Что, это разве не "конкретная задача"?
Если Вам интересно зачем, скажу, так потом в целом все быстрее работает. Подчеркну, это - не вообще, а конкретно у меня и конкретно в этой программе ( так например я получаю доступ к полям другого юнита как к своим ).
| |
Страницы: 