Deutsch English Français Italiano |
<slrnva7gg6.39g.bencollver@svadhyaya.localdomain> View for Bookmarking (what is this?) Look up another Usenet article |
Path: ...!feeds.phibee-telecom.net!2.eu.feeder.erje.net!feeder.erje.net!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail From: Ben Collver <bencollver@tilde.pink> Newsgroups: comp.misc Subject: strlcpy and how CPUs can defy common sense Date: Fri, 26 Jul 2024 15:36:17 -0000 (UTC) Organization: A noiseless patient Spider Lines: 256 Message-ID: <slrnva7gg6.39g.bencollver@svadhyaya.localdomain> Injection-Date: Fri, 26 Jul 2024 17:36:18 +0200 (CEST) Injection-Info: dont-email.me; posting-host="25c82515a3793f0405007c5555736d3a"; logging-data="3051943"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX18UzezBadE+UlSEjcbOWfzX9bHkRUydp+0=" User-Agent: slrn/1.0.3 (Linux) Cancel-Lock: sha1:n/wW5GS3Oo5+79tmoYd5blm3E7s= Bytes: 11330 strlcpy and how CPUs can defy common sense ========================================== 24 Jul 2024 Recently one of my older post about strlcpy has sparked some discussion on various forums. Presumably the recently released POSIX edition had something to do with it. One particular counter-argument was raised by multiple posters - and it's an argument that I've heard before as well: * In the common case where the source string fits in to the destination buffer, strlcpy would only traverse the string once whereas strlen + memcpy would traverse it twice always. Hidden in this argument is the assumption that traversing the string once is faster. Which - to be clear - is not at all an unreasonable assumption. But is it actually true? That's the focus of today's article. <https://nrk.neocities.org/articles/not-a-fan-of-strlcpy> CPU vs common sense =================== > Computers do not have common sense. Computers are surprising. > - Tony Hoare to Lomuto The following is from openbsd, where strlcpy originated - modified a bit for brevity. size_t strlcpy(char *dst, const char *src, size_t dsize) { const char *osrc = src; size_t nleft = dsize; /* Copy as many bytes as will fit. */ if (nleft != 0) while (--nleft != 0) { if ((*dst++ = *src++) == '\0') break; } /* Not enough room in dst, add NUL and traverse rest of src. */ if (nleft == 0) { if (dsize != 0) *dst = '\0'; /* NUL-terminate dst */ while (*src++) ; } return(src - osrc - 1); /* count does not include NUL */ } It starts by copying from src to dst as much as it can, and if it has to truncate due to insufficient dst size, then traverses the rest of src in order to get the strlen(src) value for returning. And so if the source string fits, it will be traversed only once. Now if you try to take a look at the glibc implementation of strlcpy, immediately you'll notice that the first line is this... size_t src_length = strlen (src); .... followed by the rest of the code using memcpy to do the copying. This already shatters the illusion that strlcpy will traverse the string once, there's no requirement for that to happen, and as you can see in practice, one of the major libcs will always traverse the string twice, once in strlen and once in memcpy. But before you open a bug report against glibc for being inefficient, here's some benchmark number when copying a 512 byte string repeatedly in a loop: 512 byte openbsd: 242us glibc: 12us <https://gist.github.com/N-R-K/ebf096448c0a7f3fdd8b93d280747550> Perhaps the string is so small that the double traversal doesn't matter? How about a string of 1MiB? 1MiB openbsd: 501646us glibc: 31793us The situation only gets worse for the openbsd version here, not better. To be fair, this huge speed up is coming from the fact that glibc punts all the work over to strlen and memcpy which on glibc are SIMD optimized. But regardless, we can already see that doing something fast, twice - is faster than doing it once but slowly. Apples to apples ================ In order to do an apples to apples comparison I've written the following strlcpy implementation, which is pretty close to the glibc implementation except with the strlen and memcpy calls written out in for loops. size_t bespoke_strlcpy(char *dst, const char *src, size_t size) { size_t len = 0; for (; src[len] != '\0'; ++len) {} // strlen() loop if (size > 0) { size_t to_copy = len < size ? len : size - 1; for (size_t i = 0; i < to_copy; ++i) // memcpy() loop dst[i] = src[i]; dst[to_copy] = '\0'; } return len; } It's important to note that in order to do a truly apples to apples comparison, you'd need to also use -fno-builtin when compiling. Otherwise gcc will realize that the "strlen loop" can be "optimized" down to a strlen call and emit that. -fno-builtin avoids that from happening and keeps the comparison fair. So how does this version, which traverses src twice, perform against the openbsd's variant which traverses src only once? 512 byte openbsd: 237us bespoke: 139us It's almost twice as fast. How about on bigger strings? 1MiB openbsd: 488469us bespoke: 277183us Still roughly twice as fast. How come? Dependencies ============ The importance of cache misses (rightfully) gets plenty of spotlight, dependencies on the other hand are not talked about as much. Your cpu has multiple cores, and each core has multiple ports (or logic units) capable of executing instructions. Which means that if you have some instructions like this (in pseudo assembly, where upper case alphabet denotes a register): A <- add B, C X <- add Y, Z E <- add A, X The computation of A and X are independent, and thus can be executed in parallel. But computation of E requires the result of A and X and thus cannot be parallelized. This process of being able to execute independent instructions simultaneously is called instruction-level-parallelism (or ILP). And dependencies are it's kryptonite. If you try to profile the "bespoke" strlcpy version, you'll notice that nearly 100% of the cpu time is spent on the "strlen loop" while the copy loop is basically free. Indeed if you replace the "strlen loop" with an actual strlen call (reminder: that it's SIMD optimized on glibc) then the bespoke version starts competing with the glibc version quite well even though we aren't using an optimized memcpy. In order to understand why this is happening, let's look at the "strlen loop", written in a verbose manner below: len = 0; while (true) { if (src[len] == '\0') break; // <- this affects the next iteration else ++len; } In the above loop, whether or not the next iteration of the loop will execute depends on the result of the previous iteration (whether src[len] was nul or not). We pay for this in our strlen loop. But our memcpy loop is free of such loop-carried-dependencies, the current iteration happens regardless of what happened on the last iteration. for (size_t i = 0; i < to_copy; ++i) // memcpy() loop dst[i] = src[i]; // <- does NOT depend on previous iteration In the openbsd version, because the length and copy loop are fused together, whether or not the next byte will be copied depends on the byte value of the previous iteration. while (--nleft != 0) { // openbsd copy loop // <- the branch taken here affect the next iteration if ((*dst++ = *src++) == '\0') break; } ========== REMAINDER OF ARTICLE TRUNCATED ==========