Permalink
Cannot retrieve contributors at this time
Fetching contributors…
Cannot retrieve contributors at this time
| // gcc -O3 -march=native -o simplehashing simplehashing.c | |
| #include <stdlib.h> | |
| #include <stdio.h> | |
| #include <stdint.h> | |
| #include <math.h> | |
| #include <string.h> | |
| #include <x86intrin.h> | |
| // https://github.com/php/php-src/blob/PHP-7.1/Zend/zend_string.h#L325 | |
| uint32_t phphash(const char *str, size_t len) { | |
| uint32_t hash = UINT32_C(5381); | |
| /* variant with the hash unrolled eight times */ | |
| for (; len >= 8; len -= 8) { | |
| hash = ((hash << 5) + hash) + *str++; | |
| hash = ((hash << 5) + hash) + *str++; | |
| hash = ((hash << 5) + hash) + *str++; | |
| hash = ((hash << 5) + hash) + *str++; | |
| hash = ((hash << 5) + hash) + *str++; | |
| hash = ((hash << 5) + hash) + *str++; | |
| hash = ((hash << 5) + hash) + *str++; | |
| hash = ((hash << 5) + hash) + *str++; | |
| } | |
| switch (len) { | |
| case 7: hash = ((hash << 5) + hash) + *str++; /* fallthrough... */ | |
| case 6: hash = ((hash << 5) + hash) + *str++; /* fallthrough... */ | |
| case 5: hash = ((hash << 5) + hash) + *str++; /* fallthrough... */ | |
| case 4: hash = ((hash << 5) + hash) + *str++; /* fallthrough... */ | |
| case 3: hash = ((hash << 5) + hash) + *str++; /* fallthrough... */ | |
| case 2: hash = ((hash << 5) + hash) + *str++; /* fallthrough... */ | |
| case 1: hash = ((hash << 5) + hash) + *str++; break; | |
| case 0: break; | |
| } | |
| return hash; | |
| } | |
| uint32_t phphash_alt(const char *str, size_t len) { | |
| uint32_t hash = UINT32_C(5381); | |
| /* variant with the hash unrolled eight times */ | |
| for (; len >= 8; len -= 8) { | |
| hash = (33 * hash) + *str++; | |
| hash = (33 * hash) + *str++; | |
| hash = (33 * hash) + *str++; | |
| hash = (33 * hash) + *str++; | |
| hash = (33 * hash) + *str++; | |
| hash = (33 * hash) + *str++; | |
| hash = (33 * hash) + *str++; | |
| hash = (33 * hash) + *str++; | |
| } | |
| switch (len) { | |
| case 7: hash = (33 * hash) + *str++; /* fallthrough... */ | |
| case 6: hash = (33 * hash) + *str++; /* fallthrough... */ | |
| case 5: hash = (33 * hash) + *str++; /* fallthrough... */ | |
| case 4: hash = (33 * hash) + *str++; /* fallthrough... */ | |
| case 3: hash = (33 * hash) + *str++; /* fallthrough... */ | |
| case 2: hash = (33 * hash) + *str++; /* fallthrough... */ | |
| case 1: hash = (33 * hash) + *str++; break; | |
| case 0: break; | |
| } | |
| return hash; | |
| } | |
| uint32_t phphash_withmulti(const char *str, size_t len) { | |
| uint32_t hash = UINT32_C(5381); | |
| size_t i = 0; | |
| for (; i + 3 < len; i += 4) { | |
| hash = 33 * 33 * 33 * 33 * hash | |
| + 33 * 33 * 33 * str[i] | |
| + 33 * 33 * str[i + 1] | |
| + 33 * str[i + 2] | |
| + str[i + 3]; | |
| } | |
| for (; i < len; i++) { | |
| hash = 33 * hash + str[i]; | |
| } | |
| return hash; | |
| } | |
| uint32_t phphash_withmulti_alt(const char *str, size_t len) { | |
| uint32_t hash = UINT32_C(5381); | |
| size_t i = 0; | |
| for (; i + 7 < len; i += 8) { | |
| hash = 33u * 33u * 33u * 33u * 33u * 33u * 33u * 33u * hash | |
| + 33u * 33u * 33u * 33u * 33u * 33u * 33u * str[i] | |
| + 33u * 33u * 33u * 33u * 33u * 33u * str[i + 1] | |
| + 33u * 33u * 33u * 33u * 33u * str[i + 2] | |
| + 33u * 33u * 33u * 33u * str[i + 3] | |
| + 33u * 33u * 33u * str[i + 4] | |
| + 33u * 33u * str[i + 5] | |
| + 33u * str[i + 6] | |
| + str[i + 7]; | |
| } | |
| for (; i < len; i++) { | |
| hash = 33 * hash + str[i]; | |
| } | |
| return hash; | |
| } | |
| #define RDTSC_START(cycles) \ | |
| do { \ | |
| register unsigned cyc_high, cyc_low; \ | |
| __asm volatile( \ | |
| "cpuid\n\t" \ | |
| "rdtsc\n\t" \ | |
| "mov %%edx, %0\n\t" \ | |
| "mov %%eax, %1\n\t" \ | |
| : "=r"(cyc_high), "=r"(cyc_low)::"%rax", "%rbx", "%rcx", "%rdx"); \ | |
| (cycles) = ((uint64_t)cyc_high << 32) | cyc_low; \ | |
| } while (0) | |
| #define RDTSC_FINAL(cycles) \ | |
| do { \ | |
| register unsigned cyc_high, cyc_low; \ | |
| __asm volatile( \ | |
| "rdtscp\n\t" \ | |
| "mov %%edx, %0\n\t" \ | |
| "mov %%eax, %1\n\t" \ | |
| "cpuid\n\t" \ | |
| : "=r"(cyc_high), "=r"(cyc_low)::"%rax", "%rbx", "%rcx", "%rdx"); \ | |
| (cycles) = ((uint64_t)cyc_high << 32) | cyc_low; \ | |
| } while (0) | |
| /* | |
| * Prints the best number of operations per cycle where | |
| * test is the function call, answer is the expected answer generated by | |
| * test, repeat is the number of times we should repeat and size is the | |
| * number of operations represented by test. | |
| */ | |
| #define BEST_TIME(test, expected, pre, repeat, size) \ | |
| do { \ | |
| printf("%s: ", #test); \ | |
| fflush(NULL); \ | |
| uint64_t cycles_start, cycles_final, cycles_diff; \ | |
| uint64_t min_diff = (uint64_t)-1; \ | |
| for (int i = 0; i < repeat; i++) { \ | |
| pre; \ | |
| __asm volatile("" ::: /* pretend to clobber */ "memory"); \ | |
| RDTSC_START(cycles_start); \ | |
| if(test != expected) {printf("not expected (%d , %d )",test,expected);break;} \ | |
| RDTSC_FINAL(cycles_final); \ | |
| cycles_diff = (cycles_final - cycles_start); \ | |
| if (cycles_diff < min_diff) min_diff = cycles_diff; \ | |
| } \ | |
| uint64_t S = size; \ | |
| float cycle_per_op = (min_diff) / (double)S; \ | |
| printf(" %.2f cycles per operation", cycle_per_op); \ | |
| printf("\n"); \ | |
| fflush(NULL); \ | |
| } while (0) | |
| void demo(int size) { | |
| printf("size = %d bytes \n",size); | |
| int repeat = 500; | |
| char * prec = malloc(size); | |
| for(int k = 0; k < size; ++k) prec[k] = -k; | |
| uint32_t expected = phphash(prec,size); | |
| BEST_TIME(phphash(prec,size),expected,, repeat, size); | |
| BEST_TIME(phphash_alt(prec,size),expected,, repeat, size); | |
| BEST_TIME(phphash_withmulti(prec,size),expected,, repeat, size); | |
| BEST_TIME(phphash_withmulti_alt(prec,size),expected,, repeat, size); | |
| free(prec); | |
| printf("\n"); | |
| } | |
| int main() { | |
| demo(16); | |
| demo(32); | |
| demo(64); | |
| demo(128); | |
| demo(1024); | |
| return 0; | |
| } | |