10 ms·
Fat pointers in C using libcello
- eqvinox 7y agoIn 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. Also, this is a huge red flag to me: https://github.com/orangeduck/Cello/blob/master/include/Cello.h#L135-L140 https://github.com/orangeduck/Cello/blob/master/include/Cell... #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.
- aaron-lebo 7y agoI'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 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?
- eqvinox 7y agoThe "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.
- artemonster 7y agoDo you, by chance, know where else object model of Piumarta is used? I think the Per6 VM "Potion" used it too as a base, but I am unsure
- aaron-lebo 7y agoUnfortunately, 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.
- artemonster 7y agohttp://perl11.org/potion/ http://perl11.org/potion/
- vardump 7y ago> Also, this is a huge red flag to me: Puke! Who would ever want to create that kind of macro abomination.
- dgellow 7y agoBjarne Stroustrup! https://en.wikipedia.org/wiki/C_alternative_tokens https://en.wikipedia.org/wiki/C_alternative_tokens And I'm not even joking :)
- vardump 7y agoYeah, damn, just found out myself. I thought I knew C inside out, but I guess there are still bits and pieces you just don't encounter very often. That said, my opinion about those macros is unchanged.
- arcticbull 7y agoMan 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++.
- int_19h 7y agoIt 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.
- arcticbull 7y agoC++ isn't exactly short on symbols haha
- garaetjjte 7y agoYou can do worse: http://oldhome.schmorp.de/marc/bournegol.html http://oldhome.schmorp.de/marc/bournegol.html
- dllu 7y agohuh. Interestingly, for "and", "or" and "not", iso646.h already defines C alternative tokens: https://en.wikipedia.org/wiki/C_alternative_tokens https://en.wikipedia.org/wiki/C_alternative_tokens
- eqvinox 7y agoI know :) ... but have you seen anyone actually use those? I'd be curious to get a pointer or two.
- dllu 7y agoI have seen people coming to C++ from Python use "and", "or", and "not" in their if-statements :)
- eqvinox 7y agoHah - 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" ;)
- aloisdg 7y agoIn programming languages, does we have something akin to a mother-tongue?
- macintux 7y agoThere’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.
- shawa_a_a 7y agoI 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. 1: https://youtu.be/bVxfwsgO00o https://youtu.be/bVxfwsgO00o
- hannibalhorn 7y agoStart and end pointers is the approach used by the C++ STL, too.
- kortex 7y agoThis is how Go does slices, though they are 3 fields: type slice struct { zerothElement *type len int cap int } Though I suspect under the hood the len and cap are ordered first. If it's good enough for C greybeard Ken Thompson and unix hacker Rob Pike, its good enough for me. In fact I've looked for a port of go-style slices to C and haven't found one. Maybe people think sds is good enough?
- LukeShu 7y ago> Though I suspect under the hood the len and cap are ordered first. A slice is stored in memory as a `reflect.SliceHeader` https://golang.org/pkg/reflect/#SliceHeader https://golang.org/pkg/reflect/#SliceHeader ; the pointer does come first.
- jgbaldwinbrown 7y agoI 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: https://github.com/jgbaldwinbrown/slice https://github.com/jgbaldwinbrown/slice It's just a proof-of-concept, though, and would need a lot of work to be used in anything serious.
- int_19h 7y agoGo 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.
- saati 7y agoRust Vec has the same representation.
- gumby 7y ago> 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.
- pjmlp 7y agoWhile 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).
- gumby 7y agoAs I know well as a KA-10 MACLISP programmer! 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.
- pjmlp 7y agoYeah, 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.
- mehrdadn 7y agoAlso see: BSTR https://docs.microsoft.com/en-us/previous-versions/windows/desktop/automat/bstr https://docs.microsoft.com/en-us/previous-versions/windows/d...
- pjmlp 7y agoAnd Strsafe https://docs.microsoft.com/en-us/windows/win32/menurc/strsafe-ovw https://docs.microsoft.com/en-us/windows/win32/menurc/strsaf...
- tonyedgecombe 7y agoBecause you can never have enough string types in your Windows projects.
- 72deluxe 7y agoOr enough wrappers to safely acquire and free those things in C++ without having to write many extra lines or spend a long time looking for leaks
- seventh-chord 7y agoThis 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.
- saagarjha 7y agoPrevious discussion: https://news.ycombinator.com/item?id=10526159 https://news.ycombinator.com/item?id=10526159 (Fixed to actually point at discussion of fat pointers; thanks, ‘dgellow.)
- dgellow 7y agoThe link I posted is the documentation about fat pointers, not the homepage of libcello.
- saagarjha 7y agoFair enough; I’ll replace the links above with https://news.ycombinator.com/item?id=10526159 https://news.ycombinator.com/item?id=10526159, which as far as I can tell points to the same page. Thanks!
- clarry 7y agoIs 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.
- mehrdadn 7y agoI think the latter. Fat pointers were supposed to be 2 pointers wide, not 1...
- eqvinox 7y agoIt'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.
- mehrdadn 7y agoI'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.
- clarry 7y ago> 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.
- dgellow 7y agoThe concept of "fat pointer" the article is about has been described by Walter Bright (D creator) as "C's Biggest Mistake": https://www.drdobbs.com/architecture-and-design/cs-biggest-mistake/228701625 https://www.drdobbs.com/architecture-and-design/cs-biggest-m.... It's also an interesting read. 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.
- tom_mellior 7y agoIt's worth noting that fat pointers didn't originate with Walter Bright or that 2009 article. The oldest C-with-fat-pointers I can think of off the top of my head is CCured from 2002: https://people.eecs.berkeley.edu/~necula/Papers/ccured_popl02.pdf https://people.eecs.berkeley.edu/~necula/Papers/ccured_popl0... 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.
- caspper69 7y agoFat 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.
- int_19h 7y agoI 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.
- 7y ago
- pjc50 7y agoOn the "weird pointer solutions" tangent, there's the ARM authenticated pointers: https://lwn.net/Articles/718888/ https://lwn.net/Articles/718888/ 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.
- arethuza 7y agoThat's a fascinating approach - how widely used is it? Would love to know whether it causes any problems for 'existing' code.
- saagarjha 7y agoEvery 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.
- pjmlp 7y agoBesides iOS, Solaris SPARC, and Android 11 onwards.
- pjmlp 7y agoThat is quite easy to validate. 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.
- arcticbull 7y agoMight 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.
- alkonaut 7y agoPerhaps 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?
- matheusmoreira 7y ago> 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. https://gcc.gnu.org/onlinedocs/gcc/Code-Gen-Options.html#index-freg-struct-return https://gcc.gnu.org/onlinedocs/gcc/Code-Gen-Options.html#ind... https://gcc.gnu.org/onlinedocs/gcc/Code-Gen-Options.html#index-fpcc-struct-return https://gcc.gnu.org/onlinedocs/gcc/Code-Gen-Options.html#ind... https://gcc.gnu.org/onlinedocs/gcc/Incompatibilities.html#index-fpcc-struct-return-1 https://gcc.gnu.org/onlinedocs/gcc/Incompatibilities.html#in...
- andrepd 7y ago>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.
- matheusmoreira 7y ago> Why does it have to be clear? 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?
- projektfu 7y agoMany 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.
- glxxyz 7y agoEvery 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.
- wyldfire 7y ago"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<>?
- pjmlp 7y agoCurrently Checked C seems to be only attempt left, and a mentality shift to at very least use the static analysis tools that come with the compilers. Contrary to common HN wisdom, most C and C++ related surveys show that only up to 50% actually use some kind of analysis tooling.
- krilovsky 7y agoFrom 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. Definitely don't use this in production code.
- jedimastert 7y agoFrom the FAQ[0] > Can it be used in Production? > 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++. [0]: http://libcello.org/home http://libcello.org/home
- asveikau 7y agoThe 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.
- krilovsky 7y agoWell 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=Repositories 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 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).
- projektfu 7y agoAnother 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 typedef struct MyStr { size_t mystr_length; char [1]; } MyStr; typedef char *PMyStr; size_t MyStrLen(const PMyStr p) { const MyStr *pmystr = ?; const size_t *psize_t = ?; return *psize_t; } How do you make a legal cast to get either pmystr or psize_t?
- saagarjha 7y agoThat 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.
- projektfu 7y agoAh, with your information I'm looking into the container_of macro which I'm not entirely certain is legitimate but hasn't run into problems.
- MichaelMoser123 7y agoThey 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)
- joejev 7y agoInteresting idea, but this implementation has UB: typedef void* var; struct Header { var type; }; // ... #define alloc_stack(T) header_init( \ (char[sizeof(struct Header) + sizeof(struct T)]){0}, T) var header_init(var head, var type) { struct Header* self = head; self->type = type; return ((char*)self) + sizeof(struct Header); } 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.
- tomp 7y agoThat's just what I was wondering, are "magic" libraries like this still safe to use considering modern compiler's UB shenanigans?
- asveikau 7y agoNot only that but you have a pointer to a parameter returned back and used outside its scope ...
- nitrogen 7y agoIt's not a pointer to a parameter, it is just the parameter itself. var is a typedef for void* and no & appears in the function.
- asveikau 7y ago> no & appears in the function. It's an array, so you don't need & to take its address, it decays into a pointer without &. Imagine: char buf[sizeof(struct Header) + sizeof(struct T)]; char *p = buf; 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.]
- butterisgood 7y agoI didn’t particularly care for the way the author starts comparing this work to some kind of C Renaissance. I mean if you want to masturbate, please do it in private.
- gumby 7y agoI 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.