Ph.D. Thesis: A Framework for Optimistic Program Optimization

Author:  Igor Pechtchanski

Ph.D. Thesis 

Abstract:  The problem of program optimization is a non-trivial one. Compilers do a fair job, but can't always deliver the best performance. The expressibility of general-purpose languages is limited, not allowing programmers to describe expected run-time behavior, for example, and some programs are thus more amenable to optimization than others, depending on what the compiler expects to see.

We present a generic framework that allows addressing this problem in two ways: through specifying verifiable source annotations to guide compiler analyses, and through optimistically using some assumptions and analysis results for the subset of the program seen so far. Two novel applications are presented, one for each of the above approaches: a dynamic optimistic interprocedural type analysis algorithm, and a mechanism for specifying immutability assertions. Both applications result in measurable speedups, demonstrating the feasibility of each approach.

Download:  This document is 197 pages long.  postscript file (1563K), PDF file (1015K)

BibTeX Entry:  
@PHDTHESIS(pechtchanski-03,
  Author      = "Igor Pechtchanski",
  Title       = "A Framework for Optimistic Program Optimization",
  School      = "New York University",
  Year        = "2003",
  Month       = "September",
)
Copyright © 2003 by Igor Pechtchanski. Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage. To copy otherwise, to republish, to post on servers, or to redistribute to lists, requires prior specific permission.

[Home]

Last modified on
Igor Peshansky
pechtcha@cs.nyu.edu