缓存友好在实际编程中的重要性-Toy模板网

这篇具有很好参考价值的文章主要介绍了缓存友好在实际编程中的重要性。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

引入

当CPU执行程序时，需要频繁地访问主存储器（RAM）中的数据和指令。然而，主存储器的访问速度相对较慢，与CPU的运算速度相比存在显著差异，每次都从主存中读取数据都会导致相对较长的等待时间，从而降低计算机的整体性能。为了减弱这种速度差异带来的影响，计算机系统引入了高速缓存（cache）作为中间层，用于存储主存储器中CPU经常访问的数据和指令。

所以，高速缓存应该缓存哪些数据以尽可能提高缓存命中率呢？这就涉及到了局部性原理的作用。

局部性原理

局部性原理是指程序访问数据和指令的模式往往具有以下两种特点：

时间局部性：如果一个存储位置被访问，在不久的将来它很可能再次被访问。这意味着计算机系统很可能会重复地访问同一个数据或指令。
空间局部性：如果一个存储位置被访问，附近的存储位置也很可能在不久的将来被访问。这意味着计算机系统在访问数据或指令时，很可能会顺序地访问附近的数据或指令。

基于局部性原理，高速缓存的设计通常采用了缓存行（Cache Line）的概念。缓存行是高速缓存中最小的存储单元，一般大小为几十字节到几百字节。当CPU访问主存储器的数据时，高速缓存将一整个缓存行的数据加载到缓存中，而不仅仅是所需的单个数据。这样，如果CPU在不久的将来需要附近的数据，它们很可能已经在同一缓存行中了，从而避免了频繁地访问主存储器。

当我们谈论算法或数据结构的“缓存友好”性质时，指的是这些算法或数据结构在计算机的缓存系统中表现良好，从而提高程序的性能。缓存友好性是一个重要的性能指标，以下是三个缓存友好性的测试例子，更深刻体会下缓存友好的重要性。

顺序访问数组

顺序访问数组：顺序访问数组中的元素是缓存友好的操作。当程序连续读取数组的元素时，计算机缓存可以将整个连续的数据块加载到缓存中，从而加快访问速度。相比之下，随机访问数组元素可能导致缓存不命中，需要频繁地从内存中读取数据，降低了访问速度。

通过一个很经典的例子来感受下缓存的存在：假设我们有一个二维矩阵，并且要对它进行某种操作，例如求和或者求积。考虑以下两种遍历方式：

行优先遍历：按照行优先遍历矩阵，先访问第一行的所有元素，然后是第二行的所有元素，以此类推。
列优先遍历：按照列优先遍历矩阵，先访问第一列的所有元素，然后是第二列的所有元素，以此类推。

因为局部性原理，当我们对矩阵进行遍历时，如果采用行优先遍历方式，那么连续的内存块都是同一行的元素，这样的访问方式在缓存中具有较好的局部性，能够更好地利用缓存，从而提高访问效率。相比之下，如果采用列优先遍历方式，由于矩阵中的元素是按列存储的，访问过程会在内存中跳跃，这会导致缓存不命中，降低访问效率。

import java.util.Random;

public class CacheFriendlyTest {
    public static void main(String[] args) {
        int rows = 10000;
        int cols = 10000;

        int[][] matrix = new int[rows][cols];

        // Fill the matrix with random values
        Random random = new Random();
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                matrix[i][j] = random.nextInt(100);
            }
        }

        // Row-wise traversal
        long startTime = System.currentTimeMillis();
        long sumRowWise = 0;
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                sumRowWise += matrix[i][j];
            }
        }
        long endTime = System.currentTimeMillis();
        System.out.println("Row-wise traversal time: " + (endTime - startTime) + " ms");

        // Column-wise traversal
        startTime = System.currentTimeMillis();
        long sumColWise = 0;
        for (int j = 0; j < cols; j++) {
            for (int i = 0; i < rows; i++) {
                sumColWise += matrix[i][j];
            }
        }
        endTime = System.currentTimeMillis();
        System.out.println("Column-wise traversal time: " + (endTime - startTime) + " ms");

        System.out.println("Sum Row-Wise: " + sumRowWise);
        System.out.println("Sum Col-Wise: " + sumColWise);
    }
}

因此，虽然两种遍历方式在时间复杂度上是相同的（都是 $O (m * n)$ ，其中 m 和 n 分别是矩阵的行数和列数），但行优先遍历的实际表现往往比列优先遍历要好得多。

Row-wise traversal time: 45 ms
Column-wise traversal time: 761 ms
Sum Row-Wise: 4949822692
Sum Col-Wise: 4949822692

紧凑数据结构

使用“紧凑”的数据结构可以提高缓存友好性。例如，使用数组而不是链表，因为数组的元素在内存中是连续存储的，而链表的节点分散在内存中，访问链表可能导致缓存不命中。

import java.util.ArrayList;
import java.util.Iterator;
import java.util.LinkedList;

public class CompactDataStructureTest {
    public static void main(String[] args) {
        int dataSize = 1000000; // 数据规模
        int repeatCount = 1000;

        // 使用 ArrayList（数组）实现紧凑的数据结构
        ArrayList<Integer> arrayList = new ArrayList<>();
        for (int i = 0; i < dataSize; i++) {
            arrayList.add(i);
        }

        // 使用 LinkedList（链表）实现非紧凑的数据结构
        LinkedList<Integer> linkedList = new LinkedList<>();
        for (int i = 0; i < dataSize; i++) {
            linkedList.add(i);
        }
        // 测试 ArrayList 遍历性能
        long startTime = System.currentTimeMillis();
        for (int i = 0; i < repeatCount; i++) {
            Iterator<Integer> arrayIterator = arrayList.iterator();
            while (arrayIterator.hasNext()) {
                int value = arrayIterator.next();
                // 在这里可以对 value 进行一些操作，以避免编译器对循环的优化
            }
        }
        long endTime = System.currentTimeMillis();
        System.out.println("ArrayList traversal time: " + (endTime - startTime) + " ms");

        // 测试 LinkedList 遍历性能
        startTime = System.currentTimeMillis();
        for (int i = 0; i < repeatCount; i++) {
            Iterator<Integer> linkedListIterator = linkedList.iterator();
            while (linkedListIterator.hasNext()) {
                int value = linkedListIterator.next();
                // 在这里可以对 value 进行一些操作，以避免编译器对循环的优化
            }
        }
        endTime = System.currentTimeMillis();
        System.out.println("LinkedList traversal time: " + (endTime - startTime) + " ms");
    }
}

实际差距并不明显，想来 JDK 对 LinkedList 的存储进行了优化。

ArrayList traversal time: 598 ms
LinkedList traversal time: 2585 ms

矩阵乘法

假设我们有两个 n x n 的矩阵 A 和 B，我们想要计算它们的乘积 C。标准的矩阵乘法算法需要 $O(n^3)$ 的时间复杂度，这是一种较高的复杂度，特别是对于大规模的矩阵。

Strassen 算法通过将两个矩阵分解成较小的子矩阵，并使用分治策略来减少乘法次数。在理论上，Strassen 算法的时间复杂度为 $O(n^{log_27})$ ，约为 $O(n^{2.807})$

但在实际中，并不总是比标准的 O(n^3) 算法表现更好，原因在于 Strassen 算法涉及多次递归，它的计算步骤涉及分解和合并子问题。这种递归的操作可能导致在计算大型矩阵乘法时，多次递归调用可能导致较多的缓存不命中，从而使得 Strassen 算法的实际性能不如预期。

import org.apache.commons.math3.linear.Array2DRowRealMatrix;
import org.apache.commons.math3.linear.RealMatrix;

import java.util.Random;

public class MatrixMultiplicationTest {
    public static void main(String[] args) {
        int n = 1000; // 矩阵大小 n x n

        double[][] A = new double[n][n];
        double[][] B = new double[n][n];

        // Fill the matrices with random values
        Random random = new Random();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                A[i][j] = random.nextDouble();
                B[i][j] = random.nextDouble();
            }
        }

        // Test Standard Matrix Multiplication
        long startTime = System.currentTimeMillis();
        double[][] C = standardMatrixMultiplication(A, B);
        long endTime = System.currentTimeMillis();
        System.out.println("Standard Matrix Multiplication time: " + (endTime - startTime) + " ms");

        // Test Strassen Matrix Multiplication
        startTime = System.currentTimeMillis();
        double[][] D = strassenMatrixMultiplication(A, B);
        endTime = System.currentTimeMillis();
        System.out.println("Strassen Matrix Multiplication time: " + (endTime - startTime) + " ms");
    }

    // Standard Matrix Multiplication
    public static double[][] standardMatrixMultiplication(double[][] A, double[][] B) {
        int n = A.length;
        double[][] C = new double[n][n];

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                for (int k = 0; k < n; k++) {
                    C[i][j] += A[i][k] * B[k][j];
                }
            }
        }

        return C;
    }

    // Strassen Matrix Multiplication
    public static double[][] strassenMatrixMultiplication(double[][] A, double[][] B) {
        // Convert input arrays to RealMatrix
        RealMatrix matrixA = new Array2DRowRealMatrix(A);
        RealMatrix matrixB = new Array2DRowRealMatrix(B);

        // Perform Strassen matrix multiplication
        RealMatrix matrixC = matrixA.multiply(matrixB);

        // Convert the result back to 2D array
        return matrixC.getData();
    }
}

需要以下依赖

<dependency>
    <groupId>org.apache.commons</groupId>
    <artifactId>commons-math3</artifactId>
    <version>3.6.1</version> <!-- 版本号可能需要根据您当前使用的版本进行调整 -->
</dependency>

测试结果

Standard Matrix Multiplication time: 11608 ms
Strassen Matrix Multiplication time: 25238 ms

总结

上面几个例子中的代码是非常粗糙，不严谨，有很多因素没有考虑，只是理解下缓存友好的意义，希望在实践中有这个意识。文章来源地址https://www.toymoban.com/news/detail-624075.html

到了这里，关于缓存友好在实际编程中的重要性的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

缓存友好在实际编程中的重要性

引入

局部性原理

顺序访问数组

紧凑数据结构

矩阵乘法

总结

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏

支付宝扫一扫领取红包，优惠每天领

二维码1

二维码2