c++ - SSBO 哈希表，缺失值

Question

我正在尝试进行一些数据压缩实验。我正在尝试将 3D 纹理压缩到哈希表中以避免存储空的体积信息。

为此，我编写了散列函数和检索函数(它们在不同的着色器中):

struct Voxel
{
    int filled;
    ivec4 position;
    vec4 normal;
    vec4 color;
};

layout(std430, binding = 0) buffer voxel_buffer
{
    uint index;
    Voxel voxels[];
};
// Data storing shader
int a_size = 10000000;
void insert(vec3 pos, Voxel value) {
    ivec3 discretized = ivec3(pos / v_size);
    int index = int(pow(7, discretized.x) * pow(2, discretized.y) * pow(3, discretized.z)) % a_size;

    for(int i=0; i<50; i++) {
        if(atomicCompSwap(voxels[index].filled, 0, 1) == 0) {
           Voxel c_voxel = voxels[index];
           value.position = ivec4(discretized, 1);
           voxels[index] = value;
           break;
         }

        index = (index * index) % a_size;
    }
}
//Data reading shader
int a_size = 10000000;
vec4 fetch(vec3 pos) {
    ivec3 discretized = ivec3(pos / v_size);
    int index = int(pow(7, discretized.x) * pow(2, discretized.y) * pow(3, discretized.z)) % a_size;

    for(int i=0; i<50; i++) {
        Voxel c_voxel = voxels[index];

        if(ivec4(discretized,1) == voxels[index].position)
            return voxels[index].color;

        index = (index * index) % a_size;
    }
}

然而，我目前的问题是我丢失了大约 90% 的体素值:

预期的结果是:

我有一些想法可能是错的，但似乎都不是:

• 散列数大于数组大小。我分配了 100 000 000 个字节，体素结构的总大小应该是 4*4*3 = 48，所以我总共可能的元素数是 2 083 333.33。我将数组大小限制在一百万，这是它的一半，所以我不应该访问未分配的内存。

• 哈希函数碰撞超过 50 次，导致大部分元素被丢弃。我可能是错的，但我正在使用二次更新来增加散列索引，这应该比线性更好。而且我还依靠 FTA 来保证在消化之前生成唯一的 key 。所以我怀疑这么多哈希碰撞超过 50 次。此外，保留的体素都在这样一个很好的区域(线性对角线切片)似乎不符合这个假设。如果这是一个碰撞问题，我应该看到整体的半均匀分布，而不是一个定义得很好的区域。

• 驱动程序无法为 ssbo 分配那么多的 vram。我正在使用带有最新 NVIDIA 驱动程序的 GTX 1070，文档说规范保证最小大小为 128 MB，但大多数实现允许您分配最大内存大小。我分配了 100 000 000 字节，低于上限，即使驱动程序将我的内存对齐到 128 MB，它也不应该影响我的计算结果，因为我自己跟踪逻辑数组大小。

关于为什么我在压缩时丢失了这么多信息有什么想法吗？

编辑:添加基于评论的原子操作

编辑 2:在评论中找到解决方案，结果:

一些内存丧失仍然会发生，但这是预料之中的。

Answer 1

你的哈希函数

int(pow(7, discretized.x) * pow(2, discretized.y) * pow(3, discretized.z)) % a_size;

很穷。自 discretized是一个 ivec3 , 整个操作都是对整数进行的，术语 pow(2, discretized.y)将是 0每当 discretized.y是>= 31 ，导致您的完整哈希值评估为 0 .此外，对于 discretized.y < 0 ，你应该得到 0，因为结果分数也不能用 int 表示类型。此外，您的二次探测也因 index == 0 而失败。 ，因为您将探测相同索引的 50 次。