Run-time algorithm specialization - Revision history

146.199.34.171: Improve wording, formatting, and clarity. Ensure 'code' is used as an uncountable noun.

2025-05-18T09:47:46Z

Improve wording, formatting, and clarity. Ensure 'code' is used as an uncountable noun.

← Previous revision		Revision as of 09:47, 18 May 2025
Line 18:		Line 18:

	The specialized algorithm has to be represented in a form that can be interpreted.		The specialized algorithm has to be represented in a form that can be interpreted.
⚫	In many situations, usually when <math>\mathit{alg}_A(B)</math> is to be computed on many values <math>B</math> in a row, ~~we can write~~ <math>\mathit{alg}_A</math> as a code of a special [[abstract machine]], and we ~~often~~ ~~say~~ that <math>A</math> is ''compiled''.
	Then the code itself can be additionally optimized by answer-preserving transformations that rely only on the semantics of instructions of the abstract machine.

		⚫	In many situations, usually when <math>\mathit{alg}_A(B)</math> is to be computed on many values of <math>B</math> in a row, <math>\mathit{alg}_A</math> can be written as machine code instructions for a special [[abstract machine]], and it is typically said that <math>A</math> is ''compiled''. The code itself can then be additionally optimized by answer-preserving transformations that rely only on the semantics of instructions of the abstract machine.
	Instructions of the abstract machine can usually be represented as records. One field of such a record stores an integer tag that identifies the instruction type, other fields may be used for storing additional parameters of the instruction, for example a pointer to another
	instruction representing a label, if the semantics of the instruction requires a jump. All instructions of a code can be stored in an array, or list, or tree.

			The instructions of the abstract machine can usually be represented as [[Record (computer science)\|record]]s. One field of such a record, an ''instruction identifier'' (or ''instruction tag''), would identify the instruction type, e.g. an [[Integer (computer science)\|integer]] field may be used, with particular integer values corresponding to particular instructions. Other fields may be used for storing additional parameters of the instruction, e.g. a [[Pointer (computer programming)\|pointer]] field may point to another instruction representing a label, if the semantics of the instruction require a jump. All instructions of the code can be stored in a traversable [[data structure]] such as an [[Array (data type)\|array]], [[linked list]], or [[Tree (abstract data type)\|tree]].
⚫	Interpretation is ~~done~~ by fetching instructions in some order, identifying their type

	and executing the actions associated with this type.
		⚫	''Interpretation'' (or ''execution'') proceeds by fetching instructions in some order, identifying their type, and executing the actions associated with said type.
	In [[C (programming language)\|C]] or C++ we can use a '''switch''' statement to associate

	some actions with different instruction tags.
	Modern compilers usually compile a ~~'''~~switch~~'''~~ statement with integer labels from a narrow range ~~rather efficiently~~ by storing the address of the statement corresponding to a value <math>i</math> in the <math>i</math>-th cell of a special array. ~~One~~ can ~~exploit~~ ~~this~~		In many programming languages, such as [[C (programming language)\|C]] and [[C++]], a simple [[Switch statement\|<code>switch</code> statement]] may be used to associate actions with different instruction identifiers. Modern compilers usually compile a <code>switch</code> statement with constant (e.g. integer) labels from a narrow range by storing the address of the statement corresponding to a value <math>i</math> in the <math>i</math>-th cell of a special array, as a means of efficient optimisation. This can be exploited by taking values for instruction identifiers from a small interval of values.
	by taking values for instruction tags from a small interval of integers.

	==Data-and-algorithm specialization==		==Data-and-algorithm specialization==

AnomieBOT: Dating maintenance tags: {{No footnotes}}

2023-11-05T03:40:14Z

Dating maintenance tags: {{No footnotes}}

← Previous revision		Revision as of 03:40, 5 November 2023
Line 1:		Line 1:
	{{no footnotes}}		{{no footnotes\|date=November 2023}}
	In [[computer science]], '''run-time algorithm specialization''' is a methodology for creating efficient algorithms for costly computation tasks of certain kinds. The methodology originates in the field of [[automated theorem proving]] and, more specifically, in the [[Vampire theorem prover]] project.		In [[computer science]], '''run-time algorithm specialization''' is a methodology for creating efficient algorithms for costly computation tasks of certain kinds. The methodology originates in the field of [[automated theorem proving]] and, more specifically, in the [[Vampire theorem prover]] project.

Sarangem at 03:20, 5 November 2023

2023-11-05T03:20:08Z

← Previous revision		Revision as of 03:20, 5 November 2023
Line 1:		Line 1:
			{{no footnotes}}
	In [[computer science]], '''run-time algorithm specialization''' is a methodology for creating efficient algorithms for costly computation tasks of certain kinds. The methodology originates in the field of [[automated theorem proving]] and, more specifically, in the [[Vampire theorem prover]] project.		In [[computer science]], '''run-time algorithm specialization''' is a methodology for creating efficient algorithms for costly computation tasks of certain kinds. The methodology originates in the field of [[automated theorem proving]] and, more specifically, in the [[Vampire theorem prover]] project.

92.40.216.239 at 23:44, 28 September 2023

2023-09-28T23:44:22Z

← Previous revision		Revision as of 23:44, 28 September 2023
Line 50:		Line 50:

	==Further reading==		==Further reading==
	* A. Riazanov and A. Voronkov, "Efficient Checking of Term Ordering Constraints", ''Proc. IJCAR'' 2004, Lecture Notes in Artificial Intelligence 3097, 2004 (''compact but self-contained illustration of the method'')		* A. Riazanov and [[Andrei Voronkov\|A. Voronkov]], "Efficient Checking of Term Ordering Constraints", ''Proc. [[IJCAR]]'' 2004, Lecture Notes in Artificial Intelligence 3097, 2004 (''compact but self-contained illustration of the method'')
	* A. Riazanov and A. Voronkov, [http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.57.8542 Efficient Instance Retrieval with Standard and Relational Path Indexing], Information and Computation, 199(1-2), 2005 (''contains another illustration of the method'')		* A. Riazanov and A. Voronkov, [http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.57.8542 Efficient Instance Retrieval with Standard and Relational Path Indexing], [[Information and Computation]], 199(1-2), 2005 (''contains another illustration of the method'')
	* A. Riazanov, [http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.4.2624 "Implementing an Efficient Theorem Prover"], PhD thesis, The University of Manchester, 2003 (''contains the most comprehensive description of the method and many examples'')		* A. Riazanov, [http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.4.2624 "Implementing an Efficient Theorem Prover"], PhD thesis, The University of Manchester, 2003 (''contains the most comprehensive description of the method and many examples'')

Akeosnhaoe: Akeosnhaoe moved page Run-time algorithm specialisation to Run-time algorithm specialization over redirect: prefer American spelling

2020-03-25T09:45:45Z

Akeosnhaoe moved page Run-time algorithm specialisation to Run-time algorithm specialization over redirect: prefer American spelling

← Previous revision	Revision as of 09:45, 25 March 2020
(No difference)

GreenC bot: Move 1 url. Wayback Medic 2.5

2020-02-13T03:41:54Z

Move 1 url. Wayback Medic 2.5

← Previous revision		Revision as of 03:41, 13 February 2020
Line 47:		Line 47:
	==References==		==References==

	* [~~http~~://~~www~~.~~springerlink~~.~~com/content/r127l5t26vu1m360/~~ A. Voronkov, "The Anatomy of Vampire: Implementing Bottom-Up Procedures with Code Trees", ''Journal of Automated Reasoning'', 15(2), 1995] (''original idea'')		* [https://doi.org/10.1007%2FBF00881918 A. Voronkov, "The Anatomy of Vampire: Implementing Bottom-Up Procedures with Code Trees", ''Journal of Automated Reasoning'', 15(2), 1995] (''original idea'')

	==Further reading==		==Further reading==

BG19bot: Remove blank line(s) between list items per WP:LISTGAP to fix an accessibility issue for users of screen readers. Do WP:GENFIXES and cleanup if needed. Discuss this at Wikipedia talk:WikiProject Accessibility#LISTGAP

2016-03-18T18:29:09Z

Remove blank line(s) between list items per WP:LISTGAP to fix an accessibility issue for users of screen readers. Do WP:GENFIXES and cleanup if needed. Discuss this at Wikipedia talk:WikiProject Accessibility#LISTGAP

195.145.172.243 at 17:30, 10 February 2014

2014-02-10T17:30:53Z

← Previous revision		Revision as of 17:30, 10 February 2014
Line 20:		Line 20:
	Then the code itself can be additionally optimized by answer-preserving transformations that rely only on the semantics of instructions of the abstract machine.		Then the code itself can be additionally optimized by answer-preserving transformations that rely only on the semantics of instructions of the abstract machine.

	Instructions of the abstract machine can usually be represented as records. One field of such a record stores an integer tag that identifies the instruction type, other fields may be used for storing additional ~~Parameters~~ of the instruction, for example a pointer to another		Instructions of the abstract machine can usually be represented as records. One field of such a record stores an integer tag that identifies the instruction type, other fields may be used for storing additional parameters of the instruction, for example a pointer to another
	instruction representing a label, if the semantics of the instruction requires a jump. All instructions of a code can be stored in an array, or list, or tree.		instruction representing a label, if the semantics of the instruction requires a jump. All instructions of a code can be stored in an array, or list, or tree.

130.49.221.178: added link to view "The Anatomy of Vampire" (original idea of this technique)

2011-08-03T20:18:05Z

added link to view "The Anatomy of Vampire" (original idea of this technique)

← Previous revision		Revision as of 20:18, 3 August 2011
Line 47:		Line 47:
	==References==		==References==

	* A. Voronkov, "The Anatomy of Vampire: Implementing Bottom-Up Procedures with Code Trees", ''Journal of Automated Reasoning'', 15(2), 1995 (''original idea'')		* [http://www.springerlink.com/content/r127l5t26vu1m360/ A. Voronkov, "The Anatomy of Vampire: Implementing Bottom-Up Procedures with Code Trees", ''Journal of Automated Reasoning'', 15(2), 1995] (''original idea'')

	==Further reading==		==Further reading==

Cydebot: Robot - Moving category Software performance optimization to Software optimization per CFD at Wikipedia:Categories for discussion/Log/2009 September 1.

2009-09-09T01:20:27Z

Robot - Moving category Software performance optimization to Software optimization per CFD at Wikipedia:Categories for discussion/Log/2009 September 1.

← Previous revision		Revision as of 01:20, 9 September 2009
Line 57:		Line 57:

	[[Category:Algorithms]]		[[Category:Algorithms]]
	[[Category:Software ~~performance~~ optimization]]		[[Category:Software optimization]]

← Previous revision		Revision as of 18:29, 18 March 2016
Line 6:		Line 6:

	The specialized algorithm may be more efficient than the generic one, since it can ''exploit some particular properties'' of the fixed value <math>A</math>. Typically, <math>\mathit{alg}_A(B)</math> can avoid some operations that <math>\mathit{alg}(A,B)</math> would have to perform, if they are known to be redundant for this particular parameter <math>A</math>.		The specialized algorithm may be more efficient than the generic one, since it can ''exploit some particular properties'' of the fixed value <math>A</math>. Typically, <math>\mathit{alg}_A(B)</math> can avoid some operations that <math>\mathit{alg}(A,B)</math> would have to perform, if they are known to be redundant for this particular parameter <math>A</math>.
	In particular, we can often identify some tests that are true or false for <math>A</math>, unroll loops and recursion, etc.		In particular, we can often identify some tests that are true or false for <math>A</math>, unroll loops and recursion, etc.

	== Difference from partial evaluation ==		== Difference from partial evaluation ==
Line 18:		Line 18:
	The specialized algorithm has to be represented in a form that can be interpreted.		The specialized algorithm has to be represented in a form that can be interpreted.
	In many situations, usually when <math>\mathit{alg}_A(B)</math> is to be computed on many values <math>B</math> in a row, we can write <math>\mathit{alg}_A</math> as a code of a special [[abstract machine]], and we often say that <math>A</math> is ''compiled''.		In many situations, usually when <math>\mathit{alg}_A(B)</math> is to be computed on many values <math>B</math> in a row, we can write <math>\mathit{alg}_A</math> as a code of a special [[abstract machine]], and we often say that <math>A</math> is ''compiled''.
	Then the code itself can be additionally optimized by answer-preserving transformations that rely only on the semantics of instructions of the abstract machine.		Then the code itself can be additionally optimized by answer-preserving transformations that rely only on the semantics of instructions of the abstract machine.

	Instructions of the abstract machine can usually be represented as records. One field of such a record stores an integer tag that identifies the instruction type, other fields may be used for storing additional parameters of the instruction, for example a pointer to another		Instructions of the abstract machine can usually be represented as records. One field of such a record stores an integer tag that identifies the instruction type, other fields may be used for storing additional parameters of the instruction, for example a pointer to another
	instruction representing a label, if the semantics of the instruction requires a jump. All instructions of a code can be stored in an array, or list, or tree.		instruction representing a label, if the semantics of the instruction requires a jump. All instructions of a code can be stored in an array, or list, or tree.

	Interpretation is done by fetching instructions in some order, identifying their type		Interpretation is done by fetching instructions in some order, identifying their type
Line 51:		Line 51:
	==Further reading==		==Further reading==
	* A. Riazanov and A. Voronkov, "Efficient Checking of Term Ordering Constraints", ''Proc. IJCAR'' 2004, Lecture Notes in Artificial Intelligence 3097, 2004 (''compact but self-contained illustration of the method'')		* A. Riazanov and A. Voronkov, "Efficient Checking of Term Ordering Constraints", ''Proc. IJCAR'' 2004, Lecture Notes in Artificial Intelligence 3097, 2004 (''compact but self-contained illustration of the method'')

	* A. Riazanov and A. Voronkov, [http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.57.8542 Efficient Instance Retrieval with Standard and Relational Path Indexing], Information and Computation, 199(1-2), 2005 (''contains another illustration of the method'')		* A. Riazanov and A. Voronkov, [http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.57.8542 Efficient Instance Retrieval with Standard and Relational Path Indexing], Information and Computation, 199(1-2), 2005 (''contains another illustration of the method'')

	* A. Riazanov, [http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.4.2624 "Implementing an Efficient Theorem Prover"], PhD thesis, The University of Manchester, 2003 (''contains the most comprehensive description of the method and many examples'')		* A. Riazanov, [http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.4.2624 "Implementing an Efficient Theorem Prover"], PhD thesis, The University of Manchester, 2003 (''contains the most comprehensive description of the method and many examples'')