효율적인 메모리 사용을 위한 free 명령어 삽입 알고리즘 이욱세 KAIST 전자전산학과/프로그램 분석 시스템 연구단 2002년 10월 26일
목적 자동으로 보다 효율적인 메모리 사용 free l fun insert i l = case l of | h::t => if i<h then i::l else h::(insert i l) free l
방법론 메모리 모양새와 사용을 분석 분석결과를 이용해 안전한 free 명령어 삽입 요약 수준을 프로그램 텍스트에 따라 조절 공유 정보 유지 힙 셀들을 분리하는 방법론 사용 분석결과를 이용해 안전한 free 명령어 삽입 실행 시간에 부가적인 정보 전달을 통해 공격적인 메모리 반납(deallocation) 가능
예제: copyright fun copyright t = case t of Leaf => Leaf | Node(t1,t2) => let p = copyright t2 in Node(t1, p)
결과: copyright fun copyright [b,s] t = case t of Leaf => Leaf | Node(t1,t2) => let p = copyright [bÆ:s,s] t2 in (free t when b; Node (t1, p))
분석: copyright (1) fun copyright t = case t of Leaf => Leaf | Node(t1,t2) => let p = copyright t2 in Node(t1, p)
분석: copyright (2) fun copyright t = case t of Leaf => Leaf | Node(t1,t2) => let p = copyright t2 in Node(t1, p)
분석: copyright (3) fun copyright t = case t of Leaf => Leaf | Node(t1,t2) => let p = copyright t2 in Node(t1, p)
분석: copyright (4) fun copyright t = case t of Leaf => Leaf | Node(t1,t2) => let p = copyright t2 in Node(t1, p)
삽입: copyright (1) fun copyright [b,s] t = case t of Leaf => Leaf | Node(t1,t2) => let p = copyright t2 in Node (t1, p)
삽입: copyright (2) fun copyright [b,s] t = case t of Leaf => Leaf | Node(t1,t2) => let p = copyright t2 in Node (t1, p)
삽입: copyright (3) fun copyright [b,s] t = case t of Leaf => Leaf | Node(t1,t2) => let p = copyright [bÆ:s,s] t2 in Node (t1, p)
실험결과
결론 효율적인 메모리 사용을 위한 free 명령어 삽입 알고리즘 제시. (5.2%-98.7%) 리스트 기반 프로그램의 경우 정확히 분석. 공유가 심한 경우 분석 결과 나쁨.