Armenian Knowledge Base  

Go Back   Armenian Knowledge Base > Technical sections > Languages, Compilers, Interpreters
Register

Reply
 
LinkBack Thread Tools
Old 30.09.2002, 04:55   #1
Грустно...
 
Agregat's Avatar
 
Join Date: 08 2002
Location: Там, где всегда идут дожди
Age: 35
Posts: 21,717
Downloads: 2
Uploads: 0
Reputation: 250 | 7
Post Еще одна задачка

Я предлагаю два алгоритма реализующих умножение.
Время первого алгоритма O(N) время второго алгоритма O(LogN).
Однако же в VC++6.0 release первый алгоритм работает быстрее.
Можете определить почему.
(Ответ я знаю, но мне интересно, найдете ли вы почему это так).
Всем удачи.
Code:
 
int Naive (int a, int b)
{
	int z = 0;

	while (a > 0)
	{
		z += b;
		--a;
	}

	return z;
}

int Russian (int a, int b)
{
	int z = 0;
	while (a > 0)
	{		
		z += a & 0x1 ? b : 0;
		b <<= 1;
		a >>= 1;
	}
	return z;
}
Reply With Quote
Old 30.09.2002, 15:36   #2
Академик
 
greka's Avatar
 
Join Date: 09 2001
Location: inside myself
Posts: 5,369
Downloads: 0
Uploads: 0
Reputation: 18 | 5
Post

может потому, что у Интел-а есть нескока устройств сдвига :-? т.е. это дело распараллеливается..?
Reply With Quote
Old 30.09.2002, 16:14   #3
Грустно...
 
Agregat's Avatar
 
Join Date: 08 2002
Location: Там, где всегда идут дожди
Age: 35
Posts: 21,717
Downloads: 2
Uploads: 0
Reputation: 250 | 7
Post

Ан нет...ведь первый вариант быстрее выходит, хотя он должен быть медленней!
Reply With Quote
Old 30.09.2002, 17:33   #4
Академик
 
greka's Avatar
 
Join Date: 09 2001
Location: inside myself
Posts: 5,369
Downloads: 0
Uploads: 0
Reputation: 18 | 5
Post

ob'yasni-ka, plz, pochemu eto 1-j DOLJEN byt' medlenee ?
Reply With Quote
Old 30.09.2002, 17:42   #5
Грустно...
 
Agregat's Avatar
 
Join Date: 08 2002
Location: Там, где всегда идут дожди
Age: 35
Posts: 21,717
Downloads: 2
Uploads: 0
Reputation: 250 | 7
Post

Первый выполняется за линейное время О(N)
Второй выполянется за логарифмическое время
O(logN).
В дебуг версии оно так и есть.
Попробуй следующий тест

Для любого N > 0 <=> N > logN - соответственно быстрее выполняется logN

Code:
  
DWORD dw = GetTickCount();
for (int i = 0; i < 1000; ++i)
for (int k = 0; k < 1000; ++k)
  Naive(i, k);
printf(&quot;Naive time = %d\n&quot;, GetTickCount() - dw);
dw = GetTickCount();
for (int i = 0; i < 1000; ++i)
for (int k = 0; k < 1000; ++k)
  Russian(i, k);
printf(&quot;Russian time = %d\n&quot;, GetTickCount() - dw);
От компилируй и в дебуг и в релиз версиях и сравни результаты.
Reply With Quote
Old 30.09.2002, 20:46   #6
Академик
 
greka's Avatar
 
Join Date: 09 2001
Location: inside myself
Posts: 5,369
Downloads: 0
Uploads: 0
Reputation: 18 | 5
Post

lol, a gde ob'yasnenie ?
Reply With Quote
Old 01.10.2002, 14:03   #7
Грустно...
 
Agregat's Avatar
 
Join Date: 08 2002
Location: Там, где всегда идут дожди
Age: 35
Posts: 21,717
Downloads: 2
Uploads: 0
Reputation: 250 | 7
Post

О(N)
и
О(logN)
и есть объяснение. Ты хочешь, чтобы я показал почему в первом случае N, a во втором логарифм?

Ну, что слабо...?
Reply With Quote
Old 01.10.2002, 14:26   #8
Академик
 
greka's Avatar
 
Join Date: 09 2001
Location: inside myself
Posts: 5,369
Downloads: 0
Uploads: 0
Reputation: 18 | 5
Wink

я надеялся, что ты объяснишь разницу с точки зрения архитектуры процессора.
эх...
Reply With Quote
Old 01.10.2002, 14:30   #9
Грустно...
 
Agregat's Avatar
 
Join Date: 08 2002
Location: Там, где всегда идут дожди
Age: 35
Posts: 21,717
Downloads: 2
Uploads: 0
Reputation: 250 | 7
Post

С точки зрения прцессора тут никакой разницы.
Тут разница с точки зрения компилятора.
В нем весь прикол... ну что?
Тесты прогнал, или как?
Reply With Quote
Old 01.10.2002, 16:01   #10
Академик
 
greka's Avatar
 
Join Date: 09 2001
Location: inside myself
Posts: 5,369
Downloads: 0
Uploads: 0
Reputation: 18 | 5
Post

ne a
Reply With Quote
Old 01.10.2002, 20:02   #11
Грустно...
 
Agregat's Avatar
 
Join Date: 08 2002
Location: Там, где всегда идут дожди
Age: 35
Posts: 21,717
Downloads: 2
Uploads: 0
Reputation: 250 | 7
Post

а ты попробуй...удивишься
Reply With Quote
Old 06.10.2002, 03:21   #12
Дошкольник
 
Join Date: 03 2002
Location: Yerevan
Posts: 111
Downloads: 0
Uploads: 0
Reputation: 0 | 0
Post

А чё, ничего страшного
В рилизе-то "maximize speed" стоит по дефолту - вот он и соптимизировал - взял вместо a-кратного суммирования b подставил простое умножение а на б. Любой алгоритм оптимизирования кода по скорости в первую очередь это и сделает

Code:
6:    int Naive (int a, int b)
7:    {
00401000 8B 4C 24 04          mov         ecx,dword ptr [esp+4]
00401004 33 C0                xor         eax,eax
00401006 85 C9                test        ecx,ecx
00401008 7E 07                jle         Naive+11h (00401011)
0040100A 0F AF 4C 24 08       imul        ecx,dword ptr [esp+8]
0040100F 8B C1                mov         eax,ecx
8:        int z = 0;
9:        while (a > 0)
10:       {
11:           z += b;
12:           --a;
13:       }
14:       return z;
15:   }
Reply With Quote
Old 06.10.2002, 21:16   #13
Грустно...
 
Agregat's Avatar
 
Join Date: 08 2002
Location: Там, где всегда идут дожди
Age: 35
Posts: 21,717
Downloads: 2
Uploads: 0
Reputation: 250 | 7
Post

Вот правильно. Но вот El Greko до этого допирать не стал. Даже поленился программу собрать, скомпилить, тесты прогнать - а ведь всего минут пять на это надо

А на самом деле тут интересней другое, как оптимизатор до этого допер (на этот вопрос у меня нет четкого решения).
Второе, такой вопрос (на который я тоже знаю ответ) - как обмануть компилятор, чтобы он не сумел соптимизировать этот код.
Итак два новых вопроса:
1. Как оптимизатор допер
2. как его обмануть

Удачи всем.
Reply With Quote
Old 07.10.2002, 03:03   #14
Дошкольник
 
Join Date: 03 2002
Location: Yerevan
Posts: 111
Downloads: 0
Uploads: 0
Reputation: 0 | 0
Post

"Как допер ?" - Ничерта себе вопросики Это уже целая теория, про это столько всего понаписано... А обмануть можно - но я думаю только за счет реального замедления - то есть вставления реальной неопределенности, за счет косвенной ссылки на счетчик или что-нибудь в таком роде. Поскольку в обще написать алгоритм, который находит тривиальные циклы в псевдокоде генерируемым компилятором из исходного кода не так уж и сложно. Обычно этот "псевдокод" куда проще выглядит, чем реальный бинарный код, получаемый на выходе.
Reply With Quote
Old 08.10.2002, 05:55   #15
Грустно...
 
Agregat's Avatar
 
Join Date: 08 2002
Location: Там, где всегда идут дожди
Age: 35
Posts: 21,717
Downloads: 2
Uploads: 0
Reputation: 250 | 7
Post

Я могу скзать самое простое решение без "чувственного" замедления

int Naive(int a, int b, int c)
{
...
}

...

int main()
{
int c = 1;
Naive(a, b, c);
}

Во время компиляции компилятор не сможет заменить это все на одну комманду и легчайшим образом обманется. Такие дела.
Сам я не мастак в деле компиляторов... уж так получилось...
Ну удачи...
Reply With Quote
Sponsored Links
Reply

Thread Tools


На правах рекламы:
реклама

All times are GMT. The time now is 16:54.


Powered by vBulletin® Copyright ©2000 - 2017, Jelsoft Enterprises Ltd.