Is there any way I can make my function for testing the equality of strings even faster?
Is there any way I can make my function for testing the equality of strings even faster?
I want to learn how to write faster code in C, so I've written and am continuously optimising a function that tests the equality of two strings.
int stringsequal(register char *s1, register char *s2)
do
if(!(*s1 ^ 0)) return 1;
while(!(*(s1 ++) ^ *(s2 ++)));
return 0;
EDIT: Thanks to your feedback I have improved my code! Here is my new code:
int stringsequal(register char *s1, register char *s2)
while(1)
if(!((*s1 + *s2) ^ 0)) return 1;
if(*(s1 ++) ^ *(s2 ++)) break;
return 0;
EDIT: If I could delete this question, I would, sorry for wasting your time everyone.
strcmp
Perhaps use memcmp() instead of strcmp()?
– danglingpointer
Sep 2 at 7:46
@StoryTeller This is just a little side project I've been working on today to help me learn how to write faster code in C. It's not in any way intended to replace strcmp() in the standard library, I just want to know if further improvement is possible.
– Joseph Pilliner
Sep 2 at 7:50
Did something lead you to believe xor is faster than !=?
– Retired Ninja
Sep 2 at 8:17
Please don't vandalize your own post. You cannot delete it because you accepted an answer.
– Jim Garrison
Oct 6 at 6:10
3 Answers
3
Your first function just do not work and is wrong.
You do not the correct parameter types. Do not use register
as it has no effect at all. Register is ignored at any level of optimization. Compilers are better than me or you in micro optimizations - so help the compiler optimizer with the const
and restrict
when applicable.
register
const
restrict
The second one can be simplified.
int stringsequal1(const char *restrict s1, const char *restrict s2)
do
if(*s1 != *s2) return 0;
while(*s1++ + *s2++);
return 1;
and thew result code for both is:
int stringsequal1(const char *s1, const char *s2)
do
if(*s1 != *s2) return 0;
while(*s1++ + *s2++);
return 1;
stringsequal1:
xor edx, edx
jmp .L11
.L15:
add rdx, 1
add eax, eax
je .L14
.L11:
movsx eax, BYTE PTR [rdi+rdx]
cmp al, BYTE PTR [rsi+rdx]
je .L15
mov eax, 1
ret
.L14:
ret
int stringsequal2(register char *s1, register char *s2)
while(1)
if(!((*s1 + *s2) ^ 0)) return 1;
if(*(s1 ++) ^ *(s2 ++)) break;
return 0;
stringsequal2:
xor eax, eax
jmp .L18
.L22:
add rax, 1
cmp cl, r9b
jne .L21
.L18:
movsx r8d, BYTE PTR [rdi+rax]
movsx r9d, BYTE PTR [rsi+rax]
mov ecx, r8d
add r8d, r9d
jne .L22
mov eax, 1
ret
.L21:
xor eax, eax
ret
Is there any way I can make my function for testing the equality of strings even faster?
Faster is better, but not if it breaks functionally. Else code might as will be
// Faster but wrong functionally
int stringsequal0(register char *s1, register char *s2)
return 0;
Both of OP's strcequal()
are functionally flawed. The first reports strequal("", any_string)
as equal and the 2nd will report as equal any time the char
s add to 0. (Consider a char
in one string with a negative value).
strcequal()
strequal("", any_string)
char
char
Faster way: Yes. Rather than call your own for strequal()
, either call the standard library function strcmp()
or look to model code after one of its implementation.
strequal()
strcmp()
Conceptually, only compares needed in the loop are *s1 == *s2
and *s1 == 0
. *s2 == 0
is not needed in the loop.
*s1 == *s2
*s1 == 0
*s2 == 0
inline /* or don't inline */ int strequal1(const char *a, const char *b)
return strcmp(a,b)==0;
int strequal2(const char *s1, const char *s2)
while (*s1 && *s1 == *s2)
s1++;
s2++;
return *s1 == *s2;
In the end, only profiling will determine which is "faster". Recall, one approach may be faster with small and unlikely-math strings, while another approach may perform better with long strings the rarely differ.
Compilers are smart and crafty. Optimization compilers can analyze code and replace a calls like strcmp(s, "abc")==0
will a single 4-byte compare. Note that compilers can "cheat" and perform things, regular C code cannot rely on. The compiler may not as well understand your strequal()
to take similar advantages.
strcmp(s, "abc")==0
strequal()
I doubt very much OP can roll a solution that significantly out-performs strcmp()
with long similar strings.
strcmp()
But the question is about the efficiency godbolt.org/z/Z-GSUn
– P__J__
Sep 2 at 10:29
@P__J__ The link presents emitted code for a select processor - maybe matching OP's or not. While smaller code is often faster, it does not demo improve speed. OP is looking for faster code yet is using a broken reference. We lack a test set of strings too. Should similar strings tend to be large, multi-byte compares tend to win such profiling - yet required more set up code and often some assumptions about object layout.
– chux
Sep 2 at 10:52
You can test on other platforms as well. Less memory access is the point here
– P__J__
Sep 2 at 10:56
I appreciate what you're saying, but characters cannot have a negative value without said value being set manually
– Joseph Pilliner
Sep 2 at 11:05
@chux I've fixed that now by declaring in the header that the inputted strings must be arrays of unsigned chars
– Joseph Pilliner
Sep 2 at 12:05
I think you're current code, does not do strcmp functionality.
The loop
while(!(*(str1 ++) ^ *(str2 ++)));
does nothing.
The strcmp return an integer less than, equal to, or greater than zero if str1 is found, respectively, to be less than, to match, or be greater than str2.
your method returns 1 or zero, and does not match strcmp specification.
Beside this, I think strcmp is already optimized. using memcmp won't give better performance, is you'll need first know the length of str1, and str2. so you'll need to pass all string characters for both str1 and str2 strings.
here the implementation of glibc.
int STRCMP (const char *p1, const char *p2)
const unsigned char *s1 = (const unsigned char *) p1;
const unsigned char *s2 = (const unsigned char *) p2;
unsigned char c1, c2;
do
c1 = (unsigned char) *s1++;
c2 = (unsigned char) *s2++;
if (c1 == '')
return c1 - c2;
while (c1 == c2);
return c1 - c2;
I have corrected my question and changed the function name to better reflect its purpose. Also, I have tested the code and it does work in so far as I'm aware.
– Joseph Pilliner
Sep 2 at 8:00
try for example str1="abc", str2="abcd"
– Eliyahu M
Sep 2 at 8:22
Apologies, I was mistaken.
– Joseph Pilliner
Sep 2 at 8:40
The new code I've written fixes that issue
– Joseph Pilliner
Sep 2 at 8:58
your function is the UB wen first string is longer than the second. You will read out of bounds of the second one
– P__J__
Sep 2 at 9:06
Thanks for contributing an answer to Stack Overflow!
But avoid …
To learn more, see our tips on writing great answers.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
But avoid …
To learn more, see our tips on writing great answers.
Required, but never shown
Required, but never shown
By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.
Did you first check if
strcmp
from the standard library isn't "fast enough"?– StoryTeller
Sep 2 at 7:45