MCS-287 Homework 4 (Spring 2009)

Due March 30, 2009

Do exercise 14.1 on pages 269-270. What follows are some hints:
- Sometimes when modifying existing code, it is helpful first to "refactor" it, that is, to modify it in ways that don't affect its behavior, but that put it into a more-easily-modifiable structure. Then, after testing that it still behaves as before, you can make the more substantive changes.
  Changing the first-fit code to best-fit might be a case in point. The current allocate method (in first-fit) is a big method which does a lot. In particular, it has a big chunk that is devoted to finding the block to allocate and another big chunk that is devoted to the problem of removing the allocated space from the free list. Because they are both in the same method, the interface between the two is relatively implicit.
  A reasonable refactoring would be to break this one big method into two or more smaller methods, each of which has a more tightly focused purpose and with an explicit interface between them. Then you might be in a better position to replace the block-finding code (to use best-fit) while not screwing up the connection to the remove-from-feelist code.
- In designing the sequences of allocations and deallocations that will show the difference between first-fit and best-fit, you need to be careful about what "first" means in "first-fit." You presumably understand that the first block found that is big enough is used. But in what order are the blocks examined? Without getting that right, the "first" is not well defined.
- A parenthetical note in the exercise says that you should use the coalescing version of deallocate. That is necessary for the book's two hints about code sequences to work. If you'd rather not use the coalescing version of deallocate, then interchange the last two lines of each of the two code sequences so that they are
```
  mm.deallocate(c);
  mm.deallocate(a);
```
  Deallocating in this order (c before a, rather than a before c) will make the hints valid whether or not you use the coalescing version of deallocate.
Exercise 14.x1: Consider the following two nearly identical Java programs, each of which uses an array of Integers, s, as a stack, with sp serving the role of stack pointer. Each program repeats 100 times the following two stages: (1) push the Integers 0 up to 100000, (2) pop them all back off.
```
public class Bar {
    public static void main(String[] args){
        Integer[] s = new Integer[100000];
        int sp = 0;
        for(int i = 0; i < 100; i++){
            for(int j = 0; j < 100000; j++){
                s[sp++] = j;
            }
            while(sp > 0){
                --sp;
            }
        }
    }
}
```
```
public class Baz {
    public static void main(String[] args){
        Integer[] s = new Integer[100000];
        int sp = 0;
        for(int i = 0; i < 100; i++){
            for(int j = 0; j < 100000; j++){
                s[sp++] = j;
            }
            while(sp > 0){
                s[--sp] = null;
            }
        }
    }
}
```
Answer the following questions about these two programs:
1. Why might Bar be faster than Baz?
2. Why might Baz be faster than Bar? (Hints: (1) What chapter is this problem associated with? (2) The assignment s[sp++] = j uses a feature known as autoboxing, whereby it is a shorthand for s[sp++] = new Integer(j).)
3. By guessing which of these effects is larger, which of the two programs do you expect to be faster?
4. Which one actually is faster? How many times faster? To time a java program, you can use the shell command time, as in
```
time java Bar
```