数据排序方法、装置、电子设备及存储介质

摘要

本申请实施例涉及一种数据排序方法、装置、电子设备及存储介质，方法包括：由待排序标识集得到T个子标识集并启动与其对应的T个线程；根据子标识集中标识分布特征将各个子标识集划分为N个区间，将待排序标识集对应的待排序数据集存储到本地非一致内存访问节点；将各个子标识集中标识分布特征相同的区间进行组合，得到N个目标子标识集，针对任一线程启动C个协程交错执行；针对任一协程，确定协程对应的目标子标识集，采用单指令多数据流向量化方式对目标子标识集循环筛选出最小或最大标识，并从本地非一致内存访问节点中获取其对应的数据，以组成N个有序目标子数据集，合并得到有序数据集。可同时解决待排序数据排序过程中遇到的多个瓶颈。

权利要求

1.一种数据排序方法，其特征在于，所述方法包括：

对待排序标识集进行切分，得到T个子标识集，并启动T个线程，所述线程与所述子标识集一一对应；

针对任一所述子标识集，根据所述子标识集中标识分布特征对所述子标识集进行划分，得到N个区间，将所述待排序标识集对应的待排序数据集存储到本地非一致内存访问节点；

针对任一所述线程，对所述线程对应的所述子标识集进行排序，以得到T个有序子标识集；

统计T个所述有序子标识集的标识分布特征，根据T个所述有序子标识集的标识分布特征，确定N个区间范围；

针对任一所述有序子标识集，根据N个所述区间范围对所述有序子标识集进行划分，得到N个区间；

对所述N个区间进行切分，得到M个区间集；

将各个有序子标识集中区间范围相同的区间集进行组合，得到M个所述区间范围相同的区间集的第一集合，将任一所述第一集合对应的数据存储到一个本地非一致内存访问节点；

将各个所述子标识集中标识分布特征相同的区间进行组合，得到N个目标子标识集，针对任一所述线程启动C个协程，其中，所述C个协程交错执行；

针对任一协程，确定所述协程对应的目标子标识集，采用单指令多数据流向量化方式对目标子标识集循环筛选出最小或最大标识，以获取本地非一致内存访问节点中所述最小或最大标识对应的数据，组成有序目标子数据集，以得到N个有序目标子数据集；

将所述N个有序目标子数据集进行合并，得到所述待排序标识集对应的待排序数据的有序数据集。

2.根据权利要求1所述的方法，其特征在于，所述对所述N个区间进行切分，得到M个区间集，包括：确定一个本地非一致内存访问节点的存储空间，根据所述存储空间对所述N个区间进行切分，得到M个区间集。

3.根据权利要求1所述的方法，其特征在于，所述N个目标子标识集包括：N个标识数量分布均匀的目标子标识集。

4.根据权利要求1所述的方法，其特征在于，所述针对任一协程，确定所述协程对应的目标子标识集，采用单指令多数据流向量化方式对目标子标识集循环筛选出最小或最大标识，以获取本地非一致内存访问节点中所述最小或最大标识对应的数据，组成有序目标子数据集，包括：针对任一协程，确定所述协程对应的目标子标识集，采用单指令多数据流向量化方式对目标子标识集循环筛选出最小或最大标识；

根据所述最小或最大标识执行数据预取指令，并暂停所述协程；

当所述数据预取指令将所述最小或最大标识对应的数据预取成功时，重新执行所述协程；

从所述本地非一致内存访问节点中获取所述数据预取指令预取到的所述最小或最大标识对应的数据，组成有序目标子数据集。

5.根据权利要求4所述的方法，其特征在于，所述根据所述最小或最大标识执行数据预取指令，并暂停所述协程之后，还包括：按照预设的优先级通知所述协程对应的线程中启动的第一协程，以使所述第一协程执行所述确定所述协程对应的目标子标识集，采用单指令多数据流向量化方式对目标子标识集循环筛选出最小或最大标识，以获取本地非一致内存访问节点中所述最小或最大标识对应的数据，组成有序目标子数据集的步骤。

6.根据权利要求1所述的方法，其特征在于，所述确定所述协程对应的目标子标识集，采用单指令多数据流向量化方式对目标子标识集循环筛选出最小或最大标识，以获取本地非一致内存访问节点中所述最小或最大标识对应的数据，组成有序目标子数据集，包括：确定所述协程对应的目标子标识集，确定所述目标子标识集中的T个区间，确定所述单指令多数据流向量化方式对应的一个指令能够同时处理的数据的第一数量；

生成一棵叶子结点数量为T的二叉树，其中，所述目标子标识集中的T个区间与T个叶子结点一一对应，所述二叉树的各个节点中可存放的标识数量为所述第一数量；

迭代执行以下步骤，直至得到所述目标子标识集对应的有序目标子数据集：确定当前迭代过程中参与归并的叶子结点，从所述参与归并的叶子结点对应的区间中获取第二数量的最小或最大标识；

从所述参与归并的叶子结点开始，按照从左到右或从右到左的顺序两两归并，直至得到当前迭代过程中的第一数量的最小或最大的有序标识；

根据所述第一数量的最小或最大的有序标识执行数据预取指令，并暂停所述协程；

当所述数据预取指令将所述第一数量的最小或最大的有序标识对应的数据预取成功时，重新执行所述协程；

从所述本地非一致内存访问节点中获取所述数据预取指令预取到的第一数量的最小或最大的有序标识对应的数据，以组成有序目标子数据集；

根据所述第一数量的最小或最大的有序标识确定下一次迭代过程中参与归并的叶子结点以及所述下一次迭代过程中参与归并的叶子结点所要获取的标识的第二数量。

7.根据权利要求6所述的方法，其特征在于，所述确定当前迭代过程中参与归并的叶子结点，从所述参与归并的叶子结点对应的区间中获取第二数量的最小或最大标识，包括：判断当前迭代过程是否为首次迭代过程；

若当前迭代过程为首次迭代过程，确定参与归并的叶子结点为T个所述叶子结点，从T个所述叶子结点对应的区间中获取所述第一数量的最小或最大标识；

若当前迭代过程非首次迭代过程，确定当前迭代过程中参与归并的叶子结点，从所述参与归并的叶子结点对应的区间中获取第二数量的最小或最大标识。

8.根据权利要求6所述的方法，其特征在于，所述根据所述第一数量的最小或最大的有序标识确定下一次迭代过程中参与归并的叶子结点以及所述下一次迭代过程中参与归并的叶子结点所要获取的标识的第二数量，包括：确定所述第一数量的最小或最大的有序标识对应的叶子结点为下一次迭代过程中参与归并的叶子结点；

针对任一下一次迭代过程中参与归并的叶子结点，从所述第一数量的最小或最大的有序标识中查找来自所述下一次迭代过程中参与归并的叶子结点的部分有序标识，并统计所述部分有序标识的数量；

确定所述部分有序标识的数量为所述下一次迭代过程中参与归并的叶子结点所要获取的标识的第二数量。

9.一种数据排序装置，其特征在于，所述装置包括：

子标识集切分模块，用于对待排序标识集进行切分，得到T个子标识集，并启动T个线程，所述线程与所述子标识集一一对应；

存储模块，用于针对任一所述子标识集，根据所述子标识集中标识分布特征对所述子标识集进行划分，得到N个区间，将所述待排序标识集对应的待排序数据集存储到本地非一致内存访问节点；

所述存储模块，还用于针对任一所述线程，对所述线程对应的所述子标识集进行排序，以得到T个有序子标识集；

所述存储模块，还用于统计T个所述有序子标识集的标识分布特征，根据T个所述有序子标识集的标识分布特征，确定N个区间范围；

所述存储模块，还用于针对任一所述有序子标识集，根据N个所述区间范围对所述有序子标识集进行划分，得到N个区间；

所述存储模块，还用于对所述N个区间进行切分，得到M个区间集；

所述存储模块，还用于将各个有序子标识集中区间范围相同的区间集进行组合，得到M个所述区间范围相同的区间集的第一集合，将任一所述第一集合对应的数据存储到一个本地非一致内存访问节点；

协程启动模块，用于将各个所述子标识集中标识分布特征相同的区间进行组合，得到N个目标子标识集，针对任一所述线程启动C个协程，其中，所述C个协程交错执行；

有序目标子数据集组成模块，用于针对任一协程，确定所述协程对应的目标子标识集，采用单指令多数据流向量化方式对目标子标识集循环筛选出最小或最大标识，以获取本地非一致内存访问节点中所述最小或最大标识对应的数据，组成有序目标子数据集，以得到N个有序目标子数据集；

有序数据集获取模块，用于将所述N个有序目标子数据集进行合并，得到所述待排序标识集对应的待排序数据的有序数据集。

10.一种电子设备，其特征在于，包括：处理器和存储器，所述处理器用于执行所述存储器中存储的数据排序程序，以实现权利要求1 8中任一项所述的数据排序方法。

~

11.一种存储介质，其特征在于，所述存储介质存储有一个或者多个程序，所述一个或者多个程序可被一个或者多个处理器执行，以实现权利要求1 8中任一项所述的数据排序~方法。

说明书

数据排序方法、装置、电子设备及存储介质

技术领域

[0001] 本申请实施例涉及计算机技术领域，尤其涉及一种数据排序方法、装置、电子设备及存储介质。

背景技术

[0002] 现代硬件的发展为内存数据库执行数据带来新的挑战，多核或者众核机器大大提升了计算速度，NUMA（Non Uniform Memory Access，非一致内存访问）架构使得单机算力能够水平扩展，同时访问内存的延迟和计算延迟的差距越来越大，并且单机不同非一致内存访问节点内存的访问速度也不对称。而数据库的执行性能并不能完全受益于当代计算机架构中的强大算力，因为数据库中的算子并没有复杂计算，更多是移动数据，反而使得内存访问的瓶颈越明显。

[0003] 内存访问的瓶颈主要体现在两个方面：首先是跨非一致内存访问节点的内存访问比访问本地非一致内存访问节点慢2倍左右，频繁的跨非一致内存访问节点内存访问会降低CPU（central processing unit，中央处理器）处理效率。此外，本地非一致内存访问节点内存访问面临cache misses瓶颈，即CPU所要访问的数据在高速缓存中查询不到，需要频繁访问内存。而访问内存的代价比CPU计算的代价高出两个数量级。类似于木桶原理，当把内存访问的瓶颈消除后，branch misses（预测错误的分支指令数）又会相继成为明显瓶颈。

[0004] 具体对于排序算子来说，在排序过程中需要拿到所有数据后才能进行排序，首先对所有数据的键值进行排序，然后根据键值的顺序调整所有数据的顺序。具体的，在调整数据过程中，根据键值顺序获取数据时，将整条数据复制到新的顺序对应的位置，在复制数据过程存在大量的随机访问，带来大量的cache misses和跨非一致内存访问节点访问数据，产生了较大的延迟，且在执行排序过程中，CPU采用分支预测执行，一旦分支预测失败，大量的指令需要重新执行，从而带来branch misses的开销。

发明内容

[0005] 鉴于此，为解决上述在调整数据过程中，根据键值顺序获取数据时，将整条数据复制到新的顺序的位置，在复制数据过程存在大量的随机访问，带来大量的cache misses和跨非一致内存访问节点访问的延迟，且在执行排序过程中，CPU采用分支预测执行，一旦分支预测失败，大量的指令需要重新执行，从而带来branch misses的技术问题，本申请实施例提供一种数据排序方法、装置、电子设备及存储介质。

[0006] 第一方面，本申请实施例提供一种数据排序方法，所述方法包括：

[0007] 对待排序标识集进行切分，得到T个子标识集，并启动T个线程，所述线程与所述子标识集一一对应；

[0008] 针对任一所述子标识集，根据所述子标识集中标识分布特征对所述子标识集进行划分，得到N个区间，将所述待排序标识集对应的待排序数据集存储到本地非一致内存访问节点；

[0009] 将各个所述子标识集中标识分布特征相同的区间进行组合，得到N个目标子标识集，针对任一所述线程启动C个协程，其中，所述C个协程交错执行；

[0010] 针对任一协程，确定所述协程对应的目标子标识集，采用单指令多数据流向量化方式对目标子标识集循环筛选出最小或最大标识，以获取本地非一致内存访问节点中所述最小或最大标识对应的数据，组成有序目标子数据集，以得到N个有序目标子数据集；

[0011] 将所述N个有序目标子数据集进行合并，得到所述待排序标识集对应的待排序数据的有序数据集。

[0012] 在一个可选的实施方式中，所述针对任一所述子标识集，根据所述子标识集中标识分布特征对所述子标识集进行划分，得到N个区间，将所述待排序标识集对应的待排序数据集存储到本地非一致内存访问节点，包括：

[0013] 针对任一所述线程，对所述线程对应的所述子标识集进行排序，以得到T个有序子标识集；

[0014] 统计T个所述有序子标识集的标识分布特征，根据T个所述有序子标识集的标识分布特征，确定N个区间范围；

[0015] 针对任一所述有序子标识集，根据N个所述区间范围对所述有序子标识集进行划分，得到N个区间；

[0016] 对所述N个区间进行切分，得到M个区间集；

[0017] 将各个有序子标识集中区间范围相同的区间集进行组合，得到M个所述区间范围相同的区间集的第一集合，将任一所述第一集合对应的数据存储到一个本地非一致内存访问节点。

[0018] 在一个可选的实施方式中，所述对所述N个区间进行切分，得到M个区间集，包括：

[0019] 确定一个本地非一致内存访问节点的存储空间，根据所述存储空间对所述N个区间进行切分，得到M个区间集。

[0020] 在一个可选的实施方式中，所述N个目标子标识集包括：N个标识数量分布均匀的目标子标识集。

[0021] 在一个可选的实施方式中，所述针对任一协程，确定所述协程对应的目标子标识集，采用单指令多数据流向量化方式对目标子标识集循环筛选出最小或最大标识，以获取本地非一致内存访问节点中所述最小或最大标识对应的数据，组成有序目标子数据集，包括：

[0022] 针对任一协程，确定所述协程对应的目标子标识集，采用单指令多数据流向量化方式对目标子标识集循环筛选出最小或最大标识；

[0023] 根据所述最小或最大标识执行数据预取指令，并暂停所述协程；

[0024] 当所述数据预取指令将所述最小或最大标识对应的数据预取成功时，重新执行所述协程；

[0025] 从所述本地非一致内存访问节点中获取所述数据预取指令预取到的所述最小或最大标识对应的数据，组成有序目标子数据集。

[0026] 在一个可选的实施方式中，所述根据所述最小或最大标识执行数据预取指令，并暂停所述协程之后，还包括：

[0027] 按照预设的优先级通知所述协程对应的线程中启动的第一协程，以使所述第一协程执行所述确定所述协程对应的目标子标识集，采用单指令多数据流向量化方式对目标子标识集循环筛选出最小或最大标识，以获取本地非一致内存访问节点中所述最小或最大标识对应的数据，组成有序目标子数据集的步骤。

[0028] 在一个可选的实施方式中，所述确定所述协程对应的目标子标识集，采用单指令多数据流向量化方式对目标子标识集循环筛选出最小或最大标识，以获取本地非一致内存访问节点中所述最小或最大标识对应的数据，组成有序目标子数据集，包括：

[0029] 确定所述协程对应的目标子标识集，确定所述目标子标识集中的T个区间，确定所述单指令多数据流向量化方式对应的一个指令能够同时处理的数据的第一数量；

[0030] 生成一棵叶子结点数量为T的二叉树，其中，所述目标子标识集中的T个区间与T个叶子结点一一对应，所述二叉树的各个节点中可存放的标识数量为所述第一数量；

[0031] 迭代执行以下步骤，直至得到所述目标子标识集对应的有序目标子数据集：

[0032] 确定当前迭代过程中参与归并的叶子结点，从所述参与归并的叶子结点对应的区间中获取第二数量的最小或最大标识；

[0033] 从所述参与归并的叶子结点开始，按照从左到右或从右到左的顺序两两归并，直至得到当前迭代过程中的第一数量的最小或最大的有序标识；

[0034] 根据所述第一数量的最小或最大的有序标识执行数据预取指令，并暂停所述协程；

[0035] 当所述数据预取指令将所述第一数量的最小或最大的有序标识对应的数据预取成功时，重新执行所述协程；

[0036] 从所述本地非一致内存访问节点中获取所述数据预取指令预取到的第一数量的最小或最大的有序标识对应的数据，以组成有序目标子数据集；

[0037] 根据所述第一数量的最小或最大的有序标识确定下一次迭代过程中参与归并的叶子结点以及所述下一次迭代过程中参与归并的叶子结点所要获取的标识的第二数量。

[0038] 在一个可选的实施方式中，所述确定当前迭代过程中参与归并的叶子结点，从所述参与归并的叶子结点对应的区间中获取第二数量的最小或最大标识，包括：

[0039] 判断当前迭代过程是否为首次迭代过程；

[0040] 若当前迭代过程为首次迭代过程，确定参与归并的叶子结点为T个所述叶子结点，从T个所述叶子结点对应的区间中获取所述第一数量的最小或最大标识；

[0041] 若当前迭代过程非首次迭代过程，确定当前迭代过程中参与归并的叶子结点，从所述参与归并的叶子结点对应的区间中获取第二数量的最小或最大标识。

[0042] 在一个可选的实施方式中，所述根据所述第一数量的最小或最大的有序标识确定下一次迭代过程中参与归并的叶子结点以及所述下一次迭代过程中参与归并的叶子结点所要获取的标识的第二数量，包括：

[0043] 确定所述第一数量的最小或最大的有序标识对应的叶子结点为下一次迭代过程中参与归并的叶子结点；

[0044] 针对任一下一次迭代过程中参与归并的叶子结点，从所述第一数量的最小或最大的有序标识中查找来自所述下一次迭代过程中参与归并的叶子结点的部分有序标识，并统计所述部分有序标识的数量；

[0045] 确定所述部分有序标识的数量为所述下一次迭代过程中参与归并的叶子结点所要获取的标识的第二数量。

[0046] 第二方面，本申请实施例提供一种数据排序装置，所述装置包括：

[0047] 子标识集切分模块，用于对待排序标识集进行切分，得到T个子标识集，并启动T个线程，所述线程与所述子标识集一一对应；

[0048] 存储模块，用于针对任一所述子标识集，根据所述子标识集中标识分布特征对所述子标识集进行划分，得到N个区间，将所述待排序标识集对应的待排序数据集存储到本地非一致内存访问节点；

[0049] 协程启动模块，用于将各个所述子标识集中标识分布特征相同的区间进行组合，得到N个目标子标识集，针对任一所述线程启动C个协程，其中，所述C个协程交错执行；

[0050] 有序目标子数据集组成模块，用于针对任一协程，确定所述协程对应的目标子标识集，采用单指令多数据流向量化方式对目标子标识集循环筛选出最小或最大标识，以获取本地非一致内存访问节点中所述最小或最大标识对应的数据，组成有序目标子数据集，以得到N个有序目标子数据集；

[0051] 有序数据集获取模块，用于将所述N个有序目标子数据集进行合并，得到所述待排序标识集对应的待排序数据的有序数据集。

[0052] 第三方面，本申请实施例提供一种电子设备，包括：处理器和存储器，所述处理器用于执行所述存储器中存储的数据排序程序，以实现第一方面中任一项所述的数据排序方法。

[0053] 第四方面，本申请实施例提供一种存储介质，所述存储介质存储有一个或者多个程序，所述一个或者多个程序可被一个或者多个处理器执行，以实现第一方面中任一项所述的数据排序方法。

[0054] 本申请实施例提供的技术方案，对待排序标识集进行切分，得到T个子标识集，并启动T个线程，所述线程与所述子标识集一一对应；针对任一所述子标识集，根据所述子标识集中标识分布特征对所述子标识集进行划分，得到N个区间，将所述待排序标识集对应的待排序数据集存储到本地非一致内存访问节点；将各个所述子标识集中标识分布特征相同的区间进行组合，得到N个目标子标识集，针对任一所述线程启动C个协程，其中，所述C个协程交错执行；针对任一协程，确定所述协程对应的目标子标识集，采用单指令多数据流向量化方式对目标子标识集循环筛选出最小或最大标识，以获取本地非一致内存访问节点中所述最小或最大标识对应的数据，组成有序目标子数据集，以得到N个有序目标子数据集；将所述N个有序目标子数据集进行合并，得到所述待排序标识集对应的待排序数据的有序数据集。通过将待排序标识集对应的待排序数据集存储到本地非一致内存访问节点，减少了获取数据时跨非一致内存访问节点访问的开销，通过在线程中启动C个协程，使C个协程交错执行的方式来掩盖cache misses，通过采用单指令多数据流向量化方式，减少了branch misses，本申请的技术方案同时解决了三个瓶颈。

附图说明

[0055] 图1为本申请实施例提供的一种数据排序方法的实施流程示意图；

[0056] 图2为本申请实施例提供的一种数据存储方法的实施流程示意图；

[0057] 图3为本申请实施例提供的另一种数据存储方法的实施流程示意图；

[0058] 图4为本申请实施例提供的另一种数据排序方法的实施流程示意图；

[0059] 图5为本申请实施例提供的又一种数据排序方法的实施流程示意图；

[0060] 图6为本申请实施例提供的一种有序目标子数据集组成方法的实施流程示意图；

[0061] 图7为本申请实施例提供的一种迭代次数判断方法的实施流程示意图；

[0062] 图8为本申请实施例提供的一种参与归并的叶子结点及第二数量确定方法的实施流程示意图；

[0063] 图9为本申请实施例提供的一种协程排序方法的实施流程示意图

[0064] 图10为本申请实施例提供的一种数据排序装置的结构示意图；

[0065] 图11为本申请实施例提供的一种电子设备的结构示意图。

具体实施方式

[0066] 为使本申请实施例的目的、技术方案和优点更加清楚，下面将结合本申请实施例中的附图，对本申请实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例是本申请一部分实施例，而不是全部的实施例。基于本申请中的实施例，本领域普通技术人员在没有做出创造性劳动的前提下所获得的所有其他实施例，都属于本申请保护的范围。

[0067] 排序算子是一个阻塞型操作，需要拿到所有数据之后才能排序，一般是对待排序数据集的键值进行排序，然后根据键值的顺序将整条数据复制到新的顺序的位置。

[0068] 图1为本申请实施例提供的一种数据排序方法的实施流程示意图，该方法可包括以下步骤：

[0069] S101：对待排序标识集进行切分，得到T个子标识集，并启动T个线程，线程与子标识集一一对应。

[0070] 在本申请实施例中，待排序标识集即为待排序数据集对应的待排序标识集，例如，一个班的学生初始是按照学生的学号进行排序的，要按成绩重新排序，则待排序数据集为学生的全部信息，待排序标识集为学生的成绩，由于要对学生的全部信息按照成绩进行排序，因此只需对学生的成绩进行排序，然后将学生其他信息复制到排好顺序的成绩对应的顺序。

[0071] 在本申请实施例中，对待排序标识集进行切分，得到T个子标识集，并启动T个线程，线程与子标识集一一对应，每个线程处理一个子标识集。例如，待排序标识集中标识数量为40000，T=4，即将待排序标识集切分为四份，得到4个子标识集，每个子标识集有10000个标识，启动4个线程，每个线程处理一个子标识集。

[0072] S102：针对任一子标识集，根据子标识集中标识分布特征对子标识集进行划分，得到N个区间，将待排序标识集对应的待排序数据集存储到本地非一致内存访问节点。

[0073] 在本申请实施例中，针对任一子标识集，根据子标识集中标识分布特征对子标识集进行划分，得到N个区间，例如，子标识集为学生成绩时，假设总成绩为120，根据成绩分布特征将每个子标识集中的成绩均按照[0，15)、[15，30)、[30，45)、[45，60)、[60，75)、[75，90)、[90，105)、[105，120]进行划分，得到8个区间。

[0074] 在本申请实施例中，将待排序标识集对应的待排序数据集存储到本地非一致内存访问节点，具体的，根据待排序标识集对应的待排序数据集中各个数据的存储地址，将数据复制到本地非一致内存访问节点。

[0075] S103：将各个子标识集中标识分布特征相同的区间进行组合，得到N个目标子标识集，针对任一线程启动C个协程，其中，C个协程交错执行。

[0076] 在本申请实施例中，将各个子标识集中标识分布特征相同的区间进行组合，得到N个区间。例如，上述假设子标识集为成绩时，将各个子标识集按照成绩分布划分为8个区间，将各个子标识集中成绩分布为[0，15)的区间进行组合，得到成绩分布为[0，15)的目标子标识集，同理，对其他成绩分布相同的区间进行组合，得到8个目标子标识集。

[0077] 在本申请实施例中，将各个子标识集中标识分布特征相同的区间进行组合，得到N个目标子标识集后，在线程启动协程对目标子标识集进行排序，需要说明的是，此时线程与子标识集不再一一对应。T个线程共启动N个协程对N个目标子标识集进行排序，每个线程中启动C个协程，其中， ，在每个线程中，协程交错执行，以减少线程的空闲时间。

[0078] S104：针对任一协程，确定协程对应的目标子标识集，采用单指令多数据流向量化方式对目标子标识集循环筛选出最小或最大标识，以获取本地非一致内存访问节点中最小或最大标识对应的数据，组成有序目标子数据集，以得到N个有序目标子数据集。

[0079] 在本申请实施例中，协程对目标子标识集进行排序时，首先确定该协程对应的目标子标识集。例如，当目标子标识集为成绩时，要将成绩从大到小排序，采用单指令多数据流向量化方式对目标子标识集一次选出一条指令能够同时处理的数量的最大的成绩，且该数量的最大成绩是由大到小排序的，将该数量的成绩对应的学生的其他信息从本地非一致内存访问节点复制到该成绩对应的位置，循环选出该数量的最大成绩，并从本地非一致内存访问节点获取该数量的最大成绩对应的学生的其他信息，直至将目标子标识集中的全部标识排序结束，将每次从非一致内存访问节点中获取的数据组合，得到有序目标子数据集。

[0080] S105：将N个有序目标子数据集进行合并，得到待排序标识集对应的待排序数据的有序数据集。

[0081] 在本申请实施例中，将N个有序目标子数据集按照标识分布特征进行合并，例如，目标子标识集中的标识为成绩，成绩分布如上述区间，每个有序目标子数据集都对应了一个区间，当按照成绩由大到小进行排序时，区间[105，120]、[90，105)、[75，90)、[60，75)、[45，60)、[30，45)、[15，30)、[0，15)依次进行合并，即得到成绩由大到小的有序数据集。

[0082] 通过上述对本申请实施例提供的技术方案的描述，本申请中将待排序标识集对应的数据复制到本地非一致内存访问节点，将数据集中存储，减少了获取数据时的跨节点访问。本申请还将待排序标识集划分为N个目标子标识集，启动T个线程并行执行，对N个目标子标识集进行排序，一个线程中启动C个协程，使N个目标子标识集各自对应一个协程，线程中的C个协程交错执行，以减少线程的空闲时间，掩盖了cache misses，同时在协程对其对应的目标子标识集进行排序时，采用单指令多数据流向量化方式，一条指令同时处理多条数据，以减少branch misses。通过本申请的技术方案，可以同时有效解决上述三个瓶颈。

[0083] 基于S102的描述，图2为本申请实施例提供的一种数据存储方法的实施流程示意图，该方法可包括以下步骤：

[0084] S201：针对任一线程，对线程对应的子标识集进行排序，以得到T个有序子标识集。

[0085] 在本申请实施例中，对待排序标识集进行切分得到T个子标识集后，启动T个线程，每个线程对一个子标识集进行处理。针对任一线程，对线程对应的子标识集进行排序，以得到T个有序子标识集。例如，待排序标识集中的标识为40000个，将待排序标识集切分为4个子标识集，每个子标识集中包含10000个标识，该子标识集对应的线程对该子标识集中的10000个标识进行排序，得到有序子标识集。T个线程并行对其对应的子标识集进行排序，得到T个有序子标识集。

[0086] S202：统计T个有序子标识集的标识分布特征，根据T个有序子标识集的标识分布特征，确定N个区间范围。

[0087] 在本申请实施例中，统计T个有序子标识集的标识分布特征，根据T个有序子标识集的标识分布特征，确定N个区间范围。例如，当标识为学生成绩时，总成绩为120，统计成绩分布特征得到，学生成绩区间为[40，120]，则对成绩进行划分时，可按照以下区间范围进行划分[40，50)、[50，60)、[60，70)、[70，80)、[80，90)、[90，100)、[100，110)、[110，120]。

[0088] 在本申请实施例中，统计T个有序子标识集的标识分布特征，根据T个有序子标识集的标识分布特征，确定N个区间范围时，使T个有序子标识集中处于各个区间范围中的标识数量之和均匀分布。由此可实现S103中得到N个目标子标识集为N个标识数量分布均匀的目标子标识集。

[0089] S203：针对任一有序子标识集，根据N个区间范围对有序子标识集进行划分，得到N个区间。

[0090] 在本申请实施例中，针对任一有序子标识集，根据上述确定的N个区间范围，对有序子标识集进行划分，得到N个区间，可以理解的是，N个区间中标识数量不唯一，根据具体的标识数值确定。

[0091] S204：对N个区间进行切分，得到M个区间集。

[0092] 在本申请实施例中，对各个有序标识集的N个区间进行等量切分，得到M个区间集，每个区间集中的区间数量相等。例如，N=8，M=2，对8个区间进行切分，得到2个区间集，其中，每个区间集包含4个区间。需要说明的是，对N个区间切分时，从左向右或从右向左的顺序切分，得到的各个区间集中的区间是相邻的区间。

[0093] S205：将各个有序子标识集中区间范围相同的区间集进行组合，得到M个区间范围相同的区间集的第一集合，将任一第一集合对应的数据存储到一个本地非一致内存访问节点。

[0094] 在本申请实施例中，将各个有序子标识集中区间范围相同的区间集进行组合，得到M个区间范围相同的区间集的第一集合。例如，按上述S202确定的区间范围进行划分，得到8个区间，将8个区间进行切分，得到2个区间集，此时2个区间集的区间范围分别为[40，80)、[80，120]，将各个有序子标识集中区间范围为[40，80)的区间组合为一个第一集合，同理，将各个有序子标识集中区间范围为[80，120]的区间也组合为一个第一集合。将任一第一集合对应的数据存储到一个本地非一致内存访问节点，即将各个第一集合对应的数据均存放至一个本地非一致内存访问节点。

[0095] 通过上述对本申请实施例提供的技术方案的描述，本申请启动T线程并行对T个子标识集进行排序，得到T个有序子标识集，然后根据T个有序子标识集的标识分布特征，确定N个区间范围，根据N个区间范围将有序子标识集进行划分，得到N个区间，然后对N个区间进行切分，得到M个区间集，将各个有序子标识集中区间范围相同的区间集进行组合，得到M个区间范围相同的第一集合，然后将第一集合对应的数据存储到同一个本地非一致内存访问节点，即将区间范围相同的数据存放至同一个节点，尽量避免了跨非一致内存访问节点访问的问题。

[0096] 图3为本申请实施例提供的另一种数据存储方法的实施流程示意图，该方法可包括以下步骤：

[0097] S301：针对任一线程，对线程对应的子标识集进行排序，以得到T个有序子标识集。

[0098] S302：统计T个有序子标识集的标识分布特征，根据T个有序子标识集的标识分布特征，确定N个区间范围。

[0099] S303：针对任一有序子标识集，根据N个区间范围对有序子标识集进行划分，得到N个区间。

[0100] 在本申请实施例中，S301至S303在S201至S203中已经做了详细说明，在此不再赘述。

[0101] S304：确定一个本地非一致内存访问节点的存储空间，根据存储空间对N个区间进行切分，得到M个区间集。

[0102] 在本申请实施例中，首先确定一个本地非一致内存访问节点的存储空间，然后基于待排序标识集对应待排序数据所需的存储空间，确定将N个区间切分为M个区间集。例如，一个本地非一致内存访问节点的存储空间为16G，待排序标识集对应的待排序数据所需的存储空间为100G，则需要将100G数据划分成8份，每份12.5G，使每个本地非一致内存访问节点每次保存一份数据，例如，有2个本地非一致内存访问节点，则每个本地非一致内存访问节点需依次保存四份数据，当一份数据处理结束时，将下一份数据复制到该本地非一致内存访问节点中。

[0103] 根据上述确定的M的数值，第N个区间进行切分，得到M个区间集。

[0104] S305：将各个有序子标识集中区间范围相同的区间集进行组合，得到M个区间范围相同的区间集的第一集合，将任一第一集合对应的数据存储到一个本地非一致内存访问节点。

[0105] 在本申请实施例中，基于上述确定M的数值的方法，会出现第一集合的数量大于本地非一致内存访问节点的数量的情况，此时，以一个本地非一致内存访问节点为例，可依次将第一集合对应的数据存储到该本地非一致内存访问节点，当该本地非一致内存访问节点中的第一集合对应的数据处理结束，将该第一集合对应的数据从本地非一致内存访问节点清除，将下一个第一集合对应的数据存储到本地非一致内存访问节点。

[0106] 通过上述对本申请实施例提供的技术方案的描述，本申请中根据一个本地非一致内存访问节点的存储空间来确定将待排序标识集对应的数据分成几份来处理，确保了一个第一集合对应的数据能够在存储在同一个本地非一致内存访问节点中。协程对一个目标子标识集中的标识进行排序的过程中，需要从内存中获取确定顺序的标识对应的数据，由于目标子标识集中的包含的是各个子标识集中标识分布特征相同的区间，第一集合中包含的是各个子标识集中区间范围相同的区间集，因此，目标子标识集中的标识对应的数据均保存在一个本地非一致内存访问节点上，在获取数据时只需访问一个非一致内存访问节点即可，从而避免了跨非一致内存访问节点获取数据的问题。

[0107] 图4为本申请实施例提供的另一种数据排序方法的实施流程示意图，该方法可包括以下步骤：

[0108] S401：对待排序标识集进行切分，得到T个子标识集，并启动T个线程，线程与子标识集一一对应。

[0109] S402：针对任一子标识集，根据子标识集中标识分布特征对子标识集进行划分，得到N个区间，将待排序标识集对应的待排序数据集存储到本地非一致内存访问节点。

[0110] S403：将各个子标识集中标识分布特征相同的区间进行组合，得到N个目标子标识集，针对任一线程启动C个协程，其中，C个协程交错执行。

[0111] S404：针对任一协程，确定协程对应的目标子标识集，采用单指令多数据流向量化方式对目标子标识集循环筛选出最小或最大标识。

[0112] 在本申请实施例中，S401至S404在S101至S104中已经做了详细说明，在此不再赘述。

[0113] S405：根据最小或最大标识执行数据预取指令，并暂停协程。

[0114] 在本申请实施例中，协程对目标子标识集进行排序时，得到最小或最大标识后，协程根据最小或最大标识所携带的数据的位置信息发送一个数据预取指令，去预取最大或最小标识对应的数据，然后协程执行协程中自带的yield（暂停指令）。此时该协程停止执行，该协程对应的线程可执行线程中的其他协程。

[0115] S406：当数据预取指令将最小或最大标识对应的数据预取成功时，重新执行协程。

[0116] 在本申请实施例中，等数据预取指令将最小或最大标识对应的数据预取成功时，该协程对应的线程暂停正在执行的协程，重新执行该协程。

[0117] S407：从本地非一致内存访问节点中获取数据预取指令预取到的最小或最大标识对应的数据，组成有序目标子数据集，得到N个有序目标子数据集。

[0118] 在本申请实施例中，从本地非一致内存访问节点中获取数据预取指令预取到的最小或最大标识对应的数据，将该数据复制到排序之后的位置，直至组成有序目标子数据集。

[0119] S408：将N个有序目标子数据集进行合并，得到待排序标识集对应的待排序数据的有序数据集。

[0120] 在本申请实施例中，S408在S105中已经做了详细说明，在此不再赘述。

[0121] 通过上述对本申请实施例提供的技术方案的描述，本申请在一个线程中启动多个协程，多个协程交错执行，当一个协程得到最大或最小标识后，首先发送数据预取指令，在等待预取数据时，该协程执行一个暂停指令，释放出线程，使线程执行其他协程，从而减少了线程的空闲时间，掩盖了cache misses。

[0122] 图5为本申请实施例提供的又一种数据排序方法的实施流程示意图，该方法可包括以下步骤：

[0123] S501：对待排序标识集进行切分，得到T个子标识集，并启动T个线程，线程与子标识集一一对应。

[0124] S502：针对任一子标识集，根据子标识集中标识分布特征对子标识集进行划分，得到N个区间，将待排序标识集对应的待排序数据集存储到本地非一致内存访问节点。

[0125] S503：将各个子标识集中标识分布特征相同的区间进行组合，得到N个目标子标识集，针对任一线程启动C个协程，其中，C个协程交错执行。

[0126] S504：针对任一协程，确定协程对应的目标子标识集，采用单指令多数据流向量化方式对目标子标识集循环筛选出最小或最大标识。

[0127] S505：根据最小或最大标识执行数据预取指令，并暂停协程。

[0128] 在本申请实施例中，S501至S505在S401至S405中已经做了详细说明，在此不再赘述。

[0129] S506：按照预设的优先级通知协程对应的线程中启动的第一协程，以使第一协程执行确定协程对应的目标子标识集，采用单指令多数据流向量化方式对目标子标识集循环筛选出最小或最大标识，以获取本地非一致内存访问节点中最小或最大标识对应的数据，组成有序目标子数据集的步骤。

[0130] 在本申请实施例中，在协程执行数据预取指令，等待数据预取指令预取数据时，执行暂停指令，释放线程，此时线程可执行其他协程。例如，可以为线程中启动的协程编号，依次为1,2,……，C。协程之间采用轮询执行的方式，即按照顺序依次执行，例如1,2,……，n，1，2,……。当正在执行的协程编号为1时，该协程执行了数据预取指令，可采用预先存储数据预取时间或根据数据存储位置估算一个数据预取时间，本申请实施例对此不做限定。轮询执行协程时，执行的协程数量n由数据预取时间确定。

[0131] 例如，此时执行协程1，在协程1执行数据预取指令后，暂停协程1，预取数据需要耗时100ns，每个协程的计算时间只需20ns，那么n=6。即切换至协程2后，协程2执行20ns也会执行数据预取指令，然后依次执行之后的协程，直至协程6的计算过程执行结束，耗时100ns，此时第一个协程的数据预取指令预取数据成功，重新切换至第一个协程继续后面的计算。

[0132] S507：当数据预取指令将最小或最大标识对应的数据预取成功时，重新执行协程。

[0133] S508：从本地非一致内存访问节点中获取数据预取指令预取到的最小或最大标识对应的数据，组成有序目标子数据集，以得到N个有序目标子数据集。

[0134] S509：将N个有序目标子数据集进行合并，得到待排序标识集对应的待排序数据的有序数据集。

[0135] 在本申请实施例中，S507至S509在S406至S408中已经做了详细说明，在此不再赘述。

[0136] 通过上述对本申请实施例提供的技术方案的描述，本申请中将数据预取指令预取数据成功的协程的优先级提高，使协程的等待时间集中在发送数据预取指令后，等待数据预取指令预取数据时，减少其他步骤的等待。

[0137] 基于S104，图6为本申请实施例提供的一种有序目标子数据集组成方法的实施流程示意图，该方法可包括以下步骤：

[0138] S601：确定协程对应的目标子标识集，确定目标子标识集中的T个区间，确定单指令多数据流向量化方式对应的一个指令能够同时处理的数据的第一数量。

[0139] 在本申请实施例中，协程对目标子标识集进行排序时，目标子标识集中包含T个区间，这T个区间分别来自T个有序子标识集。例如，基于对上述附图中步骤的描述，待排序标识集中的标识为成绩，待排序标识集对应的待排序数据集为学生姓名、学号、性别等，本申请实施例对此不做限定。设T=4，N=8，即将待排序标识集切分成4个子标识集，并启动4个线程，并行对4个子标识集进行排序，得到4个有序子标识集，将各个有序子标识集按照相同的8个区间范围均划分为8个区间，将各个有序子标识集中区间范围相同的区间进行组合得到
8个目标子标识集。两个非一致内存访问节点分别得到4个目标子标识集。每个线程操作2个目标子标识集，针对各个目标子标识集均启动一个协程，对各个目标子标识集中来自4个有序子标识集的4个区间进行归并，并从本地非一致内存访问节点中复制数据，由4个有序区间得到1个有序子数据集。

[0140] 在本申请实施例中，由于采用单指令多数据流向量化方式，一个指令可以同时对多条数据进行处理，因此确定本申请中单指令多数据流向量化方式对应的一个指令能够同时处理的数据的第一数量。

[0141] S602：生成一棵叶子结点数量为T的二叉树，其中，目标子标识集中的T个区间与T个叶子结点一一对应，二叉树的各个节点中可存放的标识数量为第一数量。

[0142] 在本申请实施例中，生成一棵叶子结点数量为T的二叉树，二叉树的各个节点中可存放的标识数量为第一数量，目标子标识集中包含来自T个有序子标识集中的T个区间，将T个区间与T个叶子结点一一对应。

[0143] S603：迭代执行以下步骤，直至得到目标子标识集对应的有序目标子数据集。

[0144] S604：确定当前迭代过程中参与归并的叶子结点，从参与归并的叶子结点对应的区间中获取第二数量的最小或最大标识。

[0145] 在本申请实施例中，首先确定当前迭代过程中参与归并的叶子结点，从参与归并的叶子结点对应的区间中获取第二数量的最小或最大标识。例如，T为4，当前迭代过程中参与归并的叶子结点为2个，则从参与归并的叶子结点对应的区间中获取第二数量的最小或最大标识。各个区间中的标识是有顺序的，因此，获取第二数量的最小或最大标识时是按照顺序依次获取的。

[0146] 在本申请实施例中，叶子结点中除存放第一数量的最小或最大标识外，还存放了每个标识还对应的叶子结点的标识以及标识对应的数据的位置信息。

[0147] S605：从参与归并的叶子结点开始，按照从左到右或从右到左的顺序两两归并，直至得到当前迭代过程中的第一数量的最小或最大的有序标识。

[0148] 在本申请实施例中，从参与归并的叶子结点开始，按照从左到右或从右到左的顺序两两归并，直至得到包含当前迭代过程中的第一数量的最小或最大标识的根节点。

[0149] 在本申请实施例中，当参与归并的叶子结点为全部叶子结点时，例如，排序要求是将标识按从小到大的顺序进行排序，T=4，第一数量为4，采用从左到右的顺序两两归并，第一个叶子结点和第二个叶子结点进行归并，第三个叶子结点和第四个叶子结点进行归并，从4个叶子结点中分别依次取4个标识，采用单指令多数据流向量化方式选出第一个叶子结点和第二个叶子结点中取出的8个标识中最小的4个标识，具体的，可同时将第一个节点中的4个标识按照标识大小插入到第二个节点中的4个标识之间，得到有序的8个标识，选出最小的4个标识放入第一个叶子结点和第二个叶子结点的父亲节点上，同理，得到第三个叶子结点和第四个叶子结点中最小的4个标识，放入第三个叶子结点和第四个叶子结点的父亲节点上，同理，将两个父亲节点进行归并，得到两个父亲节点中最小的4个标识，放入根节点上。

[0150] 需要说明的是，上述仅是对节点两两归并获得包含第一数量的最小或最大标识时的归并方式给出的一个示例，本申请实施例对此不做限定。

[0151] S606：根据第一数量的最小或最大的有序标识执行数据预取指令，并暂停协程。

[0152] S607：当数据预取指令将第一数量的最小或最大的有序标识对应的数据预取成功时，重新执行协程。

[0153] S608：从本地非一致内存访问节点中获取数据预取指令预取到的第一数量的最小或最大的有序标识对应的数据，以组成有序目标子数据集。

[0154] 在本申请实施例中，S606至S608在S405至S407中已经做了详细说明，在此不再赘述。

[0155] S609：根据第一数量的最小或最大的有序标识确定下一次迭代过程中参与归并的叶子结点以及下一次迭代过程中参与归并的叶子结点所要获取的标识的第二数量。

[0156] 在本申请实施例中，由于第一数量的最小或最大的有序标识对应有叶子结点的标识，可根据第一数量的最小或最大的有序标识确定其对应的叶子结点，并确定其对应的叶子结点为下一次迭代过程中参与归并的叶子结点。第一数量的最小或最大的有序标识可能来自不同的叶子结点，确定其对应的叶子结点后，确定其对应的叶子结点中为第一数量的最小或最大的有序标识的标识数量，将该标识数量作为下一次迭代过程中，参与归并的叶子结点所要获取的第二数量。

[0157] 例如，第一数量为4，初始化一个数组fromID={0，1，2，3}，当得到第一数量的最小或最大的有序标识时，根据第一数量的最小或最大的有序标识对应的叶子结点更新fromID，第一数量的最小或最大的有序标识对应的叶子结点为0、0、1、1，则更新后的fromID={0，0，1，1}，由此，可确定下一次参与归并的叶子结点为标识为0和1的节点，标识为0的叶子结点中有两个标识为最终确定的最小或最大的有序标识，即标识为0的叶子结点对应的第二数量为2，标识为1的叶子结点中有两个标识为最终确定的最小或最大的有序标识，即标识为1的叶子结点对应的第二数量为2。

[0158] 基于S604，由于当前迭代过程为首次迭代时，需要对全部叶子节点进行归并，图7为本申请实施例提供的一种迭代次数判断方法的实施流程示意图，该方法可包括以下步骤：

[0159] S701：判断当前迭代过程是否为首次迭代过程。

[0160] S702：若当前迭代过程为首次迭代过程，确定参与归并的叶子结点为T个叶子结点，从T个叶子结点对应的区间中获取第一数量的最小或最大标识。

[0161] S703：若当前迭代过程非首次迭代过程，确定当前迭代过程中参与归并的叶子结点，从参与归并的叶子结点对应的区间中获取第二数量的最小或最大标识。

[0162] 以下对S701至S703进行统一描述：

[0163] 在本申请实施例中，需要判断当前迭代过程是否为首次迭代过程，若当前迭代过程为首次迭代过程，则确定参与归并的叶子结点为T个叶子结点，从T个叶子结点对应的区间中获取第一数量的最小或最大标识。若当前迭代过程非首次迭代，确定当前迭代过程中参与归并的叶子结点，从参与归并的叶子结点对应的区间中获取第二数量的最小或最大标识，其中当前迭代过程中参与归并的叶子结点以及参与归并的叶子结点对应的区间中应获取的最小或最大标识的第二数量由上一次迭代过程获取的第一数量的最小或最大的有序标识确定。

[0164] 在本申请实施例中，从当前迭代过程中参与归并的叶子结点对应的区间中获取第二数量的最小或最大标识时，由于叶子结点中已存放了第一数量的标识，用第二数量的最小或最大标识将叶子结点中已存放的标识中属于第一数量的最小或最大的有序标识的标识覆盖，从而实现对当前迭代过程中参与归并的叶子结点的更新。

[0165] 基于S609，得到第一数量的最小或最大的有序标识对应的第一数量的最小或最大有序数据之后，需要根据第一数量的最小或最大的有序标识确定下一次迭代过程中参与归并的叶子结点以及下一次迭代过程中参与归并的叶子结点所要获取的第二数量，具体确定方法如图8所示，图8为本申请实施例提供的一种参与归并的叶子结点及第二数量确定方法的实施流程示意图，该方法可包括以下步骤：

[0166] S801：确定第一数量的最小或最大的有序标识对应的叶子结点为下一次迭代过程中参与归并的叶子结点。

[0167] 在本申请实施例中，第一数量的最小或最大的有序标识为已经确定顺序的有序标识，基于第一数量的最小或最大的有序标识确定各个有序标识对应的叶子结点，需要对有序标识对应的叶子结点进行更新，然后在下一次迭代过程中进行归并。

[0168] S802：针对任一下一次迭代过程中参与归并的叶子结点，从第一数量的最小或最大的有序标识中查找来自下一次迭代过程中参与归并的叶子结点的部分有序标识，并统计部分有序标识的数量。

[0169] 在本申请实施例中，有序标识对应的叶子结点可能为一个或多个，确定下一次迭代过程中参与归并的叶子结点，针对任一下一次迭代过程中参与归并的叶子结点，从第一数量的最小或最大的有序标识中查找来自该下一次迭代过程中参与归并的叶子结点的部分有序标识，统计部分有序标识的数量。

[0170] S803：确定部分有序标识的数量为下一次迭代过程中参与归并的叶子结点所要获取的标识的第二数量。

[0171] 在本申请实施例中，由于第一数量的最小或最大的有序标识中来自该下一次迭代过程中参与归并的叶子结点的部分有序标识为已经确定顺序的有序标识，该下一次迭代过程中参与归并的叶子结点中的部分有序标识可由其对应的区间中的最小或最大标识覆盖，因此可确定部分有序标识的数量为下一次迭代过程中参与归并的叶子结点所要获取的标识的第二数量。

[0172] 通过上述对本申请实施例提供的技术方案的描述，本申请一个协程处理一个目标子标识集的归并排序，首先生成一棵二叉树，二叉树的叶子结点数量与目标子标识集中的区间一一对应，每个迭代过程更新叶子结点，从叶子结点开始归并，直至得到第一数量的最小或最大的有序标识，然后发送数据预取指令，在该协程等待数据预取指令预取数据时，执行一个暂停指令，释放线程资源，以使线程中的其他协程执行。更新叶子结点时，根据上一次迭代过程中得到第一数量的最小或最大的有序标识确定参与归并的叶子结点以及参与归并的叶子结点需要更新的标识数量，对参与归并的叶子结点中的标识进行更新后，直接从参与归并的叶子结点开始进行归并，无需对未更新标识的叶子结点进行重新归并，提高了归并排序的效率。

[0173] 图9以4路归并的具体实施例对协程排序进行说明，图9为本申请实施例提供的一种协程排序方法的实施流程示意图，具体步骤如下所示：

[0174] 在本申请实施例中，线程/协程处理标识划分，将待排序数据集等份分成4个子标识集，对各个子标识集进行排序，之后每个线程根据标识分布特征划分成8个区间，然后将数据复制到本地非一致内存访问节点。接着每个线程取每个标识分区的两个区间标识排序，具体是生成两个协程排序，每个协程处理4个子标识集的一个区间。

[0175] 协程排序时循环执行以下步骤：

[0176] ①先根据4个区间生成一棵叶子结点为4的二叉树，如图9所示，叶子结点为4的二叉树包含2个父亲节点，一个根节点，二叉树的各个节点可保存的标识数量为单指令多数据流向量化方式中一个指令可处理的数据数量，保存形式为三个向量，如图9所示，第一行为标识，第二行为数据位置信息，第三行为区间标识。然后设置来源标识集fromIDs={0，1，2，3}，来源标识即为图9中的区间标识，由于叶子结点与区间一一对应，因此区间标识与叶子结点标识一一对应；

[0177] ②每个叶子结点从叶子结点对应的区间里获取标识，保存至叶子结点。从叶子结点开始，获得每个节点最小的4个标识，最终得到4个区间有序标识流的4个最小或最大有序标识，具体的，通过向量合并的方式将节点两两合并，本步骤即图9所示的更新二叉树；

[0178] （3）将最小4个标识对应的数据位置信息指向的数据项复制到目标位置。具体的，首先预取目标数据，然后通过协程yield来暂停协程，之后重启复制数据项；

[0179] （4）根据最小4个标识对应的区间标识更新fromIDs，根据更新的fromIDs对取出最小标识的叶子结点进行补位，从叶子结点对应的区间的有序标识流中依次取出标识，例如，更新后的fromIDs={0，0，1，1}，则从区间0和区间1的有序标识流中各自依次取出两个标识，以补齐叶子结点中取出标识之后的空位，然后更新二叉树。

[0180] 循环执行以上步骤，直至各个区间有序标识流均取出，在过程中将各个标识对应的数据复制到目标位置，最终得到有序目标子数据集。

[0181] 图10为本申请实施例提供的一种数据排序装置的结构示意图，该装置包括：子标识集切分模块1001、存储模块1002、协程启动模块1003、有序目标子数据集组成模块1004，以及有序数据集获取模块1005。

[0182] 子标识集切分模块1001，用于对待排序标识集进行切分，得到T个子标识集，并启动T个线程，线程与子标识集一一对应；

[0183] 存储模块1002，用于针对任一子标识集，根据子标识集中标识分布特征对子标识集进行划分，得到N个区间，将待排序标识集对应的待排序数据集存储到本地非一致内存访问节点；

[0184] 协程启动模块1003，用于将各个子标识集中标识分布特征相同的区间进行组合，得到N个目标子标识集，针对任一线程启动C个协程，其中，C个协程交错执行；

[0185] 有序目标子数据集组成模块1004，用于针对任一协程，确定协程对应的目标子标识集，采用单指令多数据流向量化方式对目标子标识集循环筛选出最小或最大标识，以获取本地非一致内存访问节点中最小或最大标识对应的数据，组成有序目标子数据集，以得到N个有序目标子数据集；

[0186] 有序数据集获取模块1005，用于将N个有序目标子数据集进行合并，得到待排序标识集对应的待排序数据的有序数据集。

[0187] 图11为本申请实施例提供的一种电子设备的结构示意图，图11所示的电子设备1100包括：至少一个处理器1101、存储器1102、至少一个网络接口1104和用户接口1103。电子设备1100中的各个组件通过总线系统1105耦合在一起。可理解，总线系统1105用于实现这些组件之间的连接通信。总线系统1105除包括数据总线之外，还包括电源总线、控制总线和状态信号总线。但是为了说明的清楚起见，在图11中将各种总线都标为总线系统1105。

[0188] 其中，用户接口1103可以包括显示器、键盘或者点击设备（例如，鼠标，轨迹球（trackball））、触感板或者触摸屏等。

[0189] 可以理解，本申请实施例中的存储器1102可以是易失性存储器或非易失性存储器，或可包括易失性和非易失性存储器两者。其中，非易失性存储器可以是只读存储器（Read‑Only Memory，ROM）、可编程只读存储器（Programmable ROM，PROM）、可擦除可编程只读存储器（Erasable PROM，EPROM）、电可擦除可编程只读存储器（Electrically EPROM，EEPROM）或闪存。易失性存储器可以是随机存取存储器（Random Access Memory，RAM），其用作外部高速缓存。通过示例性但不是限制性说明，许多形式的RAM可用，例如静态随机存取存储器（Static RAM，SRAM）、动态随机存取存储器（Dynamic RAM，DRAM）、同步动态随机存取存储器（Synchronous DRAM，SDRAM）、双倍数据速率同步动态随机存取存储器（Double Data Rate SDRAM，DDRSDRAM）、增强型同步动态随机存取存储器（Enhanced SDRAM，ESDRAM）、同步连接动态随机存取存储器（Synchlink DRAM，SLDRAM）和直接内存总线随机存取存储器（Direct Rambus RAM，DRRAM）。本文描述的存储器1102旨在包括但不限于这些和任意其它适合类型的存储器。

[0190] 在一些实施方式中，存储器1102存储了如下的元素，可执行单元或者数据结构，或者他们的子集，或者他们的扩展集：操作系统11021和应用程序11022。

[0191] 其中，操作系统11021，包含各种系统程序，例如框架层、核心库层、驱动层等，用于实现各种基础业务以及处理基于硬件的任务。应用程序11022，包含各种应用程序，例如媒体播放器（Media Player）、浏览器（Browser）等，用于实现各种应用业务。实现本申请实施例方法的程序可以包含在应用程序11022中。

[0192] 在本申请实施例中，通过调用存储器1102存储的程序或指令，具体的，可以是应用程序11022中存储的程序或指令，处理器1101用于执行各方法实施例所提供的方法步骤，例如包括：对待排序标识集进行切分，得到T个子标识集，并启动T个线程，所述线程与所述子标识集一一对应；针对任一所述子标识集，根据所述子标识集中标识分布特征对所述子标识集进行划分，得到N个区间，将所述待排序标识集对应的待排序数据集存储到本地非一致内存访问节点；将各个所述子标识集中标识分布特征相同的区间进行组合，得到N个目标子标识集，针对任一所述线程启动C个协程，其中，所述C个协程交错执行；针对任一协程，确定所述协程对应的目标子标识集，采用单指令多数据流向量化方式对目标子标识集循环筛选出最小或最大标识，以获取本地非一致内存访问节点中所述最小或最大标识对应的数据，组成有序目标子数据集，以得到N个有序目标子数据集；将所述N个有序目标子数据集进行合并，得到所述待排序标识集对应的待排序数据的有序数据集。

[0193] 上述本申请实施例揭示的方法可以应用于处理器1101中，或者由处理器1101实现。处理器1101可能是一种集成电路芯片，具有信号的处理能力。在实现过程中，上述方法的各步骤可以通过处理器1101中的硬件的集成逻辑电路或者软件形式的指令完成。上述的处理器1101可以是通用处理器、数字信号处理器（Digital Signal Processor，DSP）、专用集成电路（Application Specific Integrated Circuit，ASIC）、现成可编程门阵列（Field Programmable Gate Array，FPGA）或者其他可编程逻辑器件、分立门或者晶体管逻辑器件、分立硬件组件。可以实现或者执行本申请实施例中的公开的各方法、步骤及逻辑框图。通用处理器可以是微处理器或者该处理器也可以是任何常规的处理器等。结合本申请实施例所公开的方法的步骤可以直接体现为硬件译码处理器执行完成，或者用译码处理器中的硬件及软件单元组合执行完成。软件单元可以位于随机存储器，闪存、只读存储器，可编程只读存储器或者电可擦写可编程存储器、寄存器等本领域成熟的存储介质中。该存储介质位于存储器1102，处理器1101读取存储器1102中的信息，结合其硬件完成上述方法的步骤。

[0194] 可以理解的是，本文描述的这些实施例可以用硬件、软件、固件、中间件、微码或其组合来实现。对于硬件实现，处理单元可以实现在一个或多个专用集成电路（Application Specific Integrated Circuits，ASIC）、数字信号处理器（Digital Signal Processing，DSP）、数字信号处理设备（DSP Device，DSPD）、可编程逻辑设备（Programmable Logic Device，PLD）、现场可编程门阵列（Field‑Programmable Gate Array，FPGA）、通用处理器、控制器、微控制器、微处理器、用于执行本申请功能的其它电子单元或其组合中。

[0195] 对于软件实现，可通过执行本文功能的单元来实现本文的技术。软件代码可存储在存储器中并通过处理器执行。存储器可以在处理器中或在处理器外部实现。本实施例提供的电子设备可以是如图11中所示的电子设备，可执行如图1 9中方法的所有步骤，进而实~现图1 9中方法的技术效果，具体请参照图1 9相关描述，为简洁描述，在此不作赘述。
~ ~

[0196] 本申请实施例还提供了一种存储介质（计算机可读存储介质）。这里的存储介质存储有一个或者多个程序。其中，存储介质可以包括易失性存储器，例如随机存取存储器；存储器也可以包括非易失性存储器，例如只读存储器、快闪存储器、硬盘或固态硬盘；存储器还可以包括上述种类的存储器的组合。

[0197] 当存储介质中一个或者多个程序可被一个或者多个处理器执行，以实现上述在电子设备侧执行的数据排序方法。处理器用于执行存储器中存储的数据排序程序，以实现以下在电子设备侧执行的数据排序方法的步骤：

[0198] 对待排序标识集进行切分，得到T个子标识集，并启动T个线程，所述线程与所述子标识集一一对应；针对任一所述子标识集，根据所述子标识集中标识分布特征对所述子标识集进行划分，得到N个区间，将所述待排序标识集对应的待排序数据集存储到本地非一致内存访问节点；将各个所述子标识集中标识分布特征相同的区间进行组合，得到N个目标子标识集，针对任一所述线程启动C个协程，其中，所述C个协程交错执行；针对任一协程，确定所述协程对应的目标子标识集，采用单指令多数据流向量化方式对目标子标识集循环筛选出最小或最大标识，以获取本地非一致内存访问节点中所述最小或最大标识对应的数据，组成有序目标子数据集，以得到N个有序目标子数据集；将所述N个有序目标子数据集进行合并，得到所述待排序标识集对应的待排序数据的有序数据集。

[0199] 专业人员应该还可以进一步意识到，结合本文中所公开的实施例描述的各示例的单元及算法步骤，能够以电子硬件、计算机软件或者二者的结合来实现，为了清楚地说明硬件和软件的可互换性，在上述说明中已经按照功能一般性地描述了各示例的组成及步骤。这些功能究竟以硬件还是软件方式来执行，取决于技术方案的特定应用和设计约束条件。
专业技术人员可以对每个特定的应用来使用不同方法来实现所描述的功能，但是这种实现不应认为超出本申请的范围。

[0200] 结合本文中所公开的实施例描述的方法或算法的步骤可以用硬件、处理器执行的软件模块，或者二者的结合来实施。软件模块可以置于随机存储器（RAM）、内存、只读存储器（ROM）、电可编程ROM、电可擦除可编程ROM、寄存器、硬盘、可移动磁盘、CD‑ROM、或技术领域内所公知的任意其它形式的存储介质中。

[0201] 以上所述的具体实施方式，对本申请的目的、技术方案和有益效果进行了进一步详细说明，所应理解的是，以上所述仅为本申请的具体实施方式而已，并不用于限定本申请的保护范围，凡在本申请的精神和原则之内，所做的任何修改、等同替换、改进等，均应包含在本申请的保护范围之内。