Unity/HLSL计算Shader哈希表：插入竞态与查询死锁修复咨询

核心问题拆解 #

1. 插入操作的竞态根源 #

当前代码对int3 grid_pos的三个分量分别执行InterlockedCompareExchange，这不是原子性的整体操作。多个线程可能同时修改同一个单元格的不同分量，导致单元格的grid_pos处于半修改状态，或者多个线程同时判定同一单元格为空，进而插入重复键值对。

2. 查询操作的死锁（无限循环） #

查询逻辑的while(true)循环未处理哈希表满的场景：当所有单元格被占用且未找到目标键时，循环会无限执行，GPU线程将陷入死锁（持续占用资源无法退出）。

针对性修复方案 #

1. 原子化键操作：将int3打包为单个数值 #

HLSL原子操作仅支持基础数值类型，因此将int3编码为单个uint64_t（需确保网格坐标范围可压缩至64位内），通过一次原子比较交换完成键的校验与更新，彻底消除分量拆分带来的竞态。

2. 限制查询循环迭代次数 #

为查询循环添加最大迭代次数（等于哈希表单元格总数），确保即使哈希表满，线程也能正常退出，避免无限循环。

3. 原子化链表头更新 #

插入时找到可用单元格后，使用InterlockedExchange原子更新链表头索引，保证多线程下链表操作的安全性。

修改后的完整代码 #

#define CELL_EMPTY 2147483647    // 单元格为空时的value值

// 预计算GRID_EMPTY对应的64位编码（int3(2147483647,2147483647,2147483647)）
const uint64_t GRID_EMPTY_U64 = 0x1FFFFF1FFFFF1FFFFF;

struct Cell
{
    uint64_t grid_pos_u64;    // 将int3网格坐标打包为64位整数
    uint value;               // 单链表头的缓冲区索引
};

RWStructuredBuffer<Cell> table;     // 哈希表缓冲区
uint num_cells;

// 将int3网格坐标编码为uint64_t（假设坐标范围在[-2^20, 2^20]内）
uint64_t encode_grid_pos(int3 grid_pos)
{
    // 先将有符号坐标偏移为非负，再取低21位打包
    uint ux = (uint)(grid_pos.x + 1048576) & 0x1FFFFF;
    uint uy = (uint)(grid_pos.y + 1048576) & 0x1FFFFF;
    uint uz = (uint)(grid_pos.z + 1048576) & 0x1FFFFF;
    
    return (uint64_t)ux | ((uint64_t)uy << 21) | ((uint64_t)uz << 42);
}

// 将uint64_t解码回int3网格坐标
int3 decode_grid_pos(uint64_t pos_u64)
{
    uint ux = (uint)(pos_u64 & 0x1FFFFF);
    uint uy = (uint)((pos_u64 >> 21) & 0x1FFFFF);
    uint uz = (uint)((pos_u64 >> 42) & 0x1FFFFF);
    
    return int3((int)ux - 1048576, (int)uy - 1048576, (int)uz - 1048576);
}

uint calc_grid_hash(int3 grid_pos)
{
    const uint p1 = 73856093;
    const uint p2 = 19349663;
    const uint p3 = 83492791;

    uint n = p1*(uint)grid_pos.x ^ p2*(uint)grid_pos.y ^ p3*(uint)grid_pos.z;
    n = n % num_cells;

    return n;
}

uint grid_lookup(RWStructuredBuffer<Cell> table, int3 grid_pos)
{
    uint64_t target_u64 = encode_grid_pos(grid_pos);
    uint slot = calc_grid_hash(grid_pos);
    uint iterations = 0;

    // 最多遍历整个哈希表一次，避免无限循环
    while (iterations < num_cells)
    {
        uint64_t current_u64 = table[slot].grid_pos_u64;
        if (current_u64 == target_u64)
        {
            return table[slot].value;
        }
        if (current_u64 == GRID_EMPTY_U64)
        {
            return CELL_EMPTY;
        }
        slot = (slot + 1) % num_cells;
        iterations++;
    }

    // 遍历完所有单元格未找到目标键
    return CELL_EMPTY;
}

void grid_insert(int3 grid_pos, uint value)
{
    if (value == CELL_EMPTY)
        return; // 跳过空值插入

    uint64_t target_u64 = encode_grid_pos(grid_pos);
    uint slot = calc_grid_hash(grid_pos);
    uint iterations = 0;

    while (iterations < num_cells)
    {
        uint64_t old_u64;
        // 原子比较交换：仅当单元格为空或已存在目标键时，更新键值
        InterlockedCompareExchange(table[slot].grid_pos_u64, target_u64, GRID_EMPTY_U64, old_u64);

        if (old_u64 == GRID_EMPTY_U64 || old_u64 == target_u64)
        {
            // 原子更新链表头：将新的链表节点索引设为表头
            uint old_value;
            InterlockedExchange(table[slot].value, value, old_value);
            // 若需处理旧链表节点（如回收），可在此添加逻辑
            break;
        }

        slot = (slot + 1) % num_cells;
        iterations++;
    }

    // 哈希表满时的处理逻辑（可根据需求添加扩容或丢弃策略）
}

修复细节说明 #

• 原子键操作：通过编码将int3转为单个uint64_t，用一次InterlockedCompareExchange完成键的原子校验与替换，彻底解决多线程修改分量的竞态问题。
• 查询循环安全：添加iterations < num_cells的终止条件，确保线程不会因哈希表满陷入无限循环。
• 链表头原子更新：使用InterlockedExchange原子更新链表头索引，保证多线程环境下链表插入的一致性。
• 坐标范围兼容：编码逻辑假设坐标范围在[-2^20, 2^20]内，若你的网格坐标范围更大，可调整编码时的位宽分配（如改用128位类型或拆分存储）。

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