computer science Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to practical disciplines (includi ...

, overhead is any combination of excess or indirect computation time, memory, bandwidth, or other resources that are required to perform a specific task. It is a special case of

engineering overhead In engineering, some methods or components make special demands on the system. The extra design features necessary to meet these demands are called overhead. For instance, in electrical engineering, a particular integrated circuit might draw large ...

. Overhead can be a deciding factor in software design, with regard to structure, error correction, and feature inclusion. Examples of computing overhead may be found in Object Oriented Programming (OOP),

functional programming In computer science, functional programming is a programming paradigm where programs are constructed by applying and composing functions. It is a declarative programming paradigm in which function definitions are trees of expressions that ...

, data transfer, and data structures.

Software design

Choice of implementation

A programmer/software engineer may have a choice of several

algorithm In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algorithms are used as specifications for performing ...

encoding In communications and information processing, code is a system of rules to convert information—such as a letter, word, sound, image, or gesture—into another form, sometimes shortened or secret, for communication through a communication ...

s, data types or data structures, each of which have known characteristics. When choosing among them, their respective overhead should also be considered.

Tradeoffs

software engineering Software engineering is a systematic engineering approach to software development. A software engineer is a person who applies the principles of software engineering to design, develop, maintain, test, and evaluate computer software. The term '' ...

, 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 In computer science, an implicit data structure or space-efficient data structure is a data structure that stores very little information other than the main or required data: a data structure that requires low overhead. They are called "implicit" ...

succinct data structure In computer science, a succinct data structure is a data structure which uses an amount of space that is "close" to the information-theoretic lower bound, but (unlike other compressed representations) still allows for efficient query operations. Th ...

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 In computer science, algorithmic efficiency is a property of an algorithm which relates to the amount of computational resources used by the algorithm. An algorithm must be analyzed to determine its resource usage, and the efficiency of an algo ...

, 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 Function or functionality may refer to: Computing * Function key, a type of key on computer keyboards * Function model, a structured representation of processes in a system * Function object or functor or functionoid, a concept of object-oriente ...

introduces a small run-time overhead. Sometimes the compiler can minimize this overhead by

inlining In computing, inline expansion, or inlining, is a manual or compiler optimization that replaces a function call site with the body of the called function. Inline expansion is similar to macro expansion, but occurs during compilation, without cha ...

some of these

function call In computer programming, a function or subroutine is a sequence of program instructions that performs a specific task, packaged as a unit. This unit can then be used in programs wherever that particular task should be performed. Functions may ...

CPU caches

In a

CPU cache A CPU cache is a hardware cache used by the central processing unit (CPU) of a computer to reduce the average cost (time or energy) to access data from the main memory. A cache is a smaller, faster memory, located closer to a processor core, whic ...

, the "cache size" (or capacity) refers to how much data a ''cache'' stores. For instance, a "4 KB cache" is a cache that holds 4 KB of data. The "4 KB" in this example excludes

overhead bit In data transmission and telecommunication, overhead bits are non-data bits necessary for transmission (usually as part of headers, checksums, and such). For example, on the Internet many data exchanges occur via HTTP. HTTP headers allow additio ...

s such as frame, address, and tag information.

Communications (data transfer overhead)

Reliably sending a payload of data over a communications network requires sending more than just payload itself. It also involves sending various control and signalling data ( TCP) required to reach the destination. This creates a so-called protocol overhead as the additional data does not contribute to the intrinsic meaning of the message.Protocol Overhead in IP/ATM Networks
Minnesota Supercomputer Center In

telephony Telephony ( ) is the field of technology involving the development, application, and deployment of telecommunication services for the purpose of electronic transmission of voice, fax, or data, between distant parties. The history of telephony is i ...

, number dialing and call set-up time are overheads. In two-way (but

half-duplex A duplex communication system is a point-to-point system composed of two or more connected parties or devices that can communicate with one another in both directions. Duplex systems are employed in many communications networks, either to allow ...

) radios, the use of "over" and other signalling needed to avoid collisions is an overhead. Protocol overhead can be expressed as a percentage of non-application

byte The byte is a unit of digital information that most commonly consists of eight bits. Historically, the byte was the number of bits used to encode a single character of text in a computer and for this reason it is the smallest addressable uni ...

s (protocol and

frame synchronization In telecommunication, frame synchronization or framing is the process by which, while receiving a stream of framed data, incoming frame alignment signals (i.e., a distinctive bit sequences or syncwords) are identified (that is, distinguished fro ...

) divided by the total number of bytes in the message.

Encodings and data structures (size overhead)

The

of information and data introduces overhead too. The date and time ''"2011-07-12 07:18:47"'' can be expressed as

Unix time Current Unix time () Unix time is a date and time representation widely used in computing. It measures time by the number of seconds that have elapsed since 00:00:00 UTC on 1 January 1970, the beginning of the Unix epoch, less adjustments m ...

with the 32-bit signed

integer An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign ( −1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the languag ...

1310447927, consuming only 4

s. Represented as

ISO 8601 ISO 8601 is an international standard covering the worldwide exchange and communication of date and time-related data. It is maintained by the Geneva-based International Organization for Standardization (ISO) and was first published in 1988, w ...

formatted

UTF-8 UTF-8 is a variable-length character encoding used for electronic communication. Defined by the Unicode Standard, the name is derived from ''Unicode'' (or ''Universal Coded Character Set'') ''Transformation Format 8-bit''. UTF-8 is capable of ...

encoded string 2011-07-12 07:18:47 the date would consume 19 bytes, a size overhead of 375% over the binary integer representation. As

XML Extensible Markup Language (XML) is a markup language and file format for storing, transmitting, and reconstructing arbitrary data. It defines a set of rules for encoding documents in a format that is both human-readable and machine-readable ...

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. 2011 07 12 07 18 47 The 349 bytes, resulting from the UTF-8 encoded XML, correlates to a size overhead of 8625% over the original integer representation.

References

{{Reflist Software optimization