Now consider the hash table data structure. An ideal hash function will map a key to a ``random'' location in the table. The random distribution of keys in the hash table allows us to limit the number of collisions. However, randomness by its very nature hampers the ability of a virtual memory system to determine which pages should be placed in physical memory.
The following simple C program illustrates the situation:
Table = malloc(TableSize*sizeof(double)) ;
for (i=1; i <= Reps ; i++) {
r = lrand48() ;
r = r % TableSize ;
x = drand48() ;
Table[r] = x ;
}
This program simply accesses the array Table at random locations many
times. When compiled and executed on an SGI Indigo with 32 megabytes
of real memory, the following running times result when Reps is set
to one million.
huckleberry% time a.out 1000 1000000
TableSize = 1000, Reps = 1000000
12.5u 0.0s 0:12 97% 0+0k 1+0io 0pf+0w
huckleberry% time a.out 100000 1000000
TableSize = 100000, Reps = 1000000
12.9u 0.0s 0:13 95% 0+0k 0+0io 0pf+0w
huckleberry% time a.out 1000000 1000000
TableSize = 1000000, Reps = 1000000
13.2u 0.3s 0:13 97% 0+0k 0+0io 0pf+0w
huckleberry% time a.out 2000000 1000000
TableSize = 2000000, Reps = 1000000
13.3u 0.7s 0:15 93% 0+0k 0+0io 0pf+0w
huckleberry% time a.out 4000000 1000000
TableSize = 4000000, Reps = 1000000
26.2u 113.1s 48:52 4% 0+0k 3+0io 128600pf+0w
huckleberry% time a.out 8000000 1000000
TableSize = 8000000, Reps = 1000000
41.4u 337.0s 4:36:47 2% 0+0k 10+0io 543991pf+0w
When TableSize is one thousand through 2 million, the running time is
essentially the same. This corresponds to our theoretical model where
each array access takes constant time. However, when TableSize is
2 million and higher, the running time increases dramatically. In these
runs, the user time (first number) and the system time (second number)
are higher. These increases are due to an increase in the number of
page faults generated by the program (the number preceding ``pf'').
When TableSize is 2 million, no page faults were generated.
When TableSize is 8 million, more than five hundred thousand page faults
occurred. Thus, more than half the array accesses resulted in a page fault.
This program was obviously thrashing, which caused the operating system
to place it in a lower priority queue. The result is that the elapsed
time for 1 million accesses went from 15 seconds to 4 hours and 36 minutes.
It is important to note that the problem here is not the size of the array, but the pattern of the array access. In the following simple program, we access each element of the array in consecutive order.
Table = malloc(TableSize*sizeof(double)) ;
for (i=0; i < TableSize; i++) {
x = drand48() ;
Table[i] = x ;
}
When compiled and executed on the same machine as above, the running time
is still reasonable for an array with 8 million elements. Note that only
8 page faults occurred in this execution.
huckleberry% time run.out 8000000
TableSize = 8000000
50.1u 3.0s 1:14 71% 0+0k 7+0io 8pf+0w
First, you should determine experimentally if real hash functions actually generate array accesses in a way that causes thrashing. You should implement at least the division method, the multiplication method and the universal hash functions described in the textbook. In your report, you should summarize the conditions under which thrashing would occur. Are there hash functions that perform well as hash functions yet are not so random as to cause thrashing?
For the second part of your project, you will consider some ways that you can work around the problems with hashing and virtual memory. Suppose that you have a list of $n $keys that you want to search in a hash table where the table size is $m$. Theoretically, each search would take $O(1)$ time, so the total running time for the $n$ searches should be $O(n)$. If the program thrashes though, the actual elapsed time might be much longer. An alternative is to ``reverse the search''. That is, you can take every element of the hash table and see if that element is in the list of $n$ keys. If you sort the list of $n$ keys, each look up would take $O(log n)$ time and the total running time is $O(mlog n)$, theoretically. In your report summarize the conditions under which ``reversing the search'' is faster than normal search. Are there other ways which you can work around the thrashing problem?
Since you are reporting the results of experimental work, be sure to explain your procedures and to interpret your results. You should explain your procedures in sufficient detail so that others can verify and replicate your findings. Summarize your findings in meaningful ways, visualizing important data (e.g. in graphs) whenever possible. Furthermore, since the behavior of your program might vary significantly among inputs of the same size, for each input size, try several inputs of that size and report the sample mean and standard deviation for that size; do not simply try one input per size.
The gl compute servers (umbc8, umbc9 and umbc10) have large amounts of real memory: 208 megabytes. The command hinv on IRIX systems will give you a list of the machine's hardware inventory, including its memory capacity. In order to perform these experiments, you should limit the amount of real memory that your processes use. This may be accomplished by the csh command:
limit memoryuse 1000
This command limits the amount of memory used by processes spawned by this
shell to 1000 kilobytes or less. You may use values lower than 1000 if you
wish. The limit command is a csh command. If you normally use a
shell other than csh, you should either switch to csh or check
that your shell has an equivalent command.
Similarly, the command time used in the example above is a csh command. It is very convenient that the time command also lists the number of page faults. If your normal shell does not do this, switch to csh.
To time a long command that you do not want to wait for, you can use:
(time a.out 8000000 1000000) >& logfile &
This will redirect the output of both the time and the a.out
commands to a file called logfile and the whole command is executed
in the background. This way you can log off, go to sleep and check how
long the command took in the morning.