Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
#include <stdint.h>
#include <stdlib.h>
#include <string.h>
#include <benchmark/benchmark.h>
unsigned int odd_constant = 0xdeadbeef | 1;
static unsigned int hash_crc32_orig(const void *keyptr)
{
unsigned int hash = odd_constant;
const char *key = (const char *)keyptr;
size_t len = strlen(key);
#if __x86_64__
while (len >= sizeof(uint64_t)) {
uint64_t data;
memcpy(&data, key, sizeof(data));
hash = (unsigned int)__builtin_ia32_crc32di(hash, data);
key += sizeof(uint64_t);
len -= sizeof(uint64_t);
}
#endif /* __x86_64__ */
while (len >= sizeof(uint32_t)) {
uint32_t data;
memcpy(&data, key, sizeof(data));
hash = __builtin_ia32_crc32si(hash, data);
key += sizeof(uint32_t);
len -= sizeof(uint32_t);
}
if (*key && *(key + 1)) {
uint16_t data;
memcpy(&data, key, sizeof(data));
hash = __builtin_ia32_crc32hi(hash, data);
key += sizeof(uint16_t);
}
/* Last byte might be the terminating NUL or the last character.
* For a hash, this doesn't matter, and shaves off a branch.
*/
hash = __builtin_ia32_crc32qi(hash, (unsigned char)*key);
return hash;
}
#ifdef __x86_64__
static inline uint64_t has_zero8(const char *ptr)
{
uint64_t v;
memcpy(&v, ptr, sizeof(v));
return ((v - 0x0101010101010101ull) & ~v & 0x8080808080808080ull);
}
#endif
static inline uint32_t has_zero4(const char *ptr)
{
uint32_t v;
memcpy(&v, ptr, sizeof(v));
return ((v - 0x01010101ul) & ~v & 0x80808080ul);
}
static unsigned int hash_crc32_new(const void *keyptr)
{
unsigned int hash = odd_constant;
const char *key = (const char *)keyptr;
#if __x86_64__
while (!has_zero8(key)) {
uint64_t data;
memcpy(&data, key, sizeof(data));
hash = (unsigned int)__builtin_ia32_crc32di(hash, data);
key += sizeof(uint64_t);
}
#endif /* __x86_64__ */
while (!has_zero4(key)) {
uint32_t data;
memcpy(&data, key, sizeof(data));
hash = __builtin_ia32_crc32si(hash, data);
key += sizeof(uint32_t);
}
if (*key && *(key + 1)) {
uint16_t data;
memcpy(&data, key, sizeof(data));
hash = __builtin_ia32_crc32hi(hash, data);
key += sizeof(uint16_t);
}
/* Last byte might be the terminating NUL or the last character.
* For a hash, this doesn't matter, and shaves off a branch.
*/
hash = __builtin_ia32_crc32qi(hash, (unsigned char)*key);
return hash;
}
template <unsigned int (*hash_func)(const void *ptr)>
static void bm_crc(benchmark::State& state)
{
while (state.KeepRunning()) {
benchmark::DoNotOptimize(hash_func("a"));
benchmark::DoNotOptimize(hash_func("ab"));
benchmark::DoNotOptimize(hash_func("abc"));
benchmark::DoNotOptimize(hash_func("abcde"));
benchmark::DoNotOptimize(hash_func("banana"));
benchmark::DoNotOptimize(hash_func("uma string maior"));
benchmark::DoNotOptimize(hash_func("uma string bem grande e que vai testar bem os limites"));
benchmark::DoNotOptimize(hash_func("uma string bem grande e que vai testar bem os limites"
"uma string bem grande e que vai testar bem os limites"
"uma string bem grande e que vai testar bem os limites"
"uma string bem grande e que vai testar bem os limites"
"uma string bem grande e que vai testar bem os limites"
"uma string bem grande e que vai testar bem os limites"
"uma string bem grande e que vai testar bem os limites"
"uma string bem grande e que vai testar bem os limites"
"uma string bem grande e que vai testar bem os limites"
"uma string bem grande e que vai testar bem os limites"
"uma string bem grande e que vai testar bem os limites"
"uma string bem grande e que vai testar bem os limites"
"uma string bem grande e que vai testar bem os limites"
"uma string bem grande e que vai testar bem os limites"
"uma string bem grande e que vai testar bem os limites"
"uma string bem grande e que vai testar bem os limites"
"uma string bem grande e que vai testar bem os limites"));
}
}
int main(int argc, char *argv[])
{
benchmark::RegisterBenchmark("orig", bm_crc<hash_crc32_orig>);
benchmark::RegisterBenchmark("new", bm_crc<hash_crc32_new>);
benchmark::Initialize(&argc, argv);
benchmark::RunSpecifiedBenchmarks();
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment