/* SPDX-License-Identifier: GPL-3.0-or-later */ #include #include #include #include #include #include #define likely(x) __builtin_expect(!!(x), 1) #define unlikely(x) __builtin_expect(!!(x), 0) #define simple_hash(name) ({ \ register unsigned char *__hash_source = (unsigned char *)(name); \ register uint32_t __hash_value = 0x811c9dc5; \ while (*__hash_source) { \ __hash_value *= 16777619; \ __hash_value ^= (uint32_t) *__hash_source++; \ } \ __hash_value; \ }) static inline uint32_t simple_hash2(const char *name) { register unsigned char *s = (unsigned char *)name; register uint32_t hval = 0x811c9dc5; while (*s) { hval *= 16777619; hval ^= (uint32_t) *s++; } return hval; } static inline unsigned long long fast_strtoull(const char *s) { register unsigned long long n = 0; register char c; for(c = *s; c >= '0' && c <= '9' ; c = *(++s)) { n *= 10; n += c - '0'; // n = (n << 1) + (n << 3) + (c - '0'); } return n; } static uint32_t cache_hash = 0; static uint32_t rss_hash = 0; static uint32_t rss_huge_hash = 0; static uint32_t mapped_file_hash = 0; static uint32_t writeback_hash = 0; static uint32_t dirty_hash = 0; static uint32_t swap_hash = 0; static uint32_t pgpgin_hash = 0; static uint32_t pgpgout_hash = 0; static uint32_t pgfault_hash = 0; static uint32_t pgmajfault_hash = 0; static uint32_t inactive_anon_hash = 0; static uint32_t active_anon_hash = 0; static uint32_t inactive_file_hash = 0; static uint32_t active_file_hash = 0; static uint32_t unevictable_hash = 0; static uint32_t hierarchical_memory_limit_hash = 0; static uint32_t total_cache_hash = 0; static uint32_t total_rss_hash = 0; static uint32_t total_rss_huge_hash = 0; static uint32_t total_mapped_file_hash = 0; static uint32_t total_writeback_hash = 0; static uint32_t total_dirty_hash = 0; static uint32_t total_swap_hash = 0; static uint32_t total_pgpgin_hash = 0; static uint32_t total_pgpgout_hash = 0; static uint32_t total_pgfault_hash = 0; static uint32_t total_pgmajfault_hash = 0; static uint32_t total_inactive_anon_hash = 0; static uint32_t total_active_anon_hash = 0; static uint32_t total_inactive_file_hash = 0; static uint32_t total_active_file_hash = 0; static uint32_t total_unevictable_hash = 0; char *strings[] = { "cache", "rss", "rss_huge", "mapped_file", "writeback", "dirty", "swap", "pgpgin", "pgpgout", "pgfault", "pgmajfault", "inactive_anon", "active_anon", "inactive_file", "active_file", "unevictable", "hierarchical_memory_limit", "total_cache", "total_rss", "total_rss_huge", "total_mapped_file", "total_writeback", "total_dirty", "total_swap", "total_pgpgin", "total_pgpgout", "total_pgfault", "total_pgmajfault", "total_inactive_anon", "total_active_anon", "total_inactive_file", "total_active_file", "total_unevictable", NULL }; unsigned long long values1[12] = { 0 }; unsigned long long values2[12] = { 0 }; unsigned long long values3[12] = { 0 }; unsigned long long values4[12] = { 0 }; unsigned long long values5[12] = { 0 }; unsigned long long values6[12] = { 0 }; #define NUMBER1 "12345678901234" #define NUMBER2 "23456789012345" #define NUMBER3 "34567890123456" #define NUMBER4 "45678901234567" #define NUMBER5 "56789012345678" #define NUMBER6 "67890123456789" #define NUMBER7 "78901234567890" #define NUMBER8 "89012345678901" #define NUMBER9 "90123456789012" #define NUMBER10 "12345678901234" #define NUMBER11 "23456789012345" // simple system strcmp() void test1() { int i; for(i = 0; strings[i] ; i++) { char *s = strings[i]; if(unlikely(!strcmp(s, "cache"))) values1[i] = strtoull(NUMBER1, NULL, 10); else if(unlikely(!strcmp(s, "rss"))) values1[i] = strtoull(NUMBER2, NULL, 10); else if(unlikely(!strcmp(s, "rss_huge"))) values1[i] = strtoull(NUMBER3, NULL, 10); else if(unlikely(!strcmp(s, "mapped_file"))) values1[i] = strtoull(NUMBER4, NULL, 10); else if(unlikely(!strcmp(s, "writeback"))) values1[i] = strtoull(NUMBER5, NULL, 10); else if(unlikely(!strcmp(s, "dirty"))) values1[i] = strtoull(NUMBER6, NULL, 10); else if(unlikely(!strcmp(s, "swap"))) values1[i] = strtoull(NUMBER7, NULL, 10); else if(unlikely(!strcmp(s, "pgpgin"))) values1[i] = strtoull(NUMBER8, NULL, 10); else if(unlikely(!strcmp(s, "pgpgout"))) values1[i] = strtoull(NUMBER9, NULL, 10); else if(unlikely(!strcmp(s, "pgfault"))) values1[i] = strtoull(NUMBER10, NULL, 10); else if(unlikely(!strcmp(s, "pgmajfault"))) values1[i] = strtoull(NUMBER11, NULL, 10); } } // inline simple_hash() with system strtoull() void test2() { int i; for(i = 0; strings[i] ; i++) { char *s = strings[i]; uint32_t hash = simple_hash2(s); if(unlikely(hash == cache_hash && !strcmp(s, "cache"))) values2[i] = strtoull(NUMBER1, NULL, 10); else if(unlikely(hash == rss_hash && !strcmp(s, "rss"))) values2[i] = strtoull(NUMBER2, NULL, 10); else if(unlikely(hash == rss_huge_hash && !strcmp(s, "rss_huge"))) values2[i] = strtoull(NUMBER3, NULL, 10); else if(unlikely(hash == mapped_file_hash && !strcmp(s, "mapped_file"))) values2[i] = strtoull(NUMBER4, NULL, 10); else if(unlikely(hash == writeback_hash && !strcmp(s, "writeback"))) values2[i] = strtoull(NUMBER5, NULL, 10); else if(unlikely(hash == dirty_hash && !strcmp(s, "dirty"))) values2[i] = strtoull(NUMBER6, NULL, 10); else if(unlikely(hash == swap_hash && !strcmp(s, "swap"))) values2[i] = strtoull(NUMBER7, NULL, 10); else if(unlikely(hash == pgpgin_hash && !strcmp(s, "pgpgin"))) values2[i] = strtoull(NUMBER8, NULL, 10); else if(unlikely(hash == pgpgout_hash && !strcmp(s, "pgpgout"))) values2[i] = strtoull(NUMBER9, NULL, 10); else if(unlikely(hash == pgfault_hash && !strcmp(s, "pgfault"))) values2[i] = strtoull(NUMBER10, NULL, 10); else if(unlikely(hash == pgmajfault_hash && !strcmp(s, "pgmajfault"))) values2[i] = strtoull(NUMBER11, NULL, 10); } } // statement expression simple_hash(), system strtoull() void test3() { int i; for(i = 0; strings[i] ; i++) { char *s = strings[i]; uint32_t hash = simple_hash(s); if(unlikely(hash == cache_hash && !strcmp(s, "cache"))) values3[i] = strtoull(NUMBER1, NULL, 10); else if(unlikely(hash == rss_hash && !strcmp(s, "rss"))) values3[i] = strtoull(NUMBER2, NULL, 10); else if(unlikely(hash == rss_huge_hash && !strcmp(s, "rss_huge"))) values3[i] = strtoull(NUMBER3, NULL, 10); else if(unlikely(hash == mapped_file_hash && !strcmp(s, "mapped_file"))) values3[i] = strtoull(NUMBER4, NULL, 10); else if(unlikely(hash == writeback_hash && !strcmp(s, "writeback"))) values3[i] = strtoull(NUMBER5, NULL, 10); else if(unlikely(hash == dirty_hash && !strcmp(s, "dirty"))) values3[i] = strtoull(NUMBER6, NULL, 10); else if(unlikely(hash == swap_hash && !strcmp(s, "swap"))) values3[i] = strtoull(NUMBER7, NULL, 10); else if(unlikely(hash == pgpgin_hash && !strcmp(s, "pgpgin"))) values3[i] = strtoull(NUMBER8, NULL, 10); else if(unlikely(hash == pgpgout_hash && !strcmp(s, "pgpgout"))) values3[i] = strtoull(NUMBER9, NULL, 10); else if(unlikely(hash == pgfault_hash && !strcmp(s, "pgfault"))) values3[i] = strtoull(NUMBER10, NULL, 10); else if(unlikely(hash == pgmajfault_hash && !strcmp(s, "pgmajfault"))) values3[i] = strtoull(NUMBER11, NULL, 10); } } // inline simple_hash(), if-continue checks void test4() { int i; for(i = 0; strings[i] ; i++) { char *s = strings[i]; uint32_t hash = simple_hash2(s); if(unlikely(hash == cache_hash && !strcmp(s, "cache"))) { values4[i] = strtoull(NUMBER1, NULL, 0); continue; } if(unlikely(hash == rss_hash && !strcmp(s, "rss"))) { values4[i] = strtoull(NUMBER2, NULL, 0); continue; } if(unlikely(hash == rss_huge_hash && !strcmp(s, "rss_huge"))) { values4[i] = strtoull(NUMBER3, NULL, 0); continue; } if(unlikely(hash == mapped_file_hash && !strcmp(s, "mapped_file"))) { values4[i] = strtoull(NUMBER4, NULL, 0); continue; } if(unlikely(hash == writeback_hash && !strcmp(s, "writeback"))) { values4[i] = strtoull(NUMBER5, NULL, 0); continue; } if(unlikely(hash == dirty_hash && !strcmp(s, "dirty"))) { values4[i] = strtoull(NUMBER6, NULL, 0); continue; } if(unlikely(hash == swap_hash && !strcmp(s, "swap"))) { values4[i] = strtoull(NUMBER7, NULL, 0); continue; } if(unlikely(hash == pgpgin_hash && !strcmp(s, "pgpgin"))) { values4[i] = strtoull(NUMBER8, NULL, 0); continue; } if(unlikely(hash == pgpgout_hash && !strcmp(s, "pgpgout"))) { values4[i] = strtoull(NUMBER9, NULL, 0); continue; } if(unlikely(hash == pgfault_hash && !strcmp(s, "pgfault"))) { values4[i] = strtoull(NUMBER10, NULL, 0); continue; } if(unlikely(hash == pgmajfault_hash && !strcmp(s, "pgmajfault"))) { values4[i] = strtoull(NUMBER11, NULL, 0); continue; } } } // inline simple_hash(), if-else-if-else-if (netdata default) void test5() { int i; for(i = 0; strings[i] ; i++) { char *s = strings[i]; uint32_t hash = simple_hash2(s); if(unlikely(hash == cache_hash && !strcmp(s, "cache"))) values5[i] = fast_strtoull(NUMBER1); else if(unlikely(hash == rss_hash && !strcmp(s, "rss"))) values5[i] = fast_strtoull(NUMBER2); else if(unlikely(hash == rss_huge_hash && !strcmp(s, "rss_huge"))) values5[i] = fast_strtoull(NUMBER3); else if(unlikely(hash == mapped_file_hash && !strcmp(s, "mapped_file"))) values5[i] = fast_strtoull(NUMBER4); else if(unlikely(hash == writeback_hash && !strcmp(s, "writeback"))) values5[i] = fast_strtoull(NUMBER5); else if(unlikely(hash == dirty_hash && !strcmp(s, "dirty"))) values5[i] = fast_strtoull(NUMBER6); else if(unlikely(hash == swap_hash && !strcmp(s, "swap"))) values5[i] = fast_strtoull(NUMBER7); else if(unlikely(hash == pgpgin_hash && !strcmp(s, "pgpgin"))) values5[i] = fast_strtoull(NUMBER8); else if(unlikely(hash == pgpgout_hash && !strcmp(s, "pgpgout"))) values5[i] = fast_strtoull(NUMBER9); else if(unlikely(hash == pgfault_hash && !strcmp(s, "pgfault"))) values5[i] = fast_strtoull(NUMBER10); else if(unlikely(hash == pgmajfault_hash && !strcmp(s, "pgmajfault"))) values5[i] = fast_strtoull(NUMBER11); } } // ---------------------------------------------------------------------------- struct entry { char *name; uint32_t hash; int found; void (*func)(void *data1, void *data2); void *data1; void *data2; struct entry *prev, *next; }; struct base { int iteration; int registered; int wanted; int found; struct entry *entries, *last; }; static inline void callback(void *data1, void *data2) { char *string = data1; unsigned long long *value = data2; *value = fast_strtoull(string); } static inline void callback_system_strtoull(void *data1, void *data2) { char *string = data1; unsigned long long *value = data2; *value = strtoull(string, NULL, 10); } static inline struct base *entry(struct base *base, const char *name, void *data1, void *data2, void (*func)(void *, void *)) { if(!base) base = calloc(1, sizeof(struct base)); struct entry *e = malloc(sizeof(struct entry)); e->name = strdup(name); e->hash = simple_hash2(e->name); e->data1 = data1; e->data2 = data2; e->func = func; e->prev = NULL; e->next = base->entries; if(base->entries) base->entries->prev = e; else base->last = e; base->entries = e; base->registered++; base->wanted = base->registered; return base; } static inline int check(struct base *base, const char *s) { uint32_t hash = simple_hash2(s); if(likely(!strcmp(s, base->last->name))) { base->last->found = 1; base->found++; if(base->last->func) base->last->func(base->last->data1, base->last->data2); base->last = base->last->next; if(!base->last) base->last = base->entries; if(base->found == base->registered) return 1; return 0; } // find it struct entry *e; for(e = base->entries; e ; e = e->next) if(e->hash == hash && !strcmp(e->name, s)) break; if(e == base->last) { printf("ERROR\n"); exit(1); } if(e) { // found // run it if(e->func) e->func(e->data1, e->data2); // unlink it if(e->next) e->next->prev = e->prev; if(e->prev) e->prev->next = e->next; if(base->entries == e) base->entries = e->next; } else { // not found // create it e = calloc(1, sizeof(struct entry)); e->name = strdup(s); e->hash = hash; } // link it here e->next = base->last; if(base->last) { e->prev = base->last->prev; base->last->prev = e; if(base->entries == base->last) base->entries = e; } else e->prev = NULL; if(e->prev) e->prev->next = e; base->last = e->next; if(!base->last) base->last = base->entries; e->found = 1; base->found++; if(base->found == base->registered) return 1; printf("relinked '%s' after '%s' and before '%s': ", e->name, e->prev?e->prev->name:"NONE", e->next?e->next->name:"NONE"); for(e = base->entries; e ; e = e->next) printf("%s ", e->name); printf("\n"); return 0; } static inline void begin(struct base *base) { if(unlikely(base->iteration % 60) == 1) { base->wanted = 0; struct entry *e; for(e = base->entries; e ; e = e->next) if(e->found) base->wanted++; } base->iteration++; base->last = base->entries; base->found = 0; } void test6() { static struct base *base = NULL; if(unlikely(!base)) { base = entry(base, "cache", NUMBER1, &values6[0], callback_system_strtoull); base = entry(base, "rss", NUMBER2, &values6[1], callback_system_strtoull); base = entry(base, "rss_huge", NUMBER3, &values6[2], callback_system_strtoull); base = entry(base, "mapped_file", NUMBER4, &values6[3], callback_system_strtoull); base = entry(base, "writeback", NUMBER5, &values6[4], callback_system_strtoull); base = entry(base, "dirty", NUMBER6, &values6[5], callback_system_strtoull); base = entry(base, "swap", NUMBER7, &values6[6], callback_system_strtoull); base = entry(base, "pgpgin", NUMBER8, &values6[7], callback_system_strtoull); base = entry(base, "pgpgout", NUMBER9, &values6[8], callback_system_strtoull); base = entry(base, "pgfault", NUMBER10, &values6[9], callback_system_strtoull); base = entry(base, "pgmajfault", NUMBER11, &values6[10], callback_system_strtoull); } begin(base); int i; for(i = 0; strings[i] ; i++) { if(check(base, strings[i])) break; } } void test7() { static struct base *base = NULL; if(unlikely(!base)) { base = entry(base, "cache", NUMBER1, &values6[0], callback); base = entry(base, "rss", NUMBER2, &values6[1], callback); base = entry(base, "rss_huge", NUMBER3, &values6[2], callback); base = entry(base, "mapped_file", NUMBER4, &values6[3], callback); base = entry(base, "writeback", NUMBER5, &values6[4], callback); base = entry(base, "dirty", NUMBER6, &values6[5], callback); base = entry(base, "swap", NUMBER7, &values6[6], callback); base = entry(base, "pgpgin", NUMBER8, &values6[7], callback); base = entry(base, "pgpgout", NUMBER9, &values6[8], callback); base = entry(base, "pgfault", NUMBER10, &values6[9], callback); base = entry(base, "pgmajfault", NUMBER11, &values6[10], callback); } begin(base); int i; for(i = 0; strings[i] ; i++) { if(check(base, strings[i])) break; } } // ---------------------------------------------------------------------------- // ============== // --- Poor man cycle counting. static unsigned long tsc; static void begin_tsc(void) { unsigned long a, d; asm volatile ("cpuid\nrdtsc" : "=a" (a), "=d" (d) : "0" (0) : "ebx", "ecx"); tsc = ((unsigned long)d << 32) | (unsigned long)a; } static unsigned long end_tsc(void) { unsigned long a, d; asm volatile ("rdtscp" : "=a" (a), "=d" (d) : : "ecx"); return (((unsigned long)d << 32) | (unsigned long)a) - tsc; } // =============== static unsigned long long clk; static void begin_clock() { struct timeval tv; if(unlikely(gettimeofday(&tv, NULL) == -1)) return; clk = tv.tv_sec * 1000000 + tv.tv_usec; } static unsigned long long end_clock() { struct timeval tv; if(unlikely(gettimeofday(&tv, NULL) == -1)) return -1; return clk = tv.tv_sec * 1000000 + tv.tv_usec - clk; } void main(void) { cache_hash = simple_hash("cache"); rss_hash = simple_hash("rss"); rss_huge_hash = simple_hash("rss_huge"); mapped_file_hash = simple_hash("mapped_file"); writeback_hash = simple_hash("writeback"); dirty_hash = simple_hash("dirty"); swap_hash = simple_hash("swap"); pgpgin_hash = simple_hash("pgpgin"); pgpgout_hash = simple_hash("pgpgout"); pgfault_hash = simple_hash("pgfault"); pgmajfault_hash = simple_hash("pgmajfault"); inactive_anon_hash = simple_hash("inactive_anon"); active_anon_hash = simple_hash("active_anon"); inactive_file_hash = simple_hash("inactive_file"); active_file_hash = simple_hash("active_file"); unevictable_hash = simple_hash("unevictable"); hierarchical_memory_limit_hash = simple_hash("hierarchical_memory_limit"); total_cache_hash = simple_hash("total_cache"); total_rss_hash = simple_hash("total_rss"); total_rss_huge_hash = simple_hash("total_rss_huge"); total_mapped_file_hash = simple_hash("total_mapped_file"); total_writeback_hash = simple_hash("total_writeback"); total_dirty_hash = simple_hash("total_dirty"); total_swap_hash = simple_hash("total_swap"); total_pgpgin_hash = simple_hash("total_pgpgin"); total_pgpgout_hash = simple_hash("total_pgpgout"); total_pgfault_hash = simple_hash("total_pgfault"); total_pgmajfault_hash = simple_hash("total_pgmajfault"); total_inactive_anon_hash = simple_hash("total_inactive_anon"); total_active_anon_hash = simple_hash("total_active_anon"); total_inactive_file_hash = simple_hash("total_inactive_file"); total_active_file_hash = simple_hash("total_active_file"); total_unevictable_hash = simple_hash("total_unevictable"); unsigned long i, c1 = 0, c2 = 0, c3 = 0, c4 = 0, c5 = 0, c6 = 0, c7; unsigned long max = 1000000; // let the processor get up to speed begin_clock(); for(i = 0; i <= max ;i++) test1(); c1 = end_clock(); begin_clock(); for(i = 0; i <= max ;i++) test1(); c1 = end_clock(); begin_clock(); for(i = 0; i <= max ;i++) test2(); c2 = end_clock(); begin_clock(); for(i = 0; i <= max ;i++) test3(); c3 = end_clock(); begin_clock(); for(i = 0; i <= max ;i++) test4(); c4 = end_clock(); begin_clock(); for(i = 0; i <= max ;i++) test5(); c5 = end_clock(); begin_clock(); for(i = 0; i <= max ;i++) test6(); c6 = end_clock(); begin_clock(); for(i = 0; i <= max ;i++) test7(); c7 = end_clock(); for(i = 0; i < 11 ; i++) printf("value %lu: %llu %llu %llu %llu %llu %llu\n", i, values1[i], values2[i], values3[i], values4[i], values5[i], values6[i]); printf("\n\nRESULTS\n"); printf("test1() in %lu usecs: if-else-if-else-if, simple strcmp() with system strtoull().\n" "test2() in %lu usecs: inline simple_hash() if-else-if-else-if, with system strtoull().\n" "test3() in %lu usecs: statement expression simple_hash(), system strtoull().\n" "test4() in %lu usecs: inline simple_hash(), if-continue checks, system strtoull().\n" "test5() in %lu usecs: inline simple_hash(), if-else-if-else-if, custom strtoull() (netdata default prior to ARL).\n" "test6() in %lu usecs: adaptive re-sortable list, system strtoull() (wow!)\n" "test7() in %lu usecs: adaptive re-sortable list, custom strtoull() (wow!)\n" , c1 , c2 , c3 , c4 , c5 , c6 , c7 ); }