无锁遍历锯齿数组：如何避免遍历外层数组实现高效索引？

你可以通过预构建前缀和数组结合二分查找的方式，避免每次遍历外层数组，具体实现如下：

步骤1：预计算前缀和数组 #

提前计算每个外层数组对应的累计元素总数，生成一个只读的前缀和数组。这个数组只需要初始化一次，多线程访问时无需同步（因为是只读结构）。

示例代码：

// 预处理：计算前缀和，prefixSum[0] = 0，prefixSum[k] 表示前k个内层数组的总元素数
int[] prefixSum = new int[arr.Length + 1];
for (int i = 0; i < arr.Length; i++)
{
    prefixSum[i + 1] = prefixSum[i] + arr[i].Length;
}
int totalElements = prefixSum[arr.Length];

步骤2：无锁工作线程实现 #

工作线程通过原子递增共享索引后，用二分查找定位到对应的外层数组索引，再计算内层索引，无需遍历整个外层数组：

int sharedIndex = -1;

// 工作线程逻辑
while (true)
{
    int index = Interlocked.Increment(ref sharedIndex);
    if (index >= totalElements)
    {
        // 所有元素处理完毕，退出线程
        break;
    }

    // 二分查找找到对应的外层数组索引i
    int left = 0, right = arr.Length;
    while (left < right)
    {
        int mid = (left + right) / 2;
        if (prefixSum[mid] <= index)
        {
            left = mid + 1;
        }
        else
        {
            right = mid;
        }
    }
    int i = left - 1;
    // 计算内层数组的索引j
    int j = index - prefixSum[i];
    
    DoWork(arr[i][j]);
}

方案优势 #

• 前缀和数组是只读结构，初始化完成后不会被修改，多线程访问完全安全，无需任何同步措施。
• 二分查找的时间复杂度是O(logM)（M是外层数组的长度），相比原来的O(M)遍历，性能提升非常明显，尤其是当外层数组元素较多时。
• 仅用一个共享原子索引分配任务，完全无锁，避免了SpinLock的开销和潜在阻塞问题。

额外注意事项 #

• 必须确保前缀和数组的计算在所有工作线程启动前完成，避免线程读取未初始化的数据。
• 如果锯齿数组的结构会动态变化（比如内层数组长度或外层数组元素增减），这个方案不适用，需要重新设计动态前缀和的同步逻辑。

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