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:
Why might Bar be faster than Baz?
Why might Baz be faster than Bar? (Hint: What chapter is this problem associated with?)
By guessing which of these effects is larger, which of the two programs do you expect to be faster?
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
Exercise 15.x1: One can show the subtype relation on Java types by
drawing a diagram with arrows, where each arrow points from a subtype
to one of its supertypes. Arrows can be omitted that are implied by transitivity. As a simple example, if
the types under consideration are Integer, Number, and Object,
one would draw an arrow pointing from Integer to
Number and a second arrow pointing from
Number to Object, but there would be no
need to show an arrow from Integer directly to
Object. Using this diagramming convention, show the
subtyping relation on List<?>,
ArrayList<?>,
List<Number>, ArrayList<Number>,
List<Integer>, and ArrayList<Integer>.