Быстрый Swap,

← →
tesseract © (2008-11-16 21:46) [40]

> хранить указатели на данные, их же и сортировать.

См Связанный двунаправленный список . ИМХО его ты и пытаешься реализовать.

← →
Тын-Дын © (2008-11-16 23:34) [41]

> 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;

← →
sniknik © (2008-11-17 00:34) [42]

Тын-Дын © (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-17 01:47) [43]

> sniknik © (17.11.08 00:34) [42]

Ну не знаю.

Для сравнения на моём ПК:
1 способ (xor) 218мс 2 способ (move) 343мс 3 способ (с char) 234мс

← →
Тын-Дын © (2008-11-17 01:50) [44]

Честно говоря, не могу придумать, где разница в обработке в памяти сотни мегабайт в 100мсек может быть критичной.

← →
main © (2008-11-17 02:25) [45]

Мой вариант:

procedure qSwap64( PData1,PData2 :pointer; Count : Integer );
asm
dd $DF03E9C1,$DF2ADF28,$833ADF38,$C28308C0,$EF774908
end;

Count должено быть кратным 8.

← →
main © (2008-11-17 02:33) [46]

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:36) [47]

Упс, про смайлики забыл совсем. :)

← →
sniknik © (2008-11-17 02:37) [48]

> Для сравнения на моём ПК:
и у тебя наверняка интел, т.к. на моем 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;

← →
Servy © (2008-11-17 03:30) [49]

Еще немного мыслей по поводу того, что без swap"а можно обойтись практически всегда.

> Ну вот допустим реальный и понятный пример, загрузил картинку
> ( 2024х2024 ), нужно ее перевернуть - верх/низ. Построчно
> меняю данные, размер строки 2024 * 4 байта, и так 1024 обмена.

1. Если загрузка в видеопамять, то можно преобразовать текстурные координаты при отображении картинки таким образом, чтобы она отображалась вверх тормашками.
2. Можно изменить процесс загрузки, и сразу читать очередную строку в нужную область памяти.
3. Если 1 и 2 по каким-то причинам отклонены, то выделить память еще под одну такую картинку, и скопировать туда строки в нужном порядке, и уничтожить первую картинку; очевидно, это будет быстрее, чем Swap с помощью 3х Move на каждую строку с промежуточным буфером (если пренебречь временем на выделение нового участка памяти); возможно, это будет быстрее, чем разнообразные ассемблерные извращения, к тому же, здесь сложнее ошибиться, и остается видимость переносимости.

← →
main © (2008-11-18 03:35) [50]

О спасибо! Я все понял! Наконец-то до меня дошло, что лучше сортировать указатели или индексы а не данные!

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

Все вот эти приссказки и ПЫСЫ, про то что лучше тусовать указатели, были вовсе и не обязательны, не бойтесь, никто про вас плохо не подумает.

Я там выше писал, что "редко, но иногда бывает необходимо ...", если быть точнее, это вовсе и не необходимость какая-нибудь. Это такая фича, что если данные расположить определенным образом, то становятся доступны некие новые оптимизации. Ну например, если выровнить данные по 16 байт, то можно использывать инструкции SSE. Если пару зависимых юнитов расположить последовательно в памяти, то можно получить доступ к полям др. юнита как к своим. Например, командир - его отряд, охранник - то что он охраняет, расса - все юниты этой рассы, и т.д. ... ( юнит - это какой-то солдатик в игре )

Это я сейчас написал просто так, чисто пофлеймить ...

:)))

← →
Германн © (2008-11-18 03:44) [51]

> main © (18.11.08 03:35) [50]
>
> О спасибо! Я все понял! Наконец-то до меня дошло, что лучше
> сортировать указатели или индексы а не данные!
>

Да не за что.
P.S. Все прочие высказывания оставь себе. Может быть позже поймёшь их суть!

← →
Германн © (2008-11-18 04:10) [52]

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

???
И кто-то тут упоминал термин "снобизм"!
?
И про "инструкции SSE"!

← →
@!!ex © (2008-11-18 09:51) [53]

> Знаете, это напоминает ситуацию с goto. Мудрый дядя преподаватель
> когда-то там сказал на 1 курсе - goto зло, и вот извращаются,
> придумывают как не использывать этот самый goto. Никто
> им и не пользуется этим goto, но иногда ж все-таки бывает,
> ведь так?

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

> Ну например, если выровнить данные по 16 байт, то можно
> использывать инструкции SSE.

SSE прекрасно работает и с невыровненными данными.

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

Это тоже повод для увольнения.
Костыли в коде, с 90% вероятностью приведут к трудно обнаружимым багам.

← →
sniknik © (2008-11-18 10:05) [54]

> Я там выше писал, что "редко, но иногда бывает необходимо ..."
но ты так и не показал вариант когда это действительно необходимо... даже притянутый за уши (не по теме) переворот картинки как оказалось можно делать без этого.
а раз нет реального обоснования все твои "но иногда бывает необходимо" воспринимаются как "я ни хрена в этом не понимаю". ([50] пост не исключение)

> Если пару зависимых юнитов расположить последовательно в памяти, то можно получить доступ к полям др. юнита как к своим.
книжку не хочешь написать - "ООП глазами хакера, или делаем наследника своими руками и через ж..."?
будет пользоваться популярность... по аналогии с "дельфи глазами хакера". тебя не будут любить в определенных кругах, но для разных поклонников, ламеров это будет своего рода откровением...

← →
Anatoly Podgoretsky © (2008-11-18 10:16) [55]

> sniknik (18.11.2008 10:05:54) [54]

Делаем наследника без рук, тут или то, или то.

← →
Тын-Дын © (2008-11-18 11:51) [56]

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

Бред какой.

← →
{RASkov} © (2008-11-18 11:59) [57]

Бедный ГёуТу :)
Один раз его не правильно охарактеризовали, и все.... теперь увольнять хотят из-за этого.... А ведь просто сами не умеют готовить кошек...)
В некоторых случаях лучше goto использовать чем мудрить с процедурами.... и это правильно.
Ибо неумелое использование всего остального, кроме goto - точно так же вредно...

← →
@!!ex © (2008-11-18 12:59) [58]

> [57] {RASkov} © (18.11.08 11:59)

Пример, плиз.

← →
{RASkov} © (2008-11-18 13:18) [59]

> [58] @!!ex © (18.11.08 12:59)

Думаешь я сам постоянно им(goto) пользуюсь, чтоб так сходу пример грамотный нарисовать....) Вот как будет пример, так сразу покажу...
Но скажу точно, что я им пользуюсь(т.е. пользовался) и ничего плохого в этом не вижу... :)

← →
@!!ex © (2008-11-18 13:48) [60]

> [59] {RASkov} © (18.11.08 13:18)

за последнии три года работы, я гото видел один раз. В блоке шифрования данных. Вот там оно уместно, т.к. позволяет усложнить работу хакера, который будет дизассемблировать код.
Где еще уместно использовать гото, я не представляю. Хотя много кода видел, в том числе и больших серьезных проектов.

← →
Riply © (2008-11-18 17:52) [61]

> [54] sniknik © (18.11.08 10:05)
> Я там выше писал, что "редко, но иногда бывает необходимо ..."
> но ты так и не показал вариант когда это действительно необходимо...
> даже притянутый за уши (не по теме)

pSource и pDist в разных адресных пространствах :)

← →
sniknik © (2008-11-18 18:59) [62]

> pSource и pDist в разных адресных пространствах :)
блин, ну как дети, честное слово...
и где же тут swap, если прямо из названия - одно источник, другое приемник? таких то примеров пруд пруди. в любой проге, даже без приплетания "разных адресных пространств".

Удалено модератором

> sniknik © (18.11.08 18:59) [62]
> > pSource и pDist в разных адресных пространствах :)блин,
> ну как дети, честное слово...и где же тут swap, если прямо
> из названия - одно источник, другое приемник? таких то примеров
> пруд пруди. в любой проге, даже без приплетания "разных
> адресных пространств".

Что не так? Я ж там сразу и поправился.

> main © (15.11.08 20:27) [2]
> ...
> Я немного не правильно написал:
> procedure QuickSwap( PData1,PData2 :pointer; count :integer );
> begin
> ???
> end;

А в 0 посте был просто заголовок по памяти, по аналогии с move.

Что прицепились то к этой картинки? Повторяю, мне нужно это вовсе не чтоб картинки переворачивать. Но уж если продолжить про картинку, то вот реальный кусок кода, именно так как там сейчас есть.

Второй вариант этой функции
1) Меньше по размеру? Да, меньше.
2) Чисто визуально, логика понятней? Да, понятней.
3) Работает быстрее? Да, быстрее.

Теперь вопрос, почему я не должен юзать этот самый swap?
Потом, метод TTexture.Turn мне нужен в любом случае, не только при загрузке, есть еще генератор текстур, который его юзает.

... //procedure TTexture.Turn; //var // j,i,L,BaseAdr :integer; // TempBuffer :array[0..2047] of integer; //begin // // L := n * Width; // if L > SizeOf( TempBuffer ) then Exit; // BaseAdr := integer(Data); // // for j := 0 to ( Height div 2 ) - 1 do // begin // i := Height - 1 - j; // move( pointer( BaseAdr + j * L )^ , TempBuffer , L ); // move( pointer( BaseAdr + i * L )^ , pointer( BaseAdr + j * L )^ , L ); // move( TempBuffer , pointer( BaseAdr + i * L )^ , L ); // end; // //end; procedure TTexture.Turn; var j,L,A1,A2 :integer; begin L := n * Width; A1 := integer(Data); A2 := A1 + ( Height - 1 ) * L; for j := 0 to ( Height div 2 ) - 1 do qSwap64( pointer( A1 + j * L ) , pointer( A2 - j * L ) , L ); end; ...

> main © (18.11.08 19:25) [63]
> Удалено модератором <Цитата>
>
>
> main © (18.11.08 19:26) [64]
> Удалено модератором

Не, не, не!!! Вы не подумайте чего. Просто поздоровался, а сообщение из-за каких-то глюков само продублировалось.

> Что не так? Я ж там сразу и поправился.
не знаю, где и когда ты поправился(кстати есть хорошие диеты... :)... но ответ это не тебе (тебе, имхо, бесполезно, ты уже "уперся"), а Riply.
ну а не так там то, что она привела пример копирования данных, что встречается сплошь и рядом, а не свопирования, пример которого (реальной нужды в нем) я просил привести.

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

> то вот реальный кусок кода, именно так как там сейчас есть.
и опять ты приводишь, по терминам из sniknik © (16.11.08 15:12) [37] "код забега через улицу". гордишься им, приводишь показания секундомера, сравнения с предыдущим забегом...
а тебя всегда просили сказать ЗАЧЕМ ты бежишь, т.е. задачу/цель, а не способ реализации, разве не понятно? если за хлебом, то может оглянутся. может булочная и на этой стороне, т.е. ближе есть. и бежать не нужно будет и быстрее обернешься...

вот тут что за Data? что и зачем "переворачивается"? очередной надуманный пример или действительно что то необходимое, по другому не решаемое.

> @!!ex © (18.11.08 12:59) [58]
> > [57] {RASkov} © (18.11.08 11:59)
>
> Пример, плиз.

Да столько раз приводили примеры с многоуровневыми вложенными циклами, что повторяться смысла не имеет.
А также много раз говорилось, что не стоит повторять дурь за авторитетами, а лучше думать головой и применять инструменты там, где это необходимо.
Если применяемый инструмент повышает читабельность и прозрачность кода - его нужно применять, а не слушать расхожие фразы о том. что "GOTO - это некошерно".

> @!!ex © (18.11.08 09:51) [53]
> Нет не бывает. Если я увижу что кто-то из моих
> прогеров использует goto, это будет причиной для серьезной
> разборки, вплоть до увольнения программиста, если не "внемлет".

Я бы сам ушел от самодура...

> sniknik © (18.11.08 20:43) [68]
> ...
> вот тут что за Data? ...

Извиняюсь. Но представь себе, мне даже и в голову не могло прийти,
что здесь может кто-то НЕ догадаться по контексту что такое Data.

Давай проверим, угадай, что такое Data? :)
А уж потом и продолжишь учить меня, что мне не надо делать.

Быстрый Swap, Найти похожие ветки