Original Post
I have two 4-byte strings (char[]). Is it sufficient to compare them like this:
*(__int32 *)str1 == *(__int32 *)str2
🔒 Locked
Fast string comparison
Advertisement
Yes, but only if they are exactly four bytes (or three bytes and a terminating \0). Also note that __int32 is not portable.
This seems like something that is bound to introduce bugs in your code, the speed up is probably not worth it. Don't use this unless you really have to; and the profiler indicates that it indeed speeds your program up significantly.
This seems like something that is bound to introduce bugs in your code, the speed up is probably not worth it. Don't use this unless you really have to; and the profiler indicates that it indeed speeds your program up significantly.
That'll die on some 64 bit processors if the char arrays are not aligned to a 4 byte boundry AFAIK, not to mention the fact that it's really really brittle. Just use strcmp. The difference between this ugly hack and strcmp will be minimal in terms of preformance, or if it isn't, you'll get far greater benifit from upgrading your compiler to one that WILL have minimal difference between the two.
If they're supposed to be numbers, store them as numbers in the first place. If they're supposed to be strings, then this micro-micro-micro optimization of yours is at best pointless, at worst going to cause you hours on end of debugging (more time than will ever be saved total by the micro-micro-micro optimization) as you try and figure out why your code crashes, having long frogotten you limited your code to 4 byte strings.
If they're supposed to be numbers, store them as numbers in the first place. If they're supposed to be strings, then this micro-micro-micro optimization of yours is at best pointless, at worst going to cause you hours on end of debugging (more time than will ever be saved total by the micro-micro-micro optimization) as you try and figure out why your code crashes, having long frogotten you limited your code to 4 byte strings.
It is not portable (you should write it with reinterpret_cast's if you're doing C++).
But it IS a valuable optimization, and if it proves efficient, no reason not to use it. Don't listen to correctness integrists! Listen to us performance integrists! ;)
Of course you should do this :
But it IS a valuable optimization, and if it proves efficient, no reason not to use it. Don't listen to correctness integrists! Listen to us performance integrists! ;)
Of course you should do this :
bool result = *reinterpret_cast<__int32*>(str1) == *reinterpret_cast<__int32*>(str2);assert (result == !strcmp (str1, str2));Quote:If he really wants to get away with that then he should add four more asserts on top of that...
Original post by Tramboi
It is not portable (you should write it with reinterpret_cast's if you're doing C++).
But it IS a valuable optimization, and if it proves efficient, no reason not to use it. Don't listen to correctness integrists! Listen to us performance integrists! ;)
Of course you should do this :
*** Source Snippet Removed ***
assert (strlen(str1) == 3);assert (strlen(str2) == 3);assert (sizeof(str1[0]) == 1);assert (sizeof(str2[0]) == 1);*reinterpret_cast<__int32*>(str1) == *reinterpret_cast<__int32*>(str2);assert (result == !strcmp (str1, str2));
The asserts do exactly diddly in a release build of his program. If either string comes from user input, file io, etc, etc then he's asking for trouble. That is of course in addition to the trouble of getting possible crashes on non-x86 cpus, possible crashes on x86 if one of the strings happens to lie at the end of a committed memory region and the string is shorter than 3 characters, etc, etc. Basically unless you tightly control every facet of how these strings are allocated then you shouldn't do it and you probably shouldn't do it anyway.
There are a couple ways to speed up strings comparisons assuming you've used a profiler to show that the perf of strings comparisons actually means anything. The first is to change your algorithm to not do so many comparisons in the first place. Another is to generate hashs for your strings and use the hash to quickly eliminate non-matches. Another is to google for "efficient string comparison" and check out the tons of articles.
There are a couple ways to speed up strings comparisons assuming you've used a profiler to show that the perf of strings comparisons actually means anything. The first is to change your algorithm to not do so many comparisons in the first place. Another is to generate hashs for your strings and use the hash to quickly eliminate non-matches. Another is to google for "efficient string comparison" and check out the tons of articles.
If your program is completely algorithmically optimized (it's not) and this string comparison really is a bottleneck (it won't be), then my advice would be to create an entire wrapper class around the whole shebang:
class four_byte_string { char data[4]; //optionally replace with a forcibly aligned typepublic: four_byte_string() { std::fill( data , data + 4 , '\0' ); } four_byte_string( const four_byte_string & other ) { std::copy( other.data , other.data + 4 , data ); } four_byte_string( const char * string ) { size_t string_length = std::strlen( string ); if ( string_length > 4 ) throw std::runtime_error( "four_byte_string: more than 4 bytes foo!!!" ); std::copy( string , string + string_length , data ); std::fill( data + string_length , data + 4 , '\0' ); } four_byte_string( const std::string & string ) { size_t string_length = string.size(); if ( string_length > 4 ) throw std::runtime_error( "four_byte_string: more than 4 bytes foo!!!" ); std::copy( string.begin() , string.end() , data ); std::fill( data + string_length , data + 4 , '\0' ); } four_byte_string & operator=( const four_byte_string & other ) { std::copy( other.data , other.data + 4 , data ); return *this; } friend bool operator==( const four_byte_string & lhs , const four_byte_string & rhs ) { return std::equal( lhs.data , lhs.data + 4 , rhs.data ); } friend bool operator!=( const four_byte_string & lhs , const four_byte_string & rhs ) { return !(lhs == rhs); } friend bool operator<( const four_byte_string & lhs , const four_byte_string & rhs ) { return std::lexicographical_compare( lhs.data , lhs.data + 4 , rhs.data , rhs.data + 4 ); }};Quote:
Original post by Anon Mike
The asserts do exactly diddly in a release build of his program. If either string comes from user input, file io, etc, etc then he's asking for trouble. That is of course in addition to the trouble of getting possible crashes on non-x86 cpus, possible crashes on x86 if one of the strings happens to lie at the end of a committed memory region and the string is shorter than 3 characters, etc, etc. Basically unless you tightly control every facet of how these strings are allocated then you shouldn't do it and you probably shouldn't do it anyway.
I did specify it wasn't portable, didn't I?
If you don't have guarantees about your data, just test and throw an exception, and be a bit slower! Or just demote the test to an upper level where you can make a formal proof...
Do you check your inputs in every routine in release? I don't!
I don't send rockets to the moon, I just program videogames :)
Quote:
There are a couple ways to speed up strings comparisons assuming you've used a profiler to show that the perf of strings comparisons actually means anything. The first is to change your algorithm to not do so many comparisons in the first place. Another is to generate hashs for your strings and use the hash to quickly eliminate non-matches. Another is to google for "efficient string comparison" and check out the tons of articles.
Why do you *by default* assume people have not profiled and are not optimizing the good stuff in their code?
I get a little tired about seeing always the same stuff about profiling, code safety, algorithms before micro-optimizations and so on...
Yes, it is nice to remind what is obvious, but...
...do you really want to use a standard string hash function for zero-terminated 3 chars strings (or const-4 bytes array) in a performance intensive part of your code?
(This kind of strings are often used to generate readable 32 bits RTTI ids)
I wouldn't if I had correct guarantee about the input data. Which you *can* get if you take proper care.
So let's avoid the generic "Profile first, optimize if they point a gun at you", and let's discuss the specifics of the post :)
(Btw, this is not intended to be a flame!)
Quote:It's the default assumption because it's the common case. People that are educated about optimization seem to just do it rather than ask here about possibilities. Also, most of the optimization books that get around seem to be older ones (ie mostly 486 or prior, rarely pentium 1) that cover micro-optimizations because at the time the book was written they weren't a bad idea.
Original post by Tramboi
[...]Why do you *by default* assume people have not profiled and are not optimizing the good stuff in their code?[...]
Quote:
Original post by Tramboi
Why do you *by default* assume people have not profiled and are not optimizing the good stuff in their code?
Because 99.9% of posters here on GameDev have not.
That, and the 0.1% that have explicitly state this in their post because they know they're posting in a forum frequented by the optimizingly-challanged.
Not to put down the optimizingly-challanged - we all are or were at one point.
Quote:
So let's avoid the generic "Profile first, optimize if they point a gun at you",
No, let's not avoid them. People don't read FAQs, and as such these generic answers are very important in educating those who are new to this aspect of programming about how to do optimizing right.
I don't think these answers are even in the GD FAQ, although I could be wrong.
Topic Locked
This topic has been locked by a moderator. New replies are not allowed.
Sign in to reply to this topic.
Advertisement