Jolt: Lightweight Dynamic Analysis and Removal of Object Churn, Ajeet Shankar, Matthew Arnold, Rastislav Bodik. OOPSLA, Nashville, TN, 2008.
Presentation Slides (Powerpoint 03)
It has been observed that component-based applications exhibit object churn, the excessive creation of short-lived objects, often caused by trading performance for modularity. Because churned objects are short-lived, they appear to be good candidates for stack allocation. Unfortunately, most churned objects escape their allocating function, making escape analysis ineffective. We reduce object churn with three contributions. First, we formalize two measures of churn, capture and control. Second, we develop lightweight dynamic analyses for measuring both capture and control. Third, we develop an algorithm that uses capture and control to inline portions of the call graph to make churned objects non-escaping, enabling churn optimization via escape analysis. Jolt is a lightweight dynamic churn optimizer that uses our algorithms. We embedded Jolt in the JIT compiler of the IBM J9 commercial JVM, and evaluated Jolt on large application frameworks, including Eclipse and JBoss. We found that Jolt eliminates over 4 times as many allocations as a state-of-the-art escape analysis alone.

Ditto: Automatic Incrementalization of Data Structure Invariant Checks (in Java), Ajeet Shankar, Rastislav Bodik. PLDI, San Diego, CA, 2007.
Presentation Slides (will only display properly if you have the Montara Std Gothic font; sorry) | Source code and more info
We present Ditto, an automatic incrementalizer for dynamic, side-effect-free data structure invariant checks. Incrementalization speeds up the execution of a check by reusing its previous executions, checking the invariant anew only on the changed parts of the data structure. Ditto exploits properties specific to the domain of invariant checks to automate and simplify the process without restricting what mutations the program can perform. Our incrementalizer works for modern imperative languages such as Java and C#. It can incrementalize, for example, verification of red-black tree properties and the consistency of the hash code in a hash table bucket. Our source-to-source implementation for Java is automatic, portable, and efficient. Ditto provides speedups on data structures with as few as 100 elements; on larger data structures, its speedups are characteristic of non-automatic incrementalizers: roughly 5-fold at 5,000 elements, and growing linearly with data structure size.

Runtime Specialization With Optimistic Heap Analysis, Ajeet Shankar, S. Subramanya Sastry, Rastislav Bodik, James Smith. OOPSLA, San Diego, CA, 2005.
Presentation Slides
We describe a highly practical program specializer for Java programs. The specializer is powerful, because it specializes optimistically, using (potentially transient) constants in the heap; it is precise, because it specializes using data structures that are only partially invariant; it is deployable, because it is hidden in a JIT compiler and does not require any user annotations or offline preprocessing; it is simple, because it uses existing JIT compiler ingredients; and it is fast, because it specializes programs in under 1s. These properties are the result of (1) a new algorithm for selecting specializable code fragments, based on a notion of influence; (2) a precise store profile for identifying constant heap locations; and (3) an efficient invalidation mechanism for monitoring optimistic assumptions about heap constants. Our implementation of the specializer in the Jikes RVM has low overhead, selects specialization points that would be chosen manually, and produces speedups ranging from a factor of~1.2 to~6.4, comparable with annotation-guided specializers.

New Temperatures in Domineering, Ajeet Shankar and Manu Sridharan. INTEGERS, Volume 5, 2005.
Domineering is a two-player game that had only 30 known temperatures with denominator less than 512. We found 259 new Domineering temperatures.

Katana: A Specialized Framework for Reliable Web Servers, Ajeet Shankar and William McCloskey. Technical Report No. UCB/EECS-2006-34, 2006.
E-commerce server reliability is critical, as downtimes cost an average of $10,000 per minute. Commercial web server development today is done with fairly generic programming languages, like Java, Perl, and C#. The generality of these languages, while permitting a wide range of target applications, makes it difficult to guarantee reliability: dynamic type errors, race conditions, and resource leaks contribute to instability. Though the languages may detect such errors at runtime, the resulting downtimes in production code are costly. We present Katana, a specialized framework for creating reliable web servers. Generality is exchanged for specific capabilities tailored to server operation. In particular, servers written with Katana benefit from these properties: truly statically type-checked code; specialized language features for common server tasks, such as data transformation and formatted output; native, statically-checked database interaction; automatic memory management and concurrency control; and built-in state-sharing mechanisms. By eliminating much of the complexity inherent in general-purpose frameworks and unnecessary for web server operation, while retaining a suitable range of expressiveness, Katana servers are not subject to several entire classes of bugs that plague existing web servers, and are thus more reliable. Preliminary results indicate that Katana is comparable to existing server frameworks in terms of ease of use and performance, suggesting that it is a viable architecture for real-world web servers.

Approaches to Bin Packing with Clique-Graph Conflicts, William McCloskey and Ajeet Shankar. Technical Report No. UCB/CSD-05-1378, 2005.
The problem of bin packing with arbitrary conflicts was introduced by Jansen. In this paper, we consider a restricted problem, bin packing with clique-graph conflicts. We prove bounds for several approximation algorithms, and show that certain on- and off-line algorithms are equivalent. Finally, we present an optimal polynomial-time algorithm for the case of constant item sizes, and analyze its performance in the more general case of bounded item sizes.

Leveraging Garbage Collection to Dynamically Infer Heap Invariants, Ajeet Shankar and Trishul Chilimbi. US Patent Application 11/134,796, filed May 2005.
The patent "details various techniques and tools for discovering data structure invariants, which are properties or characteristics of the data structure that generally do not vary during execution of the program (such as, 'Foo.x is a constant' or 'Object[] bar only contains objects of type Baz,' etc.). These techniques and tools leverage the garbage collection process, in that the techniques and tools infer the invariants dynamically, at runtime, by analyzing the data structures on the heap as the garbage collector traverses the data structures. The invariants discovered through this technique could be reintroduced to the source code as static annotations (e.g., in a language like Spec#) to facilitate further code development. Also, the invariants could be learned then enforced at runtime (or through static analysis) to find bugs - those parts of the program code that violate the invariants."

Polar Bears Ultimate is the team I play for.

Modista is a a startup company I founded with Arlo Faria. We help users browse for apparel (shoes, eyewear, and bags) via visual similarity and an intuitive, fast interface. We won first place in the UC Berkeley Business Plan Competition. Pretty exciting stuff!

Sudoku Slam is a site I made with Bill. We think it's the best Sudoku web site out there. (The others we tried were more cumbersome than using a pencil and paper.) There are a bunch of cool features, including Smart Hints (that tell you why the next move makes sense, so you become a better player), smart undo (that takes to back to before you screwed up), bookmarking (to resume a puzzle later or send it to a friend), printing to PDF, and above all a cool UI. Right now it serves up about 10,000 puzzles a day.

Big East Hoops is a blog my high school friends and I run about basketball.

NewsDog is a site I wrote for posting and discussing news articles.

Real Personality lets you see what the people you know really think of you.

Boogle is a program I wrote to generate and solve Boggle boards. If you like playing, it's a good way to see how you stack up to an optimal player.

Gradeboy can help you manage your grades. It's especially useful for applications and such where you need to compute your GPA in various formats and with different sets of classes. It's freeware, and has been downloaded about 20,000 times so far.

Here is a paper I wrote for cs263 on removing array bounds checks from loops.

... and my cs265 survey of incremental computation.

My friend Wing and I have worked together on several successful computer science research projects. Most recently, we created a natural language interface for a graduate databases class called Gnarli (yes, Gnarli). I'm not talking about the cheesy Ask Jeeves-type interface ("the following are possible answers to your question"), but about one that attempts to understand exactly what you're asking and find the correct answer. It can handle questions like, "Which actors have won an oscar for starring in an r-rated action movie longer than 2 hours, and when?" and "How many associate math profs teach classes that meet after 2 on Mondays?" If you're interested, check out a sample walkthrough.

We've also done some pretty interesting graphics projects. In the spring of 2001, we a wrote a sketch renderer that takes computer-generated images and makes it look like people drew them. In the spring of 2000, we made an image inpainter, a program that attempts to intelligently eliminate scratches and other undesired elements of a picture. It's actually useful for anyone who likes photographs.

I was part of IBM's Extreme Blue program during the summer of 2000, and was a project mentor for the program the subsequent year. I then worked as a full timer as one of the project leads for SashXB, an open-source application environment for Linux that was, in retrospect, way ahead of its time. It allowed users to write sophisticated native applications in JavaScript, an idea that seems to be gaining steam now. Check out the tour.

Speaking of CS projects, my brother and I took a compilers class together before he graduated. We worked together on a C-like language we created called Cheetah.

My high school friends and I run our own Fantasy Football league. I wrote the website. It's all automated and stuff.

I took a great Biology class on animal behavior in the fall of 2000. I learned a lot, and found many of the topics to be amazingly interesting. Here is my final research proposal.