On Thu, Feb 9, 2017 at 4:16 PM, Jan Ziak <0xe2.0x9a.0...@gmail.com> wrote: > Hello > > IMPORTANT NOTE: Using the uint32_t data type, quad_hash*quad_hash will > overflow as soon as the hash table has more than 2**16=65536=64K > elements. To enable more than 64K elements in hash table, the data > types need to be changed to uint64_t - unfortunately uint64_t > arithmetic operations will slow down the hash table in 32-bit OpenGL > apps.
This actually doesn't matter, since at the end of the day we only need the result modulo the table size which is a power of two -- even if the multiplication overflows, the lowest n bits (if the table size is 2^n) are still correct, so we get the same answer as long as we use at least n bits. > > OPTIMIZATION: All "} while (hash_address != start_hash_address);" can > be replaced with "} while (1);" assuming that the hash table always > contains at least several free/unallocated entries. This optimization > applies both to current mesa-git and to the quadratic probing patch. > For quadratic probing this optimization works if the statement "values > of h(k,i) for i in [0,m-1] are all distinct" at > https://en.wikipedia.org/wiki/Quadratic_probing is correct. > > Jan > _______________________________________________ > mesa-dev mailing list > mesa-dev@lists.freedesktop.org > https://lists.freedesktop.org/mailman/listinfo/mesa-dev _______________________________________________ mesa-dev mailing list mesa-dev@lists.freedesktop.org https://lists.freedesktop.org/mailman/listinfo/mesa-dev
