In my personal experience, "a bit more than a pointer" works best as a pair of (start, end) pointers (where "end" points to just beyond the last element.) The most obvious reasons for this are:
- slices become a total non-issue since a pair of (start, end) already is a slice and you can just move start and end.
- comparing against an end pointer is generally easier than adding up a length value first, particularly if you're slicing at the same time.
- the end pointer value is independent of the array element type, so if you e.g. cast to uint8_t * (which arguably you shouldn't in most cases) it stays exactly the same. If you store a count you need to adjust a multiplier. If you store a byte length, you need to do a lot of divides or casts to deal with pointer arithmetics.
#define is ==
#define isnt !=
#define not !
#define and &&
#define or ||
#define in ,
P.S.: This also is a "try to invent a new programming language without inventing a new programming language" thing. Have your cake and eat it... either it's C or it isn't, and this library is leaving the space of "normal" C.
I don’t think you’re too far off with ‘leaving the space of normal C’, but I think it may help to see the context from which the author was coming when writing Cello [1] and evaluating it in that context.
It’s been a while since I watched the talk but I believe his intention was to do just that, to push the bounds of what could be done in a header file purely for the fun of it. The second half of the talk specifically addresses the “why are you doing this?” in quite a charming way.
Twice: once for a CTF challenge that stripped out certain symbols, and one other time when I set up an emulator with a sketchy key map and didn’t want to bother figuring out what those symbols were mapped to.
I've only seen wrong use: CS students working on a project in C++, using "and" and "or" as identifiers (which their local MSVC compiler apparently was cool with) and then being surprised that the course's testing environment (using gcc) found some errors.
Hah - I kid you not, I have the reverse problem! I work a lot with both C and Python (embedded interpreter & CPython extensions) and whenever I switch from a stretch of C coding to doing some Python, I catch myself typing "&&" and "||" instead of "and" and "or" :D
(C is my "native" language, so it doesn't really happen the other way around, but that's just me)
But honestly, I'm pretty sure we can call iso646.h "fringe" ;)
Curiously, & and | are occasionally useful in Python. They do work properly with booleans, so the difference compared to "and" and "or" is that you don't get short circuiting, which in some very rare cases you might not want. ^ is less useful because it's almost the same as != (except stricter about types) - but it documents the intent more clearly.
There’s a fair bit of debate about the impact of learning specific programming styles as your first language. Quite a few people would argue that learning functional programming first is a benefit to understanding the concept of state and how to write clean code, even if you end up using something less pure.
Certainly, speaking as someone brought up on imperative and later OO code, it took a fair bit of unlearning to understand functional programming, and I still have no clue about type theory.
It's not UB to #include standard headers that do such things. It is UB to #undef or redefine them yourself, though. And it looks like <stdbool.h> gets an explicit exemption, at least in C11:
"Notwithstanding the provisions of 7.1.3, a program may undefine and perhaps then redefine the macros bool, true, and false"
I guess it's because defining these was so common even before C99. But there's no similar verbiage for <iso646.h>, so...
Yet curiously absent from that quoted comment is anything about it being a problem, which you nonetheless ask about. I wonder if more context or a more well-intentioned reading is the solution? ;)
I read and reread it and I honestly don't understand how it is possible to come up with an interpretation where that is not seen as an issue by the author
I'll admit I've never written more than small programs in C, but the criticism that this "isn't C" isn't a fair criticism to me. He's not doing anything more than any other library can do, were he to write a compiler that mapped directly to really boring C, would it be more or less C than this? I don't feel like those questions are useful. We need experiments like this, and for me personally, cello was a revelation when it was posted here years ago. There are no rules that say you can't do it.
I know he's doing a little hackiness by placing the size before the start of the object, but they also take that approach here (https://www.piumarta.com/software/cola/objmodel2.pdf) so maybe it's not that uncommon. How would you do the dual pointer setup? Is there any overhead from that, or is it small enough to not worry about?
The "isn't C" argument is more about the library as a whole, not specifically about the fat pointer suggestions. (Please look at the github repo, IMHO it's obvious.)
Placing a length "before" a pointer is perfectly fine on a _technical_ level. It's also how glibc's malloc works, it has its own data before any allocation it returns. However, hackiness is not the question here - it's whether it's the "best" approach. I simply believe, based on my own experiences, that twin pointers cover/win out in a much larger subset of applicable scenarios.
As for how to implement it - declare a struct with 2 pointers in it. Or just pass 2 pointers around.
Unfortunately, no, your info about Perl 6 is news to me. Only ran into it a few months ago, tried it in Python and Nim, but haven't seen it in the wild. It's very cool though.
> In my personal experience, "a bit more than a pointer" works best as a pair of (start, end) pointers (where "end" points to just beyond the last element.)
There’s a PARC paper from the Cedar team benchmarking base-and bounds vs marker-terminated (e.g. null terminated) strings and base-and-bounds won hands down on a variety of use cases. Won on speed, not just the safety grounds. In those days some people actually worried about the space taken up by the extra bounds variable.
While people did worry about the space taken up by the bounds checking information, systems 10 years older than the PDP-11 had enough hardware resources to support high level systems programming languages with bounds checking data structures, let alone the beefy PDP-11 (by comparison with those older models).
But most people these days have a hard time realizing what it was like to program a machine with only a few K of memory. PL/1 (the Multics implementation language) had bounded strings. C did not as it was believed the PDP-7 couldn't afford it. Of course by today's standards the GE 645 is an absurdly tiny machine.
Yeah, that was my point, this knowledge is getting lost, only to be re-discovered by those that love to dig into computer history.
Just to think that what is now on a ESP32 die took over a complete desk at the high school computer club and was still weaker than what ESP32 is capable of, yet that mentality also persists for what 80's hardware was already capable of.
I actually wrote a (sort of) Go-style slice library. It's a little heavier than Go slices because it allows for dynamic array resizing and tracking the parentage of slices:
Go has a rather idiosyncratic take on arrays and how they're used, which is reflected in its slices. I can't think of any other language or framework that did it this way.
Man Bjarne Stroustrup is like the guy in college who flatly refused to conform in any way whatsoever no matter how good or bad it would have been for 'em. It's more of an oppositional personality disorder ;) That kid grew up and invented, because of course he did, C++.
It might have something to do with various symbols that C uses not being convenient to type in many non-US keyboard layouts. In the standard Danish one, ~|^ all require the use of AltGr.
The section "struct Header* self = head" is UB.
The alignement requirement of the local char array is 1 but the alignment
requirement of struct Header is that of void* which is probably 8.
Then take away the names so that you are effectively passing p as a parameter... Then returning p.
As in, an anonymous temporary being given to the function, and the function returns its address back.
It's assuming that this temporary parameter buffer will exist after it is used and the function has returned. I'm not sure what the standard says for that but it is crazy sketchy. [Edit: Googling around, it seems like maybe this is illegal in C99 but possibly legal in C11? Or that C11 changed the rules for this. Does not seem like a great thing to rely upon.]
There is no issue here (except the one highlighted by joejev).
Many standard library functions return a pointer which they got as a parameter (or another pointer offset from it, as is the case here). The compound literal is no more "temporary" than a variable that was introduced right before the function call. Lifetimes of compound literals are specified in section 6.5.2.5 of both C99 and C11.
func((int[256]){ 0 });
// is mostly equivalent to
int __a__[256] = { 0 };
func(__a__);
> Many standard library functions return a pointer which they got as a parameter
Obviously. But this does not extend the lifetime of the buffer they are passed. Namely you can't use this as a technique to extend the life of automatic storage falling out of scope.
> Lifetimes of compound literals are specified in section 6.5.2.5 of both C99 and C11.
This is what I was missing. So it is valid by the standard. Which is good if you have looked it up. It remains not obvious when reading source without a copy of the standard on hand, or prior knowledge of that section. Passing an expression of that sort and keeping a pointer to it visually looks like the intent is to retain a pointer of more limited scope. Intuitively it would make just as much sense if the lifetime were shorter. If you are seeking clarity of intent this is not a great thing to rely upon.
Perhaps a stupid questoon: Why isn't a vector type similar to { ptr, count } a normal thing to pass around in C? It's what you reach for in any other language, why did it become idiomatic to pass pointers and lengths separately in C?
A C standard library has a header file for complex math but it doesn't define a simple fixed size array struct? Why is that? Is it because they become pointless when there is no generics to deal with the stride?
> why did it become idiomatic to pass pointers and lengths separately in C?
I've read that it's because there used to be binary interface issues with structures. They can be returned from functions and passed as parameters but it isn't immediately clear how that happens: is it on the stack, in one register or in several registers? Even today there are compiler options that affect the generated code in those cases:
-fpcc-struct-return
Return “short” struct and union values in memory like
longer ones, rather than in registers.
-freg-struct-return
Return struct and union values in registers when possible.
>They can be returned from functions and passed as parameters but it isn't immediately clear how that happens: is it on the stack, in one register or in several registers?
Why does it have to be clear? It can be unspecified and the compiler will do what it thinks is best given the struct, e.g. return `struct {int x,y};` in registers, return `struct int[80] x}` as pointer to memory or write in-place to the caller's stack, via RVO.
Because it's part of the binary interface. Changing the binary interface prevents existing programs from interoperating. Everything breaks until the software is recompiled and that can be a major nuisance at best and impossible in the worst case.
Simple, well-defined and stable binary interfaces are a major reason why C is still widely used. Uncertainty in this area is never a good thing so people will actively avoid language features that introduce it. Looks like enums aren't favored for similar reasons: what is the underlying type?
It doesn't have to be a return value though. You could pass pointers to it as parameters.
To answer the question though, a number of people do define structures containing a buffer and a length (and potentially capacity), there just isn't such a structure standardized so everybody who wants to do this has to bring their own.
Some examples from Unix: iovec, sendmsg/recvmsg. Surely there are others I'm just not thinking of right now.
In the Windows world you have UNICODE_STRING and similar structures. SChannel has "PSecBufferDesc". Again, surely there are others.
And prominent libraries might also have their own.
Passing struct arguments by value is also complicated in some ABIs. The most reliable way is to pass a pointer to struct, but with slices that means double indirection.
I don't think ABI is a concern these days, though, even if things were different 30 years ago. The specs that we have today do cover how to pass and return structs in the standard manner.
Because C is a thin layer above assembly language. A pointer fits in one register, { ptr, count } would require two registers. Also if the count is being passed around, it should surely be checked when doing ptr + i, which slows things down further and is unnecessary if the caller knows what they are doing. If you start trying to make C safe and idiot-proof you also make it slower.
Yet plenty of Assembly languages have opcodes for bounded checking memory accesses, some of them in computer systems developed in the early 60's, 10 years before C was born.
> Why isn't a vector type similar to { ptr, count } a normal thing to pass around in C?
For one thing, as I recall in the original K&R version of C (before ANSI C89), the language didn't support passing a struct as a function argument or return value.
That means if you did make a struct, then every time you wanted to pass one of these pairs around, you'd have to pass a pointer to the struct, and you'd have to dereference that on every use. Which is arguably just as cumbersome as just passing two arguments, at least in terms of how much code you have to type. Plus it was probably slower.
From there it's no surprise if using separate arguments becomes the normal, idiomatic way to do it.
Given the circumstances of C's birth, it was, in many ways, optimized to be ergonomic for the compiler writer. If you don't ever need to return structs, then you can always just use the same register to hold the return value. Similarly, if there are no struct-typed arguments, then each argument is either a register, or a single machine word on the stack (C did other things for the latter - e.g. consider the conversion rules for functions called without being declared).
It's indeed a weird thing. It should have been an easy addition to the standard library. But instead people either pass around pointer/length pairs all the time - or even worse: They rely on null-terminated strings / arrays.
I had discussions with people who claimed that null terminated strings are the only idiomatic thing to do in C - because that is how C does strings. They assumed that since the standard library only provided methods which acted on those kinds of strings it was a preferred way to do things. Even though that is a lot less efficient than the string/array types that other languages use as defaults.
Given that years ago we added a mandatory piece of hardware to most systems to implement virtual memory, I'm now starting to wonder what security and/or performance benefits could be achieved by delegating memory allocation to (or through) hardware.
Since years, Oracle has shipped SPARC Solaris with ADI turned on.
Since iPhone X iOS makes use of memory tagging for pointers.
Starting with Android 11, hardware memory tagging is a required feature on ARM platforms on the CPUs that support it, while on other CPUs the kernel will randomly attach GWP-ASan to user processes and is enabled by default on all system processes during the ongoing preview releases.
Every new (post-2018) iPhone ships with this. iOS developers can build code for the architecture but I believe Apple currently strips it out before distribution, so its use is limited to the OS for now. I would assume at some point they’ll flip the switch to allow it; until then developers can use the toolchain to test if their code still works (generally it does, but messing with function pointers in ways unspecified by the standard can occasionally cause problems). ‘pjmlp is fairly interested in this topic so they might be able to share some more examples of it being used if they drop by the thread.
The summary version (from Walter Bright's article) is:
> C can still be fixed. All it needs is a little new syntax:
> void foo(char a[..])
> meaning an array is passed as a so-called "fat pointer", i.e. a pair consisting of a pointer to the start of the array, and a size_t of the array dimension.
The paper mentions fat pointers in passing, not putting the term in quotes, not defining it, and not giving a citation -- which makes it clear that the term was already well established at the time.
Fat pointers were part of Pascal (and derivatives), although I'm sure the concept has existed in one form or another going back to the beginning.
edit: Pascal pointers were just a location and size, however, not a slice-type fat pointer; however, I have always heard of any pointer containing more information than a memory address referred to as a fat pointer (except tagged pointers). YMMV.
I don't think Pascal pointers had to be implemented as location+size, since most operations that required checking the size were undefined or implementation-defined anyway. Some implementations might have used them to provide runtime checks, but it was certainly not the case in Turbo Pascal, for example.
Sure, I never said that Walter Bright created the concept. What I’m saying is that the link from Cello that I posted on HN is actually using that definition from Walter Bright’s article.
They're clearly using a different definition. In Cello, you are not passing a fat pointer ("a pair consisting of a pointer to the start of the array, and a size_t"), but a totally standard pointer that points to the second member of a packed struct containing a size_t and an array.
The difference is massive. Bright's idea would allow me to use existing interfaces with fixed structure: as long as I know the declared length of an array, I could pass a fat pointer to a function that accepts one. The Cello approach would require me to modify the interface to accommodate the new size header that is packed with the array. ABI break, not compatible with existing C code and libraries.
One could justify the name of fat pointer, the other is really just arrays with headers.
> The Cello approach would require me to modify the interface to accommodate the new size header that is packed with the array. ABI break, not compatible with existing C code and libraries.
Isn't the entire point of the article that this is not the case?
My understanding is that a Cello array is laid out like this:
<metadata header>.<actual payload data in standard C format>
^
|
this pointer is what you pass to existing C code
The existing C code gets a pointer to data exactly as it expects. It does not get a pointer to the metadata. It could access it by subtracting an offset from the pointer it's given, but it will not do that since it does not expect anything meaningful to be there. "This pointer is fully compatible with normal pointers".
No. The problem is that you have to have that metadata there, where ever it is that you want to point. What if it's not there? Oh yeah, doesn't work. It's just a normal pointer, pointing to an array and header.
If I pick up some library (or system call interface..), and it uses this structure
struct foo {
struct bar a;
char b[64];
};
The metadata field that cello wants is not there. I cannot use cello's "fat pointers" because they are not fat pointers at all. I would have to modify the struct to have array-with-length-header (which is what cello calls a fat pointer.. talk about confusing pointers and arrays!) , which might be impossible if it's someone else's binary interface that I am using.
If I had actual fat pointers, then the size would be simply passed together with the pointer and I wouldn't have to have modify structures to accommodate an extra field. Of course, I can't pass these pointers to functions that expect normal pointers, but it wouldn't make sense to do that anyway, and if implemented right, doing that would require me to misdeclare a function. You would pass normal pointers to old C code that expects and deals with normal pointers.
You can pass Cello pointers to old C code that expects and deals with normal pointers.
It's true that the internal array inside a struct cannot magically become a Cello fat pointer. So yes, you cannot pass a pointer to that array into a Cello function that expects a fat pointer, but that's the opposite of "pass normal pointers to old C code".
Is this blog post confused or am I confused? It keeps talking about fat pointers but the description looks much more like "arrays with their length stored before their first element," which is a massive difference.
It's just using "fat pointer" to refer to the concept of passing around a pointer with extra information concerning the data it points to. I agree that generally people would expect "fat pointer" to imply a larger pointer itself, but I don't think the label is misused egregiously enough to warrant picking at this.
> It's just using "fat pointer" to refer to the concept of passing around a pointer with extra information concerning the data it points to.
Is it actually? Here's a quote: "The trick is to place the value representing the number of items in the array in memory just before the pointer we actually pass to functions. This pointer is fully compatible with normal pointers,"
So suppose I pass this "fully compatible with normal pointers" pointer to a function.. and it ends up being stored in a register. Now where is this location "just before the pointer"? In the previous register?
I don't think this post is describing fat pointers at all. I think it is describing arrays with a prepended length header. There is no data in or before the pointer, there is metadata before the pointee assuming you're pointing at something with metadata prepended to it.. No extra information is passed with a pointer, it's just assumed to be there at the pointee. Call it a fat pointee if you want a fancy name; at least that acknowledges the onus is on the pointee to have the right metadata in the right place. There's nothing in the pointer here.
Yes, the extra data being the length that is located in memory before the pointer.
> So suppose I pass this "fully compatible with normal pointers" pointer to a function.. and it ends up being stored in a register. Now where is this location "just before the pointer"? In the previous register?
You’re at the wrong level of indirection; the header in in the memory before what the pointer points to, as in p - 1 rather &p - 1.
> I think it is describing arrays with a prepended length header.
Correct.
> Call it a fat pointee if you want a fancy name; at least that acknowledges the onus is on the pointee to have the right metadata in the right place.
I would prefer that this was not called a “fat pointer”, but the claim made above is that a pointer with any implicit data associated with it is “fat”.
> There's nothing in the pointer here.
No data, but there is an implicit guarantee that it points to the data portion of a length-prepended array.
> Yes, the extra data being the length that is located in memory before the pointer.
> You’re at the wrong level of indirection; the header in in the memory before what the pointer points to, as in p - 1 rather &p - 1.
You are contradicting yourself. &p - 1 is before the pointer. p - 1 is before the pointee.
> I would prefer that this was not called a “fat pointer”, but the claim made above is that a pointer with any implicit data associated with it is “fat”.
> No data, but there is an implicit guarantee that it points to the data portion of a length-prepended array.
I think that's a borderline useless definition. In my C, there's an implicit guarantee that any pointer, in a context where it may be dereferenced, points to a valid object (as long as it's not NULL and there's no programming error causing it to point at nothing well defined). Usually it points at the start of a struct, sometimes it points at list node (or whatever) embedded in a struct and I might have to work my way back with offsetof. Either virtually all of my pointers are fat or none of them are. I go by that none of them are, because whatever data I have (implicit or explicit) is not a property of the pointers I use but of the data I point them to.
I'd be (just) a little bit more inclined to agree with you if merely the representation was different. But the thing is, so much of the utility of fat pointers is that a fat pointer can refer to any portion of memory. Even a slice of a bigger allocation. The entire idea is that it can denote the size of what it points to, but be still used like a slim pointer. This thing can't pull off the same tricks. Calling it a fat pointer almost an insult to fat pointers. It's kinda like buying a motorcycle and calling it a "car" just because it refers to the concept of transportation with wheels, running on gasoline.
I understand their desire to use a library, but there's a faster and safer way to do this that's more C-like if you have access to the compiler:
Just locate anything declared as an array in a particular linker section so the pointer manipulation can be done with two (or one if it's at the top of memory) comparison, possibly even to a constant.
If you do this you can even forbid pointer arithmetic except in actual []-declared memory, and can do transparent bounds checking (&array-1 can hold the array length or, possibly faster, the address of the location after the end of the array).
An advantage of this over the library route is you can prevent pointer/array punning but otherwise allow any C program to work fine. And apart from a few corner cases (there are legit non-array uses of pointer arithmetic, though very few) and noncompliant program can be changed to use [] and still work perfectly fine without this option being used.
"This proposal wasn't accepted into the C standard..."
Walter often shows up on HN, so I'll ask: was this proposal merely on the Dr Dobbs article or did it actually go to a committee for review? If the latter, why wasn't it accepted?
Should C reconsider this? Especially now that C++ has std::span<> and std::string_view<>?
This seems to assume you want to actually allocate individual objects using malloc/calloc, when in reality you usually want to pool your allocations somehow, both for performance and for your own sanity.
Might be a nice safety feature to tag the first few bits of the size with a magic sequence so the "free" method can sometimes catch an attempt to free a non-fat pointer passed into it.
Another question for language lawyers: if you are given a pointer to char, is it defined behavior to somehow cast the data before that into a correct integer? Assuming you have
That depends on what p points to. If it’s the address of the char[1] array inside a valid PMyStr, then as far as I’m aware you can subtract the correct number of bytes (offsetof is your friend) and cast the resulting pointer to your MyStr, then get the size from there.
Many string functions are intended to operate on a substring. These functions would appear to need the original string passed in every time to find the length.
Every pointer into an array could pass the triple {current, start, len}, or even maybe the quadruple {current, start, len, allocated}, which is the kind of minimal efficiency C programmers are looking for.
They use a similar trick with std::string in libstdc++. The string object has a pointer to the null terminated character string, right before that string is a structure that contains the reference count. (I think libcello could add reference counted objects that way)
From a cursory look, this is one of the most unsafe pieces of code I have seen, with complete disregard to memory alignment requirements and the lifetime of temporary objects passed as arguments to functions.
> It might be better to try Cello out on a hobby project first. Cello does aim to be production ready, but because it is a hack it has its fair share of oddities and pitfalls, and if you are working in a team, or to a deadline, there is much better tooling, support and community for languages such as C++.
The author has already made it clear they consider "memory allocation by unaligned offset into temporary char[] cast into a struct pointer" to be a valid strategy, so frankly I'm not very interested in their opinions on whether it's production ready.
I've seen it on HN before, whenever this project gets mentioned. People who don't know much about C confuse it for a really cool thing you can do with C, as if it's just another legit library that you can pick up and use. It's a lot of undefined behavior. People have enough problems writing safe C as it is, and on top of this complaint about alignment and misuse of temporaries, this thing makes the problem worse in other ways too, removing the few safeguards that exist by treating everything as void* for instance.
Well it shouldn't be used for toy projects either with all of that hackery that it pulls (even if you don't use atomics, violating alignment requirements alone means that your code can never make use of vector instructions).
The new code on GitHub makes it clear that this library is not about fat pointers, but about writing unsafe C in another language, powered by undefined behaviour and the glory of the C preprocessor.
If you want to have safe arrays in C, just use a proper library for that instead of going the route of abusing undefined behaviour. There are plenty of libraries to choose from: https://github.com/search?l=C&q=vector+array&type=Repositori... (not all of them are serious projects, so you should be careful when you pick one. I personally have been using this one: https://github.com/iscgar/cvec2 because I like the easy interface it provides and especially the fact that type safety is a top priority, but other may have different tastes and priorities).
- slices become a total non-issue since a pair of (start, end) already is a slice and you can just move start and end.
- comparing against an end pointer is generally easier than adding up a length value first, particularly if you're slicing at the same time.
- the end pointer value is independent of the array element type, so if you e.g. cast to uint8_t * (which arguably you shouldn't in most cases) it stays exactly the same. If you store a count you need to adjust a multiplier. If you store a byte length, you need to do a lot of divides or casts to deal with pointer arithmetics.
Also, this is a huge red flag to me:
https://github.com/orangeduck/Cello/blob/master/include/Cell...
P.S.: This also is a "try to invent a new programming language without inventing a new programming language" thing. Have your cake and eat it... either it's C or it isn't, and this library is leaving the space of "normal" C.