Оптимизация

← →
optimizer (2007-01-22 12:39) [0]

Продолжение ветки.
http://delphimaster.net/view/15-1169395280/

TPassGen = class ... FBaseLen: DWord; FCurPass: String; // есть вариант с array of Char, но скорость не меняется FPassBase: String; end; { генерация пароля. входные параметры - Unique - некое число, которое снаружи увеличивается всегда на 1, за счет чего и генерирую пасс, PassLen - длина пароля, контролируется снаружи } procedure TPassGen.CreatePassword(Unique: DWord; PassLen: DWord); var vMod, i: DWord; begin for i := 1 to PassLen do begin // FBaseLen - длина словаря vMod := Unique mod FBaseLen + 1; // FCurPass - результат, FPassBase - словарь FCurPass[i] := FPassBase[vMod]; Unique := Unique div FBaseLen; end; end;

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

возможно ли оптимизировать? судя по всему наибольшее время уходит на операции mod / div. за счет перехода на DWord удалось избежать использования виндового апи (_llmod / _lldiv). из апи используется только UniqueString, от которого можно избавиться при переходе на array of char. но на скорости это не сказывается практически.

при раскладе алфавит = 26 UpperCase Latin, генерация 1-2-3-4 знаковых паролей, скорость составляет порядка 2.1 млн паролей / секунду.

ест еще несколько идей в плане алго для генерации, но, этот, имхо, самый гибкий и удобный (мне). если у кого есть "стоящие" идеи в плане оптимизации - с удовольствием выслушаю.

--
p.s. @модератор: в предыдущей ветке вышла проблема с никами, потому что компьютер рабочий и не я один пользуюсь своим любимым форумом. браузер FireFox, включено автозаполнение.

← →
optimizer (2007-01-22 12:48) [1]

дизасм (для удобства), жирным выделены "некрасивые" места. к сожалению BASMом владею на уровне read-only.

procedure TvPasswordGenerator.CreatePassword (Self: TvPasswordGenerator; Unique: Windows.DWORD; PassLen: Windows.DWORD); var vMod: Windows.DWORD; i: Windows.DWORD; begin 00000000 : // -- Line #207 -- 00000000 : 53 PUSH EBX 00000001 : 56 PUSH ESI 00000002 : 57 PUSH EDI 00000003 : 55 PUSH EBP{i} 00000004 : 51 PUSH ECX 00000005 : 8B F2 MOV ESI,EDX 00000007 : 8B D8 MOV EBX,EAX 00000000 : // -- Line #208 -- 00000009 : 8B F9 MOV EDI,ECX{PassLen} 0000000B : 85 FF TEST EDI,EDI 0000000D : 76 3A JBE +58; (0x49) 0000000F : C7 04 24 01 00 00 00 MOV DWORD PTR [ESP],$00000001 00000000 : // -- Line #210 -- 00000016 : 8B C6 MOV EAX,ESI{Unique} 00000018 : 33 D2 XOR EDX,EDX 0000001A : F7 73 3C DIV DWORD PTR [EBX+60{@Self^+60}] 0000001D : 8B EA MOV EBP{i},EDX 0000001F : 45 INC EBP{i} 00000000 : // -- Line #211 -- 00000020 : 8D 43 50 LEA EAX,DWORD PTR [EBX+80{@Self^+80}] 00000023 : E8(00 00 00 00 CALL @UniqueStringA{0x47} 00000028 : 8B 14 24 MOV EDX,DWORD PTR [ESP] 0000002B : 8D 44 10 FF LEA EAX,DWORD PTR [EAX+EDX-1] 0000002F : 50 PUSH EAX 00000030 : 8B 43 38 MOV EAX,DWORD PTR [EBX+56{@Self^+56}] 00000033 : 8A 44 28 FF MOV AL,BYTE PTR [EAX+EBP{vMod}-1] 00000037 : 5A POP EDX 00000038 : 88 02 MOV BYTE PTR [EDX],AL 00000000 : // -- Line #212 -- 0000003A : 8B C6 MOV EAX,ESI{Unique} 0000003C : 33 D2 XOR EDX,EDX 0000003E : F7 73 3C DIV DWORD PTR [EBX+60{@Self^+60}] 00000041 : 8B F0 MOV ESI{Unique},EAX 00000000 : // -- Line #213 -- 00000043 : FF 04 24 INC DWORD PTR [ESP] 00000000 : // -- Line #208 -- 00000046 : 4F DEC EDI 00000047 : 75 CD JNE -51; (0x16) 00000000 : // -- Line #214 -- 00000049 : 5A POP EDX 0000004A : 5D POP EBP{i} 0000004B : 5F POP EDI 0000004C : 5E POP ESI 0000004D : 5B POP EBX 0000004E : C3 RET NEAR end;

если бы "облегчить" работу со стеком, попытаться уменьшить влияние mod / div"a. (отказаться от апи UniqueString не проблема, просто не влияет на скорость в масштабах процедуры).

от ООП отказываться глупо. ей богу. слишком крупно все навалено, без классов, и тех приятностей что дает ООП просто не разобраться дальше. просто выдавить бы из этой штуки еще пару миллионов +) ведь реально, имхо.

p.s. вот бы Великий Sha пришел на помощь =)

← →
icWasya © (2007-01-22 14:51) [2]

попробуй сначала переписать код вот так

procedure TPassGen.CreatePassword(Unique: DWord; PassLen: DWord); var vMod, i: DWord; PCurrPass:PChar; begin PCurrPass:=PChar(FCurPass); for i := 1 to PassLen do begin // FBaseLen - длина словаря vMod := Unique mod FBaseLen + 1; // FCurPass - результат, FPassBase - словарь PCurPass^ := FPassBase[vMod]; Unique := Unique div FBaseLen; Inc(PCurrPass); end; end;
должно исчезнуть UniqueString

← →
optimizer (2007-01-22 15:22) [3]

[b]icWasya[/b]
UniqueString конечно исчезнет, но
1. Используем апи LStrToPChar
2. На скорость не влияет (проверил)

Решить можно было и через замену FCurrPass на PChar / array of Char.

← →
optimizer (2007-01-22 15:26) [4]

icWasya
вот дизасм вашего варианта:

procedure TvPasswordGenerator.CreatePassword (Self: TvPasswordGenerator; Unique: Windows.DWORD; PassLen: Windows.DWORD); var vMod: Windows.DWORD; i: Windows.DWORD; PCurPass: System.PChar; begin 00000000 : // -- Line #208 -- 00000000 : 53 PUSH EBX 00000001 : 56 PUSH ESI 00000002 : 57 PUSH EDI 00000003 : 55 PUSH EBP 00000004 : 8B E9 MOV EBP,ECX 00000006 : 8B F2 MOV ESI,EDX 00000008 : 8B D8 MOV EBX,EAX 00000000 : // -- Line #209 -- 0000000A : 8B 43 50 MOV EAX,DWORD PTR [EBX+80{@Self^+80}] 0000000D : E8(00 00 00 00 CALL @LStrToPChar{0x49} 00000012 : 8B F8 MOV EDI,EAX 00000000 : // -- Line #210 -- 00000014 : 8B CD MOV ECX,EBP{PassLen} 00000016 : 85 C9 TEST ECX,ECX 00000018 : 76 20 JBE +32; (0x3A) 00000000 : // -- Line #212 -- 0000001A : 8B C6 MOV EAX,ESI{Unique} 0000001C : 33 D2 XOR EDX,EDX 0000001E : F7 73 3C DIV DWORD PTR [EBX+60{@Self^+60}] 00000021 : 8B C2 MOV EAX,EDX 00000023 : 40 INC EAX 00000000 : // -- Line #213 -- 00000024 : 8B 53 38 MOV EDX,DWORD PTR [EBX+56{@Self^+56}] 00000027 : 8A 44 02 FF MOV AL{vMod},BYTE PTR [EDX+EAX{vMod}-1] 0000002B : 88 07 MOV BYTE PTR [EDI{PCurPass}],AL{vMod} 00000000 : // -- Line #215 -- 0000002D : 8B C6 MOV EAX,ESI{Unique} 0000002F : 33 D2 XOR EDX,EDX 00000031 : F7 73 3C DIV DWORD PTR [EBX+60{@Self^+60}] 00000034 : 8B F0 MOV ESI{Unique},EAX 00000000 : // -- Line #216 -- 00000036 : 47 INC EDI{PCurPass} 00000000 : // -- Line #210 -- 00000037 : 49 DEC ECX 00000038 : 75 E0 JNE -32; (0x1A) 00000000 : // -- Line #218 -- 0000003A : 5D POP EBP 0000003B : 5F POP EDI 0000003C : 5E POP ESI 0000003D : 5B POP EBX 0000003E : C3 RET NEAR end;

← →
optimizer (2007-01-24 17:32) [5]

появилась идея ускорить mod / div путем прегенерации таблиц с рассчитанными значениями... идея ахтунговая, но у напарника скорость выросла в 2 раза.

← →
Alx2 © (2007-01-25 09:18) [6]

>optimizer (24.01.07 17:32)
Если Unique снаружи всегда на единицу увеличивается - от деления можно избавиться вообще. Например, ведя инкремент в заданной системе счисления. Увеличивая последний разряд и наблюдая его выход за предельное значение - меняем его на минимальное значение и делаем попытку увеличить следующий разряд. Если же увеличить удалось без переполнения - все ok.

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

← →
Сергей М. © (2007-01-25 10:10) [7]

> если бы "облегчить" работу со стеком

Операции со стеком (сохранение/восстановление РОН) в прологе/эпилоге на практике очень незначительно влияют на сквозную производительность алгоритма п/программы. Но если "ловля блох" все же нужна, то придется отказаться от процедуры с параметрами (по кр.мере для метода ограничиться не более чем двумя cardinal-based-параметрами) и полностью переписать тело процедуры на basm.

← →
optimizer (2007-01-26 05:29) [8]

@Alx2
Простите, не до конца понял идею. Если можно в двух словах, но на пальцах.

@Сергей М.
По поводу стека вы правы, но, имхо, при многотысячном запуске повлияет. "Для метода не более чем двумя" - важный момент - считается ли передача Self"a (которая не видна не вооруженным глазом) как параметр для вашего условия?

С BASMом тяжко, поэтому и обратился к публике. Может кто чего подскажет.

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

ООП очень сильно сказывается на производительности. Но как избежать падения без потери удобства?

>optimizer (26.01.07 05:29) [8]
Имел в в иду примерно это
procedure TPassGen.IteratePassword(UniqueStart, UniqueStop, PassLen: DWord); var i: DWord; CounterStr: array of byte; tmp: DWord; Over: boolean; CPRef : Pchar; begin SetLength(CounterStr, PassLen + 1); fillchar(CounterStr[0], PassLen + 1, 0); SetLength(FCurPass,PassLen); CPRef := @FCurPass[1]; tmp := UniqueStart; i := 0; while tmp > 0 do begin CounterStr[i] := tmp mod FBaseLen; tmp := tmp div FBaseLen; CPRef[i] := FPassBase[CounterStr[i] + 1]; inc(i); end; while i<PassLen do begin CPRef[i] := FPassBase[1]; inc(i); end; // Здесь первая генерация FCurrPass готова (для UniqueStart) UniqueStart := UniqueStop - UniqueStart; while UniqueStart > 0 do begin dec(UniqueStart); i := 0; inc(CounterStr[0]); over := CounterStr[0] = FBaseLen; while over and (i < PassLen) do begin CounterStr[i] := 0; CPRef[i] := FPassBase[1]; inc(i); inc(CounterStr[i]); over := CounterStr[i] = FBaseLen; end; if i < PassLen then CPRef[i] := FPassBase[CounterStr[i] + 1]; // Теперь здесь готова очередная генерация FCurrPass end; end;

И вызов
Var PG: TPassGen;
begin
PG := TPassGen.Create;
PG.FPassBase := "012"; // сорри за непосредственный доступ к полям - оно здесь от мово скудоумия
PG.FBaseLen := 3;
PG.IteratePassword(5 {С какого значения},100 {по какое},20 {длина цепочки});
end;

>optimizer (22.01.07 15:26) [4]
>icWasya
>вот дизасм вашего варианта:

Ну а Вы смотрите, этот код выполняется в цикле или нет?

Оптимизация Найти похожие ветки