Optimization Topics - Revision history

Root: /* Other */

2024-05-23T18:01:14Z

Other

← Older revision		Revision as of 18:01, 23 May 2024
Line 149:		Line 149:
	This transformation reduces the complexity of operations within the loop, effectively turning a multiplication and addition into a simple addition. This not only saves computational resources but also enhances the clarity and potentially the performance of the loop, especially in cases where '''n''' is large.		This transformation reduces the complexity of operations within the loop, effectively turning a multiplication and addition into a simple addition. This not only saves computational resources but also enhances the clarity and potentially the performance of the loop, especially in cases where '''n''' is large.

	=== Other ===		<!--=== Other ===
			-->

	= Machine-dependent Optimizations =		= Machine-dependent Optimizations =

Root: /* Variable induction */

2024-05-23T18:00:55Z

Variable induction

← Older revision		Revision as of 18:00, 23 May 2024
Line 146:		Line 146:
	k = k + 4; // Increment k by 4 in each iteration.		k = k + 4; // Increment k by 4 in each iteration.
	}		}
			</source>
	This transformation reduces the complexity of operations within the loop, effectively turning a multiplication and addition into a simple addition. This not only saves computational resources but also enhances the clarity and potentially the performance of the loop, especially in cases where '''n''' is large.		This transformation reduces the complexity of operations within the loop, effectively turning a multiplication and addition into a simple addition. This not only saves computational resources but also enhances the clarity and potentially the performance of the loop, especially in cases where '''n''' is large.
	~~</source>~~

	=== Other ===		=== Other ===

Root: /* Variable induction */

2024-05-23T18:00:28Z

Variable induction

← Older revision		Revision as of 18:00, 23 May 2024
Line 129:		Line 129:

	=== Variable induction ===		=== Variable induction ===
			Variable induction is an optimization technique that simplifies the calculation of values that are repeatedly updated based on their previous value within a loop. This is achieved by transforming the loop to update the variable directly, rather than recalculating it entirely in each iteration. The following is an example using C code.

			Original code with repeated computation:
	<source lang="c">		<source lang="c">
	for (i = 1; i < n; i++)		for (i = 1; i < n; i++) {
	k = i * 4 + m;		k = i * 4 + m; // Each time, k is calculated as i multiplied by 4 plus m.
			}
	</source>		</source>

	~~Becomes~~:		After applying variable induction, the code is refactored to initialize '''k''' with the start value '''m''' and then increment it by a constant value in each iteration, eliminating the need to compute the entire expression repeatedly:

			Optimized code with variable induction applied:
	<source lang="c">		<source lang="c">
	k = m;		k = m; // Initialize k with m.
	for (i = 1; i < n; i++)		for (i = 1; i < n; i++) {
	k = k + 4;		k = k + 4; // Increment k by 4 in each iteration.
			}
			This transformation reduces the complexity of operations within the loop, effectively turning a multiplication and addition into a simple addition. This not only saves computational resources but also enhances the clarity and potentially the performance of the loop, especially in cases where '''n''' is large.
	</source>		</source>

Root: /* Moving invariant code */

2024-05-23T17:56:15Z

Moving invariant code

← Older revision		Revision as of 17:56, 23 May 2024
Line 106:		Line 106:

	=== Moving invariant code ===		=== Moving invariant code ===
			Moving invariant code out of loops is an optimization technique designed to enhance performance by reducing unnecessary computations inside a loop. This method involves identifying code within a loop that does not change across iterations and moving it outside the loop. This reduces the computational overhead per iteration. The following example uses C code do demonstrate the technique.

			Original code with invariant computations within the loop:
	<source lang="c">		<source lang="c">
	for (i = 1; i < n; i++) {		for (i = 1; i < n; i++) {
	a[i] = b[i] + c * d;		a[i] = b[i] + c * d; // The product c*d is computed in every iteration but does not change.
	e = g[k];		e = g[k]; // The value e is assigned in every iteration but does not depend on the loop variable i.
	}		}
	</source>		</source>

	~~Becomes~~:		After refactoring to move invariant code out of the loop, the computation of the constant expressions is performed only once, prior to the loop.

			Optimized code with invariant code moved out:
	<source lang="c">		<source lang="c">
	t = c * d;		t = c * d; // Compute c*d once and store it in t.
	for (i = 1; i < n; i++) {		for (i = 1; i < n; i++) {
	a[i] = b[i] + t;		a[i] = b[i] + t; // Use the precomputed value t inside the loop.
	}		}
	e = g[k];		e = g[k]; // Move assignment of e outside the loop since it does not depend on i.
	</source>		</source>
			By executing these expressions only once instead of on every iteration, the loop becomes more efficient, reducing the runtime, especially for large values of '''n'''. This optimization often yields significant performance improvements in loops that execute a high number of iterations.

	=== Variable induction ===		=== Variable induction ===

Root: /* Cycles / Loops */

2024-05-23T17:52:27Z

Cycles / Loops

← Older revision		Revision as of 17:52, 23 May 2024
Line 80:		Line 80:

	=== Loop unrolling ===		=== Loop unrolling ===
			Loop unrolling is an optimization technique that reduces the overhead of loop control operations (like incrementing and evaluating the loop variable) by executing multiple iterations of the loop body per iteration of the unrolled loop. This can improve the performance of tight loops significantly. The following is an example applied to C code.

			Original code with a simple loop:
	<source lang="c">		<source lang="c">
	for (i = 1; i < n; i++)		for (i = 1; i < n; i++) // Loop iterates from 1 to n-1.
	a[i] = b[i] + 10;		a[i] = b[i] + 10; // Each element of array a is set to the corresponding element of array b plus 10.
	</source>		</source>

	~~Becomes~~:		After applying loop unrolling, the loop body is expanded to perform several iterations' work in a single pass through the loop, thus reducing the loop overhead.

			Optimized code with loop unrolled:
	<source lang="c">		<source lang="c">
	for (i = 1; i < (n/4)*4; i+=4) {		for (i = 1; i < (n/4)*4; i+=4) {
	a[i] = b[i] + 10;		a[i] = b[i] + 10; // Processes four consecutive array elements in one loop iteration.
	a[i+1] = b[i+1] + 10;		a[i+1] = b[i+1] + 10;
	a[i+2] = b[i+2] + 10;		a[i+2] = b[i+2] + 10;
	a[i+3] = b[i+3] + 10;		a[i+3] = b[i+3] + 10;
	}		}

	// rest of the ~~cycle~~		// Handling the rest of the elements if n is not a multiple of 4
	for (; i < n; i++)		for (; i < n; i++)
	a[i] = b[i] + 10;		a[i] = b[i] + 10; // Processes any remaining elements one at a time.
	</source>		</source>
			This technique improves data locality and can make better use of the processor's instruction pipeline by executing more operations in each iteration. However, it can increase code size and potentially impact cache behavior.

	=== Moving invariant code ===		=== Moving invariant code ===

Root: /* Elimination of Common Subexpressions */

2024-05-23T17:47:36Z

Elimination of Common Subexpressions

← Older revision		Revision as of 17:47, 23 May 2024
Line 59:		Line 59:

	== Elimination of Common Subexpressions ==		== Elimination of Common Subexpressions ==
			Elimination of common subexpressions is an optimization technique that identifies and eliminates expressions which are computed more than once within a block of code. By storing the result of such expressions in a temporary variable, the number of calculations is reduced, thus improving the execution efficiency. The following is an example using C code.

	~~Using temporary variables to store common results~~:		Original code with repeated expressions:
	<source lang="c">		<source lang="c">
	d = c * (a + b)		d = c * (a + b); // Computes (a + b) and multiplies the result with c.
	e = (a + b) / 2		e = (a + b) / 2; // Again computes (a + b) and then divides it by 2.
	</source>		</source>

	~~Becomes~~:		After applying the elimination of common subexpressions, the code is refactored to compute the common expression '''(a + b)''' only once and reuse the result.

			Optimized code with common subexpressions eliminated:
	<source lang="c">		<source lang="c">
	t = a + b		t = a + b; // Common expression (a + b) stored in temporary variable t.
	d = c * t		d = c * t; // Uses the value stored in t.
	e = t / 2		e = t / 2; // Reuses the value in t, avoiding the need to compute (a + b) again.
	</source>		</source>
			This technique saves computational resources by reducing redundant calculations and thus can significantly enhance the performance of the program.

	== Cycles / Loops ==		== Cycles / Loops ==

Root: /* Machine-independent optimizations */

2024-05-23T17:44:46Z

Machine-independent optimizations

← Older revision		Revision as of 17:44, 23 May 2024
Line 38:		Line 38:

	== Constant folding ==		== Constant folding ==
	Constant folding is an optimization technique where expressions involving constants are evaluated during the compile-time rather than at runtime (direct evaluation of expressions using only literal and known values). This technique improves the performance by reducing the number of computations needed during execution. Consider the following example using C code:		Constant folding is an optimization technique where expressions involving constants are evaluated during the compile-time rather than at runtime (direct evaluation of expressions using only literal and known values). This technique improves the performance by reducing the number of computations needed during execution. Consider the following example using C code.

	Original code with expressions involving constants:		Original code with expressions involving constants:

Root: /* Constant folding */

2024-05-23T17:43:29Z

Constant folding

← Older revision		Revision as of 17:43, 23 May 2024
Line 55:		Line 55:
	int z = 70; // The expression (20 * 3 + 10) is evaluated as 70 during compile-time.		int z = 70; // The expression (20 * 3 + 10) is evaluated as 70 during compile-time.
	</source>		</source>

			This simplification leads to faster execution as the calculations are performed at compile-time, and the runtime operation involves fewer computations.

	== Elimination of Common Subexpressions ==		== Elimination of Common Subexpressions ==

Root: /* Constant folding */

2024-05-23T17:42:34Z

Constant folding

← Older revision		Revision as of 17:42, 23 May 2024
Line 38:		Line 38:

	== Constant folding ==		== Constant folding ==
			Constant folding is an optimization technique where expressions involving constants are evaluated during the compile-time rather than at runtime (direct evaluation of expressions using only literal and known values). This technique improves the performance by reducing the number of computations needed during execution. Consider the following example using C code:

	~~Direct evaluation of~~ expressions ~~using only literal and known values~~:		Original code with expressions involving constants:
	<source lang="c">		<source lang="c">
	int x = (int )malloc(1024 * 4); // Allocating memory space for 1024 integers, assuming each integer is 4 bytes.		int x = (int )malloc(1024 * 4); // Allocating memory space for 1024 integers, assuming each integer is 4 bytes.
Line 46:		Line 47:
	</source>		</source>

	~~Becomes~~:		After applying constant folding, the code is simplified by evaluating the expressions that involve only constants.

			Optimized code with constant expressions evaluated:
	<source lang="c">		<source lang="c">
	int x = (int )malloc(4096); // Directly allocating memory for 4096 bytes (as 1024 * 4 equals 4096).		int x = (int )malloc(4096); // Directly allocating memory for 4096 bytes (as 1024 * 4 equals 4096).

Root: /* Constant folding */

2024-05-23T17:39:29Z

Constant folding

← Older revision		Revision as of 17:39, 23 May 2024
Line 41:		Line 41:
	Direct evaluation of expressions using only literal and known values:		Direct evaluation of expressions using only literal and known values:
	<source lang="c">		<source lang="c">
	int x = (int )malloc(1024 * 4);		int x = (int )malloc(1024 * 4); // Allocating memory space for 1024 integers, assuming each integer is 4 bytes.
	int y = 3;		int y = 3; // Initializing y with the value 3.
	int z = 20 * y + 10;		int z = 20 * y + 10; // Calculating z using the value of y.
	</source>		</source>

	Becomes:		Becomes:
	<source lang="c">		<source lang="c">
	int x = (int )malloc(4096);		int x = (int )malloc(4096); // Directly allocating memory for 4096 bytes (as 1024 * 4 equals 4096).
	int y = 3;		int y = 3; // The value of y remains the same.
	int z = 70;		int z = 70; // The expression (20 * 3 + 10) is evaluated as 70 during compile-time.
	</source>		</source>