Early Programming

The first computers were little more than electrical calculating engines. They could perform tasks like additions faster than their human and mechanical counterparts. A typical use for these machines would be calculating bills. Each customer would have a punch card for their usage and each item on this would be multiplied by the per-item cost stored in a table, added to an accumulator and then emitted, often on another punch card which would be fed into a separate machine that would type numbers on an invoice.

These operations were very simple, and supporting them in the first generation machines involved wiring them up to perform the task. In June 1948, the Manchester Baby changed this by storing its programs in the same way that it stored data, allowing it to be reprogrammed without being rewired.

Optimal Programming

In 1936, Alan Turing proposed the Turing Machine as a universal model of a computing engine. A Turing Machine had an infinitely long tape containing data. It would read the current cell on the tape, then either write something over it or move the tape left or right and update some internal state. A Universal Turing Machine was one where the tape could contain an encoded form of another Turing Machine. This is the basis of all modern programming - making a general purpose computing machine behave like a special purpose one.

One feature of note with a Turing Machine is that the running time of an algorithm depended heavily on the location of data on the tape. Adding two values together could be very quick or very slow depending on how much the machine had to move the tape to get to each of them.

Although the Turing Machine was a purely theoretical idea, early computers inherited this limitation. Most of them used a storage mechanism that was either inherently serial or had large penalties for seeking. In a modern computer, main memory is Random Access Memory (RAM) and the time taken to read a value is more or less independent of its location. In a machine using mercury delay lines for storage, each value in the line was read in order and could only be accessed one nth of the time, where n is the number of values stored in the line. Magnetic drums had similar limitations, since accessing a value required turning the drum to make it visible. Even modern hard drives retain this limitation, but it is less of a problem since they are generally used as secondary storage (if at all) on a modern computer.

The cost of seeking in early hardware lead to the development of optimal programming, with Alan Turing one of the subject’s principle proponents. The idea behind optimal programming was to ensure that data and instructions that would be accessed together were placed physically close together. This meant that the computer would spend more time computing and less time waiting for data.

In modern programming, this kind of thing is rarely done by programmers, but is still very important for compilers. Modern computers use a memory hierarchy, with two or three layers of cache between the main memory and the CPU. Accessing data from a cache is much faster than accessing data in main memory. Data is loaded into these caches and evicted from them in blocks, and so positioning related data so that they can be loaded together still provides a performance benefit.

David Chisnall