In 1968, a set of computer animated films produced using GROATS were used in a Compiling Techniques Course at Brunel University and elsewhere to illustrate hash tables and their speed compared with standard table lookup.
The films were originally produced on the Chilton SC4020. In 1974, one of the films was redone using the newer FR80 and with a synchronised soundtrack for a presentation at IFIP74 in Stockholm.
Alan Francis interfaced a VCS3 Synthesiser to the Chilton PDP15 and a program on the PDP15 very similar to the GROATS program controlled the basic sounds from the synthesiser.
The soundtrack itself was output to a sprocketed audio tape. This allowed Peter Hadingham of Swift Films to generate the version with synchronised sound. To add some humour to the soundtrack, Alan added more harmonics interactively as the search paths got longer.
The IFIP 74 Paper, Computer Animation used as a Tool in Teaching Computer Science, received a Best Papers Award at the Conference.
The individual table positions are numbered 1 to 128 (anticlockwise from top left). The hash function generates a position to first try (random numbers generated between 1 and 128). The graph shows the current average length of search. Even with the table at 80% full, the average search length is around 3 compared with approximately 50 for the standard table lookup. An asterisk indicates positions where the search path is of length 1, the number of vertical lines indicate the search length for the other entries. The number above the graph indicates the maximum path length so far. For anybody interested in redoing the animation, the random numbers and the details are given in the table below.
Entry | Random | Path End | Length | Average |
---|---|---|---|---|
1 | 43 | 43 | 1 | 1.00 |
2 | 101 | 101 | 1 | 1.00 |
3 | 30 | 30 | 1 | 1.00 |
4 | 12 | 12 | 1 | 1.00 |
5 | 54 | 54 | 1 | 1.00 |
6 | 15 | 15 | 1 | 1.00 |
7 | 55 | 55 | 1 | 1.00 |
8 | 119 | 119 | 1 | 1.00 |
9 | 94 | 94 | 1 | 1.00 |
10 | 87 | 87 | 1 | 1.00 |
11 | 89 | 89 | 1 | 1.00 |
12 | 18 | 18 | 1 | 1.00 |
13 | 1 | 1 | 1 | 1.00 |
14 | 11 | 11 | 1 | 1.00 |
15 | 57 | 57 | 1 | 1.00 |
16 | 85 | 85 | 1 | 1.00 |
17 | 101 | 102 | 2 | 1.06 |
18 | 126 | 126 | 1 | 1.06 |
19 | 91 | 91 | 1 | 1.05 |
20 | 9 | 9 | 1 | 1.05 |
21 | 52 | 52 | 1 | 1.05 |
22 | 53 | 53 | 1 | 1.05 |
23 | 109 | 109 | 1 | 1.04 |
24 | 33 | 33 | 1 | 1.04 |
25 | 51 | 51 | 1 | 1.04 |
26 | 108 | 108 | 1 | 1.04 |
27 | 84 | 84 | 1 | 1.04 |
28 | 102 | 103 | 2 | 1.07 |
29 | 38 | 38 | 1 | 1.07 |
30 | 103 | 104 | 2 | 1.10 |
31 | 102 | 105 | 4 | 1.19 |
32 | 108 | 110 | 3 | 1.25 |
33 | 96 | 96 | 1 | 1.24 |
34 | 13 | 13 | 1 | 1.24 |
35 | 85 | 86 | 2 | 1.26 |
36 | 94 | 95 | 2 | 1.28 |
37 | 7 | 7 | 1 | 1.27 |
38 | 97 | 97 | 1 | 1.26 |
39 | 75 | 75 | 1 | 1.26 |
40 | 20 | 20 | 1 | 1.25 |
41 | 12 | 14 | 3 | 1.29 |
42 | 59 | 59 | 1 | 1.29 |
43 | 52 | 56 | 5 | 1.37 |
44 | 123 | 123 | 1 | 1.36 |
45 | 71 | 71 | 1 | 1.36 |
46 | 94 | 98 | 5 | 1.43 |
47 | 58 | 58 | 1 | 1.43 |
48 | 84 | 88 | 5 | 1.50 |
49 | 79 | 79 | 1 | 1.49 |
50 | 86 | 90 | 5 | 1.56 |
51 | 115 | 115 | 1 | 1.55 |
52 | 52 | 60 | 9 | 1.69 |
53 | 124 | 124 | 1 | 1.68 |
54 | 43 | 44 | 2 | 1.69 |
55 | 54 | 61 | 8 | 1.80 |
56 | 99 | 99 | 1 | 1.79 |
57 | 26 | 26 | 1 | 1.77 |
58 | 95 | 100 | 6 | 1.84 |
59 | 44 | 45 | 2 | 1.85 |
60 | 3 | 3 | 1 | 1.83 |
61 | 77 | 77 | 1 | 1.82 |
62 | 66 | 66 | 1 | 1.81 |
63 | 8 | 8 | 1 | 1.79 |
64 | 9 | 10 | 2 | 1.80 |
65 | 35 | 35 | 1 | 1.78 |
66 | 14 | 16 | 3 | 1.80 |
67 | 116 | 116 | 1 | 1.79 |
68 | 4 | 4 | 1 | 1.78 |
69 | 88 | 92 | 5 | 1.83 |
70 | 94 | 106 | 13 | 1.99 |
71 | 45 | 46 | 2 | 1.99 |
72 | 55 | 62 | 8 | 2,07 |
73 | 74 | 74 | 1 | 2,05 |
74 | 106 | 107 | 2 | 2,05 |
75 | 74 | 76 | 3 | 2,07 |
76 | 4 | 5 | 2 | 2,07 |
77 | 27 | 27 | 1 | 2,05 |
78 | 25 | 25 | 1 | 2,04 |
79 | 59 | 63 | 5 | 2,08 |
80 | 32 | 32 | 1 | 2,06 |
81 | 5 | 6 | 2 | 2,06 |
82 | 98 | 111 | 14 | 2,21 |
83 | 117 | 117 | 1 | 2,19 |
84 | 31 | 31 | 1 | 2,18 |
85 | 92 | 93 | 2 | 2,18 |
86 | 124 | 125 | 2 | 2,17 |
87 | 74 | 78 | 5 | 2,21 |
88 | 78 | 80 | 3 | 2,22 |
89 | 67 | 67 | 1 | 2,20 |
90 | 98 | 112 | 15 | 2,34 |
91 | 119 | 120 | 2 | 2,34 |
92 | 88 | 113 | 26 | 2,60 |
93 | 15 | 17 | 3 | 2,60 |
94 | 31 | 34 | 4 | 2,62 |
95 | 92 | 114 | 23 | 2,83 |
96 | 64 | 64 | 1 | 2,81 |
97 | 89 | 118 | 30 | 3.09 |
98 | 113 | 121 | 9 | 3.15 |
99 | 108 | 122 | 15 | 3.27 |
100 | 43 | 47 | 5 | 3.29 |
101 | 67 | 68 | 2 | 3.28 |
102 | 59 | 65 | 7 | 3.31 |
103 | 68 | 69 | 2 | 3.30 |
104 | 121 | 127 | 7 | 3.34 |
105 | 104 | 128 | 25 | 3.54 |
It was difficult to get exact times so not all are totally correct. The increments along a search were 4 frames per position (0.25secs at 16 frames per sec).
The relevant FORTRAN files if you have a compiler are: