当前位置: 首页 > news >正文

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

引入

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

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

局部性原理

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

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

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

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

顺序访问数组

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

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

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

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

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 valuesRandom 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 traversallong 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 traversalstartTime = 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 ) O(m * n) O(mn),其中 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 ) O(n^3) O(n3) 的时间复杂度,这是一种较高的复杂度,特别是对于大规模的矩阵。

Strassen 算法通过将两个矩阵分解成较小的子矩阵,并使用分治策略来减少乘法次数。在理论上,Strassen 算法的时间复杂度为 O ( n l o g 2 7 ) O(n^{log_27}) O(nlog27),约为 O ( n 2.807 ) O(n^{2.807}) O(n2.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 ndouble[][] A = new double[n][n];double[][] B = new double[n][n];// Fill the matrices with random valuesRandom 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 Multiplicationlong 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 MultiplicationstartTime = System.currentTimeMillis();double[][] D = strassenMatrixMultiplication(A, B);endTime = System.currentTimeMillis();System.out.println("Strassen Matrix Multiplication time: " + (endTime - startTime) + " ms");}// Standard Matrix Multiplicationpublic 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 Multiplicationpublic static double[][] strassenMatrixMultiplication(double[][] A, double[][] B) {// Convert input arrays to RealMatrixRealMatrix matrixA = new Array2DRowRealMatrix(A);RealMatrix matrixB = new Array2DRowRealMatrix(B);// Perform Strassen matrix multiplicationRealMatrix matrixC = matrixA.multiply(matrixB);// Convert the result back to 2D arrayreturn 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

总结

上面几个例子中的代码是非常粗糙,不严谨,有很多因素没有考虑,只是理解下缓存友好的意义,希望在实践中有这个意识。

相关文章:

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

引入 当CPU执行程序时&#xff0c;需要频繁地访问主存储器&#xff08;RAM&#xff09;中的数据和指令。然而&#xff0c;主存储器的访问速度相对较慢&#xff0c;与CPU的运算速度相比存在显著差异&#xff0c;每次都从主存中读取数据都会导致相对较长的等待时间&#xff0c;从…...

uni-ajax网络请求库使用

uni-ajax网络请求库使用 uni-ajax是什么 uni-ajax是基于 Promise 的轻量级 uni-app 网络请求库,具有开箱即用、轻量高效、灵活开发 特点。 下面是安装和使用教程 安装该请求库到项目中 npm install uni-ajax编辑工具类request.js // ajax.js// 引入 uni-ajax 模块 import ajax…...

MYSQL进阶-事务

1.什么是数据库事务&#xff1f; 事务是一个不可分割的数据库操作序列&#xff0c;也是数据库并发控制的基本单位&#xff0c;其执 行的结果必须使数据库从一种一致性状态变到另一种一致性状态。事务是逻辑上 的一组操作&#xff0c;要么都执行&#xff0c;要么都不执行。 事务…...

python 常见数据类型和方法

不可变数据类型 不支持直接增删改 只能查 str 字符串 int 整型 bool 布尔值 None None型特殊常量 tuple 元组(,,,)回到顶部 可变数据类型&#xff0c;支持增删改查 list 列表[,,,] dic 字典{"":"","": ,} set 集合("",""…...

a-date-picker报错TypeError: date4.locale is not a function

问题描述 使用日期选择器&#xff0c;数据从后端获得&#xff0c;再赋值给a-date-picker做数据回显&#xff0c;遇到这个报错&#xff0c;排错后定位到a-date-picker组件本身接收数据的问题。 如果使用了dayjs或moment库来处理时间字符串&#xff0c;并且使用.format对时间数据…...

LNMP安装

目录 1、LNMP简述&#xff1a; 1.1、概述 1.2、LNMP是一个缩写词&#xff0c;及每个字母的含义 1.3、编译安装与yum安装差异 1.4、编译安装的优点 2、通过LNMP创建论坛 2.1、 安装nginx服务 2.1.1、关闭防火墙 2.1.2、创建运行用户 2.1.3、 编译安装 2.1.4、 优化路…...

matplotlib绘图风格

文章目录 绘图风格测试代码默认和mpl风格复制风格seaborn风格 绘图风格 matplotlib功能强大&#xff0c;可以定制各种绘图要素&#xff0c;以满足个性化的绘图需求&#xff0c;而更换绘图风格也十分便捷&#xff0c;一个matplotlib.style.use函数轻松搞定&#xff0c;而可用的…...

【初级教程】Appium 启动应用 log 日志分析

刚开始学习 appium 时&#xff0c;老师给我布置了 appium 启动应用 log 分析的作业。由于工作比较忙&#xff0c;再者自己想先动手用 appium 写个公司的 app 的 UI 测试&#xff08;目前简单的框架基本完成&#xff0c;在不断完善用例管理中&#xff09;。写这篇文章是为了完成…...

FANUC机器人SRVO-300机械手断裂故障报警原因分析及处理办法

FANUC机器人SRVO-300机械手断裂故障报警原因分析及处理办法 首先,我们查看报警说明书上的介绍: 总结:即在机械手断裂设置为无效时,机器人检测出了机械手断裂信号(不该有的信号,现在检测到了,所以报警) 使机械手断裂设定为无效/有效的具体方法:  按下示教器的MENU菜单…...

MobPush iOS SDK iOS实时活动

开发工具&#xff1a;Xcode 功能需要: SwiftUI实现UI页面&#xff0c;iOS16.1以上系统使用 功能使用: 需应用为启动状态 功能说明 iOS16.1 系统支持实时活动功能&#xff0c;可以在锁定屏幕上实时获知各种事情的进展&#xff0c;MobPushSDK iOS 4.0.3版本已完成适配&#xf…...

c++开发模式,组合模式

组合模式&#xff0c;顾名思义&#xff0c;通过组合关系定义类间的关联关系&#xff0c;实现了将对象组合成树形结构&#xff0c;最终实现类的复用。可能是由于设计模式看的多了&#xff0c;初看组合模式的类图&#xff0c;感觉和装饰者模式类图很相似&#xff0c;都是使用继承…...

【GITHUB】FlipIt – Windows的开源翻页时钟

FlipIt 是一款免费开源的翻页时钟应用&#xff0c;专为 Windows 平台设计。该应用灵感来源于备受喜爱的老牌翻页时钟应用 Fliqlo&#xff0c;后者被公认为经典的翻页时钟屏保。然而&#xff0c;由于 Fliqlo 是基于 Flash 技术开发的&#xff0c;随着微软最近正式禁用 Flash&…...

基于 Flink Paimon 实现 Streaming Warehouse 数据一致性管理

摘要&#xff1a;本文整理自字节跳动基础架构工程师李明&#xff0c;在 Apache Paimon Meetup 的分享。本篇内容主要分为四个部分&#xff1a; 背景 方案设计 当前进展 未来规划 点击查看原文视频 & 演讲PPT 一、背景 ​ 早期的数仓生产体系主要以离线数仓为主&#xf…...

云游戏App简记

注&#xff1a;在安卓手机端使用。其他端不做分析。 App手机游戏PC和主机游戏免费时长&#xff08;手机游戏&#xff09;是否排队备注咪咕快游支持。数量一般&#xff0c;和腾讯还有合作&#xff0c;有不少腾讯的游戏支持每日登录签到送30-60分钟&#xff0c;当天失效&#xf…...

ChatGPT已打破图灵测试,新的测试方法在路上

生信麻瓜的 ChatGPT 4.0 初体验 偷个懒&#xff0c;用ChatGPT 帮我写段生物信息代码 代码看不懂&#xff1f;ChatGPT 帮你解释&#xff0c;详细到爆&#xff01; 如果 ChatGPT 给出的的代码不太完善&#xff0c;如何请他一步步改好&#xff1f; 全球最佳的人工智能系统可以通过…...

Flask学习笔记_异步CMS(五)

Flask学习笔记_异步CMS&#xff08;五&#xff09; 1.环境1.安装nvm2.安装node 2.使用vue-cli创建项目3.安装相关插件4.后台CMS开发1.页面结构1.app.vue搭建结构2.element-icon组件的使用3.iconfont组件的使用 2.使用[Vue-router](https://router.vuejs.org/installation.html)…...

争夺年度智能汽车「中间件」方案提供商TOP10,谁率先入围

进入2023年&#xff0c;整车电子架构升级进入新周期&#xff0c;无论是智能驾驶、智能座舱、车身控制还是信息网络安全&#xff0c;软件赋能仍是行业的主旋律。 作为智能汽车赛道的第三方研究咨询机构&#xff0c;高工智能汽车研究院持续帮助车企、投资机构挖掘具备核心竞争力…...

【Spring Cloud一】微服务基本知识

系列文章目录 微服务基本知识 系列文章目录前言一、系统架构的演变1.1单体架构1.2分层架构1.3分布式架构1.4微服务架构1.5分布式、SOA、微服务的异同点 二、CAP原则三、RESTfulRESTful的核心概念&#xff1a; 四、共识算法 前言 在实际项目开发过程中&#xff0c;目前负责开发…...

swift - 如何在数组大小更改后刷新 ForEach 显示元素的数量(SwiftUI、Xcode 11 Beta 5)

我正在尝试实现一个 View &#xff0c;该 View 可以在内容数组的大小发生变化时更改显示项目的数量(由 ForEach 循环创建)&#xff0c;就像购物应用程序可能会在用户下拉刷新后更改其可用项目的数量一样 这是我到目前为止尝试过的一些代码。如果我没记错的话&#xff0c;这些适…...

编程导航算法村第七关 |二叉树的遍历

编程导航算法村第七关 | 二叉树的遍历 前序遍历&#xff08;递归&#xff09; public List<Integer> preorderTraversal(TreeNode root) {ArrayList<Integer> result new ArrayList<Integer>();preorder(root, result);return result;}public void preorde…...

XCTF-web-easyupload

试了试php&#xff0c;php7&#xff0c;pht&#xff0c;phtml等&#xff0c;都没有用 尝试.user.ini 抓包修改将.user.ini修改为jpg图片 在上传一个123.jpg 用蚁剑连接&#xff0c;得到flag...

关于nvm与node.js

1 安装nvm 安装过程中手动修改 nvm的安装路径&#xff0c; 以及修改 通过nvm安装node后正在使用的node的存放目录【这句话可能难以理解&#xff0c;但接着往下看你就了然了】 2 修改nvm中settings.txt文件配置 nvm安装成功后&#xff0c;通常在该文件中会出现以下配置&…...

2024年赣州旅游投资集团社会招聘笔试真

2024年赣州旅游投资集团社会招聘笔试真 题 ( 满 分 1 0 0 分 时 间 1 2 0 分 钟 ) 一、单选题(每题只有一个正确答案,答错、不答或多答均不得分) 1.纪要的特点不包括()。 A.概括重点 B.指导传达 C. 客观纪实 D.有言必录 【答案】: D 2.1864年,()预言了电磁波的存在,并指出…...

Opencv中的addweighted函数

一.addweighted函数作用 addweighted&#xff08;&#xff09;是OpenCV库中用于图像处理的函数&#xff0c;主要功能是将两个输入图像&#xff08;尺寸和类型相同&#xff09;按照指定的权重进行加权叠加&#xff08;图像融合&#xff09;&#xff0c;并添加一个标量值&#x…...

Matlab | matlab常用命令总结

常用命令 一、 基础操作与环境二、 矩阵与数组操作(核心)三、 绘图与可视化四、 编程与控制流五、 符号计算 (Symbolic Math Toolbox)六、 文件与数据 I/O七、 常用函数类别重要提示这是一份 MATLAB 常用命令和功能的总结,涵盖了基础操作、矩阵运算、绘图、编程和文件处理等…...

多种风格导航菜单 HTML 实现(附源码)

下面我将为您展示 6 种不同风格的导航菜单实现&#xff0c;每种都包含完整 HTML、CSS 和 JavaScript 代码。 1. 简约水平导航栏 <!DOCTYPE html> <html lang"zh-CN"> <head><meta charset"UTF-8"><meta name"viewport&qu…...

网络编程(UDP编程)

思维导图 UDP基础编程&#xff08;单播&#xff09; 1.流程图 服务器&#xff1a;短信的接收方 创建套接字 (socket)-----------------------------------------》有手机指定网络信息-----------------------------------------------》有号码绑定套接字 (bind)--------------…...

JVM暂停(Stop-The-World,STW)的原因分类及对应排查方案

JVM暂停(Stop-The-World,STW)的完整原因分类及对应排查方案,结合JVM运行机制和常见故障场景整理而成: 一、GC相关暂停​​ 1. ​​安全点(Safepoint)阻塞​​ ​​现象​​:JVM暂停但无GC日志,日志显示No GCs detected。​​原因​​:JVM等待所有线程进入安全点(如…...

【MATLAB代码】基于最大相关熵准则(MCC)的三维鲁棒卡尔曼滤波算法(MCC-KF),附源代码|订阅专栏后可直接查看

文章所述的代码实现了基于最大相关熵准则(MCC)的三维鲁棒卡尔曼滤波算法(MCC-KF),针对传感器观测数据中存在的脉冲型异常噪声问题,通过非线性加权机制提升滤波器的抗干扰能力。代码通过对比传统KF与MCC-KF在含异常值场景下的表现,验证了后者在状态估计鲁棒性方面的显著优…...

第7篇:中间件全链路监控与 SQL 性能分析实践

7.1 章节导读 在构建数据库中间件的过程中&#xff0c;可观测性 和 性能分析 是保障系统稳定性与可维护性的核心能力。 特别是在复杂分布式场景中&#xff0c;必须做到&#xff1a; &#x1f50d; 追踪每一条 SQL 的生命周期&#xff08;从入口到数据库执行&#xff09;&#…...