[C 프로그래밍] 1억개의 0 또는 1 를 다루는 배열..

배열의 크기는 1억개 ( 100 M ) 이고, 배열의 원소는 0 or 1 이다..

다음 3 가지 방법중 가장 빠른 것은 무엇일까?

1. int 타입의 1억개 크기를 가지는 배열을 malloc 하여 사용한다.
2. char 타입의 1억개 크기를 가지는 배열을 malloc 하여 사용한다.
3. char 타입으로 1억/8 = 1250만개의 크기를 가지는 배열을 malloc 하여 bitwise 연산을 사용한다.

일단 배열의 크기는 당연히 1번은 400 MB, 2번은 100 MB, 3번은 12.5 MB 로 3번이 가장 적게 사용한다.

그러면, 속도는 어느게 제일 빠를까?

데이터는 워드 단위로 처리되니, 워드 크기를 가지는 int 타입이 제일 빠를까?

실제로 프로그래밍 해보면,, 3번이 제일 빠르고, 2번, 1번 순서로 느리다.
비트와이즈 연산을 하는 오버헤드를 고려하더라도 3번이 제일 빠르다.

왜 이런 결과가 나오는 것일까?
이거에 관련된 내용을 k모 게시판에 올렸더니 zz모 님께서 캐쉬 때문이라고 이야기 해주었다.

현재의 컴퓨터 수준에서는 CPU <=> 메모리 구간도 어마어마하게 느린 구간이고, CPU <=> 캐쉬 구간에서 잘 돌아야만 성능이 잘 나온다는 것이다. 캐쉬가 잘 동작하기 위해서는 당연히 사용하는 메모리가 적어야 하며, bitwise 연산을 사용하여 최대한 압축시킨 것이 가장 빠르게 동작한다는 것이다.

- 이쁜왕자 -
- Valken the SEXy THief~~ ^_* -

추가>
unsigned int 타입으로 312.5만개 의 배열을 잡아 bitwise 연산하는게 제일 빠르네요.