Overhead (computing)

Choice of implementation A programmer or software engineer may have a choice of several algorithms, encodings, data types or data structures, each of which has 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 includedor 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 cost, 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 resourcesa combination (though not a trivial one) of complexity and overhead. ==Examples==

File system metadata In addition to file content, a file system uses storage space for overhead information, including: metadata (such as file name and modification timestamps), hierarchical directory organization and much more. In general, many small files requires more overhead than a smaller number of large files. CPU cache metadata In a CPU cache, capacity is the maximum amount of data that it stores, including overhead data, not how much user content it holds. For instance, a 4 KB capacity cache stores less than 4 KB of user data since some of the space is required for overhead bits such as frame, address, and tag information. Communication protocol Reliably sending a payload of data over a communications network requires sending more than just the payload itself. It also involves sending various control and signaling 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. In telephony, number dialing and call set-up time are overheads. In two-way (but half-duplex) radios, the use of "over" and other signaling needed to avoid collisions is an overhead. Protocol overhead can be expressed as a percentage of non-application bytes (protocol and frame synchronization) divided by the total number of bytes in the message. Data encoding 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 bytes, 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. 2011 07 12 07 18 47 The 349 bytes, resulting from the UTF-8 encoded XML, correlate to a size overhead of 8625% over the original integer representation. Function call Calling a function requires a relatively small amount of run-time overhead for operations such as stack maintenance and parameter passing. The overhead is relatively small, but can be problematic when there are many calls (i.e. in a loop) or when timing requirements are tight. Sometimes a compiler can minimize this overhead by inlining a function, eliminating the function call. ==See also==