Topic: efficiency

topics > computer science > programming > Group: goals for a programming system

memory management
Thesa programming system

code optimization
computer performance
data caching
file cache
function cost
memory cache
optimization of object-oriented programs
no need for efficiency
programmer productivity


Efficiency has gained a bad reputation because efficient programming has been expensive, non-standard, and difficult to maintain. The shift against efficiency is fairly new. For example FORTRAN's success was closely tied to its efficient code generation. Thesa shares FORTRAN's emphasis on production programming in cost-conscious environments. Thesa systems provide local resource efficiency, efficient procedure representation and an efficient user interface, while the user organizes his programs for global efficiency. Instead of providing a general purpose machine, Thesa provides the user a database particularly tuned to his needs.

Programming costs increase rapidly when hardware limits are reached. Due to limited memories, space efficiencies are usually more important than temporal efficiency. In many systems efficient disk access determines a program's overall efficiency. (cbb 5/80)

Subtopic: performance measurement up

Quote: portable API for performance tools using the on-chip performance monitoring hardware; measurements per-thread; PAPI [»muccP6_2005]
Quote: when optimizing a program, measure performance before and after each change [»blocJ_2001]
Quote: a good performance benchmark is repeatable, observable, portable, easily presented, realistic, and runnable [»smaaB2_2006]

Subtopic: efficiency is important up

Quote: performance work done at the beginning of the project in terms of benchmark, algorithm, and data-structure selection will pay tremendous dividends later on [»smaaB2_2006]
Quote: think about performance during design; pervasive architectural flaws can limit performance forever; changing a design later can produce an ill-structured sytsem [»blocJ_2001]
Quote: first order efficiency must be kept in mind throughout the design and implementation effort; avoid gargantuism and inherently inefficient constructs that can not be optimized [»stroB_1991]
Quote: engineering economy is a fundamental component of engineering; it is ignored in software education and practice [»tockS11_1997]
Quote: programming costs increase rapidly when reach hardware limits of speed and memory [»boehBW5_1973, OK]
Quote: software designed independent of cost is different from software designed by technicians under economics-driven contexts [»boehBW12_1976, OK]
Quote: as a system grows, need to improve performance [»belaLA_1979]
Quote: a design should be well structured, simple, efficient, adequate, flexible, practical, implementable, and standardized [»parnDL8_1985]
Quote: need a programming language that is easy to understand and efficient to execute; currently too detailed or too inefficient [»tarjRE3_1987]
QuoteRef: cbb_1973 ;;4/3/75 must be some sense of cost--of effort and time
Quote: while clients of an interface depend on an efficient implementation; the costs are seldom documented [»lampBW10_1983]
Quote: an interface should be fast; basic operations should execute quickly, otherwise everyone pays for a powerful by slow operation [»lampBW10_1983]
Quote: properties of records -- small number of labels, frequent creation and access, multiple records with the same domain, efficient use of space and time [»remyD6_1992]

Subtopic: tradeoffs for efficiency up

Quote: developers should document their assumptions and write tests for these assumptions; catch changing conditions or inapproriate reuse [»smaaB2_2006]
Quote: make programs as fast as possible with acceptable correctness; or as correct as possible with acceptable speed [»stoyJE3_1972]
Quote: system can not at the same time be programmable, efficient, and amenable to evolution [»conrM5_1985]
Quote: existing programming languages attempt to capture all of program development in one text; the program must balance clarity with efficiency [»scheWL9_1983]
Quote: if response time and space requirements are important than applicative programming is less applicable [»morrJH_1980]
Quote: military programmers are so concerned about efficiency that they will tune for their compiler even though readability is destroyed [»goodJB8_1976]
Quote: programming must balance machine time, storage space, programmer's time, and result accuracy; they all cost something [»turiA3_1951]

Subtopic: design for efficiency up

Quote: bound the variabilities to minimize production costs and automate software generation [»coplJ11_1998]
Quote: listen carefully to what users want; understand what they really want; achieve the latter at a fraction of the cost of the former [»hoarCA_1974]
Quote: a specification language should separate system performance from interface correctness [»hamiM3_1976]
Quote: efficiency and safety of real world actions are often difficult to discern; must be learned; tools can help [»yeeKP12_2002]
Quote: periodically stop development for a week to analyze and resolve performance problems; otherwise minor performance losses will accumulate [»colwRP_2006]

Subtopic: algorithm efficiency up

Quote: for Solaris 10 development, all of the really big performance improvements resulted in changes to algorithms; study performance early in a project [»smaaB2_2006]
Quote: simple algorithms often faster because easily optimized and good cache performance
Quote: empirical test of online list accessing; move-to-front, frequency-count, and move-to-recent-item(0) were best [»bachR1_1997]

Subtopic: type safety efficiency up

Quote: efficient type safety with CCured -- 3-87% time overhead, 1-284% space overhead; Purify and Valgrind are 5x to 130x slower [»necuGC5_2005]

Subtopic: eliminate unappreciated work up

Quote: eliminate unneeded or unappreciated work; only the end state matters [»smaaB2_2006]

Subtopic: memory hierarchy up

Quote: system designers and programmers need to understand program memory management; vast difference in performance [»hoarCA_1971]
Quote: five orders of magnitude performance difference between main store and backing store
Quote: memory management changes runtimes dramatically but users have little control [»kernBW7_1998]

Subtopic: object-oriented efficiency up

Quote: C++'s abstraction mechanisms map a user's high-level concepts into a machine model without loss of time or space efficiency [»stroB12_2004]
Quote: parameterize with function objects; inlined; no code for unused template functions; much faster than function pointers [»stroB12_2004]
Quote: templates capture abstractions while retaining performance; at instantiation, compiler has the calling and called context; instantiated only if needed [»dosrG1_2006]
Quote: quidelines for faster Java; reduce frequency of object allocation and object copies; up to 15x improvement [»klemR6_1999]
Quote: designed Java's semantics so that 'a=b+c' and 'p.m' could be implemented quickly; e.g., lead to static typing [»goslJ6_1997]
Quote: Java's runtime efficiency is acceptable but it has a huge memory overhead [»precL10_2000]
Quote: rewrote LINPACK in Java; Fortran-style Java code was 4x slower than original; Java with explicit base types was 4x or more slower; object-oriented Java was 19x to 140x slower on average [»budiZ2_1999]
Quote: layered abstractions increase the stack data cache footprint, TLB misses, and function call overhead; too many arguments; spectacularly deep call stacks [»smaaB2_2006]

Subtopic: machine code efficiency up

Quote: to estimate timing for a routine, the plan should include the instructions in the inner loop [»turiA3_1951]
Quote: users and programs make assumptions about operator complexity; e.g., push and pop should be amortized constant time, string copy should be linear [»dehnJC4_1998]
Quote: efficient operations are add, subtract, XOR, rotate by constant, and table lookup
Quote: arithmetic expressions are highly efficient because of the extreme narrowness of the interface; a single number stored in a high-speed register [»hoarCA_1974]
Quote: performance analysis of encryption algorithms on the Intel Pentium; general optimization principles [»schnB1_1997]
Quote: suggestions for improving low-level performance; careful of inner loops, parallelism, setup [»schnB1_1997]
Quote: even though C and C++ are excellent languages for low-level systems work, assembly code can be significantly smaller and faster, and expensive to maintain [»stroB_1994]

Subtopic: bit-level efficiency up

Quote: converting a bit-level implementation to word-level often requires algorithm-specific insights; vectorizing compilers are largely ineffective [»solaA6_2005]
Quote: demonstrate sketching the DropThird algorithm; i.e., drop every third bit from the input stream; surprisingly difficult [»solaA6_2005]

Subtopic: space vs. time efficiency up

Quote: reducing the size of a program is usually more important than increasing speed of execution [»jackMA_1975]
Quote: a garbage collector needs to partition memory into different strategies, traverse by tracing or reference counting, decide on space-time tradeoffs [»bacoDF10_2004]
Quote: achieve 'free' garbage collection by using 8x the memory [»appeAW6_1987]
Note: want tight inner loops and space-efficient, low frequency code; for overall space and time efficiency [»cbb_1990, OK]

Subtopic: update vs. replace, reference vs. value up

Quote: for large operands, update is more efficient than replacement; provide notation, e.g., L1.append(L2) [»hoarCA_1974]

Subtopic: centralized vs. distributed efficiency up

Quote: differing performance requirements for centralized vs. distributed systems; e.g., compare idle locomotives with idle cars [»liskB10_1981]
Quote: designed occam for efficiency in an distributed implementation; same program is then also valid for a single computer [»mayD_1987]

Subtopic: software development efficiency up

Quote: allow online addition and removal of performance-oriented structures for databases; do not stop the database [»coddEF_1990]
Quote: ABC programs are a quarter or a fifth the length of Pascal/C programs; e.g., FOR line IN document: PUT max{longest; #line} IN longest; faster development [»pembS1_1987]
Quote: a programming language specifies actions to be executed, and supplies concepts that help with programming [»stroB_1991]
Quote: fast compilation for rapid turnaround; fast code for instrumenting a program [»hoarCA_1974]
Quote: speed of compilation is important for debugging [»hoarCA_1974]
Quote: efficient object code is important; allows better-structured and clearer programs [»hoarCA_1974]

Subtopic: sequential composition up

Quote: sequential composition is key to efficient programs because all computational resources immediately available at each step [»hoarCA9_1987]

Subtopic: programming language efficiency up

Quote: cost-effective success in language design is progress in programming methodology
Quote: ESP for efficient, device implementations of concurrent programming; other languages support concurrency but not as efficiently [»kumaS6_2001]
Quote: a programming language should be close to the machine, like C, and close to the problem, like C++
Quote: user-defined types in C++ can deal efficiently with fundamental hardware objects such as bits, bytes, words, and addresses [»stroB_1991]
Quote: FORTRAN was designed for efficiency instead of good language design; Backus believes this decision was correct [»backJ8_1978]
Quote: FORTRAN was designed as needed; the real problem was a compiler that produced efficient programs [»backJ8_1978]
Quote: FORTRAN was designed for both local and global efficiency of instructions and their context [»backJW_1957]
Quote: a good Common Lisp compiler is as efficient as FORTRAN for numeric programs [»tichWF11_1987]
Quote: Bliss defined data structures by a macro-like accessing algorithm; every detail specified [»shawM3_1980]

Subtopic: compile vs. script up

Quote: compiled languages most memory-efficient while Java least memory-efficient; script languages overlap the worst half of the compiled languages [»precL10_2000]
Quote: 2-3x shorter programs for scripting languages such as Perl; more comments [»precL10_2000]
Quote: scripting languages are good alternatives; better programmer productivity and acceptable efficiency
Quote: for initialization, compiled languages fastest and script languages slowest; Java in between [»precL10_2000]
QuoteRef: grisRE4_1979 ;;18 "Unlike SNOBOL4 and SL5, Icon is intended to be practical for production programming
Quote: code generation is inefficient for languages whose semantics are not close to the bytes-and-pointers model; often 3 to 10 times slower, especially with dynamic typing [»koenA12_1995]
Quote: compared speed of scripting and user-interface languages; enormous variation [»kernBW7_1998]

Subtopic: benchmarks up

Quote: do not take benchmarks at face value
Quote: up to 30x performance ratio between the median programs of the upper and lower half
Quote: individual differences have a greater effect on performance than Java vs. C/C++
Quote: a good performance benchmark is repeatable, observable, portable, easily presented, realistic, and runnable [»smaaB2_2006]

Subtopic: efficiency of programming language features up

Quote: keep bidirectional iterators separate from random access iterators; e.g., different algorithms for rotate and random shuffle using these iterators
Quote: if know a value is fixed, can produce more efficient software in time and space
Quote: C++ follows the zero-overhead rule: a new feature can not decrease the efficiency of programs without the feature [»stroB_1994]
Quote: C is restricted to tasks where a compiler is effective; all other tasks are relegated to subroutine libraries; greater flexibility [»ritcDM7_1978c]
Quote: an implementation of Modula-3 exceptions should not increase the cost of procedure calls; the specification suggests a minimum ratio of a 1000 to 1 [»cardL_1991]
Quote: a 'char' is a signed or an unsigned integer; an 'unsigned char' may be significantly less efficient than a 'char'

Subtopic: OS efficiency up

Quote: V kernel IPC file access is efficient enough for file transfer and terminal protocols; depends on high data rate, low delay and errors [»cherDR4_1984]
Quote: the V kernel is about 50K bytes of code and data on a Motorola 68000 [»cherDR4_1984]
Quote: files should be extended one block at a time, with fragment at end; UNIX tells applications the optimal read/write size

Related Topics up

Group: memory management   (11 topics, 367 quotes)
Group: Thesa programming system   (11 topics, 561 quotes)

Topic: code optimization (54 items)
Topic: computer performance (14 items)
Topic: data caching (35 items)
Topic: file cache (23 items)
Topic: function cost (8 items)
Topic: memory cache (29 items)
Topic: optimization of object-oriented programs (16 items)
Topic: no need for efficiency (28 items)
Topic: programmer productivity
(57 items)

Updated barberCB 6/05
Copyright © 2002-2008 by C. Bradford Barber. All rights reserved.
Thesa is a trademark of C. Bradford Barber.