양방향 스택. 이름만 들어보면 거창해보이지만 그리 대단한 아이디어는 아님. 덱이랑 비슷하다고 느낄수도 있지만 덱은 자료를 저장하기 위한 자료구조고 내가 생각한 양방향 스택은 자료구조를 보조하는 수단으로 생각해낸 것임.


예시를 하나 들어보자. 어떤 프로그램에서 메모리 할당이 자주 일어나서 성능이 저하된다고 하자. 그중에서 가장 많은 비중을 차지하는 것은 구조체의 할당과 소멸이였음. 메모리 할당 자체는 시스템 호출이 아니지만 오버헤드가 상당해서 할당과 소멸이 자주 일어나면 성능이 크게 하락할 가능성이 높다. 미리 메모리를 할당하고 단순히 구조체의 소멸을 비트 하나로 기록하는 것이 좋은 최적화라고 생각함. 그런데 소멸이 발생했다는 정보는 어떻게 기록할까? 그리고 어떻게 해야 가상으로 소멸된 구조체를 다시 할당했을때의 성능 저하를 피할 수 있을까?


나는 처음에 휴지통이라는 개념을 생각해서 구조체 소멸 명령이 떨어지면 이 구조체의 주소값을 취한 다음 휴지통에 넣고 나중에 구조체를 생성해야 할 일이 생길때 먼저 휴지통을 조사해서 사용 가능한 구조체 주소가 있는지 확인하고 없으면 새로 만든다는 발상을 했었고 실제로도 자주 사용했었음. 그러나 이 방법은 휴지통이라는 공간이 별도로 할당되고 이 공간의 크기가 적절치 않으면 공간을 초과해서 사용할 가능성도 있기 때문에 좋은 방법은 아님. 그런데 예전에 구조체 포인터 <-> 정수형 아이디 변환을 생각하다가 양방향 스택이라는 것을 생각해내고(그때 당시에는 이름을 짓진 않았지만 그런 구조가 가능할 수 있을거라고만 생각하고 있었음.) 이제 그 설명을 해볼려고 함.


앞서 설명했듯이 양방향 스택이라는 구조는 자료구조라고 보기 어렵고 자료구조의 효율성을 위해 보조적으로 사용하는 구조라고 설명한다. (결국 자료구조네)


일단 구조체의 거대한 배열과 각각의 구조체를 가리키는 포인터의 배열을 생각해보자. 구조체의 목적은 데이터를 저장하기 위한 목적이고 포인터의 배열은 구조체에 바로 접근할 수 있는 포인터 대신에 기억하기 쉬운 숫자로 쉽게 구조체 포인터를 나타낼 수 있도록 하는 일종의 테이블이다. 0xDEADBEEF, 0xDEADBEF0, 0xDEADBEF1 따위로 기억하기는 어려우니까 처음 할당된 순서대로 0, 1, 2, ... 이렇게 대응시킨다.


구조체가 생성되면 낮은 주소부터 높은 주소까지 미리 할당된 구조체의 포인터가 1대1 대응이 되고 포인터 배열(테이블)에 구조체의 주소가 저장됨. 미리 설명을 안했지만 포인터 배열에서 각 인덱스에 해당하는 요소가 널 포인터면 해당하는 인덱스의 구조체는 생성되지 않았거나 소멸되었다는 것을 의미함. 이때 생성된 구조체 몇개를 삭제한다면 운이 좋게도 마지막 구조체가 소멸되니 작업이 간단하지만 마지막이 아닌 요소의 구조체가 소멸되면 이 내용을 어딘가에 기록해두어야 하는데 양방향 스택은 구조체가 소멸되었다는 정보를 배열의 마지막 요소에 기록한다. 그리고 나중에 다시 구조체를 생성해야 할때 단순히 배열 마지막부터 저장된 주소값을 가져와서 다시 사용한다.


덱과 앞서 설명한 휴지통의 개념과 분명히 다른 부분이 덱은 추상적으로 생각했을때 중앙부터 데이터가 채워지지만 양방향 스택은 양쪽 끝에서부터 데이터가 채워지고 휴지통과 다른점은 소멸된 구조체를 재사용하기 위해서 기록하는 추가 공간이 필요하지 않다는 것임. 증명은 정말 간단하게도 메모리 공간의 크기 = 사용되고 있는 공간 + 사용되고 있지 않은 공간; 이기 때문임.


그리고 이 방식은 캐시 지역성에도 영향을 주기 때문에 휴지통같이 버퍼를 이용하는 것보다는 성능이 좋을지도 모름. 일단 피곤해서 여기까지만 적어보고 실제 사용례는 내일 올려봄.