Automatic memory management can be more than the garbage collection. Using the static analysis technologies, we can automatically find memory reuse opportunities in user programs, hence reducing the frequency of garbage collections.
In this thesis, we present a static analysis that estimates reusable memory cells and a source-level transformation that inserts explicit memory-reuse commands into the programs that support algebraic data types. For benchmark programs in ML, our analysis and transformation achieves the memory reuse ratio from 5.2% to 91.3%. The small-ratio cases are for programs that have too much sharings among memory cells. For other cases, our experimental results are encouraging in terms of accuracy and cost. Major features of our analysis are: (1) use of multiset formulas in expressing the sharings and partitionings of heap cells; (2) poly-variant analysis of functions by parameterization for the argument heap cells; (3) deallocations conditioned by dynamic flags that are passed as extra arguments to functions.
Our method is better than existing reported works in terms of its analysis accuracy and effectiveness. Our analysis and transformation is fully automatic and proven correct. Our experiment results are promising enough to conclude that garbage collection combined with the static analysis techniques can comprise more efficient, automatic memory management than garbage collection alone does.
ML같은 상위의 언어에서 메모리 재활용 방법 (garbage collection) 이상의 효율로 메모리를 자동관리할 수 있다. 프로그램 분석 기술을 사용하여 메모리 수거를 거치지 않고 바로 재사용하도록 변환함으로써 메모리 수거의 회수를 줄이거나 필요 메모리 크기를 줄일 수 있다.
본 논문에서는 재사용 가능한 메모리를 추정하는 프로그램 분석과 이를 기반으로 메모리 재사용 명령어를 삽입하는 프로그램 변환 알고리즘을 제시한다. 고안한 기술을 구현해서 다양한 ML 프로그램들에 적용해 본 결과, 총 할당된 메모리 중 5.2%에서 91.3%를 재사용하였고, 재사용에 의해 프로그램이 필요로 하는 메모리 공간을 최대 71.9% 까지 줄일 수 있었다. 향상된 정도가 작은 경우는 프로그램이 원천적으로 재사용 가능성이 낮은 경우들이었다.
제안한 분석과 변환 알고리즘의 핵심 기술은 다음과 같다. (1) 분석의 정확도를 높이기 위해 메모리 셀들의 집합을 분석 도중 나누는 두 가지 방법을 사용한다. (2) 나누어진 조각들이 서로 겹치지 않는지를 메모리 셀들간의 공유정보를 통하여 분석한다. (3) 함수의 분석 결과가 인자에 대한 식으로 얻어지므로 매번 함수 호출시 분석하지 않아도 싸게 정확한 결과를 얻을 수 있다. (4) 실행 시간에 전달되는 논리값 정보를 통해 조건적으로 메모리를 재사용하도록 변환한다.
제안된 알고리즘은 지금까지 알려진 방법과 비교하여 정확하고 효과적이다. 또한 프로그램 작성자의 아무런 도움도 받지 않고 자동으로 프로그램을 변환하며, 변환된 코드는 언제나 안전하다는 것이 증명되었다. 실험 결과를 통하여 프로그램 분석과 결합된 메모리 재활용 방법이 프로그램 분석 없이 홀로 메모리를 관리하는 것보다 더 효과적일 수 있음을 규명하였다.
