효율적인 메모리 사용을 위한 free 명령어 삽입 알고리즘

Presentation on theme: "효율적인 메모리 사용을 위한 free 명령어 삽입 알고리즘"— Presentation transcript:

1 효율적인 메모리 사용을 위한 free 명령어 삽입 알고리즘
이욱세 KAIST 전자전산학과/프로그램 분석 시스템 연구단 2002년 10월 26일

2 목적 자동으로 보다 효율적인 메모리 사용 free l fun insert i l = case l of
| h::t => if i<h then i::l else h::(insert i l) free l

3 방법론 메모리 모양새와 사용을 분석 분석결과를 이용해 안전한 free 명령어 삽입 요약 수준을 프로그램 텍스트에 따라 조절
공유 정보 유지 힙 셀들을 분리하는 방법론 사용 분석결과를 이용해 안전한 free 명령어 삽입 실행 시간에 부가적인 정보 전달을 통해 공격적인 메모리 반납(deallocation) 가능

4 예제: copyright fun copyright t = case t of Leaf => Leaf
| Node(t1,t2) => let p = copyright t2 in Node(t1, p)

5 결과: 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))

6 분석: copyright (1) fun copyright t = case t of Leaf => Leaf
| Node(t1,t2) => let p = copyright t2 in Node(t1, p)

7 분석: copyright (2) fun copyright t = case t of Leaf => Leaf
| Node(t1,t2) => let p = copyright t2 in Node(t1, p)

8 분석: copyright (3) fun copyright t = case t of Leaf => Leaf
| Node(t1,t2) => let p = copyright t2 in Node(t1, p)

9 분석: copyright (4) fun copyright t = case t of Leaf => Leaf
| Node(t1,t2) => let p = copyright t2 in Node(t1, p)

10 삽입: copyright (1) fun copyright [b,s] t = case t of Leaf => Leaf
| Node(t1,t2) => let p = copyright t2 in Node (t1, p)

11 삽입: copyright (2) fun copyright [b,s] t = case t of Leaf => Leaf
| Node(t1,t2) => let p = copyright t2 in Node (t1, p)

12 삽입: 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)

13 실험결과

14 결론 효율적인 메모리 사용을 위한 free 명령어 삽입 알고리즘 제시. (5.2%-98.7%)
리스트 기반 프로그램의 경우 정확히 분석. 공유가 심한 경우 분석 결과 나쁨.