Тестове за производителност

3. Сортиране през двоично дърво

Тук ще направим тестове с познатата ни програма, която взима данните от масив, построява двоично дърво. После дървото се обхожда от ляво на дясно, като числата записани във всеки възел се записват обратно в масива. В резултат масивът е сортиран. Тестът ще е с масив от 1000 елемента, същият който използвахме при методът на мехурчето. За да направя този тест се наложи да увелича паметта за програмата на 10к. Самата програма се побира в първите 1000 адреса от паметта. Масивът с данните е 1000 адреса. Дървото ще заеме 4 x 1000 = 4000 адреса. До тук са 6000. Имайки предвид, че дървото се обхожда с рекурсия, за което се изразходва доста памет за стек закръглих на 10к, които се оказаха достатъчни. За да се уверя, че програмата ще работи нормално, че ще е достатъчна паметта първо изпълних програмата като в клетка с етикет arraySize въведох 99, тоест ще се сортират първите 100 елемента от масива. После пробвах с 199, 499 и 999 елемента. След изпълнение на програмата проверявах паметта за да се уверя, че масивът е сортиран.

Това е таблицата с данните от теста и обяснението на значението на колонките в нея:

N – номер на ред
Buss – Buss/CPU clok ratio – отношение между чвстотата на процесора и паметта. 1:1 равни честоти. 1:8 – шината е 8 пъти по-бавна
Instr Cache – размер на кеша. В редове памет.
Int Cache – размер на кеша за цели чилса в редове памет(адреси).

Резултатите са в брой тактови импулси необходими за изпълнението на програмата – Clocks
В 4 колони:
1. Нормални инструкции без включен механизъм за предсказване на преход
2. Нормални инструкции с включен механизъм за предсказване на преход
3. Компресирани инструкции без включен механизъм за предсказване на преход
4. Компресирани инструкции с включен механизъм за предсказване на преход

Таблица 4


Продължение на таблицата:
N – е номера на реда
5. Подобрението на производителността в % при нормални инструкции със и без предсказване на прехода = 100*(1. - 2.)/1.
6. Подобрението на производителността в % при нормални към компресирани инструкции без предсказване на преход = 100*(1. - 3.)/1.
7. Подобрението на производителността в % при компресирани инструкции със и без предсказване на прехода = 100*(3. - 4.)/3.
* 1. 2. 3. 4. са колонките от таблицата под Cloks




Влиянието на отношението при честотите памет/цпу, размера на кеша за инструкции и кеша за данни е същото както при метода за мехурчето.

Сравнение на резултатите между метода на мехурчето и сортирането през двоично дърво.

1. С нормални инструкции.

Най-лошият резултат при метода на мехурчето е на ред 3 от таблица 1.
64,068,104 - ред 3 памет/цпу 3; Кеш за инструкции 0; Кеш за данни 8
При същите условия, сортирайки през двоично дърво програмата се изпълнява за
3,763,768 тактови импулса.

Подобрението в производителността е 17 пъти !!!
Най-добрият резултат при метода на мехурчето е на ред 7 от таблица 1.
10,511,019 - ред 7 памет/цпу 1; Кеш за инструкции 32; Кеш за данни 8
При тези условия резултатът с двоично дърво е 541,957 тактови импулса.
Подобрението е 19.4 пъти !!!

2. С компресирани инструкции.

Най-лошият резултат при метода на мехурчето е на ред 3 от таблица 1.
54,060,080 - ред 3 памет/цпу 3; Кеш за инструкции 0; Кеш за данни 8
При същите условия, сортирайки през двоично дърво програмата се изпълнява за
3,094,408 тактови импулса.
Подобрението е 17.47 !!!

Най-добрият резултат при метода на мехурчето е на ред 7 от таблица 1.
10,511,019 - ред 7 памет/цпу 1; Кеш за инструкции 32; Кеш за данни 8
При тези условия резултатът с двоично дърво е 519,545 тактови импулса.
Подобрението е 20.23 пъти!!!

Изводи.

Подобрението в производителността използвайки двоично дърво за сортиране е 17 – 20 пъти. Това е много голяма разлика. Ако сортираме още по-голям масив разликата ще е още по-голяма. Причината е, че при метода на мехурчето имаме много итерации. При по-голям масив итерациите ще са още повече.

Предимството на метода на мехурчето е в по-малко използваната памет. При методът с двоично дърво трябва да се построи дърво. То ще заеме памет 3 пъти по голяма от масива. Един възел на дървото има 3 елемента – стойност, ляв указател и десен указател. Още памет се изразходва и за стек, който е доста използван заради рекурсията за обхождането на дървото. Разбирасе има алгоритми за обхождане на дърво и без рекурсия.