like loop unrolling, in-line function expansion, common subexpression elimination, improved register
allocation, omitting runtime checks on array bounds, loop-invariant code motion, operator strength
reduction (turning exponen-tiation into multiplication, turning multiplication into bit-shifting and/or
addition), and so on.
The data file contained about 10,000 numbers, so assuming it took a millisecond just to read and
process each number (about par for the systems at the time), the fastest possible program would take
about ten seconds.
The actual results were very surprising. The fastest program, as reported by the operating system, took
minus three seconds. That's right—the winner ran in a negative amount of time! The next fastest
apparently took just a few milliseconds, while the entry in third place came in just under the expected
10 seconds. Obviously, some devious programming had taken place, but what and how? A detailed
scrutiny of the winning programs eventually supplied the answer.
The program that apparently ran backwards in time had taken advantage of the operating system. The
programmer knew where the process control block was stored relative to the base of the stack. He
crafted a pointer to access the process control block and overwrote the "CPU-time-used" field with a
very high value. [2] The operating system wasn't expecting CPU times that large, and it misinterpreted
the very large positive number as a negative number under the two's complement scheme.
[2] A flagrant abuse of the rules, ranking equal to the time Argentinian soccer ace Diego Maradona used his
forearm to nudge the ball into the England net for the winning goal in the 1986 soccer World Cup.
The runner-up, whose program took just a few milliseconds, had been equally cunning in a different
way. He had used the rules of the competition rather than exotic coding. He submitted two different
entries. One entry read the numbers, calculated the answer in the normal way, and wrote the result to a
file; the second entry spent most of its time asleep, but woke up briefly every few seconds and
checked if the answer file existed. When it did, it printed it out. The second process only took a few
milliseconds of total CPU time. Since contestants were allowed to submit multiple entries, the smaller
time counted and put him in second place.
The programmer whose entry came in third, taking slightly less than the calculated minimum time,
had the most elaborate scheme. He had worked out the optimized machine code instructions to solve
the problem, and stored the instructions as an array of integers in his program. It was easy to overwrite
a return address on the stack (as Bob Morris, Jr. later did with the Internet worm of 1988) and cause
the program to jump into and start executing this array. These instructions solved the problem
honestly in record time.
There was an uproar among the faculty when these stratagems were uncovered. Some of the staff were
in favor of severely reprimanding the winners. A younger group of professors proposed instead
awarding them an extra prize in recognition of their ingenuity. In the end, a compromise was reached.
No prizes were awarded, no punishments were handed down, and the results stuck. Sadly, the contest
was a casualty of the strong feelings, and this incident marked the final year it was held.
For Advanced Students Only
A word to the wise: it's possible to embed assembler code in C source. This is usually only done for
the most machine-specific things in the depths of the OS kernel, like setting specific registers on
changing from supervisor mode to user mode. Here's how we plant a no-op (or other instruction) in a
C function using a SunPro SPARCompiler: