Overhead (computing)

In computer science, overhead is any combination of excess or indirect computation time, memory, bandwidth, or other resources that are required to attain a particular goal. It is a special case of engineering overhead.

Software design

Choice of implementation

A programmer/software engineer may have a choice of several algorithms, encodings, data types or data structures, each of which have known characteristics. When choosing among them, their respective overhead should also be considered.

Tradeoffs

In software engineering, overhead can influence the decision whether or not to include features in new products, or indeed whether to fix bugs. A feature that has a high overhead may not be included – or needs a big financial incentive to do so. Often, even though software providers are well aware of bugs in their products, the payoff of fixing them is not worth the reward, because of the overhead.

For example, an implicit data structure or succinct data structure may provide low space overhead, but at the cost of slow performance (space/time tradeoff).

Run-time complexity of software

Algorithmic complexity is generally specified using Big O Notation. This makes no comment on how long something takes to run or how much memory it uses, but how its increase depends on the size of the input. Overhead is deliberately not part of this calculation, since it varies from one machine to another, whereas the fundamental running time of an algorithm does not.

This should be contrasted with algorithmic efficiency, which takes into account all kinds of resources – a combination (though not a trivial one) of complexity and overhead.

Examples

Computer Programming (run-time and computational overhead)

Invoking a function introduces a small run-time overhead. Sometimes the compiler can minimize this overhead by inlining some of these function calls.

Communications (data transfer overhead)

Sending a payload of data (reliably) over a communications network requires sending more than just the desired payload data, itself. It also involves sending various control and signalling data (TCP) required to achieve the reliable transmission of the desired data in question. The control signalling is overhead. A simplified version is the need and time to dial a number to establish a phone call, before the call can take place. Dialing the number and establishing the call are overhead. Another simplified scenario is in the use of 2-way (but half-duplex) radios. Overhead would be the use of “over” and other signalling needed to avoid collisions, as extra traffic to that of the actual message(s) to be conveyed.

Encoding and data structures (size overhead)

The encoding of information and data introduces overhead too. The date and time "2011-07-12 07:18:47" can be expressed as Unix time with the 32-bit signed integer 1310447927, consuming only 4 bytes. Represented as ISO 8601 formatted UTF-8 encoded string 2011-07-12 07:18:47 the date would consume 19 byte, a size overhead of 375% over the binary integer representation. As XML this date can be written as follows with an overhead of 218 characters, while adding the semantic context that it is a CHANGEDATE with index 1.


              <?xml version="1.0" encoding="UTF-8"?>
              <DATETIME qualifier="CHANGEDATE" index="1">
                 <YEAR>2011</YEAR>
                 <MONTH>07</MONTH>
                 <DAY>12</DAY>
                 <HOUR>07</HOUR>
                 <MINUTE>18</MINUTE>
                 <SECOND>47</SECOND>
              </DATETIME>

The 349 byte, resulting from the UTF-8 encoded XML, correlates to a size overhead of 8625% over the original integer representation.