[질문] 효율적인 배열의 초기화 방법...

xyz6572의 이미지

~~~~~~
int x[1000000];
for(int i=0; i < 1000000; i++) x[i]=0;
~~~~~~

이 코드는 배열 x 전체를 초기화 하는 것이 목적인데요,
좀 더 개선된 형태로는 어떤 것들이 있을까요?
정태영의 이미지

man memset

오랫동안 꿈을 그리는 사람은 그 꿈을 닮아간다...

http://mytears.org ~(~_~)~
나 한줄기 바람처럼..

winner의 이미지

현재의 computer architecture 의 단일 CPU 에서 가장 효율적으로 일반화된 algorithm 입니다. -_-

unsigned char 가 아니라면 memset 은 잠재적인 문제를 낳을 수 있습니다.
http://bbs.kldp.org/viewtopic.php?t=22802&highlight=

winner의 이미지

int x[1000000]; 
for(int i=0; i < 1000000; i += 8) {
    x[i]=0;
    x[i+1] = 0;
    x[i+2] = 0;
    x[i+3] = 0;
    x[i+4] = 0;
    x[i+5] = 0;
    x[i+6] = 0;
    x[i+7] = 0;
}

이런 식의 code 가 병렬화를 돕는다고 하는군요...
정말 KIN 이 아닐 수 없습니다.

그 책에서는 안쪽에 조건문이 포함된 예제였는데 그의 실험에서는 8번 펼치는 것이 가장 성능이 좋았다고 합니다..

이런 성능최적화는 platform 에 따라 다를 수 있습니다.

자신의 computer architecture 에서 일반화된 효율적인 algorithm 을 사용하시는 것을 추천합니다.

akbar의 이미지

...

IOKLO의 이미지

int x[1000000]={0};

단 0으로 초기화할경우만 해당되겠네요;

방준영의 이미지

winner wrote:
현재의 computer architecture 의 단일 CPU 에서 가장 효율적으로 일반화된 algorithm 입니다. -_-

unsigned char 가 아니라면 memset 은 잠재적인 문제를 낳을 수 있습니다.
http://bbs.kldp.org/viewtopic.php?t=22802&highlight=


memset은 100% 안전하고도 가장 빠른 방법입니다.
익명사용자의 이미지

0 이외의 값으로 초기화하는데 특히 "특정" 정수값으로 초기화하는데는 조금 더 머리를 써야합니다. 직접해보시면 알수 있음

ㅡ,.ㅡ;;의 이미지

xyz6572 wrote:
~~~~~~
int x[1000000];
for(int i=0; i < 1000000; i++) x[i]=0;
~~~~~~

이 코드는 배열 x 전체를 초기화 하는 것이 목적인데요,
좀 더 개선된 형태로는 어떤 것들이 있을까요?

int x[1000000] = { 1, 2, 3, 0, };
C언어는 아주간단히 초기화 됩니다.


----------------------------------------------------------------------------

cinsk의 이미지

정수일 경우에는 memset()을 쓰시는게 젤 낫습니다.
실수일 경우나 포인터의 경우에는 그냥 for를 쓰시는게 좋구요.

winner의 이미지

초기화선언 멋지군요...
동적할당을 사용하지 않는 경우입니다만...

방준영 wrote:
memset은 100% 안전하고도 가장 빠른 방법입니다.

memset 의 안정성은 정수형의 bit 표현에 있어 모든 bit 가 꺼진 상태를 0 이라고 해야만 보장됩니다.
그러므로 100% 라는 것은 잘못되었다고 봅니다.

그리고 akbar 씨의 source 를 보면 double 형으로 변환한다음 하는군요.
doube 형에서 0 의 bit 표현은 어떻게 되나요?

제가 알기로 IEEE, PDP-11 의 부동소수점 표현은 hidden bit 가 있기 때문에 0 은 특별히 정해놓아야 한다는 것으로 압니다.
모든 bit 가 0 일때인가요?

akbar의 이미지

winner wrote:

doube 형에서 0 의 bit 표현은 어떻게 되나요?

제가 알기로 IEEE, PDP11 의 부동소수점 표현은 hidden bit 가 있기 때문에 0 은 특별히 정해놓아야 한다는 것으로 압니다.
모든 bit 가 0 일때인가요?

IEEE 규격의 경우 모든 bit 가 0 입니다.
그러나 컴파일러가 IEEE 규격으로 소수를 표현해야 될 의무는 없습니다.
그러니 제가 짠 소스는 이식성면에서 약간 흠이 있는 것이죠
게다가 int 형배열을 2 개씩 끊어서 double 형으로 변환하는 과정에서
약간의 오버헤드가 있을 듯도 합니다.
더 튜닝을 해봐야 되겠지만
저 처럼 doube 형을 이용하는 것 보다는
g++ 의 경우 8 바이트 짜리 long long 형이나
VC++ 의 경우 _int64 형 정수를 이용하는 것이 더 좋습니다.

방준영의 이미지

winner wrote:
방준영 wrote:
memset은 100% 안전하고도 가장 빠른 방법입니다.

memset 의 안정성은 정수형의 bit 표현에 있어 모든 bit 가 꺼진 상태를 0 이라고 해야만 보장됩니다.
그러므로 100% 라는 것은 잘못되었다고 봅니다.

0은 모든 비트가 꺼져 있다는 뜻입니다.
saxboy의 이미지

int x[1000000]; 
for(int i=0; i < 1000000; i += 8) { 
    x[i]=0; 
    x[i+1] = 0; 
    x[i+2] = 0; 
    x[i+3] = 0; 
    x[i+4] = 0; 
    x[i+5] = 0; 
    x[i+6] = 0; 
    x[i+7] = 0; 
} 

일명 loop unrolling 이지요. gcc라면 -funroll-loops

winner의 이미지

'생각하는 programming' 에서 Jon Bently 는 자신의 compiler 의 최대최적화 option 을 주고 test 했다고 하는데 역시 성능이란 알 수 없군요.

ㅡ,.ㅡ;;의 이미지

음.. 그참이상하군요..
왜전부 초기화를 그렇게 하시는건지....

제가 간단히 테스트를 해봤습니다.



int a( void )
{
        int a[100] = { 0, };

        return 0;
}

int b( void )
{
        int a[100];
        memset( a, 0, sizeof( a ));
        return 0;
}

int c( void )
{
        int a[100];
        int i;

        for( i = 0; i < 100 - 8; i += 8 )
        {
                a[i] = 0;
                a[i+1] = 0;
                a[i+2] = 0;
                a[i+3] = 0;
                a[i+4] = 0;
                a[i+5] = 0;
                a[i+6] = 0;
                a[i+7] = 0;
        }

        for( ; i < 100; i++ ) a[i] = 0;


        return 0;
}

int main( void ) 
{ 
        int i;

        time_elapse();
        for( i = 0; i < 1000000; i++ ) a();
        printf( "a[%f]sec \n", time_elapse() ); 

        time_elapse();
        for( i = 0; i < 1000000; i++ ) b();
        printf( "b[%f]sec \n", time_elapse() ); 

        time_elapse();
        for( i = 0; i < 1000000; i++ ) c();
        printf( "c[%f]sec \n", time_elapse() ); 


        return 0;  
} 
-----------결과
a[0.190625]sec 
b[0.293522]sec 
c[1.209016]sec 

로나옵니다. 그나마 맴셋은 성능이 두배까지는 안떨어져도 상당히 떨어지죠
마지막 c함수는 성능이 말도 안되는군요..


----------------------------------------------------------------------------

saxboy의 이미지

Quote:
음.. 그참이상하군요..
왜전부 초기화를 그렇게 하시는건지....

제가 간단히 테스트를 해봤습니다.

음... 컴파일 옵션을 어떻게 주신 건지 여쭤봐도 될까요?
제가 돌려보려고 했더니 time_elapse()를 쓰기가 귀찮군요. :oops:

ㅡ,.ㅡ;;의 이미지

saxboy wrote:
음... 컴파일 옵션을 어떻게 주신 건지 여쭤봐도 될까요?
제가 돌려보려고 했더니 time_elapse()를 쓰기가 귀찮군요. :oops:

[time_compare]$ cc time_elapse.c

ㅡㅡ;;


----------------------------------------------------------------------------

방준영의 이미지

ㅡ,.ㅡ;; wrote:
saxboy wrote:
음... 컴파일 옵션을 어떻게 주신 건지 여쭤봐도 될까요?
제가 돌려보려고 했더니 time_elapse()를 쓰기가 귀찮군요. :oops:

[time_compare]$ cc time_elapse.c

ㅡㅡ;;


최적화 옵션을 안주고 컴파일하니까 당연히 그런 결과가 나올 수 밖에요. :roll: -O1만 줘도 루프로 돌리는거나 memset 쓰는 거나 똑같은 코드가 생성됩니다. 그밖에도 memset은 컴파일러에 의해 아키텍쳐에 가장 적합한 코드로 최적화될 수 있기 때문에 더 권장할 만한 방법입니다.
정태영의 이미지

server root # gcc -O3 test.c
server root # ./a.out
a[0.000001]sec
b[0.196343]sec
c[0.194609]sec
server root # gcc -O2 test.c
server root # ./a.out
a[0.000002]sec
b[0.058705]sec
c[0.192005]sec
server root # ./a.out
a[0.000001]sec
b[0.002172]sec
c[0.241806]sec
server root # gcc -O1 test.c
server root # ./a.out
a[0.000002]sec
b[0.111558]sec
c[0.252275]sec
server root # gcc -O0 test.c
server root # ./a.out
a[0.000003]sec
b[0.293094]sec
c[0.662229]sec
server root #

O2 의 최적화가 힘을 발휘하는군요 흐흐흐흐..
결과가 이상해서 두번 실행시켰었습니다..

O2 가 O3보다 더 빠른 코드를 만들어낸다는 걸 어디서 본 기억이 있는데..
실제로 그런 코드가 바로 여기서 나타났군요 ;)

#include <stdio.h>
#include <sys/time.h>
                                                                                
struct timeval st, sp;
                                                                                
double time_elapse(){
                                                                                
        struct timeval tt;
        gettimeofday( &sp, NULL );
                                                                                
        tt.tv_sec = sp.tv_sec - st.tv_sec;
        tt.tv_usec = sp.tv_usec - st.tv_usec;
                                                                                
        gettimeofday( &st, NULL );
                                                                                
        if( tt.tv_usec < 0 ){
                                                                                
                tt.tv_usec += 1000000;
                tt.tv_sec--;
                                                                                
        }
        return (double)tt.tv_usec/1000000 + (double)tt.tv_sec;
                                                                                
}

첨부해주신 소스에 이런걸 추가해서 컴파일한 후 테스트했습니다 ;)

오랫동안 꿈을 그리는 사람은 그 꿈을 닮아간다...

http://mytears.org ~(~_~)~
나 한줄기 바람처럼..

최종호의 이미지

Sun Sparc, Solaris 7에서 time_elapse 실행결과입니다.

최적화 없음

% a.out
a[0.750000]sec 
b[0.870000]sec 
c[1.470000]sec 

% a.out
a[0.740000]sec 
b[0.640000]sec 
c[1.500000]sec 

% a.out
a[0.740000]sec 
b[0.600000]sec 
c[1.470000]sec 

% a.out
a[0.740000]sec 
b[0.630000]sec 
c[1.470000]sec 

% a.out
a[0.740000]sec 
b[0.670000]sec 
c[1.470000]sec 

최적화 1 (-xO1)

% a.out
a[0.700000]sec 
b[0.540000]sec 
c[0.820000]sec 

% a.out
a[0.710000]sec 
b[0.540000]sec 
c[0.760000]sec 

% a.out
a[0.700000]sec 
b[0.530000]sec 
c[0.760000]sec 

% a.out
a[0.700000]sec 
b[0.530000]sec 
c[0.770000]sec 

% a.out
a[0.710000]sec 
b[0.530000]sec 
c[0.760000]sec 

최적화 2

% a.out
a[0.030000]sec 
b[0.900000]sec 
c[0.370000]sec 

% a.out
a[0.020000]sec 
b[0.930000]sec 
c[0.370000]sec 

% a.out
a[0.030000]sec 
b[0.520000]sec 
c[0.370000]sec 

% a.out
a[0.030000]sec 
b[0.510000]sec 
c[0.380000]sec 

% a.out
a[0.030000]sec 
b[0.920000]sec 
c[0.370000]sec 

최적화 3

% a.out
a[0.030000]sec 
b[0.510000]sec 
c[0.310000]sec 

% a.out
a[0.020000]sec 
b[0.610000]sec 
c[0.310000]sec 

% a.out
a[0.030000]sec 
b[0.580000]sec 
c[0.310000]sec 

% a.out
a[0.020000]sec 
b[0.860000]sec 
c[0.310000]sec 

% a.out
a[0.030000]sec 
b[0.510000]sec 
c[0.310000]sec 

최적화 만땅옵션 (-xO5)
% a.out
a[0.030000]sec 
b[0.870000]sec 
c[0.310000]sec 

% a.out
a[0.030000]sec 
b[0.950000]sec 
c[0.310000]sec 

% a.out
a[0.010000]sec 
b[0.520000]sec 
c[0.300000]sec 

% a.out
a[0.030000]sec 
b[0.730000]sec 
c[0.300000]sec 

% a.out
a[0.020000]sec 
b[0.540000]sec 
c[0.300000]sec 

% a.out
a[0.020000]sec 
b[0.530000]sec 
c[0.300000]sec 

컴파일과 실행환경은 다음과 같습니다.

% cc [최적화옵션] time_elapse.c

% cc -V
cc: WorkShop Compilers 5.0 98/12/15 C 5.0
usage: cc [ options] files.  Use 'cc -flags' for details

% uname -a
SunOS hostname 5.7 Generic_106541-23 sun4u sparc SUNW,Ultra-80
winner의 이미지

정태영씨의 실험에 있어서

Assembly Code 를 생성해서 분석해봐야 알겠는데 a 함수의 실행속도는 경이적이다 못해 사기에 가깝네요.

실제로 배열을 사용하지 않으므로 아예 만들지도 않은 것은 아닌지...
Linux 는 copy on write 최적화가 잘 되어 있다고 들었습니다.

0 으로 초기화를 하면 일단 write 하는 것입니다만 초기화 해놓고 사용하지 않으니 아예 만들지도 않은 것은 아닌지... -_-

memset 의 안정성에 대해서는 저도 자신이 없었는데 영문 news group 을 뒤지다 이런 글을 찾았습니다.
[url]http://groups.google.co.kr/groups?hl=ko&lr=&ie=UTF-8&inlang=ko&newwindow=1&threadm=danpop.879265341%40news.cern.ch&rnum=3&prev=/groups%3Fq%3Dmemset%2Bgroup:comp.lang.c.*%26hl%3Dko%26lr%3D%26ie%3DUTF-8%26inlang%3Dko%26newwindow%3D1%26group%3Dcomp.lang.c.*%26selm%3Ddanpop.879265341%2540news.cern.ch%26rnum%3D3[/url]

글쓴이:Richard Heathfield
제목:Re: memset

전략...

3) integer types (except unsigned char and, possibly, char and signed char). Trap representations are the problem here. Imagine a system with INT_MAX at 1000000000+ (you can work it out if you like!), so ints have a sign bit, 30 value bits, and a parity bit which keeps the number of 1 bits odd, and traps if the number of 1 bits is even.

후략...

-해석-
정수형들은(unsigned char 를 제외한다. 어쩌면 char 와 signed char 도 제외될지 모른다.) 내부표현함정이 이 경우에 존재한다. INT_MAX 의 최대값이 10억 이상인 system 을 생각해보자(당신이 관심을 갖는다면 해볼 수 있다!), int 는 부호 bit 를 가지고, 30 개의 값 bit 들을 가진다, 그리고 켜진 bit 들의 수를 항상 홀수로 만들어주는 parity bit 가 있다. 만약 켜진 bit 들이 짝수라면 문제가 발생한다.

해석하기 힘드네요... -_-..

제대로 해석했는지도 모르겠군요. 일단 직역해봤습니다.
여기서 볼 수 있는 문제는 0 을 표현할 때 다른 모든 bit 들이 꺼진다면 켜진 bit 들을 홀수로 만들어주는 parity bit 는 켜져야 한다는 것입니다.

memset 을 사용하면 모든 bit 들이 꺼지기 때문에 unsigned char 가 아닌 다른 정수형의 0 과는 동일하지 않게 된다는 이야기입니다.

처음 이문제를 보았을 때 padding bit 문제라는 것은 알겠는데 padding bit 가 동일한가를 판별하는 기준이 될 수 있는가라는 고민을 했습니다.
즉 padding bit 의 차이가 == 연산을 거짓이라고 만들 수 있는가라는 것이죠.
물론 memcmp 는 거짓이 나올 수 있습니다만 그것으로 정수형의 0과는 다르다고 할 수는 없을 것입니다.

위의 parity bit 처럼 padding bit 의 값이 중요한 system 도 있다는 것을 처음 알았습니다... -_-

방준영의 이미지

위 벤치마크 프로그램은 잘못되었습니다. 초기화를 한 뒤 아무것도 안하기 때문에 컴파일러가 해당 코드를 아예 생성조차 하지 않거든요. 그러니 a()가 b()보다 수만배 이상 빠르게 보여도 이상한 일이 아니죠.

ㅡ,.ㅡ;;의 이미지

더 빠른방법을 찾아냈습니다...

int a( void )
{
	int a[1000] = { 0, };

	return 0;
}

int b( void )
{
	int a[1000];
	memset( a, 0, sizeof( a ));
	return 0;
}

int c( void )
{
	int a[1000];
	int i;

	for( i = 0; i < 1000 - 8; i += 8 )
	{
		a[i] = 0;
		a[i+1] = 0;
		a[i+2] = 0;
		a[i+3] = 0;
		a[i+4] = 0;
		a[i+5] = 0;
		a[i+6] = 0;
		a[i+7] = 0;
	}
	
	for( ; i < 1000; i++ ) a[i] = 0;
	
	
	return 0;
}

int d( void )
{
	int a[1000];
	long double *p;
	int *ap;

	for( p = (long double *)a; p < (long double *)( a + 1000 ) - 8; p += 8 )
	{
		*p = 0;
		*( p + 1 ) = 0;
		*( p + 2 ) = 0;
		*( p + 3 ) = 0;
		*( p + 4 ) = 0;
		*( p + 5 ) = 0;
		*( p + 6 ) = 0;
		*( p + 7 ) = 0;
	}
	for(  ap = (int *)p; ap < a + 1000; ap++ ) *ap = 0;
	return 0;
}
int main( void ) 
{ 
	int i;
	
	time_elapse();
	for( i = 0; i < 100000; i++ ) a();
	printf( "a[%f]sec \n", time_elapse() ); 

	
	time_elapse();
	for( i = 0; i < 100000; i++ ) b();
	printf( "b[%f]sec \n", time_elapse() ); 

	time_elapse();
	for( i = 0; i < 100000; i++ ) c();
	printf( "c[%f]sec \n", time_elapse() ); 

	time_elapse();
	for( i = 0; i < 100000; i++ ) d();
	printf( "d[%f]sec \n", time_elapse() ); 
	
	return 0;  
} 

[localhost time_compare]$ cc -O5 time_elapse.c
[localhost time_compare]$ ./a.out
a[0.146114]sec
b[0.145287]sec
c[0.128750]sec
d[0.097788]sec


----------------------------------------------------------------------------

akbar의 이미지

배열을 크게 잡고 다른 방식으로 비교하면 다소 결과가 틀립니다.
그리고 VC++ 이냐 g++ 이냐에 따라서도 약간 달라지네요


#include<ctime>
#include<cstdlib>
#include<iostream>

using namespace std;

const int ArrCnt=258500;

void Init1()
{
    int ArrInt[ArrCnt];
    int Cnt=(ArrCnt)/(sizeof(long double)/sizeof(int));
    int Mod=(ArrCnt)%(sizeof(long double)/sizeof(int));

    long double* pDouble=(long double*)ArrInt;

    int Loop;

    for(Loop=1;Loop<=Cnt;++Loop)
    {
        *pDouble++=0;
    }
    //end for

    int* pInt=(int*)pDouble;

    for(Loop=1;Loop<=Mod;++Loop)
    {
        *pInt++=0;
    }
    //end for
}
//end void Init1()

void Init2()
{
    int ArrInt[ArrCnt] = { 0, };
}
//end void Init2()

void Init3()
{
    int ArrInt[ArrCnt]; 
    memset(ArrInt, 0, sizeof(ArrInt));
}
//end void Init3()

void Init4()
{
    int ArrInt[ArrCnt];

    for(int i=0;i<ArrCnt;++i)
    {
        ArrInt[i]=0;
    }
    //endfor
}
//end void Init3()


int main()
{
    unsigned int i;
    unsigned int Max=3100;

    long l;

    cout<<(l=clock())<<endl;

    for(i=1;i<=Max;++i)
    {
        Init1();
    }
    //endfor

    cout<<(clock()-l)<<endl;
    l=clock();

    for(i=1;i<=Max;++i)
    {
        Init2();
    }
    //endfor

    cout<<(clock()-l)<<endl;
    l=clock();

    for(i=1;i<=Max;++i)
    {
        Init3();
    }
    //endfor

    cout<<(clock()-l)<<endl;
    l=clock();

    for(i=1;i<=Max;++i)
    {
        Init4();
    }
    //endfor

    cout<<(clock()-l)<<endl;
    l=clock();

    return 0;
}
//end int main()

g++ 의 경우

31
4875
3844
3953
4906

VC++ 의 경우 Realse 모드에서는 속도가 워낙 빨라서
unsigned int Max=310000000; 로 더 많게 설정하고...

0
1421
1406
1407
1453

게다가 큰 배열일 경우
Init1() Init2() Init3() Init4() 차례로 호출하지 말고
순서를 바꾸면 결과가 또 약간 달라집니다.
페이징의 영향이긴 하겠지만
아마도 memset 가 가장 일반적으로 빠르지 않나 생각됩니다.

catzbi의 이미지

int a[0x10000000]={0,};

alsong의 이미지

음 속도 체크시 스케쥴링의 영향은 받지 않나요?
그런 방법이 없나요.
글을 읽다보니 궁금해지네요. 왠지 없을것 같은데...

그나저나 백수 언제 탈출하냐... ㅡㅡ; 배고파라.

choissi의 이미지

catzbi wrote:
int a[0x10000000]={0,};

이것은 문제가 될수 있는 초기화 방법입니다.
두개의 코드를 컴파일 해보세요..
초기화를 시키면 그대로 바이너리 사이즈에 반영이 됩니다.

#include <stdio.h>

int aaa[10000000]={0,};
main ()
{

printf("%s\n");

}

#include <stdio.h>

int aaa[10000000];
main ()
{

printf("%s\n");

}

울랄라~ 호기심 천국~!!
http://www.ezdoum.com

winner의 이미지

choissi wrote:
catzbi wrote:
int a[0x10000000]={0,};

이것은 문제가 될수 있는 초기화 방법입니다.
두개의 코드를 컴파일 해보세요..
초기화를 시키면 그대로 바이너리 사이즈에 반영이 됩니다.

#include <stdio.h>

int aaa[10000000]={0,};
main ()
{

printf("%s\n");

}

#include <stdio.h>

int aaa[10000000];
main ()
{

printf("%s\n");

}

예전에 Turbo C 2.01 에서 compile 할 당시에는 차이가 있었습니다.
하지만 Linux 와 GCC 는 차이를 만들지 않는군요.
copy on write 로 인한 차이가 아닌지...
이경우는 copy on use 일까요?

그런데 이것은 조금 의문입니다.
int a[0x10000000]={0,};

왜 16진수로 배열크기를 정하죠?

akbar 씨의 source 를 다시 생각해보는데
C++ 적으로 생각해볼 때 int * 를 double * 로 변환하는 것은 위험하지 않나요?

alignment restriction 문제가 발생할 것 같습니다.

이것은 static_cast 로도 잘못된 cast 이고 reinterpret_cast 를 통해서 해야하지 않나 싶습니다.
아시다시피 reinterpret_cast 는 trick 수준입니다.

ㅡ,.ㅡ;;의 이미지

여테까지중에 속도가 가장빠르게 나오는방법이 d 방법이군요..
생각나서 해봤는데 성능이 다른방법과 비교도 안되게 좋게 나오네요..

int a( void )
{
	int a[1000] = { 0, };

	return 0;
}

int b( void )
{
	int a[1000];
	memset( a, 0, sizeof( a ));
	return 0;
}

int c( void )
{
	int a[1000];
	int i;

	for( i = 0; i < 1000 - 8; i += 8 )
	{
		a[i] = 0;
		a[i+1] = 0;
		a[i+2] = 0;
		a[i+3] = 0;
		a[i+4] = 0;
		a[i+5] = 0;
		a[i+6] = 0;
		a[i+7] = 0;
	}
	
	for( ; i < 1000; i++ ) a[i] = 0;
	
	
	return 0;
}



int d( void )
{
	int a[1000];
	long double *p;
	int *ap;

	for( p = (long double *)a; p < (long double *)( a + 1000 ) - 8; )
		*(p++) = *(p++) = *(p++) = *(p++) = *(p++) = *(p++) = *(p++) = *(p++) = 0;

	for(  ap = (int *)p; ap < a + 1000; ap++ ) *ap = 0;

	return 0;
}

int main( void ) 
{ 
	int i;
	
	time_elapse();
	for( i = 0; i < 100000; i++ ) a();
	printf( "a[%f]sec \n", time_elapse() ); 

	
	time_elapse();
	for( i = 0; i < 100000; i++ ) b();
	printf( "b[%f]sec \n", time_elapse() ); 

	time_elapse();
	for( i = 0; i < 100000; i++ ) c();
	printf( "c[%f]sec \n", time_elapse() ); 

	time_elapse();
	for( i = 0; i < 100000; i++ ) d();
	printf( "d[%f]sec \n", time_elapse() ); 

	return 0;  
} 

역시 C 포인터의 힘은 강력하네요..
아래 결과 입니다.

[localhost time_compare]$ cc -O5 time_elapse.c 
[localhost time_compare]$ ./a.out
a[0.145047]sec 
b[0.146154]sec 
c[0.128411]sec 
d[0.028112]sec


----------------------------------------------------------------------------

akbar의 이미지

winner wrote:

akbar 씨의 source 를 다시 생각해보는데
C++ 적으로 생각해볼 때 int * 를 double * 로 변환하는 것은 위험하지 않나요?

alignment restriction 문제가 발생할 것 같습니다.

이것은 static_cast 로도 잘못된 cast 이고 reinterpret_cast 를 통해서 해야하지 않나 싶습니다.
아시다시피 reinterpret_cast 는 trick 수준입니다.

char A[100]; 이라는 배열이 있을 때
2의 배수 단위로 메모리에 접근하는 CPU 를 가정하고
시작번지가 100 이라면 각 원소가
A[0] 은 100 번지
A[2] 은 102 번지
A[3] 은 104 번지
A[4] 은 106 번지..
이렇게 잡힐까요
그렇지 않죠 1 바이트씩 차곡차곡잡힙니다.
alignment restriction 문제가 발생한다면
시작번지 A 를 정할 때 발생할 수가 있겠네요

그리고 int * 를 double * 로 변환하는 것은 위험할 것 같지만
어차피 int 형 배열 범위를 넘지 않으면 상관없죠.
reinterpret_cast 는 다른 형변환 연산자와는 달리
이식성이 없다는 것을 보장하는 연산자입니다.
변칙적인 reinterpret_cast 도 컴파일이 당연히 안되겠지만
reinterpret_cast 의 또 다른 역할은

" 이 변환은 이식성이 없으니 개발자가 다른 플랫폼에 이식할 때 주의하라"

는 메시지를 전달하는 것입니다.
따라서 int 형 배열을 초기화하는 목적으로
int * 를 double * 로 변환하는 코드는
어떤 플랫폼에서도 동일하게 동작함으로
(int 의 크기를 sizeof(int) 로 사용한다든지 하는 기본 룰을 지키면 )
이때에 reinterpret_cast 을 쓰는 것은
바람직하지 않는 것 같습니다.

아래 코드에는 이식성없는 매우 위험한 부분이 있습니다.

ㅡ,.ㅡ;; wrote:
여테까지중에 속도가 가장빠르게 나오는방법이 d 방법이군요..
생각나서 해봤는데 성능이 다른방법과 비교도 안되게 좋게 나오네요..


/* 여러 함수 */

int d( void )
{
	int a[1000];
	long double *p;
	int *ap;

	for( p = (long double *)a; p < (long double *)( a + 1000 ) - 8; )
		*(p++) = *(p++) = *(p++) = *(p++) = *(p++) = *(p++) = *(p++) = *(p++) = 0;

	for(  ap = (int *)p; ap < a + 1000; ap++ ) *ap = 0;

	return 0;
}

int main( void ) 
{ 
                /* 어쩌구 저쩌구 */
	return 0;  
} 

역시 C 포인터의 힘은 강력하네요..
아래 결과 입니다.

[localhost time_compare]$ cc -O5 time_elapse.c 
[localhost time_compare]$ ./a.out
a[0.145047]sec 
b[0.146154]sec 
c[0.128411]sec 
d[0.028112]sec

위에서 int d() 함수는 int a[1000] 를 정상적으로 초기화 할 수 없습니다.
직접 값을 찍어보세요 초기화되지 않는 원소들이 있을 겁니다.
그러니 빨라 보이는 수 밖에...

winner의 이미지

우선

akbar wrote:
char A[100]; 이라는 배열이 있을 때
2의 배수 단위로 메모리에 접근하는 CPU 를 가정하고
시작번지가 100 이라면 각 원소가
A[0] 은 100 번지
A[2] 은 102 번지
A[3] 은 104 번지
A[4] 은 106 번지..
이렇게 잡힐까요
그렇지 않죠 1 바이트씩 차곡차곡잡힙니다.
alignment restriction 문제가 발생한다면
시작번지 A 를 정할 때 발생할 수가 있겠네요

A[0] 은 100 번지
A[1] 은 101 번지
A[2] 은 102 번지

이런 식으로 1byte 씩이란 것인가요?(저는 이렇게 되는 것으로 아는데...)

제가 alignment restriction 을 이해하고 있지 못한 것인지... -_-

시작위치인 A[0] 에서는 alignment restriction 이 발생할 수 있다는 뜻인가요?
(제가 보기에는 그런 것 같은데...)

글의 뜻이 저에게 정확히 오지 않고 있습니다.

ㅡ,.ㅡ;; 씨의 source 에서
*(p++) = *(p++) = *(p++) = *(p++) = *(p++) = *(p++) = *(p++) = *(p++) = 0;
와 같은 code 는 정확한 보장이 안되는 것으로 알고 있습니다.
side effect 가 발생하는 변수는 같은 문장내에서 두번 이상 읽을 경우 side effect 가 발생한 후의 값인지 발생하기 전의 값인지 알 수 없는 것으로 압니다.
만약 제 생각이 맞다면 이것이 제대로 실행되고 있는 것을 확인할려면 Assembly Code 를 생성해서 분석해봐야 할 것 같습니다.

그런데 조금 헷갈리네요.
최근 side effect 와 sequence point 에 대해 다시 찾아볼려고 하고 있습니다.
http://bbs.kldp.org/viewtopic.php?t=33631
와 같이 제가 잘못알고 있는 부분이 꽤 되는군요.

얼라?! ㅡ,.ㅡ;; 씨의 또하나의 답글은 지워졌군요..

ㅡ,.ㅡ;;의 이미지

그렇군요.. 문제가 있네요.. 저도 단순하게 생각했더니.. 약간이상하긴하네요..
고쳐봤습니다..



int d( void )
{
	int a[1000];
	long double *p;
	int *ap;

	for( p = (long double *)a; p < (long double *)( a + 1000 ) - 8; p += 8 )
		*(p) = *(p+1) = *(p+2) = *(p+3) = *(p+4) = *(p+5) = *(p+6) = *(p+7) = 0;
	for(  ap = (int *)p; ap < a + 1000; ap++ ) *ap = 0;

	return 0;
}

결과..

./a.out
a[0.145414]sec 
b[0.145502]sec 
c[0.128796]sec 
d[0.092304]sec 

그래도 제일빠르네요..


----------------------------------------------------------------------------

albamc의 이미지

이렇게 하면... 사족인가요? :oops:

int dd(void)
{
        int a[1000];
        int i;
        long double *p;
        int *ap;
        for (i=0; i<sizeof(long double)/sizeof(int); i++)
                a[i] = 0;
        for (p = (long double*)a; p<(long double*)(a+1000)-8; p+=8)
                *(p) = *(p+1) = *(p+2) = *(p+3) = *(p+4) = *(p+5) = *(p+6) = *(p+7) = *(long double*)&a[0];
        for (ap=(int*)p; ap<a+1000; ap++) *ap=0;
        return 0;
}

근데 속도가 무지 떨어져 버리네요 ... 켁....

^^*

ㅡ,.ㅡ;;의 이미지

winner wrote:

A[0] 은 100 번지
A[1] 은 101 번지
A[2] 은 102 번지

이런 식으로 1byte 씩이란 것인가요?(저는 이렇게 되는 것으로 아는데...)

..

A[0] A[1]... 은 순차적으로 잡힙니다. 단.. 위처럼되진않고요

실제 int 4byte 일경우
int A[1000]; 일때
A[0] 100번지 이면
A[1] 는 104번지가 되겠죠
A[2]]는 108번지...


----------------------------------------------------------------------------

akbar의 이미지

winner wrote:

A[0] 은 100 번지
A[1] 은 101 번지
A[2] 은 102 번지

이런 식으로 1byte 씩이란 것인가요?(저는 이렇게 되는 것으로 아는데...)

제 글에 오타가 있었군요
예, 1byte 씩( 즉 sizeof(자료형) 씩 ) 쌓입니다.

winner wrote:

시작위치인 A[0] 에서는 alignment restriction 이 발생할 수 있다는 뜻인가요?
(제가 보기에는 그런 것 같은데...)

예, 스택배열은 시작위치를 지정할 때 alignment 제한이 있습니다.

char ch1='A';
char ch2='B';
char ch3='C';

에서 각 변수 ch1 ,ch2, ch3 의 구간 길이는 sizeof(char) 바이트가 아닙니다.
char ch3 뒤에 int A[100] 라는 배열을 선언할 경우
변수 ch3 바로 다음부터 배열 A 가 잡히지 않을 수 있습니다.
각 변수의 메모리 주소를 찍어보세요

Testors의 이미지

준영님 말씀대로 위의 테스트 프로그램은 무의미합니다.
비단 a() 뿐만 아니라 다른 테스트 함수의 경우에게도 마찬가지입니다.

똑똑한 컴파일러라면 초기화만 하고 사용되지 않는 위 테스트 함수의 코드를
아예 만들지 않아서 시간이 0에 가까워야 정상입니다.
제가 해당 플렛폼에서 테스트해보지 않았지만, 기가막힌 성능차이가 나온다면 그것은 아마 최적화의 결과일 것입니다.

가령 a(), b(), c() 코드를 그대로 VC++ .Net 에서 컴파일 하면 최적화 되어서 시간이 0 ms 가 걸립니다.

최적화를 피해갈 수 있는 트릭으로는
아래와 같이 변수를 static 으로 바꿔보면..

int b( void ) 
{ 
   static int a[1000]; 
   memset( a, 0, sizeof( a )); 
   return 0; 
} 

이것만으로 저 b() 는 제 플랫폼에서 속도가 약 900배 더 느려졌습니다.
보시다시피 static 키워드를 사용하면 언제 다시 쓰일지 컴파일러가 판단하기 곤란하기 때문에 대개의 최적화가 무시됩니다.

하지만 이 트릭은 a() 와 같은 경우는 무의미 합니다. 왜냐하면..

int a( void ) 
{ 
   static int a[1000] = { 0, }; 
   return 0; 
}

에서 static 변수는 1회 이상 초기화 되지 않기 때문입니다.
해서 a() 같은 경우는 배열을 static 으로 잡는다 해도 여전히 a() 는 0ms 란 경이적인 속도를 자랑하지요. (제 플랫폼 의 경우)

여튼간에 요지는.. 방법간의 성능 비교를 원하신다면
최적화를 피해서 초기화 코드가 수행이 될수 있도록 테스트 프로그램을 재작성 하셔야 한다는 것입니다.

사족인데, 뭔가 삽질을 하는게 아니라면 성능은 크게 차이가 안날것 같습니다만..

ㅡ,.ㅡ;;의 이미지

Testors wrote:
준영님 말씀대로 위의 테스트 프로그램은 무의미합니다.
비단 a() 뿐만 아니라 다른 테스트 함수의 경우에게도 마찬가지입니다.

똑똑한 컴파일러라면 초기화만 하고 사용되지 않는 위 테스트 함수의 코드를
아예 만들지 않아서 시간이 0에 가까워야 정상입니다.
제가 해당 플렛폼에서 테스트해보지 않았지만, 기가막힌 성능차이가 나온다면 그것은 아마 최적화의 결과일 것입니다.

..

제컴파일러는 시키는데로 잘초기화하네요..
시키는데로 말을잘안듣고(?) 게기는 컴파일러라면
return a[999]; 이런식으로 한번줘보시든지
아니면 다르게 한번 간단히 사용해주면되겠죠..


----------------------------------------------------------------------------

댓글 달기

Filtered HTML

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

BBCode

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param>
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

Textile

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • You can use Textile markup to format text.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Markdown

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • Quick Tips:
    • Two or more spaces at a line's end = Line break
    • Double returns = Paragraph
    • *Single asterisks* or _single underscores_ = Emphasis
    • **Double** or __double__ = Strong
    • This is [a link](http://the.link.example.com "The optional title text")
    For complete details on the Markdown syntax, see the Markdown documentation and Markdown Extra documentation for tables, footnotes, and more.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Plain text

  • HTML 태그를 사용할 수 없습니다.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 줄과 단락은 자동으로 분리됩니다.
댓글 첨부 파일
이 댓글에 이미지나 파일을 업로드 합니다.
파일 크기는 8 MB보다 작아야 합니다.
허용할 파일 형식: txt pdf doc xls gif jpg jpeg mp3 png rar zip.
CAPTCHA
이것은 자동으로 스팸을 올리는 것을 막기 위해서 제공됩니다.