그냥 이래저래 알고리즘 공부하다가 또, 이전에 Deep Learning공부하던것도 떠오르며 드는 생각은 알고리즘은 꽤나 옛날~ 70년대도 전에 만들어지고, 현재에도 유용하게 사용하는 것들이 많은데, 그때의 문제 공간과 요즘의 문제공간, 그리고 환경이 다르다는 것을 다시 떠올려보고, 여태 잘 쓰이고 있는 이유를 생각해보면서, 아무래도 모든 문제는 공간과 시간의 문제인것으로 결론을 내려봤습니다. 과거의 공간보다 현재의 공간이 더 확장되고, 그만큼 시간도 늘어난 것 같습니다. 컴퓨터는 계속 발전하여, 공간(물리적인 부분)*시간(논리적인 부분)의 가용한 총량을 계속 늘려주고 있는 셈인거고요.
그리고는 그냥 막무가내로 1부터 UINT_MAX까지 더해보는 프로그램을 짜봤습니다. 십몇년전, 학생시절, 또 그보다더 어린시절에도 해봤던 것 같은데, 그때는 엄두가 안 났던것을 그냥 가볍게 할 수 있는 세상이네요. 현재 돌려본 PC는 페넘2 HexaCore 2.8Ghz(boost 3.1Ghz)입니다. 복잡하게 짠게 아닌데, Window10이 똘똘한건지, CPU3개정도가 50%를 찍으며 돌아가네요.
sum(1:4294967286) 의 결과가 78905.8ms가 나옵니다. 연산이 길어서 IO출력은 무시해도 될 것 같고요. 거의 cache내에서 add compare2회 정도가 돌았을 것이라서, 효율이 좋았을 것을 생각한다면.
4294967286/78905.8ms = 54431579 operation-set / second 가 나오네요. 기준 클럭으로 돌았다고 생각하면, 54431579/2800000000 = 0.0194 instruction per clock정도가 나오는데. 대충 디스어셈블 해서, 루프내의 명령이 얼마정도 돌았나 싶은가 세보면, 대강 25개정도가 거의 꾸준히 동작하고 있었을거로 보면. 0.388 instruction / clock 가 되겠네요. IPS로 다시 환산하면, 54431579*25 Instruction/sec = 1360MIPS정도 되네요.
너무 값이 안나온다 싶어서, 중간 IO빼고 돌려봤습니다. 12396.5ms가 나오고, 디어셈해서 명령어 개수는 13정도되네요. 4294967286 * 13/12396.5 ms = 4505MIPS라고 나오니. IO가 눈으로 보이는게 별로 없어도. 그걸 처리하는데 시간 쏟은게 많았던 듯 합니다.
똑같은 코드를 ODROID에서 한번 돌려보렵니다…. 뻗으면 안되는데 –;;
—- 2018/08/14
중고 구매한 Thinkpad X230T에서 돌려봤습니다. I5-3320M 인데, 대략 돌리는 동안 4Thread 45%정도 유지하고, 2Ghz로 동작하네요. Windows 기본속도는 2.6Ghz인데 Full로는 못 뽑나봅니다. 시간은 IO없이. 11972.1ms 가 나오네요.. 빠르네요. 모바일 프로세서인데 2012년도 생산이라 1055T보다 2년 뒤에 나왔을 뿐인데…
—- 2018/8/15
샤오미북 프로 15 에서 확인한 결과. I7-8550 쿼드코어 옥타쓰레드 에서 50%로 3.7Ghz full boosting으로 돌고 대략 9000ms가 나옵니다…. 중간 io안찍을때가 그런건데… 중간중간 출력코드 활성화 해도 14334ms정도가 나오네요… OS는 같았으니, 뭔가 다른 차이가 있는건지 모르겠네요.
코드 붙여 봅니다. Crayon Syntax highlighter를 설치했습니다. 2년전에 업데이트 되고 업데이트가 없는데. 다른 프로젝트로 옮겨간건지.. 취업한건지.. 아무튼 사용은 잘되는것 같고요..
#include <iostream>
#include <chrono>
using namespace std;
int find_MSB(long long v)
{
int n = 0;
while (v >> (n++));
return n-1;
}
#define NDEBUG
int main(void)
{
long long sum = 0;
unsigned int i;
auto start = chrono::steady_clock::now();
for (i = 0; i < UINT_MAX; i++)
{
sum += i;
#if !defined(NDEBUG)
if (sum > LLONG_MAX - (long long)UINT_MAX*10) {
printf("almost there :%lld, exit\n", sum);
break;
}
else
{
if(i%100000000L==0)
printf(" %.1lf G (%.3f%%) iteration, sum=%lld (%.3lf%%)\n", (double)i/ 1000000000L, ((double) i*100/ UINT_MAX), sum, ((double)sum*100/LLONG_MAX) );
}
#endif
}
auto end = chrono::steady_clock::now();
printf(" %lu (%.3lf%%) iteration, sum=%lld (%.3lf%%) MSB @ %d\n", i, ((double)i * 100 / UINT_MAX), sum, ((double)sum*100 / LLONG_MAX), find_MSB(sum));
auto diff = end - start;
cout << chrono::duration<double, milli>(diff).count() << " ms" << endl;
return 0;
}
디어셈블 코드는 아래와같이 나오네요.
auto start = chrono::steady_clock::now();
01063016 lea eax,[start]
01063019 push eax
0106301A call std::chrono::steady_clock::now (010610AAh)
0106301F add esp,4
for (i = 0; i < UINT_MAX; i++)
01063022 mov dword ptr [i],0
01063029 jmp main+44h (01063034h)
0106302B mov eax,dword ptr [i]
0106302E add eax,1
01063031 mov dword ptr [i],eax
01063034 cmp dword ptr [i],0FFFFFFFFh
01063038 jae main+5Dh (0106304Dh)
{
sum += i;
0106303A mov eax,dword ptr [i]
0106303D xor ecx,ecx
0106303F add eax,dword ptr [sum]
01063042 adc ecx,dword ptr [ebp-8]
01063045 mov dword ptr [sum],eax
01063048 mov dword ptr [ebp-8],ecx
#if !defined(NDEBUG)
if (sum > LLONG_MAX - (long long)UINT_MAX*10) {
printf("almost there :%lld, exit\n", sum);
break;
}
else
{
if(i%100000000L==0)
printf(" %.1lf G (%.3f%%) iteration, sum=%lld (%.3lf%%)\n", (double)i/ 1000000000L, ((double) i*100/ UINT_MAX), sum, ((double)sum*100/LLONG_MAX) );
}
#endif
}
0106304B jmp main+3Bh (0106302Bh)
auto end = chrono::steady_clock::now();
0106304D lea eax,[end]
01063050 push eax
01063051 call std::chrono::steady_clock::now (010610AAh)