thrust::merge内部采用的合并算法及其与GPU Merge Path的差异

thrust 是面向多后端的通用算法库，不存在跨所有后端通用的单一合并算法，实际实现会根据绑定的执行后端动态切换：

• 非CUDA后端（串行CPP、TBB、OpenMP等面向CPU的后端）：核心逻辑是经典的双指针顺序归并，为了适配多线程并行，会将总合并输出区间拆分为大小相等的子块，每个子块的边界通过二分查找在两个输入序列中定位，再分配给不同CPU线程独立完成块内的顺序合并，整体复杂度保持O(n+m)。
• NVIDIA CUDA GPU后端：从Thrust 1.8版本（随CUDA 7首次发布）开始，核心框架完全基于GPU Merge Path的思路实现，和提到的mgpu::merge属于同一技术根源，而非早期版本采用的逐块全局二分查找的旧方案。

两者核心思路同源，但落地实现的优化方向完全不同，具体差异体现在：

• 通用适配层带来的额外开销
  mgpu的merge是纯面向GPU执行模型的极简实现，会把GPU线程束大小、共享内存容量这类硬件参数做编译期硬编码，无运行时分支判断。而thrust::merge为了兼容跨后端的统一调用接口，会在运行时判断当前GPU算力版本、内存类型、比较器类型，多了一层适配逻辑，在满负载最优场景下的纯合并性能会比原生mgpu实现低5%~10%。
• 块内合并的内存访问策略不同
  原生mgpu的GPU Merge Path实现，块内合并环节直接通过线程级二分查找确定每个线程负责的元素位置，直接从全局内存读取需要合并的元素，没有额外的共享内存预取步骤。而thrust::merge的CUDA实现会在块启动时，先把两个输入序列对应块的范围预取到共享内存中，减少全局内存的重复访问——这种设计在处理int、float这类小尺寸元素时，全局内存访问效率更高；但在处理大尺寸结构体元素时，反而会因为共享内存的搬运开销降低性能。
• 语义兼容带来的逻辑分支差异
  thrust::merge需要完全对齐std::merge的标准语义，支持自定义比较器、空序列输入、稳定合并等边界场景，在计算合并路径位置的时候，会额外增加稳定性校验的分支判断。而原生mgpu的merge为了极致性能，默认假设输入序列无位置歧义，稳定性依赖元素原始索引的隐式排序，没有额外的校验分支。
• 分块粒度的自适应逻辑不同
  原生mgpu的GPU Merge Path采用固定的分块粒度（一般每个线程块负责128个输出元素），在小数据量场景下，线程启动的固定开销占比会很高。而thrust::merge会根据总输入数据量动态调整分块大小，在小数据量场景下自动降低块大小，减少空转的线程调度开销，小数据量下的执行效率会比原生mgpu版本更高。

内容的提问来源于stack exchange，提问作者p4dn24x