Search This Blog

Tuesday, November 8, 2022

Copyleft

From Wikipedia, the free encyclopedia
 
Small letter c turned 180 degrees, surrounded by a single line forming a circle.
Copyleft symbol

Copyleft is the legal technique of granting certain freedoms over copies of copyrighted works with the requirement that the same rights be preserved in derivative works. In this sense, freedoms refers to the use of the work for any purpose, and the ability to modify, copy, share, and redistribute the work, with or without a fee. Licenses which implement copyleft can be used to maintain copyright conditions for works ranging from computer software, to documents, art, scientific discoveries and even certain patents.

Copyleft software licenses are considered protective or reciprocal in contrast with permissive free software licenses, and require that information necessary for reproducing and modifying the work must be made available to recipients of the software program, which are often distributed as binary executables. This information is most commonly in the form of source code files, which usually contain a copy of the license terms and acknowledge the authors of the code.

Notable copyleft licenses include the GNU General Public License (GPL), originally written by Richard Stallman, which was the first software copyleft license to see extensive use, the Mozilla Public License, the Free Art License, and the Creative Commons share-alike license condition, with the last two being intended for other types of works, such as documents and pictures, both academic or artistic in nature.

History

An early use of the word copyleft was in Li-Chen Wang's Palo Alto Tiny BASIC's distribution notice "@COPYLEFT ALL WRONGS RESERVED" in June 1976. Tiny BASIC was not distributed under any formal form of copyleft distribution terms, but it was presented in a context where source code was being shared and modified. In fact, Wang had earlier contributed edits to Tiny BASIC Extended before writing his own BASIC interpreter. He encouraged others to adapt his source code and publish their adaptions, as with Roger Rauskolb's version of PATB published in Interface Age.

The concept of copyleft was described in Richard Stallman's GNU Manifesto in 1985, where he wrote:

GNU is not in the public domain. Everyone will be permitted to modify and redistribute GNU, but no distributor will be allowed to restrict its further redistribution. That is to say, proprietary modifications will not be allowed. I want to make sure that all versions of GNU remain free.

Stallman worked a few years earlier on a Lisp interpreter. Symbolics asked to use the Lisp interpreter, and Stallman agreed to supply them with a public domain version of his work. Symbolics extended and improved the Lisp interpreter, but when Stallman wanted access to the improvements that Symbolics had made to his interpreter, Symbolics refused. Stallman then, in 1984, proceeded to work towards eradicating this emerging behavior and culture of proprietary software, which he named software hoarding. This was not the first time Stallman had dealt with proprietary software, but he deemed this interaction a "turning point". He justified software sharing, protesting that when sharing, the software online can be copied without the loss of the original piece of work. The software can be used multiple times without ever being damaged or wearing out.

As Stallman deemed it impractical in the short term to eliminate current copyright law and the wrongs he perceived it to perpetuate, he decided to work within the framework of existing law; in 1985, he created his own copyright license, the Emacs General Public License, the first copyleft license. This later evolved into the GNU General Public License, which is now one of the most popular free-software licenses. For the first time, a copyright holder had taken steps to ensure that the maximal number of rights be perpetually transferred to a program's users, no matter what subsequent revisions anyone made to the original program. This original GPL did not grant rights to the public at large, only those who had already received the program; but it was the best that could be done under existing law.

The new license was not at this time given the copyleft label. Richard Stallman stated that the use of "Copyleft" comes from Don Hopkins, who mailed him a letter in 1984 or 1985, on which was written: "Copyleft – all rights reversed". In the early 1970s, the self-published book Principia Discordia contains the notice "Ⓚ All Rites Reversed – reprint what you like" (sic). In the arts, Ray Johnson had earlier coined the term independently as it pertained to his making of and distribution of his mixed media imagery in his mail art and ephemeral gifts, for which he encouraged the making of derivative works. (While the phrase appears briefly as (or on) one of his pieces in the 2002 documentary How to Draw a Bunny, Johnson himself is not referenced in the 2001 documentary Revolution OS.)

In France, a series of meetings taking place in 2000 under the title "Copyleft Attitude" gave birth to the Free Art License (FAL), theoretically valid in any jurisdiction bound by the Berne Convention and recommended by Stallman's own Free Software Foundation. Shortly thereafter, a separate, unrelated initiative in the United States yielded the Creative Commons license, available since 2001 in several different versions (only some of which can be described as copyleft) and more specifically tailored to U.S. law.

Copyleft principles

Freedom

While copyright law gives software authors control over copying, distribution and modification of their works, the goal of copyleft is to give all users of the work the freedom to carry out all of these activities. These freedoms (from the Free Software Definition) include:

Freedom 0
the freedom to use the work
Freedom 1
the freedom to study the work
Freedom 2
the freedom to copy and share the work with others
Freedom 3
the freedom to modify the work, and the freedom to distribute modified and therefore derivative works

Similar terms are present in the Open Source Definition, a separate definition that contains similar freedoms. The vast majority of copyleft licenses satisfy both definitions, that of the Free Software Definition and Open Source Definition. By guaranteeing viewers and users of a work the freedom and permission to reproduce, adapt, or distribute it, copyleft licenses are distinct from other types of copyright licenses that limit such freedoms.

Reciprocity

Instead of allowing a work to fall completely into the public domain, where no ownership of copyright is claimed, copyleft allows authors to impose restrictions on the use of their work. One of the main restrictions imposed by copyleft is that derived works must also be released under a compatible copyleft license.

This is due to the underlying principle of copyleft: that anyone can benefit freely from the previous work of others, but that any modifications to that work should benefit everyone else as well, and thus must be released under similar terms. For this reason, copyleft licenses are also known as reciprocal licenses: any modifiers of a copyleft-licensed work are expected to reciprocate the author's action of copyleft-licensing the software by also copyleft-licensing any derivatives they might have made. Because of this requirement, copyleft licenses have also been described as "viral" due to their self-perpetuating terms.

In addition to restrictions on copying, copyleft licenses address other possible impediments. They ensure that rights cannot be later revoked, and require the work and its derivatives to be provided in a form that allows further modifications to be made. In software, this means requiring that the source code of the derived work be made available together with the software itself.

Economic incentive

The economic incentives to work on copyleft content can vary. Traditional copyright law is designed to promote progress by providing economic benefits to creators. When choosing to copyleft their work, content creators may seek complementary benefits like recognition from their peers.

In the world of computer programming, copyleft-licensed computer programs are often created by programmers to fill a need they have noticed. Such programs are often published with a copyleft license simply to ensure that subsequent users can also freely use modified versions of that program. This is especially true for creators who wish to prevent "open source hijacking", or the act of reusing open-source code and then adding extra restrictions to it, an action prevented by copyleft-licensing the software. Some creators, such as Elastic, feel that preventing commercial enterprises from using and then selling their product under a proprietary license is also an incentive.

Furthermore, the open-source culture of programming has been described as a gift culture, where social power is determined by an individual's contributions. Contributing to or creating open-source, copyleft-licensed software of high quality can lead to contributors gaining valuable experience and can lead to future career opportunities.

Copyleft software has economic effects beyond individual creators. The presence of quality copyleft software can force proprietary software developers to increase the quality of their software to compete with free software. This may also have the effect of preventing monopolies in areas dominated by proprietary software. However, competition with proprietary software can also be a reason to forgo copyleft. The Free Software Foundation recommends that when "widespread use of the code is vital for advancing the cause of free software", allowing the code to be copied and used freely is more important than a copyleft.

Copyleft application

Common practice for using copyleft is to codify the copying terms for a work with a license. Any such license typically includes all the provisions and principles of copyleft inside the license's terms. This includes the freedom to use the work, study the work, copy and share the work with others, modify the work, and distribute exact or modified versions of that work, with or without fee.

Unlike similar permissive licenses that also grant these freedoms, copyleft licenses also ensure that any modified versions of a work covered by a copyleft license must also grant these freedoms. Thus, copyleft licenses have conditions: that modifications of any work licensed under a copyleft license must be distributed under a compatible copyleft scheme and that the distributed modified work must include a means of modifying the work. Under fair use, however, copyleft licenses may be superseded, just like regular copyrights. Therefore, any person utilizing a source licensed under a copyleft license for works they invent is free to choose any other license (or none at all) provided they meet the fair use standard.

Copyleft licenses necessarily make creative use of relevant rules and laws to enforce their provisions. For example, when using copyright law, those who contribute to a work under copyleft usually must gain, defer, or assign copyright holder status. By submitting the copyright of their contributions under a copyleft license, they deliberately give up some of the rights that normally follow from copyright, including the right to be the unique distributor of copies of the work.

Some laws used for copyleft licenses vary from one country to another, and may also be granted in terms that vary from country to country. For example, in some countries it is acceptable to sell a software product without warranty, in standard GNU General Public License style, while in most European countries it is not permitted for a software distributor to waive all warranties regarding a sold product. For this reason, the extent of such warranties are specified in most European copyleft licenses, for example the European Union Public Licence (EUPL), or the CeCILL license, a license that allows one to use GNU GPL in combination with a limited warranty.

For projects which will be run over a network, a variation of the GNU GPL, called the Affero General Public License (GNU AGPL), ensures that the source code is available to users of software over a network.

Types and relation to other licenses


Free Non-free
Public domain & equivalents Permissive license Copyleft (protective license) Noncommercial license Proprietary license Trade secret
Description Grants all rights Grants use rights, including right to relicense (allows proprietization, license compatibility) Grants use rights, forbids proprietization Grants rights for noncommercial use only. May be combined with share-alike. Traditional use of copyright; certain rights may or may not be granted No information made public
For software PD, Unlicense, CC0 BSD, MIT, Apache GPL, AGPL JRL, AFPL Proprietary software, no public license Private, internal software
For other creative works PD, CC0 CC-BY CC-BY-SA, FAL CC-BY-NC Copyright, no public license Unpublished
The Creative Commons icon for Share-Alike, a variant of the copyleft symbol

Copyleft is a distinguishing feature of some free software licenses, while other free-software licenses are not copyleft licenses because they do not require the licensee to distribute derivative works under the same license. There is an ongoing debate as to which class of license provides the greater degree of freedom. This debate hinges on complex issues, such as the definition of freedom and whose freedoms are more important: the potential future recipients of a work (freedom from proprietization) or just the initial recipient (freedom to proprietize). However, current copyright law and the availability of both types of licenses, copyleft and permissive, allows authors to choose the type under which to license the works they invent.

For documents, art, and other works other than software and code, the Creative Commons share-alike licensing system and the GNU Free Documentation License (GFDL) allow authors to apply limitations to certain sections of their work, exempting some parts of the work from the full copyleft mechanism. In the case of the GFDL, these limitations include the use of invariant sections, which may not be altered by future editors. The initial intention of the GFDL was as a device for supporting the documentation of copylefted software. However, the result is that it can be used for any kind of document.

Strong and weak copyleft

The strength of the copyleft license governing a work is determined by the extent its provisions can be imposed on all kinds of derivative works. Thus, the term "weak copyleft" refers to licenses where not all derivative works inherit the copyleft license; whether a derivative work inherits or not often depends on how it was derived.

"Weak copyleft" licenses are often used to cover software libraries. This allows other software to link to the library and be redistributed without the requirement for the linking software to also be licensed under the same terms. Only changes to the software licensed under a "weak copyleft" license becomes subject itself to copyleft provisions of such a license. This allows programs of any license to be compiled and linked against copylefted libraries such as glibc and then redistributed without any re-licensing required. The concrete effect of strong vs. weak copyleft has yet to be tested in court. Free-software licenses that use "weak" copyleft include the GNU Lesser General Public License and the Mozilla Public License.

The GNU General Public License is an example of a license implementing strong copyleft. A stronger copyleft license is the AGPL, which requires the publishing of the source code for software as a service use cases.

The Sybase Open Watcom Public License is one of the strongest copyleft licenses, as this license closes the so-called "private usage" loophole of the GPL, and requires the publishing of source code in any use case. For this reason, the license is considered non-free by the Free Software Foundation, the GNU Project, and the Debian project. However, the license is accepted as open source by the OSI.

The Design Science License (DSL) is a strong copyleft license that applies to any work, not only software or documentation, but also literature, artworks, music, photography, and video. DSL was written by Michael Stutz after he took an interest in applying GNU-style copyleft to non-software works, which later came to be called libre works. In the 1990s, it was used on music recordings, visual art, and even novels. It is not considered compatible with the GNU GPL by the Free Software Foundation.

Full and partial copyleft

"Full" and "partial" copyleft relate to another issue. Full copyleft exists when all parts of a work (except the license itself) may only be modified and distributed under the terms of the work's copyleft license. Partial copyleft, by contrast, exempts some parts of the work from the copyleft provisions, permitting distribution of some modifications under terms other than the copyleft license, or in some other way does not impose all the principles of copylefting on the work. An example of partial copyleft is the GPL linking exception made for some software packages.

Share-alike

The "share-alike" condition in some licenses imposes the requirement that any freedom that is granted regarding the original work must be granted on exactly the same or compatible terms in any derived work.

This implies that any copyleft license is automatically a share-alike license but not the other way around, as some share-alike licenses include further restrictions such as prohibiting commercial use. Another restriction is that not everyone wants to share their work and some share-alike agreements require that the whole body of work be shared, even if the author only wants to share a certain part. The plus side for an author of source code is that any modification to the code will not only benefit the original author, but that the author will be recognized and ensure the same or compatible license terms cover the changed code. Some Creative Commons licenses are examples of share-alike copyleft licenses.

Permissive licenses

Permissive software licenses are those that grant users of the software the same freedoms as copyleft licenses, but do not require modified versions of that software to also include those freedoms. They have minimal restrictions on how the software can be used, modified, and redistributed, and are thus not copyleft licenses. Examples of this type of license include the X11 license, Apache license, Expat license, and the various BSD licenses.

Debate and controversy

It has been suggested that copyleft has become a divisive issue in the ideological strife between the Open Source Initiative and the free software movement. However, there is evidence that copyleft is both accepted and proposed by both parties:

  • Both the OSI and the FSF have copyleft and non-copyleft licenses in their respective lists of accepted licenses.
  • The OSI's original Legal Counsel Lawrence Rosen has written a copyleft license, the Open Software License.
  • The OSI's licensing how-to recognises the GPL as a "best practice" license.
  • Some of the software programs of the GNU Project are published under non-copyleft licenses.
  • Stallman himself has endorsed the use of non-copyleft licenses in certain circumstances, most recently in the case of the Ogg Vorbis license change.

Viral licensing

Viral license is a pejorative name for copyleft licenses. It originates from the terms 'General Public Virus' or 'GNU Public Virus' (GPV), which dates back to 1990, a year after the GPLv1 was released. The name "viral licenses" refers to the fact that any works derived from a copyleft work must preserve the copyleft permissions when distributed.

Some advocates of the various BSD Licenses used the term derisively in regards to the GPL's tendency to absorb BSD-licensed code without allowing the original BSD work to benefit from it, while at the same time promoting itself as "freer" than other licenses. Microsoft vice-president Craig Mundie remarked, "This viral aspect of the GPL poses a threat to the intellectual property of any organization making use of it." In another context, Steve Ballmer declared that code released under GPL is useless to the commercial sector, since it can only be used if the resulting surrounding code is licensed under a GPL-compatible license, and described it thus as "a cancer that attaches itself in an intellectual property sense to everything it touches".

In response to Microsoft's attacks on the GPL, several prominent free-software developers and advocates released a joint statement supporting the license. According to FSF compliance engineer David Turner, the term "viral license" creates a misunderstanding and a fear of using copylefted free software. While a person can catch a virus without active action, license conditions take effect upon effective usage or adoption. David McGowan has also written that there is no reason to believe the GPL could force proprietary software to become free software, but could "try to enjoin the firm from distributing commercially a program that combined with the GPL'd code to form a derivative work, and to recover damages for infringement." If the firm "actually copied code from a GPL'd program, such a suit would be a perfectly ordinary assertion of copyright, which most private firms would defend if the shoe were on the other foot." Richard Stallman has described this view with an analogy, saying, "The GPL's domain does not spread by proximity or contact, only by deliberate inclusion of GPL-covered code in your program. It spreads like a spider plant, not like a virus."

Popular copyleft licenses, such as the GPL, have a clause allowing components to interact with non-copyleft components as long as the communication is abstract, such as executing a command-line tool with a set of switches or interacting with a web server. As a consequence, even if one module of an otherwise non-copyleft product is placed under the GPL, it may still be legal for other components to communicate with it in ways such as these. This allowed communication may or may not include reusing libraries or routines via dynamic linking – some commentators say it does, the FSF asserts it does not and explicitly adds an exception allowing it in the license for the GNU Classpath re-implementation of the Java library. This ambiguity is an important difference between the GPL and the LGPL, in that the LGPL specifically allows linking or compiling works licensed under terms which are not compatible with the LGPL, with works covered by the LGPL.

Symbol

© 🄯
Copyleft symbol
In UnicodeU+1F12F 🄯 COPYLEFT SYMBOL
Alternative symbol: (ɔ)
Different from
Different fromU+00A9 © COPYRIGHT SIGN

The copyleft symbol is a mirror image of the copyright symbol, ©: a reversed C in a circle. It has no legal status. A 2016 proposal to add the symbol to a future version of Unicode was accepted by the Unicode Technical Committee. The code point U+1F12F 🄯 COPYLEFT SYMBOL was added in Unicode 11.

As of 2018, it is largely unimplemented in fonts, but can be approximated with character U+2184 LATIN SMALL LETTER REVERSED C or the more widely available character U+0254 ɔ LATIN SMALL LETTER OPEN O between parenthesis (ɔ) or, if supported by the application or web browser, by combining a reversed c with the character U+20DD ↄ⃝ COMBINING ENCLOSING CIRCLE: ↄ⃝.

For a list of fonts that include this glyph, see Unicode fonts § List of SMP Unicode fonts and then row "Enclosed Alphanumeric Supplement (173: 1F100–1F1FF)" (This list is not guaranteed to be current).

Algorithmic efficiency

From Wikipedia, the free encyclopedia

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 algorithm can be measured based on the usage of different resources. Algorithmic efficiency can be thought of as analogous to engineering productivity for a repeating or continuous process.

For maximum efficiency it is desirable to minimize resource usage. However, different resources such as time and space complexity cannot be compared directly, so which of two algorithms is considered to be more efficient often depends on which measure of efficiency is considered most important.

For example, bubble sort and timsort are both algorithms to sort a list of items from smallest to largest. Bubble sort sorts the list in time proportional to the number of elements squared (, see Big O notation), but only requires a small amount of extra memory which is constant with respect to the length of the list (). Timsort sorts the list in time linearithmic (proportional to a quantity times its logarithm) in the list's length (), but has a space requirement linear in the length of the list (). If large lists must be sorted at high speed for a given application, timsort is a better choice; however, if minimizing the memory footprint of the sorting is more important, bubble sort is a better choice.

Background

The importance of efficiency with respect to time was emphasised by Ada Lovelace in 1843 as applied to Charles Babbage's mechanical analytical engine:

"In almost every computation a great variety of arrangements for the succession of the processes is possible, and various considerations must influence the selections amongst them for the purposes of a calculating engine. One essential object is to choose that arrangement which shall tend to reduce to a minimum the time necessary for completing the calculation"

Early electronic computers had both limited speed and limited random access memory. Therefore, a space–time trade-off occurred. A task could use a fast algorithm using a lot of memory, or it could use a slow algorithm using little memory. The engineering trade-off was then to use the fastest algorithm that could fit in the available memory.

Modern computers are significantly faster than the early computers, and have a much larger amount of memory available (Gigabytes instead of Kilobytes). Nevertheless, Donald Knuth emphasised that efficiency is still an important consideration:

"In established engineering disciplines a 12% improvement, easily obtained, is never considered marginal and I believe the same viewpoint should prevail in software engineering"

Overview

An algorithm is considered efficient if its resource consumption, also known as computational cost, is at or below some acceptable level. Roughly speaking, 'acceptable' means: it will run in a reasonable amount of time or space on an available computer, typically as a function of the size of the input. Since the 1950s computers have seen dramatic increases in both the available computational power and in the available amount of memory, so current acceptable levels would have been unacceptable even 10 years ago. In fact, thanks to the approximate doubling of computer power every 2 years, tasks that are acceptably efficient on modern smartphones and embedded systems may have been unacceptably inefficient for industrial servers 10 years ago.

Computer manufacturers frequently bring out new models, often with higher performance. Software costs can be quite high, so in some cases the simplest and cheapest way of getting higher performance might be to just buy a faster computer, provided it is compatible with an existing computer.

There are many ways in which the resources used by an algorithm can be measured: the two most common measures are speed and memory usage; other measures could include transmission speed, temporary disk usage, long-term disk usage, power consumption, total cost of ownership, response time to external stimuli, etc. Many of these measures depend on the size of the input to the algorithm, i.e. the amount of data to be processed. They might also depend on the way in which the data is arranged; for example, some sorting algorithms perform poorly on data which is already sorted, or which is sorted in reverse order.

In practice, there are other factors which can affect the efficiency of an algorithm, such as requirements for accuracy and/or reliability. As detailed below, the way in which an algorithm is implemented can also have a significant effect on actual efficiency, though many aspects of this relate to optimization issues.

Theoretical analysis

In the theoretical analysis of algorithms, the normal practice is to estimate their complexity in the asymptotic sense. The most commonly used notation to describe resource consumption or "complexity" is Donald Knuth's Big O notation, representing the complexity of an algorithm as a function of the size of the input . Big O notation is an asymptotic measure of function complexity, where roughly means the time requirement for an algorithm is proportional to , omitting lower-order terms that contribute less than to the growth of the function as grows arbitrarily large. This estimate may be misleading when is small, but is generally sufficiently accurate when is large as the notation is asymptotic. For example, bubble sort may be faster than merge sort when only a few items are to be sorted; however either implementation is likely to meet performance requirements for a small list. Typically, programmers are interested in algorithms that scale efficiently to large input sizes, and merge sort is preferred over bubble sort for lists of length encountered in most data-intensive programs.

Some examples of Big O notation applied to algorithms' asymptotic time complexity include:

Notation Name Examples
constant Finding the median from a sorted list of measurements; Using a constant-size lookup table; Using a suitable hash function for looking up an item.
logarithmic Finding an item in a sorted array with a binary search or a balanced search tree as well as all operations in a Binomial heap.
linear Finding an item in an unsorted list or a malformed tree (worst case) or in an unsorted array; Adding two n-bit integers by ripple carry.
linearithmic, loglinear, or quasilinear Performing a Fast Fourier transform; heapsort, quicksort (best and average case), or merge sort
quadratic Multiplying two n-digit numbers by a simple algorithm; bubble sort (worst case or naive implementation), Shell sort, quicksort (worst case), selection sort or insertion sort
exponential Finding the optimal (non-approximate) solution to the travelling salesman problem using dynamic programming; determining if two logical statements are equivalent using brute-force search

Benchmarking: measuring performance

For new versions of software or to provide comparisons with competitive systems, benchmarks are sometimes used, which assist with gauging an algorithms relative performance. If a new sort algorithm is produced, for example, it can be compared with its predecessors to ensure that at least it is efficient as before with known data, taking into consideration any functional improvements. Benchmarks can be used by customers when comparing various products from alternative suppliers to estimate which product will best suit their specific requirements in terms of functionality and performance. For example, in the mainframe world certain proprietary sort products from independent software companies such as Syncsort compete with products from the major suppliers such as IBM for speed.

Some benchmarks provide opportunities for producing an analysis comparing the relative speed of various compiled and interpreted languages for example and The Computer Language Benchmarks Game compares the performance of implementations of typical programming problems in several programming languages.

Even creating "do it yourself" benchmarks can demonstrate the relative performance of different programming languages, using a variety of user specified criteria. This is quite simple, as a "Nine language performance roundup" by Christopher W. Cowell-Shah demonstrates by example.

Implementation concerns

Implementation issues can also have an effect on efficiency, such as the choice of programming language, or the way in which the algorithm is actually coded, or the choice of a compiler for a particular language, or the compilation options used, or even the operating system being used. In many cases a language implemented by an interpreter may be much slower than a language implemented by a compiler. See the articles on just-in-time compilation and interpreted languages.

There are other factors which may affect time or space issues, but which may be outside of a programmer's control; these include data alignment, data granularity, cache locality, cache coherency, garbage collection, instruction-level parallelism, multi-threading (at either a hardware or software level), simultaneous multitasking, and subroutine calls.

Some processors have capabilities for vector processing, which allow a single instruction to operate on multiple operands; it may or may not be easy for a programmer or compiler to use these capabilities. Algorithms designed for sequential processing may need to be completely redesigned to make use of parallel processing, or they could be easily reconfigured. As parallel and distributed computing grow in importance in the late 2010s, more investments are being made into efficient high-level APIs for parallel and distributed computing systems such as CUDA, TensorFlow, Hadoop, OpenMP and MPI.

Another problem which can arise in programming is that processors compatible with the same instruction set (such as x86-64 or ARM) may implement an instruction in different ways, so that instructions which are relatively fast on some models may be relatively slow on other models. This often presents challenges to optimizing compilers, which must have a great amount of knowledge of the specific CPU and other hardware available on the compilation target to best optimize a program for performance. In the extreme case, a compiler may be forced to emulate instructions not supported on a compilation target platform, forcing it to generate code or link an external library call to produce a result that is otherwise incomputable on that platform, even if it is natively supported and more efficient in hardware on other platforms. This is often the case in embedded systems with respect to floating-point arithmetic, where small and low-power microcontrollers often lack hardware support for floating-point arithmetic and thus require computationally expensive software routines to produce floating point calculations.

Measures of resource usage

Measures are normally expressed as a function of the size of the input .

The two most common measures are:

  • Time: how long does the algorithm take to complete?
  • Space: how much working memory (typically RAM) is needed by the algorithm? This has two aspects: the amount of memory needed by the code (auxiliary space usage), and the amount of memory needed for the data on which the code operates (intrinsic space usage).

For computers whose power is supplied by a battery (e.g. laptops and smartphones), or for very long/large calculations (e.g. supercomputers), other measures of interest are:

  • Direct power consumption: power needed directly to operate the computer.
  • Indirect power consumption: power needed for cooling, lighting, etc.

As of 2018, power consumption is growing as an important metric for computational tasks of all types and at all scales ranging from embedded Internet of things devices to system-on-chip devices to server farms. This trend is often referred to as green computing.

Less common measures of computational efficiency may also be relevant in some cases:

  • Transmission size: bandwidth could be a limiting factor. Data compression can be used to reduce the amount of data to be transmitted. Displaying a picture or image (e.g. Google logo) can result in transmitting tens of thousands of bytes (48K in this case) compared with transmitting six bytes for the text "Google". This is important for I/O bound computing tasks.
  • External space: space needed on a disk or other external memory device; this could be for temporary storage while the algorithm is being carried out, or it could be long-term storage needed to be carried forward for future reference.
  • Response time (latency): this is particularly relevant in a real-time application when the computer system must respond quickly to some external event.
  • Total cost of ownership: particularly if a computer is dedicated to one particular algorithm.

Time

Theory

Analyze the algorithm, typically using time complexity analysis to get an estimate of the running time as a function of the size of the input data. The result is normally expressed using Big O notation. This is useful for comparing algorithms, especially when a large amount of data is to be processed. More detailed estimates are needed to compare algorithm performance when the amount of data is small, although this is likely to be of less importance. Algorithms which include parallel processing may be more difficult to analyze.

Practice

Use a benchmark to time the use of an algorithm. Many programming languages have an available function which provides CPU time usage. For long-running algorithms the elapsed time could also be of interest. Results should generally be averaged over several tests.

Run-based profiling can be very sensitive to hardware configuration and the possibility of other programs or tasks running at the same time in a multi-processing and multi-programming environment.

This sort of test also depends heavily on the selection of a particular programming language, compiler, and compiler options, so algorithms being compared must all be implemented under the same conditions.

Space

This section is concerned with use of memory resources (registers, cache, RAM, virtual memory, secondary memory) while the algorithm is being executed. As for time analysis above, analyze the algorithm, typically using space complexity analysis to get an estimate of the run-time memory needed as a function as the size of the input data. The result is normally expressed using Big O notation.

There are up to four aspects of memory usage to consider:

  • The amount of memory needed to hold the code for the algorithm.
  • The amount of memory needed for the input data.
  • The amount of memory needed for any output data.
    • Some algorithms, such as sorting, often rearrange the input data and don't need any additional space for output data. This property is referred to as "in-place" operation.
  • The amount of memory needed as working space during the calculation.

Early electronic computers, and early home computers, had relatively small amounts of working memory. For example, the 1949 Electronic Delay Storage Automatic Calculator (EDSAC) had a maximum working memory of 1024 17-bit words, while the 1980 Sinclair ZX80 came initially with 1024 8-bit bytes of working memory. In the late 2010s, it is typical for personal computers to have between 4 and 32 GB of RAM, an increase of over 300 million times as much memory.

Caching and memory hierarchy

Current computers can have relatively large amounts of memory (possibly Gigabytes), so having to squeeze an algorithm into a confined amount of memory is much less of a problem than it used to be. But the presence of four different categories of memory can be significant:

  • Processor registers, the fastest of computer memory technologies with the least amount of storage space. Most direct computation on modern computers occurs with source and destination operands in registers before being updated to the cache, main memory and virtual memory if needed. On a processor core, there are typically on the order of hundreds of bytes or fewer of register availability, although a register file may contain more physical registers than architectural registers defined in the instruction set architecture.
  • Cache memory is the second fastest and second smallest memory available in the memory hierarchy. Caches are present in CPUs, GPUs, hard disk drives and external peripherals, and are typically implemented in static RAM. Memory caches are multi-leveled; lower levels are larger, slower and typically shared between processor cores in multi-core processors. In order to process operands in cache memory, a processing unit must fetch the data from the cache, perform the operation in registers and write the data back to the cache. This operates at speeds comparable (about 2-10 times slower) with the CPU or GPU's arithmetic logic unit or floating-point unit if in the L1 cache. It is about 10 times slower if there is an L1 cache miss and it must be retrieved from and written to the L2 cache, and a further 10 times slower if there is an L2 cache miss and it must be retrieved from an L3 cache, if present.
  • Main physical memory is most often implemented in dynamic RAM (DRAM). The main memory is much larger (typically gigabytes compared to ≈8 megabytes) than an L3 CPU cache, with read and write latencies typically 10-100 times slower. As of 2018, RAM is increasingly implemented on-chip of processors, as CPU or GPU memory.
  • Virtual memory is most often implemented in terms of secondary storage such as a hard disk, and is an extension to the memory hierarchy that has much larger storage space but much larger latency, typically around 1000 times slower than a cache miss for a value in RAM. While originally motivated to create the impression of higher amounts of memory being available than were truly available, virtual memory is more important in contemporary usage for its time-space tradeoff and enabling the usage of virtual machines. Cache misses from main memory are called page faults, and incur huge performance penalties on programs.

An algorithm whose memory needs will fit in cache memory will be much faster than an algorithm which fits in main memory, which in turn will be very much faster than an algorithm which has to resort to virtual memory. Because of this, cache replacement policies are extremely important to high-performance computing, as are cache-aware programming and data alignment. To further complicate the issue, some systems have up to three levels of cache memory, with varying effective speeds. Different systems will have different amounts of these various types of memory, so the effect of algorithm memory needs can vary greatly from one system to another.

In the early days of electronic computing, if an algorithm and its data wouldn't fit in main memory then the algorithm couldn't be used. Nowadays the use of virtual memory appears to provide much memory, but at the cost of performance. If an algorithm and its data will fit in cache memory, then very high speed can be obtained; in this case minimizing space will also help minimize time. This is called the principle of locality, and can be subdivided into locality of reference, spatial locality and temporal locality. An algorithm which will not fit completely in cache memory but which exhibits locality of reference may perform reasonably well.

Criticism of the current state of programming

Software efficiency halves every 18 months, compensating Moore's Law

May goes on to state:

In ubiquitous systems, halving the instructions executed can double the battery life and big data sets bring big opportunities for better software and algorithms: Reducing the number of operations from N × N to N × log(N) has a dramatic effect when N is large ... for N = 30 billion, this change is as good as 50 years of technology improvements.

  • Software author Adam N. Rosenburg in his blog "The failure of the Digital computer", has described the current state of programming as nearing the "Software event horizon", (alluding to the fictitious "shoe event horizon" described by Douglas Adams in his Hitchhiker's Guide to the Galaxy book). He estimates there has been a 70 dB factor loss of productivity or "99.99999 percent, of its ability to deliver the goods", since the 1980s—"When Arthur C. Clarke compared the reality of computing in 2001 to the computer HAL 9000 in his book 2001: A Space Odyssey, he pointed out how wonderfully small and powerful computers were but how disappointing computer programming had become".

Competitions for the best algorithms

The following competitions invite entries for the best algorithms based on some arbitrary criteria decided by the judges:

Butane

From Wikipedia, the free encyclopedia ...