4 ms·

The proposal here is way too vague. And if you flesh it out, things start to fall apart: If nul-termination of strings is gone, does that mean that the fat poin

The proposal here is way too vague. And if you flesh it out, things start to fall apart: 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"? 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)? 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? 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.

WalterBright 8y ago
I happened to know the idea does work, and has been working in D for 18 years now. > 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]; The compiler can insert checks that the slice[] lies within the bounds of array[]. > 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]; > How about a pointer to a sequence of elements? 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.
- drfuchs 8y ago
  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.
alphaglosined 8y ago
This article was not created based upon theory. 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);
_ph_ 8y ago
It would be 2/3rds of a Go slice. You have a fat pointer with the capacity of the array it is pointing to. If you want to implement shorter strings, you would have to store the length independently, or use 0 termination. You still would have the length information as a safeguard of overflowing the array. You still could do everything, what you can do with current C strings, just safer. One could have fat pointers to array elements to, just with an accordingly shorter capacity. 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.
Too 8y ago
Can't see how this would affect string concatenation negatively compared to plain char? The problem with java string is that it's pre-allocated to the exact length, normally char-strings are also that. They don't magically make things faster just because they are missing a length-field, quite the contrary actually because now you need to iterate it twice to concatenate two strings without a StringBuffer equivalent, once to figure out the length of the result so you can allocate the correct size and once to do the actual copy. 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.
GlitchMr 8y ago
> The proposal here is way too vague. And if you flesh it out, things start to fall apart 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.
- pjmlp 8y ago
  > No, it's not, those ideas were implemented in practice in D and Rust, and there are no real issues with those. 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.
fnord123 8y ago
>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"? 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.
jacinabox 8y ago
I tried implementing a scheme like this once. What you do for efficiency is allocate some extra header space with the array size, and access it with negative pointer offsets. You pass to fat pointers if asked to take slices of the array. This way the common use case has good locality. The way you get things onto the stack is with a macro, which preallocates and initializes the array with the (statically known) array length.

WalterBright 8y ago

I happened to know the idea does work, and has been working in D for 18 years now. > 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]; The compiler can insert checks that the slice[] lies within the bounds of array[]. > 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]; > How about a pointer to a sequence of elements? 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.

drfuchs 8y ago
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.

alphaglosined 8y ago

This article was not created based upon theory. 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);

_ph_ 8y ago

It would be 2/3rds of a Go slice. You have a fat pointer with the capacity of the array it is pointing to. If you want to implement shorter strings, you would have to store the length independently, or use 0 termination. You still would have the length information as a safeguard of overflowing the array. You still could do everything, what you can do with current C strings, just safer. One could have fat pointers to array elements to, just with an accordingly shorter capacity. 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.

Too 8y ago

Can't see how this would affect string concatenation negatively compared to plain char? The problem with java string is that it's pre-allocated to the exact length, normally char-strings are also that. They don't magically make things faster just because they are missing a length-field, quite the contrary actually because now you need to iterate it twice to concatenate two strings without a StringBuffer equivalent, once to figure out the length of the result so you can allocate the correct size and once to do the actual copy. 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.

GlitchMr 8y ago

> The proposal here is way too vague. And if you flesh it out, things start to fall apart 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.

pjmlp 8y ago
> No, it's not, those ideas were implemented in practice in D and Rust, and there are no real issues with those. 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.

fnord123 8y ago

>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"? 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.

jacinabox 8y ago

I tried implementing a scheme like this once. What you do for efficiency is allocate some extra header space with the array size, and access it with negative pointer offsets. You pass to fat pointers if asked to take slices of the array. This way the common use case has good locality. The way you get things onto the stack is with a macro, which preallocates and initializes the array with the (statically known) array length.