Created
July 20, 2012 06:55
-
-
Save nlguillemot/3149159 to your computer and use it in GitHub Desktop.
comparison of constexpr hashed string with assembly
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <iostream> | |
constexpr unsigned _hash_string_recursive(unsigned hash, const char* str) | |
{ | |
return ( !*str ? hash : | |
_hash_string_recursive(((hash << 5) + hash) + *str, str + 1)); | |
} | |
constexpr unsigned hash_string(const char* str) | |
{ | |
return ( !str ? 0 : | |
_hash_string_recursive(5381, str)); | |
} | |
class HashedString | |
{ | |
public: | |
inline explicit constexpr HashedString(const char* str); | |
inline constexpr bool operator==(const HashedString& other) const; | |
inline constexpr bool operator!=(const HashedString& other) const; | |
inline constexpr bool operator<(const HashedString& other) const; | |
unsigned hash; | |
}; | |
constexpr HashedString::HashedString(const char* str): | |
hash(hash_string(str)) | |
{ | |
} | |
bool constexpr HashedString::operator==(const HashedString& other) const | |
{ | |
return hash == other.hash; | |
} | |
bool constexpr HashedString::operator!=(const HashedString& other) const | |
{ | |
return hash != other.hash; | |
} | |
bool constexpr HashedString::operator<(const HashedString& other) const | |
{ | |
return hash < other.hash; | |
} | |
static_assert(HashedString("foo") != HashedString("bar"), "compare different hashed string by key"); | |
static_assert(HashedString("foo") == HashedString("foo"), "compare identical strings by key"); | |
static_assert(HashedString("bar") < HashedString("foo"), "compare strings by key ordering"); | |
int main() | |
{ | |
HashedString foo("foo"); | |
HashedString bar("bar"); | |
if (foo != HashedString("foo")) | |
{ | |
std::cout << "foo" << std::endl; | |
} | |
else if (HashedString("foo") != bar) | |
{ | |
std::cout << "bar" << std::endl; | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
.file "hashstr.cpp" | |
.section .rodata.str1.1,"aMS",@progbits,1 | |
.LC0: | |
.string "foo" | |
.LC1: | |
.string "bar" | |
.section .text.startup,"ax",@progbits | |
.p2align 4,,15 | |
.globl main | |
.type main, @function | |
main: | |
.LFB1283: | |
.cfi_startproc | |
pushl %ebp | |
.cfi_def_cfa_offset 8 | |
.cfi_offset 5, -8 | |
movl $5381, %eax | |
movl %esp, %ebp | |
.cfi_def_cfa_register 5 | |
movl $102, %ecx | |
pushl %ebx | |
movl $.LC0, %edx | |
andl $-16, %esp | |
subl $16, %esp | |
.p2align 4,,7 | |
.p2align 3 | |
.L2: | |
movl %eax, %ebx | |
.cfi_offset 3, -12 | |
movsbl %cl, %ecx | |
sall $5, %ebx | |
addl $1, %edx | |
addl %ebx, %ecx | |
addl %ecx, %eax | |
movzbl (%edx), %ecx | |
testb %cl, %cl | |
jne .L2 | |
cmpl $193491849, %eax | |
jne .L9 | |
movl $5381, %eax | |
movl $102, %ecx | |
movl $.LC0, %edx | |
.p2align 4,,7 | |
.p2align 3 | |
.L3: | |
movl %eax, %ebx | |
movsbl %cl, %ecx | |
sall $5, %ebx | |
addl $1, %edx | |
addl %ebx, %ecx | |
addl %ecx, %eax | |
movzbl (%edx), %ecx | |
testb %cl, %cl | |
jne .L3 | |
cmpl $193487034, %eax | |
je .L4 | |
movl $.LC1, 4(%esp) | |
movl $_ZSt4cout, (%esp) | |
call _ZStlsISt11char_traitsIcEERSt13basic_ostreamIcT_ES5_PKc | |
movl %eax, (%esp) | |
call _ZSt4endlIcSt11char_traitsIcEERSt13basic_ostreamIT_T0_ES6_ | |
.L4: | |
xorl %eax, %eax | |
movl -4(%ebp), %ebx | |
leave | |
.cfi_remember_state | |
.cfi_restore 5 | |
.cfi_def_cfa 4, 4 | |
.cfi_restore 3 | |
ret | |
.L9: | |
.cfi_restore_state | |
movl $.LC0, 4(%esp) | |
movl $_ZSt4cout, (%esp) | |
call _ZStlsISt11char_traitsIcEERSt13basic_ostreamIcT_ES5_PKc | |
movl %eax, (%esp) | |
call _ZSt4endlIcSt11char_traitsIcEERSt13basic_ostreamIT_T0_ES6_ | |
jmp .L4 | |
.cfi_endproc | |
.LFE1283: | |
.size main, .-main | |
.p2align 4,,15 | |
.type _GLOBAL__sub_I_main, @function | |
_GLOBAL__sub_I_main: | |
.LFB1439: | |
.cfi_startproc | |
subl $28, %esp | |
.cfi_def_cfa_offset 32 | |
movl $_ZStL8__ioinit, (%esp) | |
call _ZNSt8ios_base4InitC1Ev | |
movl $__dso_handle, 8(%esp) | |
movl $_ZStL8__ioinit, 4(%esp) | |
movl $_ZNSt8ios_base4InitD1Ev, (%esp) | |
call __cxa_atexit | |
addl $28, %esp | |
.cfi_def_cfa_offset 4 | |
ret | |
.cfi_endproc | |
.LFE1439: | |
.size _GLOBAL__sub_I_main, .-_GLOBAL__sub_I_main | |
.section .ctors,"aw",@progbits | |
.align 4 | |
.long _GLOBAL__sub_I_main | |
.local _ZStL8__ioinit | |
.comm _ZStL8__ioinit,1,1 | |
.weakref _ZL20__gthrw_pthread_oncePiPFvvE,pthread_once | |
.weakref _ZL27__gthrw_pthread_getspecificj,pthread_getspecific | |
.weakref _ZL27__gthrw_pthread_setspecificjPKv,pthread_setspecific | |
.weakref _ZL22__gthrw_pthread_createPmPK14pthread_attr_tPFPvS3_ES3_,pthread_create | |
.weakref _ZL20__gthrw_pthread_joinmPPv,pthread_join | |
.weakref _ZL21__gthrw_pthread_equalmm,pthread_equal | |
.weakref _ZL20__gthrw_pthread_selfv,pthread_self | |
.weakref _ZL22__gthrw_pthread_detachm,pthread_detach | |
.weakref _ZL22__gthrw_pthread_cancelm,pthread_cancel | |
.weakref _ZL19__gthrw_sched_yieldv,sched_yield | |
.weakref _ZL26__gthrw_pthread_mutex_lockP15pthread_mutex_t,pthread_mutex_lock | |
.weakref _ZL29__gthrw_pthread_mutex_trylockP15pthread_mutex_t,pthread_mutex_trylock | |
.weakref _ZL31__gthrw_pthread_mutex_timedlockP15pthread_mutex_tPK8timespec,pthread_mutex_timedlock | |
.weakref _ZL28__gthrw_pthread_mutex_unlockP15pthread_mutex_t,pthread_mutex_unlock | |
.weakref _ZL26__gthrw_pthread_mutex_initP15pthread_mutex_tPK19pthread_mutexattr_t,pthread_mutex_init | |
.weakref _ZL29__gthrw_pthread_mutex_destroyP15pthread_mutex_t,pthread_mutex_destroy | |
.weakref _ZL30__gthrw_pthread_cond_broadcastP14pthread_cond_t,pthread_cond_broadcast | |
.weakref _ZL27__gthrw_pthread_cond_signalP14pthread_cond_t,pthread_cond_signal | |
.weakref _ZL25__gthrw_pthread_cond_waitP14pthread_cond_tP15pthread_mutex_t,pthread_cond_wait | |
.weakref _ZL30__gthrw_pthread_cond_timedwaitP14pthread_cond_tP15pthread_mutex_tPK8timespec,pthread_cond_timedwait | |
.weakref _ZL28__gthrw_pthread_cond_destroyP14pthread_cond_t,pthread_cond_destroy | |
.weakref _ZL26__gthrw_pthread_key_createPjPFvPvE,pthread_key_create | |
.weakref _ZL26__gthrw_pthread_key_deletej,pthread_key_delete | |
.weakref _ZL30__gthrw_pthread_mutexattr_initP19pthread_mutexattr_t,pthread_mutexattr_init | |
.weakref _ZL33__gthrw_pthread_mutexattr_settypeP19pthread_mutexattr_ti,pthread_mutexattr_settype | |
.weakref _ZL33__gthrw_pthread_mutexattr_destroyP19pthread_mutexattr_t,pthread_mutexattr_destroy | |
.ident "GCC: (Ubuntu/Linaro 4.6.3-1ubuntu5) 4.6.3" | |
.section .note.GNU-stack,"",@progbits |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
lines of interest in hashstr.s: | |
17: why is the hash magic number being moved into a register if the hashing function is already computed at compile-time? | |
17-37: if I'm not mistaken, this is the algorithm for calculating the string. Why does this code need to be executed if the answer is known in the very next line 38 after? | |
38: this is the integer representing the hashed string of "foo" | |
55: this is the integer representing the hashed string of "bar" |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment