Timeline for Determining if one string occurs at the end of another
Current License: CC BY-SA 3.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Sep 10, 2013 at 8:30 | comment | added | Frerich Raabe |
@asveikau: Yeah, the point is: if you fuse the loops, you can pull the tlen > slen check into the loop. In your code, imagine if t is 1048576 bytes and s is just two bytes. As it is, the strlen(t) call will walk the entire t string. If you fuse the loops and pull in the tlen > slen check you wouldn't need to compute the exact length of t if you can tell that it's longer than s. The if is quite simple too, so the branch predictor of the processor should have an easy time with it.
|
|
| Sep 9, 2013 at 22:34 | comment | added | asveikau |
@FrerichRaabe - I agree that there could be performance benefits to a single-pass rather than doing both strlen and strcmp. OTOH it might be that your libc's string functions have crazy platform-specific optimizations that you won't be able to beat. Or, for most common data sizes, maybe there'd be no difference at all. And in big-O terms a cost of N and 2N is still O(N).
|
|
| Sep 9, 2013 at 21:30 | comment | added | Frerich Raabe |
Writing strlen yourself has the potential of fusing the loops, i.e. you could calculate the length of both strings in a single loop and bail out immediately if you notice that s is shorter than t instead of computing the exact length of t in all cases.
|
|
| May 21, 2011 at 1:28 | comment | added | asveikau | @grok12 correct. | |
| May 20, 2011 at 21:33 | comment | added | grok12 | Thx, asveikau, good points. I guess that !s will be true is s is null because a null pointer points to address 0, right? | |
| May 20, 2011 at 15:41 | history | edited | asveikau | CC BY-SA 3.0 |
added 138 characters in body; added 21 characters in body; added 4 characters in body; deleted 17 characters in body
|
| May 20, 2011 at 15:27 | history | edited | asveikau | CC BY-SA 3.0 |
added 138 characters in body; added 25 characters in body
|
| May 20, 2011 at 15:21 | history | answered | asveikau | CC BY-SA 3.0 |