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

多核多cluster多系统之间缓存一致性概述

目录

  • 1.思考和质疑
  • 2.怎样去维护多核多系统缓存的一致性
    • 2.1多核缓存一致性
    • 2.2多Master之间的缓存一致性
    • 2.3`dynamIQ`架构同一个core中的L1和L2 cache
  • 3.MESI协议的介绍
  • 4.ACE维护的缓存一致性
  • 5.软件定义的缓存和替换策略
  • 6.动图示例

本文转自 周贺贺,baron,代码改变世界ctw,Arm精选, armv8/armv9,trustzone/tee,secureboot,资深安全架构专家,11年手机安全/SOC底层安全开发经验。擅长trustzone/tee安全产品的设计和开发。文章有感而发。

在这里插入图片描述
在这里插入图片描述

1.思考和质疑

在一个大架构大系统中,有哪些一致性需要维护?我们先看如下一张架构图。
请添加图片描述
然后请思考:

  • (1)、core0中的L1和L2 cache有一致性的要求吗?缓存和替换策略是怎样的?
  • (2)、core0 cache 和 core1 cache的一致性是谁来维护? 遵从MESI协议吗?
  • (3)、core0 cache 和 core4 cache的是怎么维护一致性的呢?
  • (4)、custer0 L3 cache 和 cluster1 L3 cache的一致性是谁来维护?遵从什么协议吗?
  • (5)、custer0 L3 cache 和 GPU的L2一致性呢?遵从什么协议?
  • (6)、custer0 L3 cache 和 其它的I/O device Master一致性呢?遵从什么协议?
  • (7)、DSU、ACE、CHI、CCI、CMN的概念?

网上的好多篇博文,一提Cache的多核一致性就必然提到MESI、MOESI ,然后就开始讲MESI、MOESI维护性原理?试问一下,您是真的不理解MESI吗?您真的需要学习MESI?你不理解的是架构吧,而不是学什么协议.
既然要学习MESI,那么这里也继续提出一些问题:

  • (1)、ARM架构中真的使用MESI了吗? 或者是哪一级cache使用了,哪一级cache没有使用?
  • (2)、MESI是一个协议? 是谁来维护的?总得有个硬件实现这个协议吧,是在ARM Core实现?DSU实现?
  • (3)、MESI的四种状态,分别记录在哪里的?
  • (4)、arm现在主流的core,到底使用的是MESI,还是MOESI?

2.怎样去维护多核多系统缓存的一致性

有三种机制可以保持一致性:

  • 禁用缓存是最简单的机制,但可能会显着降低 CPU 性能。为了获得最高性能,处理器通过管道以高频率运行,并从提供极低延迟的缓存中运行。缓存多次访问的数据可显着提高性能并降低 DRAM 访问和功耗。将数据标记为“非缓存”可能会影响性能和功耗。
  • 软件管理的一致性是数据共享问题的传统解决方案。在这里,软件(通常是设备驱动程序)必须清除或刷新缓存中的脏数据,并使旧数据无效,以便与系统中的其他处理器或主设备共享。这需要处理器周期、总线带宽和功率。
  • 硬件管理的一致性提供了一种简化软件的替代方案。使用此解决方案,任何标记为“共享”的缓存数据将始终自动更新。该共享域中的所有处理器和总线主控器看到的值完全相同。

然而,我们在ARM架构中,默认使用的却是第三种 硬件管理的一致性, 意思就是:做为一名软件工程师,我们啥也不用管了,有人帮我们干活,虽然如此,但我们还是希望理解下硬件原理。

再讲原理之前,我们先补充一个场景:
假设在某一操作系统中运行了一个线程,该线程不停着操作0x4000_0000地址处内存(所以我们当然期望,它总是命中着),由于系统调度,这一次该线程可能跑在cpu0上,下一次也许就跑在cpu1上了,再下一次也许就是cpu4上了(其实这种行为也叫做CPU migration)

或者举个这样的场景也行:
在Linux Kernel系统中,定义了一个全局性的变量,然后多个内核线程(多个CPU)都会访问该变量.

在以上的场景中,都存在一块内存(如0x4000_0000地址处内存)被不同的ARM CORE来访问,这样就会出现了该数据在main-memory、cluster cache、core cache不一致的情况, 复杂点场景可能还会考虑cluster chache和other Master(如GPU) cache的一致性情况。

既然出现了数据在内存和不同的cache中的不一致的情况,那么就需要解决这个问题(也叫维护cache一致性),那么怎么维护的呢,上面也说了“使用 硬件管理的一致性”,下面就以直接写答案的方式,告诉你硬件是怎样维护一致性的。

2.1多核缓存一致性

同一个cluster中多core之间的缓存一致性由DSU(big.LITTLE叫SCU)来维护,遵循MESI协议。
请添加图片描述

2.2多Master之间的缓存一致性

在讲述多Master之间的缓存一致性之前,我们先将Master分为以下几类:

  • ACE Master : 如 big.LITTLE cluster 或 DSU cluster
  • CHI Master : 如 big.LITTLE cluster 或 DSU cluster
  • ACE-lite Master: 如 GPU cluster
  • I/O Device Master : 如 DMA
    请添加图片描述
    以下是多Master之间的缓存一致性的结论:
  • 首先,CHI/ACE总线都是支持MESI协议数据传输的
  • Master与I/O Device Master之间没有一致性,因为I/O Device没有链接到CCI/CMN缓存互联总线上。
  • 多个ACE/CHI Master之间的缓存一致性,是否遵循MESI,要具体情况具体分析,简而言之就是:
  • (1) 如果两个Master都支持带MESI状态位,支持带有MESI信号的读写,那么这两个Master缓存一致性是遵从MESI协议的
  • (2) 如果有一个Master不支持带MESI状态位,那么这个Master就无法支持带有MESI信号的读写,那么这两个Master缓存一致性是不遵从MESI协议的
  • (3) Master的MESI状态位,是在该Master的cache的TAG中。
  • ACE/CHI Master和ACE-lite Master之间的缓存一致性,是不遵从MESI协议的。这主要是因为ACE/CHI Master无法snoop ACE-lite Master的内存,而ACE-lite Master却可以snoop ACE/CHI Master的内存,总得来说,这不是一个完整的MESI协议。

举一个最常见的例子:两个DSU cluster的L3 cache中的TAG中,是有MESI比特位的,这两个DSU通过ACE/CHI 接口发起的读写是带有MESI信号的,所以他们是支持MESI协议的。
请添加图片描述
再举一个例子,一个DSU cluster 和一个接到SMMU上的DMA,此时正好对应一个是ACE/CHI Master,一个ACE-lite Master,由于DMA/SMMU中并没有MESI状态位,他们也不会发起带有MESI信号的读写,所以这两个Master之间是不支持MESI协议的。
请添加图片描述

2.3dynamIQ架构同一个core中的L1和L2 cache

dynamIQ架构core中的L1和L2 cache不存在缓存一致性的问题,但有分配和替换策略。

我们先看一下DynamIQ架构中的cache中新增的几个概念:

  • (1) Strictly inclusive: 所有存在L1 cache中的数据,必然也存在L2 cache中
  • (2) Weakly inclusive: 当miss的时候,数据会被同时缓存到L1和L2,但在之后,L2中的数据可能会被替换
  • (3) Fully exclusive: 当miss的时候,数据只会缓存到L1

其实inclusive/exclusive属性描述的正是是 L1和L2之间的替换策略,这部分是硬件定死的,软件不可更改的。

我们再以 ARMV9 cortex-A710 为例,查看其TRM手册,得知:请添加图片描述

  • L1 I-cache和L2之间是 weakly inclusive的
  • L1 D-cache和L2之间是 strictly inclusive的
    也就是说:
  • 当发生D-cache发生miss时,数据缓存到L1 D-cache的时候,也会被缓存到L2 Cache中,当L2 Cache被替换时,L1 D-cache也会跟着被替换
  • 当发生I-cache发生miss时,数据缓存到L1 I-cache的时候,也会被缓存到L2 Cache中,当L2 Cache被替换时,L1 I- cache不会被替换
    所以总结一下就是 : L1 和 L2之间的cache的替换策略,针对I-cache和D-cache可以是不同的策略,每一个core都有每一个core的做法,这部分是硬件决定的,请查阅你使用core的TRM手册。

3.MESI协议的介绍

本协议适用于:

  • big.LITTLE架构中多核缓存一致性
  • dynamIQ架构中多核缓存一致性
  • 多cluster之间缓存一致性
    请添加图片描述
    其实也适用于:
  • 不同cluster之间多核的缓存一致性
    请添加图片描述
    然后接下来,我们开始学习MESI协议,注意着仅仅是一个协议 ,它既不是软件也不是硬件,算上一个标准吧。
    首先是Modified Exclusive Shared Invalid (MESI) 协议中定义了4个状态:
MESI StateDefinition
Modified (M)这行数据有效,数据已被修改,和内存中的数据不一致,数据只存在于该高速缓存中
Exclusive (E)这行数据有效,数据和内存中数据一致,数据只存在于该高速缓存中
Shared (S)这行数据有效,数据和内存中数据一致,多个高速缓存有这行数据的副本
Invalid (I)这行数据无效

其次,在ARM的部分的core中,定义了第五种状态Shared Modified,这种称之为MOESI 协议.
我查询大量的Core的TRM手册,信息如下:

  • 使用MESI协议的core有:A710 A510 A78 A77 A76 A75 A72 A57 A55…
  • 使用MOESI协议的core有:A7 A15 A53

发现问题了没? 并不是网上主流博客所说,arm一般都用MOESI。请记住arm主流core在使用的是MESI。所以接下来,我们也不会再介绍和学习MOESI了。
然后我们通过数据流图的方式,观看下MESI这四种状态的情况:
请添加图片描述
MESI状态之间的切换:

请添加图片描述

Events:
RH = Read Hit
RMS = Read miss, shared
RME = Read miss, exclusive
WH = Write hit
WM = Write miss
SHR = Snoop hit on read
SHI = Snoop hit on invalidate
RU = LRU replacement

Bus Transactions:
Push = Write cache line back to memory
Invalidate = Broadcast invalidate
Read = Read cache line from memory

学到这里,我们对多核之间缓存一致性也有了大概的理解,我们也知道了MESI是干啥的了,那么我们继续抛几个问题:
(1)、为什么说“多核之间的缓存一致性,遵从MESI协议,是DSU/SCU来维护”的?

其实吧,这也不是我说的,这来自ARM官方文档:

对于big.LITTLE架构,SCU是这样描述的:
请添加图片描述
对于dynamIQ架构,DSU文档中这样描述的:
请添加图片描述
(2)、MESI的状态位记录在哪里的?
ARMV9 cortex-A710 为例,记录在core cache的TAG中的BIT[1:0]中,即在TAG中。
请添加图片描述
对于big.LITTLE架构SCU的L2 cache、dynamIQ架构的DSU L3 cache中的TAG中,也都是有MESI比特位的,不过这一点在arm ARMstrm文档都是找不到的,不过在一些的PPT上是可以看到的。
请添加图片描述

4.ACE维护的缓存一致性

ACE master是接到 CCI 缓存互联总线上的, 在 CCI Interconnect中,其实也是有一个Snoop Filter单元。 ACE协议和Snoop filter单元一起来完成了ACE Master之间的缓存一致性。
请添加图片描述
snoop filter的主要作用:用于记录存储在ACE中的缓存。

Snoop Filter可以在未命中的情况下响应侦听事务,并侦听适当的主控只有在命中的情况下。Snoop Filter条目通过观察来自 ACE 主节点的事务来维护以确定何时必须分配和取消分配条目。

Snoop Filter可以响应多个一致性请求,而无需向所有master广播ACE 接口。例如,如果地址不在任何缓存中,则Snoop Filter会以未命中和将请求定向到内存。如果地址在处理器缓存中,则请求被视为命中,并且指向在其缓存中包含该地址的 ACE 端口。

以下也举了一个多cluster之间缓存一致性的示例,A53 cluster读取A57 cluster缓存一致性数据。
请添加图片描述

  • (1). Cortex-A53 cluster 发出 Coherent Read Request。
  • (2). CCI-400 将请求传递Request以窥探 Cortex-A57 cluster 缓存。
  • (3). 收到请求后,Cortex-A57 cluster会检查其数据缓存的可用性并以所需信息进行响应。
  • (4). 如果请求的数据在缓存中,CCI-400 将数据从 Cortex-A57 cluster移动到 Cortex-A53 cluster,从而导致 Cortex-A53 cluster中的缓存行填充。

5.软件定义的缓存和替换策略

以上的multi cores、multi cluster、system之间的缓存策略或协议,都是由硬件决定,软件改不了。那么我们软件可以做什么呢? 其实,在软件的MMU页表的entry中的属性位中,是可以定义该页面内存的缓存策略的。
如果软件定义了内存位non-cacheable或non-shareable,那么以上的"硬件维护的一致性"将不会生效。
接下来对,软件定义的缓存策略做了一个小小的总结。
请添加图片描述

总结了一下shareable、cacheable属性对缓存策略的影响:

-Non-cacheablewrite-backcacheablewrite-through cacheable
non-shareable数据不会缓存到cache(对于观察则而言,又相当于outer-shareable)core访问该内存时,数据只缓存的到Core的 cache 中,不会缓存到其它cache中同左侧
inner-shareable数据不会缓存到cache(对于观察则而言,又相当于outer-shareable)core访问该内存时,数据只会缓存到core的cache和 cluster的 cache中,该地址的TAG也不会存到snoop filter中,即不会被其它ACE Master snoop同左侧
outer-shareable数据不会缓存到cache(对于观察则而言,又相当于outer-shareable)core访问该内存时,数据只会缓存到core的cache和 cluster的 cache中,该地址的TAG会存到snoop filter中,会被其它ACE Master snoop同左侧

6.动图示例

前置条件:
dynamIQ架构、L1 Data weakly inclusive、读写的内存配置位outer-shareable/write-back cacheable

步骤:

  • (1)、core0 读取了一行数据,数据缓存到了core0的L1 Dcache、L2 cache
  • (2)、随后core0的L2 中的数据是有可能会被替换出
  • (3)、core1 也读取了该行数据,数据缓存到了core1的L1 Dcache、L2 cache、L3 cache
  • (4)、随后core1的L2 中的数据也是有可能会被替换出
  • (5)、core4 也读取了该行数据,数据缓存到了core4的L1 Dcache、L2 cache
  • (6)、随后core4的L2 中的数据也是有可能会被替换出
  • (7)、至此,core0的L1、core1的L1、cluster0的L3、core4的L1 中都缓存了该数据。core0的L2、core1的L2、core4的L2 可能缓存了该行数据
    请添加图片描述

推荐

  • ARMv8/ARMv9架构从入门到精通 --博客专栏
  • 《Armv8/Armv9架构从入门到精通 第二期》 --大课程
  • 8天入门ARM架构 --入门课程

相关文章:

多核多cluster多系统之间缓存一致性概述

目录 1.思考和质疑2.怎样去维护多核多系统缓存的一致性2.1多核缓存一致性2.2多Master之间的缓存一致性2.3dynamIQ架构同一个core中的L1和L2 cache 3.MESI协议的介绍4.ACE维护的缓存一致性5.软件定义的缓存和替换策略6.动图示例 本文转自 周贺贺,baron,代…...

力扣爆刷第91天之hot100五连刷41-45

力扣爆刷第91天之hot100五连刷41-45 文章目录 力扣爆刷第91天之hot100五连刷41-45一、102. 二叉树的层序遍历二、108. 将有序数组转换为二叉搜索树三、98. 验证二叉搜索树四、230. 二叉搜索树中第K小的元素五、199. 二叉树的右视图 一、102. 二叉树的层序遍历 题目链接&#x…...

STM32day2

1.思维导图 个人暂时的学后感,不一定对,没什么东西,为做项目奔波中。。。1.使用ADC采样光敏电阻数值,如何根据这个数值调节LED灯亮度。 while (1){/* USER CODE END WHILE *//* USER CODE BEGIN 3 */adc_val HAL_ADC_GetValue(&a…...

查询IP地址保障电商平台安全

随着电子商务的快速发展,网购已经成为人们日常生活中不可或缺的一部分。然而,网络交易安全一直是人们关注的焦点之一,尤其是在面对日益频发的网络诈骗和欺诈行为时。为了提高网购平台交易的安全性,一种有效的方法是通过查询IP地址…...

使用pytorch实现线性回归(很基础模型搭建详解)

使用pytorch实现线性回归 步骤: 1.prepare dataset 2.design model using Class 目的是为了前向传播forward,即计算y hat(预测值) 3.Construct loss and optimizer (using pytorch API) 其中计算loss是为了进行反向传播&#xff0…...

【力扣100】【好题】322.零钱兑换 || 01背包完全背包

添加链接描述 思路: dp[j]数组表示的是在金额达到 j 的时候所需要的最小硬币数金额:背包容量,每个硬币的个数都为1:背包中物品的价值,硬币面额:物品重量dp[j]min(dp[j],dp[j-coin]1) class Solution:def …...

工单管理系统建设方案

1.1 系统概述 1.1.1 需求描述 1.1.2 需求分析 1.1.3 重难点分析 1.1.4 重难点解决措施 1.2 系统架构设计 1.2.1 系统架构图 1.2.2 关键技术 1.3 系统功能设计 1.3.1 工单创建 1.3.2 工单管理 1.3.3 工单处理 1.3.4 工单催办 1.3.5 工单归档 1.3.6 工单统计 软件项目全套资料获取…...

什么是农业四情监测设备?

【TH-Q2】智慧农业四情监测设备是一种高科技的农田监测工具,旨在实时监测和管理农田中的土壤墒情、作物生长、病虫害以及气象条件。具体来说,它主要包括以下组成部分: 气象站:用于监测气温、湿度、风速等气象数据,为农…...

Java面试题:请解释Java并发工具包中的主要组件及其应用场景,请描述一个使用Java并发框架(如Fork/Join框架)解决实际问题的编程实操问题

文章标题:《Java内存模型深入解析与多线程并发工具类应用》 引言: 在Java的世界里,掌握内存模型和多线程并发是高级开发者的必备技能。Java内存模型(JMM)和多线程并发工具包为开发者提供了强大的能力,同时…...

boot应用打包

1.创建项目 2.编写 3.native构建 报错: [WARNING] native:build goal is deprecated. Use native:compile-no-fork instead. [INFO] Found GraalVM installation from GRAALVM_HOME variable. [INFO] Executing: S:\Coding\graalvm-jdk-17_windows-x64_bin\graalv…...

探索数据可视化:Matplotlib 多图布局

多图布局 子视图 import numpy as np import matplotlib.pyplot as pltx np.linspace(0,2*np.pi)plt.figure(figsize(9,6))# 创建子视图 # subplot(2,1,1)表示将当前图形分割成 2 行 1 列的子图网格,并在第 1 个子图位置绘制图形 ax plt.subplot(2,1,1) ax.plot…...

springboot262基于spring boot的小型诊疗预约平台的设计与开发

小型诊疗预约平台 摘 要 现代经济快节奏发展以及不断完善升级的信息化技术,让传统数据信息的管理升级为软件存储,归纳,集中处理数据信息的管理方式。本小型诊疗预约平台就是在这样的大环境下诞生,其可以帮助管理者在短时间内处理…...

Java项目修改源码jar文件(无需反编译)

文章目录 应用场景实现方案实现原理注意事项 应用场景 在项目中用了第三方的jar包,但是jar包内某个类不符合项目业务需求,需要修改第三方jar包源码文件内容。 实现方案 首先我们尝试直接修改jar包源码文件内容时,页面上会提示文件是只读的&a…...

java使用BatchPoints批量写入Influxdb

前言 使用时序数据库influxdb时,我们经常需要写入大量的数据。而单单使用influxDB.write(Point)进行单条写入时,速度过慢,无法支撑时序数据大量写入的速度。 所以我们需要采用批量的方式进行存储,增加写入…...

Java 集合类的高级特性介绍

在 Java 编程中,了解集合类的高级特性对于编写高效和可维护的代码至关重要。以下是一些你应该知道的 Java 集合类的高级特性,以及简单的例子来说明它们的用法。 1. 迭代器(Iterators)和列表迭代器(ListIterators&#…...

使用Docker搭建Caddy

使用Docker搭建Caddy,可以快速部署一个轻量级的、支持自动HTTPS的web服务器。下面将分别介绍使用Docker CLI和Docker Compose两种方式来搭建Caddy服务器,并给出配置文件示例以及参数解释。 使用Docker CLI搭建Caddy 首先,确保你的系统上已安…...

synchronized是重量级锁???

synchronized作为Java程序员最常用同步工具,很多人却对它的用法和实现原理一知半解,以至于还有不少人认为synchronized是重量级锁,性能较差,尽量少用。 但不可否认的是synchronized依然是并发首选工具,连volatile、CA…...

Linux之线程控制

目录 一、POSIX线程库 二、线程的创建 三、线程等待 四、线程终止 五、分离线程 六、线程ID:pthread_t 1、获取线程ID 2、pthread_t 七、线程局部存储:__thread 一、POSIX线程库 由于Linux下的线程并没有独立特有的结构,所以Linux并…...

Python实现线性查找算法

Python实现线性查找算法 以下是使用 Python 实现线性查找算法的示例代码: def linear_search(arr, target):"""线性查找算法:param arr: 要搜索的数组:param target: 目标值:return: 如果找到目标值,返回其索引;否则返回 -1…...

总结Redis的原理

一、为什么要使用Redis 缓解数据库访问压力mysql读请求进行磁盘I/O速度慢,给数据库加Redis缓存(参考CPU缓存),将数据缓存在内存中,省略了I/O操作 二、Redis数据管理 2.1 redis数据的删除 定时删除惰性删除内存淘汰…...

AI Agent与Agentic AI:原理、应用、挑战与未来展望

文章目录 一、引言二、AI Agent与Agentic AI的兴起2.1 技术契机与生态成熟2.2 Agent的定义与特征2.3 Agent的发展历程 三、AI Agent的核心技术栈解密3.1 感知模块代码示例:使用Python和OpenCV进行图像识别 3.2 认知与决策模块代码示例:使用OpenAI GPT-3进…...

mongodb源码分析session执行handleRequest命令find过程

mongo/transport/service_state_machine.cpp已经分析startSession创建ASIOSession过程,并且验证connection是否超过限制ASIOSession和connection是循环接受客户端命令,把数据流转换成Message,状态转变流程是:State::Created 》 St…...

PPT|230页| 制造集团企业供应链端到端的数字化解决方案:从需求到结算的全链路业务闭环构建

制造业采购供应链管理是企业运营的核心环节,供应链协同管理在供应链上下游企业之间建立紧密的合作关系,通过信息共享、资源整合、业务协同等方式,实现供应链的全面管理和优化,提高供应链的效率和透明度,降低供应链的成…...

【位运算】消失的两个数字(hard)

消失的两个数字(hard) 题⽬描述:解法(位运算):Java 算法代码:更简便代码 题⽬链接:⾯试题 17.19. 消失的两个数字 题⽬描述: 给定⼀个数组,包含从 1 到 N 所有…...

【快手拥抱开源】通过快手团队开源的 KwaiCoder-AutoThink-preview 解锁大语言模型的潜力

引言: 在人工智能快速发展的浪潮中,快手Kwaipilot团队推出的 KwaiCoder-AutoThink-preview 具有里程碑意义——这是首个公开的AutoThink大语言模型(LLM)。该模型代表着该领域的重大突破,通过独特方式融合思考与非思考…...

linux 错误码总结

1,错误码的概念与作用 在Linux系统中,错误码是系统调用或库函数在执行失败时返回的特定数值,用于指示具体的错误类型。这些错误码通过全局变量errno来存储和传递,errno由操作系统维护,保存最近一次发生的错误信息。值得注意的是,errno的值在每次系统调用或函数调用失败时…...

CMake控制VS2022项目文件分组

我们可以通过 CMake 控制源文件的组织结构,使它们在 VS 解决方案资源管理器中以“组”(Filter)的形式进行分类展示。 🎯 目标 通过 CMake 脚本将 .cpp、.h 等源文件分组显示在 Visual Studio 2022 的解决方案资源管理器中。 ✅ 支持的方法汇总(共4种) 方法描述是否推荐…...

return this;返回的是谁

一个审批系统的示例来演示责任链模式的实现。假设公司需要处理不同金额的采购申请,不同级别的经理有不同的审批权限: // 抽象处理者:审批者 abstract class Approver {protected Approver successor; // 下一个处理者// 设置下一个处理者pub…...

A2A JS SDK 完整教程:快速入门指南

目录 什么是 A2A JS SDK?A2A JS 安装与设置A2A JS 核心概念创建你的第一个 A2A JS 代理A2A JS 服务端开发A2A JS 客户端使用A2A JS 高级特性A2A JS 最佳实践A2A JS 故障排除 什么是 A2A JS SDK? A2A JS SDK 是一个专为 JavaScript/TypeScript 开发者设计的强大库&#xff…...

排序算法总结(C++)

目录 一、稳定性二、排序算法选择、冒泡、插入排序归并排序随机快速排序堆排序基数排序计数排序 三、总结 一、稳定性 排序算法的稳定性是指:同样大小的样本 **(同样大小的数据)**在排序之后不会改变原始的相对次序。 稳定性对基础类型对象…...