5 ms·

You seem to be confused about the implementation of C's standard string library. There are certainly not 3 strlen calls underneath a strcpy() plus a strcat() ca

You seem to be confused about the implementation of C's standard string library. There are certainly not 3 strlen calls underneath a strcpy() plus a strcat() call. But what's the mention of "terminating 0"? The article says that terminating zeros should not be needed under its proposal; and that's what I was saying didn't make sense. [Added:] So, if you didn't just happen to know that the global string variable foo contains a string that was 3 characters long, how would you concatenate "1234" to it? I don't see any way without either double-fat pointers, or terminating NUL.

vardump 8y ago
> There are certainly not 3 strlen calls underneath a strcpy() plus a strcat() call. No, but strcpy does need to check each char for NUL byte as it copies the string. And strcat will need to redo same check on the original strcpy'ied string plus the new one. So "abc" length is effectively checked twice and "1234" once. So there's some truth to the matter, even though they're not "true" strlen calls.
WalterBright 8y ago
strcpy(s1,s2) does a strlen on s2. strcat(s1,s2) does a strlen on s1 and s2. Now, two of the strlen's can be replaced with byte-by-byte copies checking for 0 for each, but that tends to lose the efficiency that a memcpy would bring, so you're pretty much suffering from it anyway. BTW, here's the strcat I wrote eons ago: https://github.com/DigitalMars/dmc/blob/master/src/CORE32/STRCAT.ASM https://github.com/DigitalMars/dmc/blob/master/src/CORE32/ST... It does do two strlen's (the repne scasb instructions). With the improvements in CPUs since there are probably better ways to write it, but that was pretty good for its day. Here's strcpy: https://github.com/DigitalMars/dmc/blob/master/src/CORE32/STRFUNC.C#L194 https://github.com/DigitalMars/dmc/blob/master/src/CORE32/ST... which does the test-every-byte method. I think Steve Russell wrote it, but I'm not sure. If there's anything efficiently implemented in a C compiler, it's memcpy. Being able to implement string processing in terms of memcpy leverages that very nicely. strcat() and strcpy() don't leverage it. Which do you think is faster (s2 is 1024 bytes long)? strcpy(s1, s2); memcpy(s1, s2, 1024); I've dramatically speeded up a lot of my code and other peoples' by replacing the strxxx functions with memcpy. It's low hanging fruit and one of the first things I look for.
- shakna 8y ago
  I'm usually one to lean on your knowledge, but looking at glibc's strcpy [0], I don't see a strlen. I do see two macros, CHECK_BOUNDS_LOW and CHECK_BOUNDS_HIGH, which get defined about here [1]. Am I missing something? [0] https://github.com/lattera/glibc/blob/master/string/strcpy.c https://github.com/lattera/glibc/blob/master/string/strcpy.c [1] https://github.com/lattera/glibc/blob/master/sysdeps/generic/bp-checks.h#L28 https://github.com/lattera/glibc/blob/master/sysdeps/generic...
  - WalterBright 8y ago
    Good question. I preface this by the fact that I am not any expert on gcc compiler internals, I am assuming how I'd do it. 1. This implementation tests every byte, as discussed in other posts here. That makes it slow. 2. This implementation is likely not used - the gcc compiler probably has an internal code sequence it emits for a strcpy.
  - iforgotpassword 8y ago
    I would've assumed glibc has a bunch of different implementations and then picks the fastest one at runtime depending on CPU capabilities, but maybe they just scrapped that since GCC has built-in versions of most string functions anyways, since it can often know or at least guess the characteristics of the input and output (length, alignment) and emit different code depending on that.
  - MikeWey 8y ago
    Seeing that the implementation relies on CHECK_BOUND_(HIGH/LOW) it's using bounded pointers, which are implemented as structs holding 3 fields. The value, the upper bound and the lower bound. That's one extra field compared to D arrays. The function still checks every byte for \0. And if i'm reading it correctly, only checks the upper bound after copying the data. And checking it before copying would require a call to strlen.
- WalterBright 8y ago
  To illustrate the advantage of memcpy, consider this inner loop possible implementation: mov EAX,[ESI] mov EBX,4[ESI] mov ECX,8[ESI] mov EDX,12[ESI] mov [EDI],EAX mov 4[EDI],EBX mov 8[EDI],ECX mov 12[EDI],EDX add ESI,16 add EDI,16 Modern processors can likely do the 4 loads and 4 stores in parallel. That can't be done with 0 terminated strings, as you have to check every byte for 0. Even worse, you have to take care not to seg fault by reading too far past the 0, as there may not be any valid memory there.
WalterBright 8y ago
The "terminating 0" is when you need it, for example when interfacing with the C standard library. D, for example, adds a terminating 0 to string literals so that they'll work with C code. For code that uses slices, the 0 is not necessary.
- drfuchs 8y ago
  So, if you don't just happen to know that the global variable "char foo[9]" currently contains a string that is 3 characters long, how would you concatenate "1234" to it in place? I don't see any way without either double-fat pointers, or terminating NUL. Non-dynamic arrays of char is just supposed to be a simplistic representation of a sort of thing that one has occasion to want to do in C that doesn't seem to fit into the proposed model without going into "old C NUL-termination" mode, or a "keep track of the string's length yourself" scheme, either of which would seem to ruin the whole thing. Thus my claim that this single feature would be hard to graft onto C in a useful, upward-compatible way. It's fine to have a language where all strings are dynamically allocated on the heap, or have an immutable known length, but that's a non-starter in the existing C universe. The point isn't that doing things D's way isn't great; the point is that there's no reasonable way to put this feature into C. Every reasonable approach to string (and pointer) safety ends up being a new language: C#, Swift, Java, etc.
  - WalterBright 8y ago
    You're trying to require this to manage memory allocation. It does not address memory allocation any more than C pointers do. Memory allocation remains up to the programmer with this proposal.
  - jibal 8y ago
    " I don't see any way without either double-fat pointers, or terminating NUL." You don't seem to have followed the discussion or the paper. The array length is known; a slice is a "fat pointer", but not "double-fat". "The point isn't that doing things D's way isn't great; the point is that there's no reasonable way to put this feature into C." You're plainly wrong; the proposal in the article does exactly that.
deleted 8y ago
[deleted]

vardump 8y ago

> There are certainly not 3 strlen calls underneath a strcpy() plus a strcat() call. No, but strcpy does need to check each char for NUL byte as it copies the string. And strcat will need to redo same check on the original strcpy'ied string plus the new one. So "abc" length is effectively checked twice and "1234" once. So there's some truth to the matter, even though they're not "true" strlen calls.

WalterBright 8y ago

strcpy(s1,s2) does a strlen on s2. strcat(s1,s2) does a strlen on s1 and s2. Now, two of the strlen's can be replaced with byte-by-byte copies checking for 0 for each, but that tends to lose the efficiency that a memcpy would bring, so you're pretty much suffering from it anyway. BTW, here's the strcat I wrote eons ago: https://github.com/DigitalMars/dmc/blob/master/src/CORE32/STRCAT.ASM https://github.com/DigitalMars/dmc/blob/master/src/CORE32/ST... It does do two strlen's (the repne scasb instructions). With the improvements in CPUs since there are probably better ways to write it, but that was pretty good for its day. Here's strcpy: https://github.com/DigitalMars/dmc/blob/master/src/CORE32/STRFUNC.C#L194 https://github.com/DigitalMars/dmc/blob/master/src/CORE32/ST... which does the test-every-byte method. I think Steve Russell wrote it, but I'm not sure. If there's anything efficiently implemented in a C compiler, it's memcpy. Being able to implement string processing in terms of memcpy leverages that very nicely. strcat() and strcpy() don't leverage it. Which do you think is faster (s2 is 1024 bytes long)? strcpy(s1, s2); memcpy(s1, s2, 1024); I've dramatically speeded up a lot of my code and other peoples' by replacing the strxxx functions with memcpy. It's low hanging fruit and one of the first things I look for.

shakna 8y ago
I'm usually one to lean on your knowledge, but looking at glibc's strcpy [0], I don't see a strlen. I do see two macros, CHECK_BOUNDS_LOW and CHECK_BOUNDS_HIGH, which get defined about here [1]. Am I missing something? [0] https://github.com/lattera/glibc/blob/master/string/strcpy.c https://github.com/lattera/glibc/blob/master/string/strcpy.c [1] https://github.com/lattera/glibc/blob/master/sysdeps/generic/bp-checks.h#L28 https://github.com/lattera/glibc/blob/master/sysdeps/generic...
- WalterBright 8y ago
  Good question. I preface this by the fact that I am not any expert on gcc compiler internals, I am assuming how I'd do it. 1. This implementation tests every byte, as discussed in other posts here. That makes it slow. 2. This implementation is likely not used - the gcc compiler probably has an internal code sequence it emits for a strcpy.
- iforgotpassword 8y ago
  I would've assumed glibc has a bunch of different implementations and then picks the fastest one at runtime depending on CPU capabilities, but maybe they just scrapped that since GCC has built-in versions of most string functions anyways, since it can often know or at least guess the characteristics of the input and output (length, alignment) and emit different code depending on that.
- MikeWey 8y ago
  Seeing that the implementation relies on CHECK_BOUND_(HIGH/LOW) it's using bounded pointers, which are implemented as structs holding 3 fields. The value, the upper bound and the lower bound. That's one extra field compared to D arrays. The function still checks every byte for \0. And if i'm reading it correctly, only checks the upper bound after copying the data. And checking it before copying would require a call to strlen.
WalterBright 8y ago
To illustrate the advantage of memcpy, consider this inner loop possible implementation: mov EAX,[ESI] mov EBX,4[ESI] mov ECX,8[ESI] mov EDX,12[ESI] mov [EDI],EAX mov 4[EDI],EBX mov 8[EDI],ECX mov 12[EDI],EDX add ESI,16 add EDI,16 Modern processors can likely do the 4 loads and 4 stores in parallel. That can't be done with 0 terminated strings, as you have to check every byte for 0. Even worse, you have to take care not to seg fault by reading too far past the 0, as there may not be any valid memory there.

WalterBright 8y ago

The "terminating 0" is when you need it, for example when interfacing with the C standard library. D, for example, adds a terminating 0 to string literals so that they'll work with C code. For code that uses slices, the 0 is not necessary.

drfuchs 8y ago
So, if you don't just happen to know that the global variable "char foo[9]" currently contains a string that is 3 characters long, how would you concatenate "1234" to it in place? I don't see any way without either double-fat pointers, or terminating NUL. Non-dynamic arrays of char is just supposed to be a simplistic representation of a sort of thing that one has occasion to want to do in C that doesn't seem to fit into the proposed model without going into "old C NUL-termination" mode, or a "keep track of the string's length yourself" scheme, either of which would seem to ruin the whole thing. Thus my claim that this single feature would be hard to graft onto C in a useful, upward-compatible way. It's fine to have a language where all strings are dynamically allocated on the heap, or have an immutable known length, but that's a non-starter in the existing C universe. The point isn't that doing things D's way isn't great; the point is that there's no reasonable way to put this feature into C. Every reasonable approach to string (and pointer) safety ends up being a new language: C#, Swift, Java, etc.
- WalterBright 8y ago
  You're trying to require this to manage memory allocation. It does not address memory allocation any more than C pointers do. Memory allocation remains up to the programmer with this proposal.
- jibal 8y ago
  " I don't see any way without either double-fat pointers, or terminating NUL." You don't seem to have followed the discussion or the paper. The array length is known; a slice is a "fat pointer", but not "double-fat". "The point isn't that doing things D's way isn't great; the point is that there's no reasonable way to put this feature into C." You're plainly wrong; the proposal in the article does exactly that.

deleted 8y ago

[deleted]