boolean 배열의 효과적인 구조
글쓴이: MyAbby / 작성시간: 월, 2014/08/04 - 12:23오전
안녕하세요 선배님들.
프로젝트를 하나 하면서 생긴 의문이에요. 영상처리 쪽인데요, 물론 C++로 개발하고 있구요. bool, true/false 자료만 많이 저장할 필요가 있는 데이터가 있어요. 저는 아무 생각없이 bool 배열을 필요한 크기만큼 만들어 사용했습니다. 그런데 생각해보니 너무 낭비인거에요! 한... 만약 720p 영상이면 1280x720 개의 비트가 필요하고, 결국 921,600바이트가 필요하죠. bool은 참거짓, 1비트로 모 아니면 도로 표현하면 되는데 쓸데없이 엔티티당 8비트를 써버리면 7비트가 아깝고 메모리 접근도 비효율적인 것 같았어요. 그래서 시도해 본 것이 첨부파일이에여 (글에 붙이기엔 너무 길고 해서). 별로 안길고, 이클립스 C++ 플러긴으로 썼어요.
시도는 좋았어... 근데 느려! 아마도 값에 접근할 때 필요한 연산이 더 많아서 그런 것 같아요: 나누기연산, 나머지연산, 쉬프트연산, 비트연산, 클래스 참조연산... 기존 bool배열 접근에 비해 5배에요. 굳이 클래스화를 안하고 스코프 내에다 바이트 배열을 선언해 똑같이 해봐도 속도엔 그리 차이가 없었습니다.
제가 실력이 없는 걸까요? 어떻게 하면 크기도 줄이고 속도도 줄일 수 있을까요...
아니면 C로는 어쩔 수 없는 문제인가요.
x
File attachments:
| 첨부 | 파일 크기 |
|---|---|
 DenseBitmap.zip | 108.05 KB |
Forums:
and 연산밖에는 방법이 없다고 보는데
비트연산이 시간이 느리다면..
1바이트 중에 4 바이트만 bool로 채워넣는 방법은 어떠신가요?
그리고 혹시 and 연산을 사용하실때 각 자리수를 구하는 방법을 n&(1<<1) 이런식으로 하셨나요?
만약 그렇게 하셨다면 미리 연산할 숫자를 정의해둬보세요.
int k[] = {1,2,4,8,16,32,64,128};
n&k[3];
이런식으로요
비트 단위로 저장하는 구조를 말하는 건가요?
비트 단위로 저장하는 구조를 말하는 건가요?
struct boolean {
int d : 1;
}
.
.
bitset, bit_vector 등등.. 여러가지 조사해 보시면..
이미 비슷한 의문을 가진 사람들이 많이 있었고 여러가지 테스트해볼 것들이 존재합니다.
이 글도 한 번 보시면 좋겠네요. 여기에 언급된 것들만 직접 테스트해보셔도 충분히 가치있는 결론을 얻으실 수 있을 듯 합니다.
http://stackoverflow.com/questions/11712479/which-bitset-implementation-should-i-use-for-maximum-performance
다만 (어찌보면 당연하지만) 속도도 최강이고 메모리도 제일 적게 먹는 그런 것은 없는 듯 합니다. 현재 테스트해보신 두 가지는 이런 관점에선 양 극단에 존재하는 걸로 생각이 되고요. 결국 트레이드 오프를 하셔야.
그리고 영상처리라면 일반적인 데이터가 아니기 때문에 데이터 자체의 특성을 이용한 추가 최적화가 가능할 수도 있습니다. 정확도를 희생한다든지, 특별히 사용해야 할 값만 저장한다든지, true나 false에 해당하는 인덱스만 저장한다든지, 압축을 동원한다든지 등등등..
--
영상처리라면 순차적으로 처리해야 할 상황이 많이 있을
영상처리라면 순차적으로 처리해야 할 상황이 많이 있을 겁니다. 이런 상황을 잘 이용해 보시기 바랍니다. 이미 읽은 거 재활용하기, 연속값을 모아서 쓰기 등의 방법이 있겠죠.
랜덤성능은 떨어지지만, 프로그램 실행과정 전체를 보았을 때는 무난한 성능인 그런 구현이 되겠죠. 적절히 레지스터를 타게 되면, 메모리 접근이 줄어들어서 어떤 상황에서는 더 빨라질 가능성도 있습니다.
하지만 이갈 써서 하는 실제 영상 프로그램이 각각의 상황을 고려하는 추가 작업을 해 주어야 하기 때문에 사람이 피곤해 지겠죠. 코드 가독성도 나빠지겠지요...
애초에 그정도의 메모리 손해를 없애는 것이, 이런 여러 귀찮은 요소들을 극복할 만한 가치가 있는지는 생각해 볼 문제입니다.
get, set과 같이 특정한 1픽셀에 관한
get, set과 같이 특정한 1픽셀에 관한 operation이라면, 8bit -> 1bit로 자료구조를 정리한 것에 대한 performance advantage는 없다고 봅니다.
하지만, 영상처리에서 주로 하는 건 특정한 1픽셀에 대한 처리가 아니라, 이미지 끼리의 연산이나 이미지 영역 전체(혹은 일부)에 대한 필터처리라고 봤을 때, 자료구조를 정리한 것은 좋은 방향으로 보이며, 특히 아래와 같은 이점을 꾀할 수 있다고 봅니다.
- SIMD명령의 병렬도가 증가함
(타겟 아키텍처가 뭔지 정보가 없지만, 요즘 흔히 쓰이는 x86계열이라면 SSE, AVX등 쓸 수 있잖아요? ARM이면 NEON)
- 캐쉬메모리에 더 잘 먹힘
음.. DenseBitmap 클래스 소스를 안올리셔서
음.. DenseBitmap 클래스 소스를 안올리셔서 직접 확인은 못했습니다만, 5배까진 아니라고 봅니다.
제가 간단히 해본 결과로는 1차원 배열 접근 시, 바이트 배열 대비 비트 배열이 약 70% 이상의 성능을 낼 수 있었습니다.
( 대충 해서 잘 비교됐는진 장담 못하겠네요 -_-;;;; )
성능은 70% 정도(2차원 화면이라면 70*70/100=50% 정도)에 저장 효율은 1/(8*8) 로 격감한다면 충분히 시도해볼만 할 겁니다.
참고로 2^n 겂을 곱하거나 나눌 때는 실제로 나머지 및 나누기 연산이 필요 없습니다.
int b = i >> 3; // 3 우 시프트하면 8로 나누는 효과
int n = i - b << 3; // 3 좌 시프트로, 8 로 나눈 값에 다시 8을 곱하고, 원래 값에서 빼면 나머지가 구해짐.
Orion Project : http://orionids.org
나머지 연산의 경우에는 n &= 8 하면 더
나머지 연산의 경우에는 n &= 8 하면 더 간단하죠.
근데 이거는 알아서 최적화 시켜 주지 않나요?
unsigned 인 경우, gcc(arm. x86)
unsigned 인 경우, gcc(arm. x86) 는 합니다.
signed 일 경우엔 shift 연산으로 바꾼다는 발상 자체가 에러죠.
제가 올려주신 코드로 테스트해 보니 대략 9배 정도
제가 올려주신 코드로 테스트해 보니 대략 9배 정도 속도가 느리군요.
그런데 첫 글에서 말씀하신 것과는 달리, 클래스로 구현하지 않고 main()안에 배열을 잡아서 클래스 구현과 같은 비트연산을 써서 구현해 보니 그 차이가 두배 이내 정도로 줄어들었습니다. 이 정도라면 메모리 잇점도 있기 때문에 상황에 따라서는 매력적으로 보일 수 있는 정도 아닌지요.
그러니까 비트연산 등 추가적인 연산이 필요한데서 오는 성능 저하도 있겠지만, 이 경우에 클래스로 구현하면서 오버헤드가 생긴 것이 더 큰거 같습니다. 따라서 클래스 구현에 개선할 여지가 없는지 조사해 보는 것에 집중할 필요가 있다고 생각합니다. 물론 질문자께서는 클래스 구현과 차이가 나지 않았다고 하시니,,, 이런 결과도 있으니 참고정도는 하시라고 말씀드려야겠네요.
굳이 직접 만들 필요없이 vector을 쓰면 됩니다.
굳이 직접 만들 필요없이 vector을 쓰면 됩니다. 공간 최적화 해줍니다. 속도도 꽤나 빠르고요.
http://www.cplusplus.com/reference/vector/vector-bool/
댓글 달기