32 ms·

How exactly then would one declare a stack variable that is a string that is initialized to "abc", and then later has "1234" concatenated to it, so it's now "ab

How exactly then would one declare a stack variable that is a string that is initialized to "abc", and then later has "1234" concatenated to it, so it's now "abc1234", without using the heap in any way? If the answer is "you can't do that", then that's fine for Java/C#/D, but not for C.

Too 8y ago
You can't do that in C either. Without either: 1) "abc" string happens to be the last variable on the stack, good luck with that. Or 2) You pre-allocate the string to fit a bit extra, not exactly a "solution". Maybe option 1 is feasible but not really practical, i can only see it being used in extremely low level stuff with a non standard compiler and going through tons of hoops like pre-creating loop-variables used later in the function and disabling optimizer.
- drfuchs 8y ago
  char foo[9]; strcpy(foo,"abc"); strcat(foo,"1234"); And yes, that's specifically written to be awful and unsafe, but there are circumstances where you need to be close to the metal and carefully resort to more complicated variations of such things. That's what C is fairly uniquely appropriate for.
  - WalterBright 8y ago
    Your example uses three strlen's. It also is at high risk for buffer overflows. Whenever I review code like this, sure as shootin', there's an error in it in the lengths somewhere. Here's the same code using dynamic arrays: char foo[9]; foo[] = "abc"; foo[3..3+5] = "1234"; No unchecked buffer overflows, and no calls to strlen. The +5 puts the terminating 0 on.
    - drfuchs 8y ago
      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
    Your example does save on code size (but not performance, due to the 3 strlen()'s). But where it won't save on code size is when, say, one wants to retrieve just the filename from filename.ext. One has to strlen it, allocate memory, copy the memory, then remember to free it exactly once. With dynamic arrays, just return a slice.
    - kyberias 8y ago
      You say strlen() but you probably mean "code has to iterate all the string elements". This doesn't happen 3 times, though: > char foo[9]; strcpy(foo,"abc"); strcat(foo,"1234"); Strcpy has to iterate through all the elements because it copies them. This would happen regardless. It doesn't do strlen. Strcat has to find the end of the destination string, so it has to iterate (or call strlen). Then it's just strcpy again. Instead of 3 strlens, there is 1. Do you not understand how C string/arrays work, or why do you insist on 3 strlens?
      - WalterBright 8y ago
        See my other reply to this above.
      - tjoff 8y ago
        > Strcpy has to iterate through all the elements because it copies them. This would happen regardless. It doesn't do strlen. Iterate all the elements and copy a fixed size is two very different things. strcpy has to read, byte for byte, and check it for null (which is exactly what strlen does). A "real" copy would just blindly copy a chunk of memory with no other processing on it. The speed difference is huge.
        WalterBright 8y ago
        You're right. I apologize for using strlen metaphorically rather than literally.
      - jibal 8y ago
        > You say strlen() but you probably mean "code has to iterate all the string elements". Yes, but that's much more expensive than a memcpy (of the two source strings) or just knowing the length (of the string in the target buffer). > Strcpy has to iterate through all the elements because it copies them. This would happen regardless. No, it wouldn't; memcpy is generally a lot faster than strcpy. > Do you not understand how C string/arrays work Do you not understand that he's written a few C compilers, and designed and implemented a language that is known for its runtime compatibility with C? > or why do you insist on 3 strlens? Um, you already noted that he really means "code has to iterate all the string elements". What he should have said is that you have to find 3 NULs. That's an expensive operation even when you're copying the string while finding it.
  - Too 8y ago
    Ok, so pre-allocating then. That's sort of equivalent to new StringBuffer(9), except java uses the heap. Safe types doesn't stop you from doing this. You do need another length-field though, one for the allocated size and one for the used size. In c++, std::string already has this feature with the reserve/capacity functions, STL is also heap based but it is possible with some effort to pass it a stack allocator. Now c++ isn't exactly the best reference when it comes to these things either but just saying conceptually fat pointers doesn't stop you from doing these things, see WalterBrights reply for a better example.
  - bumholio 8y ago
    > there are circumstances where you need to be close to the metal and carefully resort to more complicated variations of such things. That's what C is fairly uniquely appropriate for. You can still do that in a C dialect with fat pointers. You can have strings with 5 byte chars and use 0x1337 as string terminator if that's what your metal needs. The point is, you don't have to, the compiler provides you with a sane array implementation that is adequate for 99% higher level algorithmic tasks.
- dmitrygr 8y ago
  char str[16] = "ABC";
- v_lisivka 8y ago
  #include <stdio.h> #include <string.h> int main() { const char* s1="abc"; const char* s2="1234"; char str[strlen (s1) + strlen (s2) + 1]; strcpy (str, s1); strcat (str, s2); puts(str); return 0; } $ gcc -std=c99 -Wall -Werror ./tst.c -o tst && ./tst abc1234
WalterBright 8y ago
Off the top of my head (in D syntax): char[3] s = "abc"; char* p = cast(char*)malloc(s.length + 4); assert(p != null); char[] a = p[0 .. s.length + 4]; a[0 .. 3] = s[]; a[3 .. 3+4] = "1234"; It's more verbose than necessary, but I wanted to illustrate the idea. Note how the allocation is turned into a dynamic array. Note that my proposal is not for a new memory allocation scheme for C, just a way to map data onto arrays.
- drfuchs 8y ago
  You don't seem to understand heap vs. stack. The call to malloc() does a heap allocation, and the question was "without using the heap in any way". If it makes it conceptually easier, how about a solution where the string is simply a global variable? No malloc allowed.
  - vkazanov 8y ago
    You don't seem to understand who you are arguing with :-)
  - WalterBright 8y ago
    I showed you how to do that in another reply.
  - geezerjay 8y ago
    > You don't seem to understand heap vs. stack. Please check who you are replying to. https://en.wikipedia.org/wiki/Walter_Bright https://en.wikipedia.org/wiki/Walter_Bright
  - deleted 8y ago
    [deleted]
  - jkabrg 8y ago
    WalterBright posted the following code snippet somewhere above: char foo[9]; foo[] = "abc"; foo[3..3+5] = "1234"; `foo` is an array. `foo[3..8]` is a slice, which is an object that does its own bounds-checking. I don't think the heap is used here. Another explicit example: char foo[5] = "abcd"; // still NUL-terminated, carries length aswell char[] bar = foo[2..3]; // a fat pointer with length 1 bar[0] = 'C'; printf(foo); // abCd bar[1] = 'D'// ERROR!!! bar has length 1 Note that the array `foo` is now bounds-checked, which may affect backwards-compatibility. Also, `bar` is no longer null-terminated, which means you can't do printf on it.
thermodynthrway 8y ago
That sounds like a fairly bad idea but both Java and C# let you access the stack and mess with variables from previous frames if you really want to. You can't access stack memory outside the heap hut I can't think of a use-case
- barrkel 8y ago
  C# does (via ref parameters) but Java does not - any values you mutate must logically live in the heap (or a static). Some JIT optimization may allocate an instance in the stack, I'm not counting that.

Too 8y ago

You can't do that in C either. Without either: 1) "abc" string happens to be the last variable on the stack, good luck with that. Or 2) You pre-allocate the string to fit a bit extra, not exactly a "solution". Maybe option 1 is feasible but not really practical, i can only see it being used in extremely low level stuff with a non standard compiler and going through tons of hoops like pre-creating loop-variables used later in the function and disabling optimizer.

drfuchs 8y ago
char foo[9]; strcpy(foo,"abc"); strcat(foo,"1234"); And yes, that's specifically written to be awful and unsafe, but there are circumstances where you need to be close to the metal and carefully resort to more complicated variations of such things. That's what C is fairly uniquely appropriate for.
- WalterBright 8y ago
  Your example uses three strlen's. It also is at high risk for buffer overflows. Whenever I review code like this, sure as shootin', there's an error in it in the lengths somewhere. Here's the same code using dynamic arrays: char foo[9]; foo[] = "abc"; foo[3..3+5] = "1234"; No unchecked buffer overflows, and no calls to strlen. The +5 puts the terminating 0 on.
  - drfuchs 8y ago
    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
  Your example does save on code size (but not performance, due to the 3 strlen()'s). But where it won't save on code size is when, say, one wants to retrieve just the filename from filename.ext. One has to strlen it, allocate memory, copy the memory, then remember to free it exactly once. With dynamic arrays, just return a slice.
  - kyberias 8y ago
    You say strlen() but you probably mean "code has to iterate all the string elements". This doesn't happen 3 times, though: > char foo[9]; strcpy(foo,"abc"); strcat(foo,"1234"); Strcpy has to iterate through all the elements because it copies them. This would happen regardless. It doesn't do strlen. Strcat has to find the end of the destination string, so it has to iterate (or call strlen). Then it's just strcpy again. Instead of 3 strlens, there is 1. Do you not understand how C string/arrays work, or why do you insist on 3 strlens?
    - WalterBright 8y ago
      See my other reply to this above.
    - tjoff 8y ago
      > Strcpy has to iterate through all the elements because it copies them. This would happen regardless. It doesn't do strlen. Iterate all the elements and copy a fixed size is two very different things. strcpy has to read, byte for byte, and check it for null (which is exactly what strlen does). A "real" copy would just blindly copy a chunk of memory with no other processing on it. The speed difference is huge.
      - WalterBright 8y ago
        You're right. I apologize for using strlen metaphorically rather than literally.
    - jibal 8y ago
      > You say strlen() but you probably mean "code has to iterate all the string elements". Yes, but that's much more expensive than a memcpy (of the two source strings) or just knowing the length (of the string in the target buffer). > Strcpy has to iterate through all the elements because it copies them. This would happen regardless. No, it wouldn't; memcpy is generally a lot faster than strcpy. > Do you not understand how C string/arrays work Do you not understand that he's written a few C compilers, and designed and implemented a language that is known for its runtime compatibility with C? > or why do you insist on 3 strlens? Um, you already noted that he really means "code has to iterate all the string elements". What he should have said is that you have to find 3 NULs. That's an expensive operation even when you're copying the string while finding it.
- Too 8y ago
  Ok, so pre-allocating then. That's sort of equivalent to new StringBuffer(9), except java uses the heap. Safe types doesn't stop you from doing this. You do need another length-field though, one for the allocated size and one for the used size. In c++, std::string already has this feature with the reserve/capacity functions, STL is also heap based but it is possible with some effort to pass it a stack allocator. Now c++ isn't exactly the best reference when it comes to these things either but just saying conceptually fat pointers doesn't stop you from doing these things, see WalterBrights reply for a better example.
- bumholio 8y ago
  > there are circumstances where you need to be close to the metal and carefully resort to more complicated variations of such things. That's what C is fairly uniquely appropriate for. You can still do that in a C dialect with fat pointers. You can have strings with 5 byte chars and use 0x1337 as string terminator if that's what your metal needs. The point is, you don't have to, the compiler provides you with a sane array implementation that is adequate for 99% higher level algorithmic tasks.
dmitrygr 8y ago
char str[16] = "ABC";
v_lisivka 8y ago
#include <stdio.h> #include <string.h> int main() { const char* s1="abc"; const char* s2="1234"; char str[strlen (s1) + strlen (s2) + 1]; strcpy (str, s1); strcat (str, s2); puts(str); return 0; } $ gcc -std=c99 -Wall -Werror ./tst.c -o tst && ./tst abc1234

WalterBright 8y ago

Off the top of my head (in D syntax): char[3] s = "abc"; char* p = cast(char*)malloc(s.length + 4); assert(p != null); char[] a = p[0 .. s.length + 4]; a[0 .. 3] = s[]; a[3 .. 3+4] = "1234"; It's more verbose than necessary, but I wanted to illustrate the idea. Note how the allocation is turned into a dynamic array. Note that my proposal is not for a new memory allocation scheme for C, just a way to map data onto arrays.

drfuchs 8y ago
You don't seem to understand heap vs. stack. The call to malloc() does a heap allocation, and the question was "without using the heap in any way". If it makes it conceptually easier, how about a solution where the string is simply a global variable? No malloc allowed.
- vkazanov 8y ago
  You don't seem to understand who you are arguing with :-)
- WalterBright 8y ago
  I showed you how to do that in another reply.
- geezerjay 8y ago
  > You don't seem to understand heap vs. stack. Please check who you are replying to. https://en.wikipedia.org/wiki/Walter_Bright https://en.wikipedia.org/wiki/Walter_Bright
- deleted 8y ago
  [deleted]
- jkabrg 8y ago
  WalterBright posted the following code snippet somewhere above: char foo[9]; foo[] = "abc"; foo[3..3+5] = "1234"; `foo` is an array. `foo[3..8]` is a slice, which is an object that does its own bounds-checking. I don't think the heap is used here. Another explicit example: char foo[5] = "abcd"; // still NUL-terminated, carries length aswell char[] bar = foo[2..3]; // a fat pointer with length 1 bar[0] = 'C'; printf(foo); // abCd bar[1] = 'D'// ERROR!!! bar has length 1 Note that the array `foo` is now bounds-checked, which may affect backwards-compatibility. Also, `bar` is no longer null-terminated, which means you can't do printf on it.

thermodynthrway 8y ago

That sounds like a fairly bad idea but both Java and C# let you access the stack and mess with variables from previous frames if you really want to. You can't access stack memory outside the heap hut I can't think of a use-case

barrkel 8y ago
C# does (via ref parameters) but Java does not - any values you mutate must logically live in the heap (or a static). Some JIT optimization may allocate an instance in the stack, I'm not counting that.