SSBO哈希表，缺少值 [英] SSBO hash table, missing values

问题描述

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

I am trying to run a little data compression experiment. I am trying to compress 3D textures into hash tables to avoid storing empty volume information.

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

To this effect I wrote the hashing function and retreiving function (they are in different shaders):

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％的体素值:

My current issue however is that I am missing about 90% of the voxel values:

预期结果是:

我对可能出什么问题有一些想法，但似乎没有:

I have had some ideas as to what could be wrong but none seem to be it:

• 哈希数大于数组大小.我分配了1亿个字节，体素结构的总大小应为4 * 4 * 3 = 48，这使我可以使用的元素总数为2 083 333.33.我将数组的大小限制为一百万，这是数组大小的一半，所以我不应该访问未分配的内存.

• Number of hashes is bigger than array size. I allocated 100 000 000 bytes, the total size of the voxel structure should be 4*4*3 = 48, giving me a total possible element number of 2 083 333.33. I capped the array size at a million, which is half of that, so I shouldn't be accessing unallocated memory.

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

Hash function collides more than 50 times, causing most of the elements to be discarded. I could be wrong, but I am using quadratic updating to increase the hashed index, this should be better than linear. And I am also relying on the FTA to guarantee unique key generation before digesting. So I am skeptic that so many hashes collide more than 50 times. Moreover, the fact that the voxels that were kept are all in such a nice region (a liner diagonal slice) doesn't seem to match this hypothesis. If it was a collision problem I should be seeing a semi uniform distribution of wholes, not such a nicely defined region.

驱动程序无法为ssbo分配那么多的vram.我使用的是带有最新NVIDIA驱动程序的GTX 1070，该文档说，该规范保证最小大小为128 MB，但是大多数实现都允许您分配总内存大小.我分配了1亿个字节，这是上限，并且即使驱动程序将我的内存对齐为128 MB，也不会影响我的计算结果，因为我自己会跟踪逻辑数组的大小.

Driver can't allocate that much vram for the ssbo. I am using a GTX 1070 with the latest NVIDIA drivers, the documentation says that the spec guarantees a minimum size of 128 MB but that most implementations let you allocate up to the total memory size. I allocated 100 000 000 bytes, which is under the upper limit, and even if the driver aligns my memory to 128 MB it should not affect the result of my computations since i keep track of the logical array size myself.

关于压缩时为什么丢失这么多信息的任何想法吗?

Any ideas as to why I am loosing so much information when compressing?

根据评论添加了原子操作

Added atomic operations based on a comment

在评论中找到了解决方案，结果:

EDIT 2: Solution was found in a comment, result:

仍然会发生一些内存丢失，但这是预期的.

Some memory loss still happens, but that was expected.

推荐答案

您的哈希函数

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

非常差.由于discretized是ivec3，因此整个操作都在整数上进行，并且每当discretized.y为>= 31时，术语pow(2, discretized.y)将为0，从而导致完整的哈希值计算为.另外，对于discretized.y < 0，您应该得到0，因为结果分数也不能用int类型表示.此外，对于index == 0，您的二次探测也会失败，因为您将探测相同索引的50倍.

is very poor. Since discretized is an ivec3, the whole operation is working on integers, and the term pow(2, discretized.y) will be 0 for whenever discretized.y is >= 31, resulting in your complete hash value to evaluate to 0. Also, for discretized.y < 0, you should get 0, as the resulting fractions are also not representable by int types. Furthermore, your quadratic probing also fails for index == 0, since you will probe 50 times the same index.

这篇关于SSBO哈希表，缺少值的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！