Skip to content

Instantly share code, notes, and snippets.

@nlguillemot
Created July 20, 2012 06:55
Show Gist options
  • Save nlguillemot/3149159 to your computer and use it in GitHub Desktop.
Save nlguillemot/3149159 to your computer and use it in GitHub Desktop.
comparison of constexpr hashed string with assembly
#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;
}
}
.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
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