当前位置: 首页 > 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…...

观成科技:隐蔽隧道工具Ligolo-ng加密流量分析

1.工具介绍 Ligolo-ng是一款由go编写的高效隧道工具&#xff0c;该工具基于TUN接口实现其功能&#xff0c;利用反向TCP/TLS连接建立一条隐蔽的通信信道&#xff0c;支持使用Let’s Encrypt自动生成证书。Ligolo-ng的通信隐蔽性体现在其支持多种连接方式&#xff0c;适应复杂网…...

未来机器人的大脑:如何用神经网络模拟器实现更智能的决策?

编辑&#xff1a;陈萍萍的公主一点人工一点智能 未来机器人的大脑&#xff1a;如何用神经网络模拟器实现更智能的决策&#xff1f;RWM通过双自回归机制有效解决了复合误差、部分可观测性和随机动力学等关键挑战&#xff0c;在不依赖领域特定归纳偏见的条件下实现了卓越的预测准…...

变量 varablie 声明- Rust 变量 let mut 声明与 C/C++ 变量声明对比分析

一、变量声明设计&#xff1a;let 与 mut 的哲学解析 Rust 采用 let 声明变量并通过 mut 显式标记可变性&#xff0c;这种设计体现了语言的核心哲学。以下是深度解析&#xff1a; 1.1 设计理念剖析 安全优先原则&#xff1a;默认不可变强制开发者明确声明意图 let x 5; …...

Vue记事本应用实现教程

文章目录 1. 项目介绍2. 开发环境准备3. 设计应用界面4. 创建Vue实例和数据模型5. 实现记事本功能5.1 添加新记事项5.2 删除记事项5.3 清空所有记事 6. 添加样式7. 功能扩展&#xff1a;显示创建时间8. 功能扩展&#xff1a;记事项搜索9. 完整代码10. Vue知识点解析10.1 数据绑…...

MFC内存泄露

1、泄露代码示例 void X::SetApplicationBtn() {CMFCRibbonApplicationButton* pBtn GetApplicationButton();// 获取 Ribbon Bar 指针// 创建自定义按钮CCustomRibbonAppButton* pCustomButton new CCustomRibbonAppButton();pCustomButton->SetImage(IDB_BITMAP_Jdp26)…...

理解 MCP 工作流:使用 Ollama 和 LangChain 构建本地 MCP 客户端

&#x1f31f; 什么是 MCP&#xff1f; 模型控制协议 (MCP) 是一种创新的协议&#xff0c;旨在无缝连接 AI 模型与应用程序。 MCP 是一个开源协议&#xff0c;它标准化了我们的 LLM 应用程序连接所需工具和数据源并与之协作的方式。 可以把它想象成你的 AI 模型 和想要使用它…...

多模态商品数据接口:融合图像、语音与文字的下一代商品详情体验

一、多模态商品数据接口的技术架构 &#xff08;一&#xff09;多模态数据融合引擎 跨模态语义对齐 通过Transformer架构实现图像、语音、文字的语义关联。例如&#xff0c;当用户上传一张“蓝色连衣裙”的图片时&#xff0c;接口可自动提取图像中的颜色&#xff08;RGB值&…...

苍穹外卖--缓存菜品

1.问题说明 用户端小程序展示的菜品数据都是通过查询数据库获得&#xff0c;如果用户端访问量比较大&#xff0c;数据库访问压力随之增大 2.实现思路 通过Redis来缓存菜品数据&#xff0c;减少数据库查询操作。 缓存逻辑分析&#xff1a; ①每个分类下的菜品保持一份缓存数据…...

Android第十三次面试总结(四大 组件基础)

Activity生命周期和四大启动模式详解 一、Activity 生命周期 Activity 的生命周期由一系列回调方法组成&#xff0c;用于管理其创建、可见性、焦点和销毁过程。以下是核心方法及其调用时机&#xff1a; ​onCreate()​​ ​调用时机​&#xff1a;Activity 首次创建时调用。​…...

安卓基础(aar)

重新设置java21的环境&#xff0c;临时设置 $env:JAVA_HOME "D:\Android Studio\jbr" 查看当前环境变量 JAVA_HOME 的值 echo $env:JAVA_HOME 构建ARR文件 ./gradlew :private-lib:assembleRelease 目录是这样的&#xff1a; MyApp/ ├── app/ …...