> If nul-termination of strings is gone, does that mean that the fat pointers need to be three words long, so they have a "capacity" as well as a "current length"?
No. You'll still have the same issues with how memory is allocated and resized. But, once the memory is allocated, you have a safe and reliable way to access the memory without buffer overflows.
> If not, how do you manage to get string variable on the stack if its length might change? Or in a struct? How does concatenation work such that you can avoid horrible performance (think Java's String vs. StringBuffer)?
As I mentioned, it does not address allocating memory. However, it does offer one performance advantage in not having to call strlen to determine the size of the data.
> On the other hand, if the fat pointers have a length and capacity, how do I get a fat pointer to a substring that's in the middle of a given string?
In D, we call those slices. They look like this:
T[] array = ...
T[] slice = array[lower .. upper];
> Am I able to take the address of an element of an array?
Yes: `T* p = &array[3];`
> Will that be a fat pointer too?
No, it'll be regular pointer. To get a fat pointer, i.e. a slice:
slice = array[lower .. upper];
Not sure what you mean. You can get a pointer or a slice of a dynamic array.
> Can I do arithmetic on these pointers?
Yes, via the slice method outlined above.
> If not, am I forced to pass around fat array pointers as well as index values when I want to call functions to operate on pieces of the array?
No, just the slice.
> How would you write Quicksort? Heapsort?
Show me your pointer version and I'll show you an array version.
> And this doesn't even start to address questions like "how can I write an arena-allocation scheme when I need one"?
The arena will likely be an array, right? Then return slices of it.
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.
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.
char foo[9]; foo[] = "abc"; foo[3..3+5] = "1234";
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.
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/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/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);
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
I do agree with the general idea that null terminated strings are a mistake though.
Am I missing something?
[0] https://github.com/lattera/glibc/blob/master/string/strcpy.c
[1] https://github.com/lattera/glibc/blob/master/sysdeps/generic...
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.
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.
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.
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.
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.
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.
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.
With dynamic arrays, just return a slice.
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?
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.
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.
#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 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";
Note that my proposal is not for a new memory allocation scheme for C, just a way to map data onto arrays.
Please check who you are replying to.
char foo[9]; foo[] = "abc"; foo[3..3+5] = "1234";
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
Some JIT optimization may allocate an instance in the stack, I'm not counting that.
It was created based upon real world experience having designed and implemented it in D. Where all of your concerns have not been discussed in the years following that article (it was already in the language for about 8 years at that point aka the start and has been solidly proven to work in the exact same context as it would have done in C).
In D at least, you can grab the pointer by a simple .ptr and for length .length. To get a specific element, it is as you would expect &f[i] all nice and straight forward. But what if you want to create an array from malloc? In D that is easy, just slice it! malloc(len)[0 .. len]. And free is just as you would expect from above, free(array.ptr);
No, it's not, those ideas were implemented in practice in D and Rust, and there are no real issues with those. This feature could be easily implemented in C, there are no dependencies on features that C doesn't have.
> If nul-termination of strings is gone, does that mean that the fat pointers need to be three words long
No need to store the capacity. This is a slice, not a buffer. Go conflates those two for user's convenience, but this is not necessary, and in fact is waste of RAM - not an issue for Go, but it is an issue for C. For instance, `&str` in Rust is a pair of pointer to a string and its length and it works really well.
> If not, how do you manage to get string variable on the stack if its length might change? How does concatenation work such that you can avoid horrible performance (think Java's String vs. StringBuffer)?
Use your own slice buffer abstraction for that purpose. It can be implemented as a struct storing a slice and its capacity. Pass a pointer to slice buffer abstraction, if you want a function to be able to add elements to it. This is also how it works in Go, for that matter.
Slices don't define concatenation. This is C, not a high level programming language.
> Am I able to take the address of an element of an array?
Yes. `&a[3]`. It's still an array, it just knows its size.
> Will that be a fat pointer too?
No.
> How about a pointer to a sequence of elements?
Probably you could add some sort of a range access syntax. Say, something like `&a[1:3]`.
> Can I do arithmetic on these pointers?
I don't know whether pointer arithmetic should be allowed or not, but even if it shouldn't be, there is nothing to stop you from doing `&a[4]` as a replacement for `a + 4`.
> How would you write Quicksort? Heapsort?
The same way you would with a regular array. Think of it as a struct storing an array pointer and its length. If you prefer to working with pair of start/end pointers instead of pair of start and array size, then note that `end - start` is array length, so getting an end pointer is trivial.
Even older than that, those features already existed in NEWP, Mesa and Modula-2, just to pick some examples back when C was being designed still.
Don't see why you shouldn't be able to make a fat pointer point into a range inside the original array either? Just point it to an element and make the length-field shorter than the original? This is usally called array_view, span or slice in other languages.
In the end, I think the Go slices are the consequential implementation of safe fat pointers, having both the capacity and length and allowing efficient and still safe reslicing. The overhead of having 24 vs 8 bytes per pointer on a 64 bit machine should be worth it in modern times.
You don't need a fat pointer. It can be part of the memory layout on the heap. How do you think `free` knows the length of the memory you are deallocating? Because the length is on the heap snuggled in right before the actual pointer malloc returned.
Similar questions apply to general arrays, as well. Also: Am I able to take the address of an element of an array? Will that be a fat pointer too? How about a pointer to a sequence of elements? Can I do arithmetic on these pointers? If not, am I forced to pass around fat array pointers as well as index values when I want to call functions to operate on pieces of the array? How would you write Quicksort? Heapsort? And this doesn't even start to address questions like "how can I write an arena-allocation scheme when I need one"?
In short, the reason that this sort of thing hasn't appeared in C is not because nobody has thought about it, nor because the C folks are too hide-bound to accept a good idea, but rather because it's not clear that there's a real, workable, limited, concise, solution that doesn't warp the language far off into Java/C#-land. It would be great if there were, but this isn't it.