Няма да повтарям в този коментар информация,
присътстваща вече и в коментара на журито,
а ще се средоточа на интересните детайли, които там липсват.
1. Кои дървета са най-бързи?
Ако отговор на този въпрос се търси из литературата, различни
автори дават на този въпрос и различни отговори: за едните
това са Red-Black дървета, за другите -- скъсени дървета
а пък за трети -- тъй наречените treaps (trees+heaps).
Разбира се, за да бъде съответната оценка що-годе адекватна,
авторите трябва да располагат с конкретните реализации
на сравняваните алгоритми, и то добре оптимизирани (никакви рекурсии,
само итерации!). И, желателно, написани в един и същ стил
(колкото и мъгляво да е последното понятие). Аз намерих
две такива реализации: едната (на C++) е в библиотеката Leda,
а другата (на ANSI C) e Libdict на Farooq Mela. А описание на
резултати от тестове с различни видове дървета намерих само в Libdict.
Тестовете бяха проведени с Webster's dictionary, съдержащ 235К думи.
Шампиони в тези тестове се оказаха скъсени дървета, които бяха
над 3 пъти (!!!) по-бързи от AVL и RB дървета.
Treaps бяха на второ място.
Тъй че аз имах голямо изкушение да изпробвам тези видове дървета.
За съжаление, нямах много време за нагаждане на кодовете от Dictlib
към дадена задача (т.е. добавяне на още един член -- индекс -- към
структурата на възела и
съответната промяна на основните операции в дървета).
Затова се задоволих с добре оптимизиран шампионски код на Петър Петров
от 1-та задача на Конкурс-2000, който изискваше само минимални добавки
за да се пригоди към дадена задача. RB-дървета, стоящи зад много
видове контейнери в STL (set, map и т.н.) отхвърлих по същата причина,
още повече, че бързите предварителни тестове с STL показаха,
че надали индексирани RB-дървета ще имат голямо предимство
пред индексирани AVL-дървета. Между другото, програмата на Илиан Илиев,
използваща индексирани RB-дървета, зае 4-то място. Обаче само от това не може
да се направи извода, че тези дървета са по-бавни от AVL, тъй като
в класирането се намесиха други ("недървени") фактори.
Може би главния от тях е оптимизация на IO операции с файловете.
При това се оказва, че най-добрата оптимизация се постига,
ако вместо ANSI C/C++ функциите за четене и запис на файловете
се исползват функциите от Win32 API.
Ама за това -- по-късно.
2. Структура на възлите.
Това също е важен въпрос. Първо: какво трябва да съдържа индекс?
В учебника на Седжуик ("Алгоритми на C"), например, индекс на един
възел съдержи броя на елементите на цялото поддърво,
излизащо от този възел, докато в кода на П.Петров -- броя на елементите
в лявото поддърво + 1. Т.е. индекса нарушава симетрията между
"ляво" и "дясно" в алгоритмите за вмъкване, изтриване и ротация. За сметка
на това броя на модификации на индексите при тези операции става средно
2 пъти по-малък отколкото при "симетричния" индекс.
Второ: Във всички учебници възлите на дървето, независимо от типа
на дървото, задължително съдержат и указател към родителския възел.
Този указател се използва почти във всички операции с дървeтa.
Дали този указател, доста раздуващ паметта необходима за съхраняване
на дървото с голям брой възела, е наистина необходим?
Както се вижда от кода на П.Петров, този указател може да бъде
заменен с един локален стек, чиято дълбочина трябва да е не по-малка,
отколкото максимална възможна дълбочина на дървото. При това ефективността
на операции с дървета не се намалява, а в системи с по-ограничена RAM
дори би трябвало да се увеличи, ако дървета са голями.
Ако приемем, че в системите с 32-битни int максимален брой на възлите
в дървото е 4G, получаваме, че за AVL-дървета е достатъчен стек с размер
32*1.41 < 46, за RB-дървета -- с размер 32*2=64, докато за splay trees
и treaps исползването на локален стек вместо указател към родителския възел
е нецелесъобразно, тъй като за тези типове дървета
няма горна граница за дълбочината на дървото, която е логаритмична по
броя на възлите в дървото (макар за treaps вероятността на това, че
дълбочината на дървото превиши 10 пъти съответния логаритм, е много малка).
3. Мистериите на оптимизация.
а) Моите тестове: първите станали последни!
Тритте от решенията, заемащи първите места в класацията по времето,
исползват една и съща реализация на AVL-дървета, с инфинитезимални
разлики в кода. Възниква тогава естествен въпрос, защо времената,
показани от тези 3 програми са тъй различни?
Първото нещо, което аз направих, след като се появиха резултатите
от тестовете, е да повторя на мое PC тестовете с програмите на
всички 5 участници набрали по 100 точки.
Резултатите бяха поразителни: при мен се е получила
съвершенно друга подредба на резултатите, като
програмите заемащи първите две места в класацията на журито,
стабилно (в 10 теста от 10) се наредиха на 4-то и 5-то место
съответно! Ето ги средните времена: 13.0, 14.9, 10.6, 11.3, 12.0 (+-0.2 сек.).
б) Какъв timer исползва журито?
Първата ми реакция беше, естествено, че трябва да проведа
същите тестове на няколко различни PC-та
(въпреки че и моето PC е доста репрезентативно, в смисел, че има 140-160М
свободна RAM) и, ако и там се получат
същите резултати, да подам контестация до журито (колкото и безнадежно
да изглежда подобна акция от моя страна :-(().
След това обаче аз се сетих, че в условията за провеждането
на предишните два конкурса беше казано, че тестваща програма
ще мери времето отпуснато от операционната система за дадена програма.
Точната фраза бе: "...действително отделеното от ядрото на Windows процесорно
време за работа на проверяваната задача". Което
с голяма вероятност
може
да се толкува като време, което даден процес е получил в схемата с preemtive
multitasking, конкурирайки с другите процеси. А програмата, която
аз исползвах за тестовете е била една простичка програмка, измерваща
пълното време между началото и краят на процеса. Като измерването
ставаше с ANSI C функцията clock(). При това аз исхождах из презумпцията, че
при усредняване по няколко теста времето на тествания процес
като процент от пълното време би трябвало да е едно и също, независимо
от тестваната програма. Това е разумна хипотеза, тъй като другите процеси
би трябвало да са независими от тествания процес.
Т.е. относителното нареждане на програмите
би трябвало да е едно и също, независимо от това, дали се измерва пълното време,
или само времето реално исползвано от процеса.
в) Построяване на новия timer.
Все пак този път реших да проверя тази хипотеза, като модифицирах моята
програма-таймер по следната схема:
.....
PROCESS_INFORMATION pi;
FILETIME starttime,exittime,kerneltime,usertime;//in 100ns time units
CreateProcess("TestedProgram",...,pi);
WaitForSingleObject(pi.hProcess,INFINITE);
GetProcessTimes(pi.hProcess,&starttime,&exittime,&kerneltime,&usertime);
.....
където, както е написано в MSDN,
kerneltime,usertime са времената, които процеса е прекарал
в kernel mode и, съответно, в user mode. Каквото и да значи това разделение,
предполагам, че търсеното процесорно време е сумата от
kerneltime и usertime.
Забележка. Този timer може да се исползва само
в ОС от фамилията NT, тъй като в Win9x функцията GetProcessTimes()
не е реализирана, т.е. съответните времена
не се пазят в "базата на данните" на процеса.
г) Тестове с новия timer.
ОК. След това направих тестове с новия таймер. И какъв беше резултата?
Подредбата по
processtime=kerneltime+usertime
напълно съвпадна с подредбата от тестовете на журито.
Като абсолютни времена в секунди, естествено, се отличаваха от тези на журито:
8.1, 8.7, 9.3, 10.4, 10.9 с отклонения от средно +- 0.2сек
(очевидно моето PC е малко:)) по-бързо от това на журито).
Сравнявайки "чисти" процесорни времена със съответните "пълни" времена
горе, лесно се вижда, че дялa на background процеси в пълното време се
варира, в зависимост от тестваната програма от 38% до 12%, което противоречи
на хипотезата, че всички тези background процеси са независими от тествани
процес. Което означава с прости думи, че в kerneltime на тествания процес
не е включено време на някои процеси от ядрото, които обслужват
тествания процес. Подозирам, че това са процеси
на заделяне на физическата памет за входно-изходни буфери.
Шампионската програма на П.Петров е шампион и в това отношение, като
заделя в 13-ти тест към 130М динамичната памет
за буфери на входния и изходен файл.
д) Тайните на оптимизация.
Възниква естествения въпрос: на какво се дължи малкото процесорно време
на шампионската програма? Първата ми мисел беше, че може би това е било заради
някакъв чудесен компилатор? Разглеждайки exe файла аз открих там стринга
"(R) Intel", което навежда на миселта, че е бил използван C++ компилатора
ICL на Intel (този компилатор е бил използван и от някои други участници).
Какво ли ще стане, ако аз ще прекомпилирам кода с VC++?
OK, прекомпилирвам кода, правя нов тест. Страхотно! Ако автора на
шампионската програма би компилирал кода си със стария добър VC++,
той би увеличил преднината си в process time със примерно 1 sec.
(и то на моето PC, а в официалните тестове -- още повече!).
Total time също се е намалило с една секунда.
Интересно, защо ли тогава беше исползван компилатора на Intel вместо този на MS?
Може би автора си е мислил, че тестовете ще се провеждат на система с Itanium
(и с поне 1G RDRAM)? Той сигурно е забравил, че в миналогодишния конкурс
тестовете са били провеждани на PC с 1G Athlon (или Duron?), а паметта му
е най-вероятно 256М, ако се съди по фразата в условия на конкурса, че
"на всяка тествана програма се предоставя 128М и повече".
Като това "и повече" най-вероятно ще се освобождава със хвърлянето на страници
от оперативната памет в paging файл, т.е. по-добре ще е да не се разчита на нея.
Аз, оптимизирайки програмата ми, изхождах от следната проста аритметика:
дървото с 4М възела ще заеме 96М памет (или 80М, ако ще се обединят в едно int
баланс-фактора на възела и броя на елементите в неговото ляво поддърво).
Входния файл необходим за построяването на такова дърво ще е с размер
най-малко 40М; ако има и други операции в него, може да се очакват и входни
файлове заемащи 60-80М. Т.е. ако ще се създадат буфери в паметта, побиращи
изцяло входния и изходния файлове, то необходимата за целта свободна
оперативна памет може спокойно да надхвърли 200М. Затова аз дори и не се опитах
да създавам такива буфери, като за целта използвах буфери с ограничен размер.
Което, за съжаление, усложнява логиката на работа с буфера, довеждайки
до съществено забавяне на моята програма по сравнение с шампионската
(по "чисто" процесорно време). Никой друг от участниците, освен шампиона,
съшо не е използвал буфери, побиращи целия входен/изходен файл. И това, според
мен е един от двата основни фактори в изоставането на всички програми (с един и същ "дървен"
код) от шампионската програма (за другия -- малко по късно).
Между другото, максималното дърво от тесттовете
съдържа само 500000 възела, а дървото построявано от файл с максимален размер
(13-ти тест) е с размер само 564 възела! Което е много далеч
от границата 4М, която фигурира в условието на задачата! А хората обикновено
оптимизират програмите си, вземайки предвид и граничните параметри от условието.
Друг интересен момент в шампионския код, който сигурно е допринесъл много
в скоростта му: вместо стандартните динамични
масиви от char и съответните C++ или C
процедури (new... или malloc()) за заделяне на динамичната памет бяха
исползвани класове string от STL и техните STL алокатори.
Обаче този код със string изглежда в контекста на задачата малко
като трик.
е) Файлове проецирани в памет
А какво ще стане, ако вместо
него ще се използват директно такива функциите от Win32 API от ниско ниво,
като VirtualAlloc(), например? Или, още по-добре,
да се мине без междинен
буфер изобщо, използвайки механизм на файлове, проецирани в паметта
(memory mapped files)?
Схемата на тяхната употреба е следната:
HANDLE hf=CreateFile("STAT.INP",...);
HANDLE hfm=CreateFileMapping(fi,...);
char*inptr=(char*)MapViewOfFile(hfm,...);
след което с inptr може да се работи като с буфер,
съдържащ целия файл (детайлите на тази технология са много добре описани
в "Advanced Windows" на J.Richter).
ж) Програма кентавр -- абсолютен шампион!
Казано--сторено. Построих новата програма, взимайки най-доброто както от кода на
П.Петров така и от "моята" реализация на дървета (която пак се базира на кода
на П.Петров отпреди две години), като замених string със файловете
проецирани в паметта. Направих тестове. Резултата беше:
totaltime=9.7 сек., processtime=4.9 сек! С други думи тази програма
не само подобри процесорно време на шампионската програма на П.Петров
компилирана с VC++ с още над 2(!!!) сек.,
но и стана шампион и по другия критерий -- пълното време на процеса!
Тъй че оттук нататък аз лично ще исползвам
IO реализиран с memory mapped files само. Поне ако има изгледи
размера на входния файл да надвиши 1М. Въпреки че при малките файлове
голяма файда нада ли ще има.
з) Класиране по всички тестове
|
| Jury
| Total
| Process
| User
| Idle
|
| Stat1
| 14.2
| 13.0
| 8.1
| 6.9
| 38%
|
| Stat2
| 16.4
| 14.9
| 8.7
| 7.6
| 42%
|
| Stat3
| 16.7
| 10.6
| 9.3
| 8.8
| 12%
|
| Stat4
| 18.7
| 11.3
| 10.4
| 9.3
| 8%
|
| Stat5
| 20.9
| 12.0
| 10.9
| 10.1
| 9%
|
| Stat1(VC)
| ---
| 12.4
| 7.1
| 6.2
| 43%
|
| Champ
| ---
| 9.7
| 4.9
| 4.6
| 49%
|
В тази таблица с червено са обозначени шампиони по съответния параметър,
а
idle=(totaltime-processtime)/totaltime в проценти.
Забележете, че колкото по-ефективна е програмата по параметър processtime,
толкова по-голямо е и нейното idletime (с едно исключение).
Моята хипотеза за това странно явление е, че системата не отчита цялото време
затрачено от Windows executive за обслужване на даден процес. По-специално,
ако процеса извиква някоя функция от ядрото на ОС, времето на испълнение
на тази функция се включва във kerneltime на процеса. Обаче част от времето
системата провежда в обработка на хардуерни исключения, предизвикани
от липсата на дадена страница от резервираната памет във RAM. И, може би,
тъкмо това време не се отчита? Не знам точния отговор на този въпрос.
и) Todo
Все пак си остава засега отворен въпроса, дали не може
да се напише програма, която хем да е толкова (или почти толкова)
бърза като champ, хем и да пести оперативната памет?
Какво всъщност става, когато ние отваряме прозорец във паметта
със MapViewOfFile(hfm,...,0)?
а) Windows резервира диапазон от линейните виртуални адреси
с дължина равна на размера на файла (по-точно, това става на
предишния етап с CreateFileMapping(hf,...,));
б) Windows обвързва този диапазон със съответния входен файл
(вместо регион от paging file, както това става при извикването
на VirtualAlloc(...,MEM_COMMIT,...));
c) Процеса на заделяне на оперативната памет е доста интелигентен:
тя се заделя само когато програма се опитва да прочете или запише
байт по някой виртуален адрес, на който не съответства адрес от RAM.
Тогава се предизвиква хардуерно исключение page fault, и
default обработчик на това исключение прехвърля съответното
парче от файла (с размер 1 страница==4К) в RAM.
Все пак, когато целия файл от 100М бъде прочетен,
програмата ще заеме и 100М от RAM (и това се вижда, ако
заедно със champ в 13-ти тест се пусне и Task Menager и се гледа
available physical memory).
В нашия случай обаче, както четенето от входния файл,
така и запис в изходния става за всеки байт само веднъж.
Така че ако ще се замени default обработчик на page fault
със try{...}...catch()
(или със по-стария __try{...}...__except()),
който едновременно със заделяне на новата страница от RAM
ще освобождава предишната, може да се очаква, че ефективността
на програмата няма да пострада особено, докато исползването
на RAM съществено ще се намали.
Въпреки че този метод е аналогичен на исползването
на IO буфери с ограничен размер, реализиран от много от участниците,
файдата би трябвало да идва от това, че вместо
софтуерната проверка
if(p==EndOfBuffer)ReadToBuffer();,
която се осъществява преди прочитането на всеки байт
от входния буфер (и задръства блока на предсказания на процесора),
ще се използва обработка на исключения,
възникващи хардуерно само когато наистина се достига граница на страницата
отобразена във RAM. Т.е. те се случват 4000 пъти по-рядко, отколкото
съответното if()... при стандартния начин. И то независимо
от това, дали ние ще сложим нашия обработчик или не.
4. Може ли таймера да бъде измамен?
Това е още един интересен въпрос. За мен той
се е оказал най-интересен от всичко до тук.
a) Фалшифициране на totaltime
Първо, ако става дума за totaltime, то WinAPI функция SetSystemTime()
може да върши такива подвизи,
ако бъде включена в кода на тестваната програма.
Един начин да се предпази от това (в WinNT/2000/XP само)
е да се логне при тестването като обикновен user, а не като admin.
Тъй като в WinNT и нагоре възможността да се променя системното
време е привилегия, която обикновен user (както и процеси стартирани
от него) не притежава, поне при настройки по-подразбиране на policies.
Този начин е, обаче доста тромав, ако сте свикнали да работите на PC-то
си като admin, (въпреки всичките препоръки за сигурността).
Така че, въпроса е, дали съществува начин един процес (timer в нашия случай)
да стартира друг процес, като да забрани на този друг процес да ползва
привилегии, които той автоматично наследява от логнатия user?
б) В дебрите на Windows security
До този момент аз само псувах Windows security (както и всeки друг
нормален user :)), а с проблемите на програмиране на такава лично не се
сблъсквах.
И имам само една книга, в която въпроса с сигурността на Windows
на ниво програмиране е донякъде разгледан. Това е
"Windows 2000 system programming" на Al Williams (в превод на руски).
За съжаление, докато такива неща като Security descriptors и ACL
са описани що-годе добре, макар и прекалено кратко, за такива работи
като access token и работа с привилегии в тази книга само се намеква
(не знам защо автора е решил, че: "...привилегиите са по-малко интересни
за програмистите, отколкото правата"). Все пак там се споменава
функцията AdjustTokenPrivileges(), която
би трябвало да служи за целта,
а в MSDN може да се открие и един примерен код, исползващ тази функция.
Проблема с този примерен код е само в това, че когато аз го вградих
в моята програма-таймер, тя бодро рапортува, че на стартираната от нея програма
е успешно забранено да променя системния часовник. Обаче въпреки
това модифицираната за целта тествана програма игнорира тази забрана
и добавя (или изважда) 1 час към системен часовник.
Тя променя времето с 1 час а не с (милли)секунди,
за да може човек веднага да види резултатите в system tray.
Какво става? Може би аз исползвам този код неправилно? Т.е.
може би преди този код и/или след него трябва да се направят някакви
необходими ритуални телодвижения (за които MS е забравила да уведоми
тъмния читател в MSDN). Да речем да инициализира security attributes
на дъщерен процес вместо с NULL с нещо по-реално (съответните
процедури на инициализацичта са описани,
обаче рядко се исползват -- толкова са тромави).
Нека да погледнем, какво има в Internet по-въпроса.
Отивам първо на codeguru.earthweb.com.
Търся с ключова дума
AdjustTokenPrivileges.
Намирам един адекватен источник: програмата killer на
Richard Eperjesi, служеща за бързо (с две щраквания на мишката и без
никакво протакане с тъпи въпроси)
убиване на произволен процес във Windows2000/XP.
Гледам сорса на privi.dll, която би трябвало да забранява или
разрешава различните привилегии.
Виждаме съшата функция SetPrivilege() от примера в MSDN,
"творчески модифицирана"
с някакъв допълнителен код (обаче без да се цитира първоистояника от MSDN).
Контекста и начин на исползването на функцията не се различава от моите.
ОК. Заменям в моя код MS-версията на SetPrivilege() с тази
на Codeguru. Уви, резултата е същият: timer съобщава за успешна забрана,
обаче тестваната програма не забелязва забраната.
Да видим, как работи тази програма (killer). Когато я стартирам като admin -- всичко
е ОК. Само че в този случай, предполагам, admin има необходимата привилеги
(debug process), тъй да се каже "по-рождение". Когато стартирам програмата
логвайки се като обикновен user, програмата изобщо не се зарежда в system tray,
тъй като не може да придобие съответната прижилегия! Което в дадения случай
е напълно логично: ако всеки user би имал привилегията да раздава привилегии,
то с една не много хитра програмка той би могъл да прави на всяка система с NT
каквото си поиска! Тъй че, според мен, фокусите с привилегии в програмата
killer са напълно излишни, и въпроса, дали
AdjustTokenPrivileges() изобщо може да бъде накарана
да отнема (временно, за един процес само)
някои от привилегиите на admin, си остава отворен.
Ако някой знае, как да се направи това, и то без
CreateProcessAsUser()
моля да ми се обади на
В.Молотков, ако не е трудно.
Почти никакви други ресурси по дадена тема не успях да открия в мрежата.
Освен сорс кода към книгата
"Programing Windows Sequrity" и някои други полезни утилити на
Keith Brown. От самата книга в мрежа има само предговор и последна глава,
а hardcopy струва 39$ в Amazon.com :((. Има още и 5-дневен курс по темата
на цена 1600$ (!).
Сигурно броя на програмиращи идиоти с пари в западното полукълбо е доста голям.
Не че в другото полукълбо има по-малко идиоти, само че там те се специализират
в други области, а и нямат, като правило, толкова излишни пари :)).
Разбира се остава такъв примитивен начин на откриване на
SetSystemTime(), като търсене на ъответния string в самия файл
с тестваната програма (в списъка на функциите, извиквани от Kernel32.dll).
Обаче тази функция при един конкретен тест може и да не бъде викана,
или да бъде извиквана само ако са зададени съответните параметри на командния ред.
И. което е по-важно, има много начини за смяна на системното време.
Да речем, може да се напише функция с произволно име, която бърка директно
в CMOS-паметта. Е, не съвсем директно, тъй като Windows NT забранява това
за програми в user mode
(за разлика от Dos и Win9x). Обаче има драйвери (със free сорс код),
които позволяват да се прави и това.
в) Фалшифициране на processtime.
Това е малко по-сложно. Идеята е следната: тестваната програма, пуска
още едно копие от себе си като отделен процес, след което заспива,
чакайки завършването на дъщерния процес, който върши цялата работа.
В същност, исползвайки технологиите
за създаване на вируси, аз написах една универсална програма ChampMaker,
която от произволна програма прави шампион (по processtime).
Трябва да се напише само:
champmaker snail jaguar
и processtime на програмата jaguar.exe (получена от snail.exe
със просто залепване на champmaker.exe към snail.exe) става пренебрежимо
малко в сравнение със processtime на snail.exe.
Тъй че за да компенсира подобни възможности програмата-таймер трябва
да проследява и всички дъщерни процеси, породени евентуално от тествания процес,
както и процеси породени от дъщерни процеси и т.н.
Това аз не го направих в моята програма-таймер.
Тъй като, всъщност, това е работа на журито :)),
ако нейния таймер няма подобна защита. А би трябвало, тъй като
току-що описания метод на "ускоряване" е напълно законен от формална гледна
точка: той не е бил забранен изрично, а и не се бърка в системата
(за разлика от SetSystemTime()).
г) Test utilities и champmaker.
Оттук всеки който иска може да свали както моите програми за тестване
testutils.zip (заедно със сорсове),
така и програмата champ (неофициален шампион,
исползващ memory file mapping, също със сорс).
testutils.zip съдержа: програмата-таймер ExeTimer,
програмата CalcSum за пресмятане на суми на числа, срещащи се в един текстови файл,
като се смята, че числата от файла образуват една таблица с N колонки, ако се
зададе параметър "-N" на командния ред, и се сумират числата в отделни колони.
Файла runtests.bat, пуснат с аргументите myprogram infile,
исползва тези програми
за да проведе последователност от тестовете на програмата myprogram с (под)множество от входните файлове
с имена 01infile.inp,...,20infile.inp (до 20 входни файла, а ако на някого му трябва
повече, runtests.bat се модифицира лесно). И, най-накрая, програмата
ChampMaker демонстрира гореописания начин на превръщане на една бавна програма в една много бърза.
А нейния код може да послужи, ако някой пожелае,
и като template за създаване на напълно боеспособни вируси или трояни.
|
