Bounds-checking elimination
- Bounds-checking elimination
In computer science, bounds-checking elimination is a compiler optimization useful in programming languages or runtimes that enforce bounds checking, the practice of consistently checking every index into an array to verify that the index is within the defined valid range of indexes. Its goal is to detect which of these indexing operations do not need to be validated at runtime, and eliminating those checks.
One common example is accessing an array element, modifying it, and storing the modified value in the same array at the same location. Normally, this example would result in a bounds check when the element is read from the array and a second bounds check when the modified element is stored using the same array index.Bounds-checking elimination could eliminate the second check if the compiler or runtime can determine that the array size cannot change and the index cannot change between the two array operations.
Another example occurs when a programmer loops over the elements of the array, and the loop condition guarantees that the index is within the bounds of the array. It may be difficult to detect that the programmer's manual check renders the automatic check redundant. However, it may still be possible for the compiler or runtime to perform proper bounds-checking elimination in this case.
Implementations
In natively compiled languages
One technique for bounds-checking elimination is to use a typed static single assignment form representation and for each array create a new type representing a safe index for that particular array. The first use of a value as an array index results in a runtime type cast (and appropriate check), but subsequently the safe index value can be used without a type cast, without sacrificing correctness or safety.
In JIT-compiled languages
Just-in-time compiled languages such as Java often check indexes at runtime before accessing Arrays. Some Just-in-time compilers such as HotSpot are able to eliminate some of these checks if they discover that the index is always within the correct range, or if an earlier check would have already thrown an exception [cite web
url=http://weblogs.java.net/blog/kohsuke/archive/2008/03/deep_dive_into.html
title=Deep dive into assembly code from Java
last=Kawaguchi|first=Kohsuke
date=2008-03-30
accessdate=2008-04-02] [cite web
url=http://ei.cs.vt.edu/~cs5314/presentations/Group2PLDI.pdf
title=Fast, Effective Code Generation in a Just-In-Time Java Compiler
publisher=Intel Corporation
accessdate=2007-06-22] .
References
External links
* W. Amme, J. von Ronne, M. Franz. [http://citeseer.ist.psu.edu/721276.html Using the SafeTSA Representation to Boost the Performance of an Existing Java Virtual Machine] (2002).
Wikimedia Foundation.
2010.
Look at other dictionaries:
Bounds checking — In computer programming, bounds checking is any method of detecting whether a variable is within some bounds before its use. It is particularly relevant to a variable used as an index into an array to ensure its value lies within the bounds of… … Wikipedia
Compiler optimization — is the process of tuning the output of a compiler to minimize or maximize some attributes of an executable computer program. The most common requirement is to minimize the time taken to execute a program; a less common one is to minimize the… … Wikipedia
Array data type — Not to be confused with Array data structure. In computer science, an array type is a data type that is meant to describe a collection of elements (values or variables), each selected by one or more indices that can be computed at run time by the … Wikipedia
Java performance — Programs written in Java have had a reputation for being slower and requiring more memory than those written in natively compiled languages such as C or C++ (see e.g. [cite web url=http://www.jelovic.com/articles/why java is slow.htm title=Why… … Wikipedia
Array — In computer science an array [Paul E. Black, array , in Dictionary of Algorithms and Data Structures , Paul E. Black, ed., U.S. National Institute of Standards and Technology. 26 August 2008 (accessed 10 September 2008).… … Wikipedia
Code bloat — is the production of code that is perceived as unnecessarily long, slow, or otherwise wasteful of resources. Code bloat can be caused by inadequacies in the language in which the code is written, inadequacies in the compiler used to compile the… … Wikipedia
Clique problem — The brute force algorithm finds a 4 clique in this 7 vertex graph (the complement of the 7 vertex path graph) by systematically checking all C(7,4)=35 4 vertex subgraphs for completeness. In computer science, the clique problem refers to any of… … Wikipedia
Data Validation and Reconciliation — Industrial process data validation and reconciliation or short data validation and reconciliation (DVR) is a technology which is using process information and mathematical methods in order to automatically correct measurements in industrial… … Wikipedia
United States — a republic in the N Western Hemisphere comprising 48 conterminous states, the District of Columbia, and Alaska in North America, and Hawaii in the N Pacific. 267,954,767; conterminous United States, 3,022,387 sq. mi. (7,827,982 sq. km); with… … Universalium
Decomposition method (constraint satisfaction) — In constraint satisfaction, a decomposition method translates a constraint satisfaction problem into another constraint satisfaction problem that is binary and acyclic. Decomposition methods work by grouping variables into sets, and solving a… … Wikipedia
