11 ms·
Go Slices Are Fat Pointers
- baby 7y agoThe “uint8* a, usize a_len“ pattern is one of the ugliest aspect of C. It’s probably the source of most bugs. To its defense, it was invented at a time where we were trying to save each byte of data and security was not really a thing. Unfortunately C is still quite popular.
- Veedrac 7y agoIn an ideal world, this would be how hardware spoke, and C wouldn't have even had a choice. Alas, the past cannot learn the lessons of the present.
- erik_seaberg 7y agoYou could put bounds-checked arrays into the 80286 segment descriptor table, but loading a segment register in protected mode was very slow and 16k entries wasn't big enough.
- jasonhansel 7y agoIMHO if C had generics then so many problems could be fixed (e.g. you could easily have a struct Slice<T> for a fat pointer). Existential generics would even give you OOP (and, in a roundabout way, closures) for free. Hmm...
- JoachimSchipper 7y agoC11 has _Generic.
- jasonhansel 7y ago_Generic is something of a misnomer; it's more like a special form of overloading than a general way of adding type parameters. C++ is a bit better with templates, but lacks type erasure (hence long compile times) and existential generics (so OOP isn't just syntactic sugar).
- bshanks 7y agoWhat are existential generics? I searched Google but couldn't find the meaning of the term.
- jasonhansel 7y agohttps://wiki.haskell.org/Existential_type#Dynamic_dispatch_mechanism_of_OOP https://wiki.haskell.org/Existential_type#Dynamic_dispatch_m...
- bshanks 7y agothanks!
- stochastic_monk 7y agoThis is analogous to spans and views in C++. I've rather enjoyed using span-lite [0], an implementation compatible with earlier C++ standards. (Roughly, all the syntactic niceness of an STL container without requiring ownership.) [0] https://github.com/martinmoene/span-lite https://github.com/martinmoene/span-lite
- WalterBright 7y agoD slices are fat pointers as well: https://dlang.org/spec/arrays.html#dynamic-arrays https://dlang.org/spec/arrays.html#dynamic-arrays My suggestion for C to adopt fat pointers: https://www.digitalmars.com/articles/b44.html https://www.digitalmars.com/articles/b44.html
- mhh__ 7y agoA chaotic part of me thinks that C should be illegal for security code for the lack of this.
- aitchnyu 7y agoJust Googled and seems fat pointers can at least prevent buffer overflow. I want to know more about other returns and costs on changing C to fat pointers. https://security.stackexchange.com/questions/155572/how-are-fat-pointers-a-good-protection https://security.stackexchange.com/questions/155572/how-are-...
- simias 7y agoThey can prevent some buffer overflows, assuming that the data in the fat pointer remains correct. If you want to prevent buffer overflows completely you need to go well beyond that and effectively either use a higher-level language with a runtime and GC making sure everything remains coherent or do what Rust is doing with its borrow checker. Not that I'm against fat pointers in C, I always thought that in hindsight not having a primitive "slice" type was a mistake. In particular using NUL-terminated strings instead of slices is both error-prone and makes implementing even basic string-splitting functions like strtok annoying or inefficient (you need to be able to mutate the source string to insert the NULs or you have to allocate memory and copy each component. If you had slices you could easily return a portion of the string without mutation or copy).
- codedokode 7y ago> If you had slices you could easily return a portion of the string without mutation or copy). In this case you get another problem: how to free memory when there might be many slices pointing at it.
- ryanworl 7y agoAnother useful unsafe slice operation is casting a byte slice to a string so you can e.g. use it as a map key. Watch your lifetimes though! You probably also wouldn’t want to use any string manipulation functions on it, but I’ve never had a reason to do that anyway.
- BarkMore 7y agoThe compiler optimizes conversion from []byte to string on map lookup. https://github.com/golang/go/commit/f5f5a8b6209f84961687d993b93ea0d397f5d5bf https://github.com/golang/go/commit/f5f5a8b6209f84961687d993...
- ryanworl 7y agoThat’s awesome! I’ll have to benchmark that and see if I can delete some code now. Thanks.
- Zach_the_Lizard 7y agoIt doesn't seem to do it in the general non-map, non-mutation case, though this optimization is welcome. I've personally resorted to using `unsafe` trickery in tight loops to overcome this limitation.
- nerdbaggy 7y agoOne of the things that was a gotcha for me when I started Go. Couldn’t figure out why my slices weren’t what I was expecting
- kccqzy 7y agoRust slices are also fat pointers. The std::string_view type is also a fat pointer. The Haskell ByteString type is also a fat pointer.
- deleted 7y ago[deleted]
- smitty1e 7y agoHigh carbohydrate diets appear to have been rough on pointers across several languages.
- quickthrower2 7y agoPhat pointers are more hip
- anandology 7y agoAny slice implementation that references to the original data has to be some kind of "fat pointer". Is there any other way that can be done? String.substring in Java does exactly that. I'm sure numpy arrays in Python are implemented like that, perhaps slightly more fatter.
- chewxy 7y agoNot numpy, but Gorgonia tensors are just pointers. The reason: it's cheaper to pass around one word than the absolute minimum "fatness" to pass around a multidimensional array. The absolute minimum meta info required for a multidim array is shape, stride. Numpy implements them as a [HUGENUMBER] array of integers for both. Gorgonia implements them as slices. Both of these incur a lot of additional movement of memory. More here: https://youtu.be/fd4EPh2tYrk?t=654 https://youtu.be/fd4EPh2tYrk?t=654
- chrisseaton 7y ago> String.substring in Java does exactly that. It used to - it doesn’t these days, where it now copies.
- masklinn 7y ago> Any slice implementation that references to the original data has to be some kind of "fat pointer". Is there any other way that can be done? Yes, add one more level of indirection. For instance traditional "oo" languages don't usually use fat pointers for dynamic dispatch, you have a single pointer to an instance which holds a pointer to its vtable. In Rust however, the "object pointer" is a fat pointer of (vtable, instance). Go's interface pointers are the same (which combined with nils leads to the dreaded "typed nil" issue).
- weberc2 7y agoI don’t understand people’s beef with “typed nil”. If an interface is just a fat pointer and the data is itself a pointer, then it stands to reason that the interface can be not nil while the data can be nil. If you understand the concept of pointers (or nillable pointers, anyway), surely this should not be surprising to anyone? It would have the same states as a asterisk-asterisk-int (HN formatting prohibits asterisk literals), would it not?
- Stratoscope 7y agoA word of caution to anyone writing C macros like the examples in the article... There is a potential error in this macro: #define COUNTOF(array) \ (sizeof(array) / sizeof(array[0])) Generally, when you write a C macro, you should parenthesize each use of any argument inside the macro. The exceptions would be cases like token pasting where you want the literal argument text and only the text. I don't have a specific failure example in mind for the COUNTOF macro (maybe someone can post one?) - but here is a macro where it is easy to see the problem: #define TIMESTWO( value ) ( value * 2 ) int ShouldBeEight = TIMESTWO( 2 + 2 ); // Oops, it's 6! This happens because the macro call expands to: 2 + 2 * 2 Parentheses prevent this problem: #define TIMESTWO( value ) ( (value) * 2 ) The macro also illustrates a common misconception: sizeof is not a macro or function call, it's an operator. So wrapping the argument to sizeof in parens isn't necessary unless they are needed for other reasons. (They don't hurt anything, they just aren't needed.) So when I've written a COUNTOF macro (and it is a very handy macro in C/C++ code if your compiler doesn't already provide a similar one like __countof in MSVC), I write it like this: #define COUNTOF( array ) \ ( sizeof (array) / sizeof (array)[0] ) The space after each sizeof is my attempt to indicate that the following parens are not function/macro call parens, but are there specifically to wrap the array argument safely.
- hedora 7y agoYou also shouldn’t repeat the argument: “while(COUNTOF(ptr++) > 0) { }” would do horrible things (if it compiles; didn’t check) for example. There are various preprocessor tricks to avoid this stuff (eg “do{ x = (array); ... } while (0)”), but, honestly, if you want this sort of memory safety, C++ is your friend.
- Stratoscope 7y agoAgreed, although I don't know of a straight C way of implementing COUNTOF without repeating the argument. So it becomes a lesser-of-two-evils question: is the macro (with its flaws) better than doing the calculation explicitly every time you need it? The __countof macro in MSVC does go to some extra work to make it more safe, so it's definitely recommended to use that instead of rolling your own COUNTOF in that environment.
- benreesman 7y agoObviously there are all kind of cute games that can be played with pointers if you know arch-specific details (IIRC v8 was using alignment guarantees to steal low bits at one point, might still be). And tagged pointers of various kinds go at least back to Symbolics if not further. One that I thought was especially nifty was [0]. [0] https://github.com/facebook/folly/blob/master/folly/PackedSyncPtr.h https://github.com/facebook/folly/blob/master/folly/PackedSy...
- drfuchs 7y agoLisp 1.5 was using tagged pointers by 1962, and I don’t think it was innovative in this regard at the time.
- db48x 7y agoOnly because the computer it was on already had a tag field in every word. Other implementations of Lisp did similar things though: https://www.snellman.net/blog/archive/2017-09-04-lisp-numbers/ https://www.snellman.net/blog/archive/2017-09-04-lisp-number...
- deleted 7y ago[deleted]
- throwaway34241 7y agoGo interfaces are also fat pointers. Basically, the pointer to the type info/method set and the actual data are stored separately. [1] As a result of this you can use pointers as interface types without boxing them. For example you can take an interior pointer to an array, or a C pointer, and use it as an interface type without boxing since the type info doesn't need to be stored with the data. [1] https://research.swtch.com/interfaces https://research.swtch.com/interfaces
- octonion 7y agoSwift arrays are the only programming language arrays that have ever baffled me. I still have no idea how to manually reconstruct them given the array struct.
- millstone 7y agoFat pointers + threads permit torn reads/writes, leading to memory unsafety. It seems weird that Go allowed memory unsafety for this narrow use case - AFAIK only slices and interfaces are fat pointers.
- DougBTX 7y agoThere's some discussion about unsafety in the face of concurrency from Rob Pike here: https://talks.golang.org/2012/splash.article#TOC_13 https://talks.golang.org/2012/splash.article#TOC_13. > There is one important caveat: Go is not purely memory safe in the presence of concurrency. Sharing is legal and passing a pointer over a channel is idiomatic (and efficient). > Some concurrency and functional programming experts are disappointed that Go does not take a write-once approach to value semantics in the context of concurrent computation, that Go is not more like Erlang for example. Again, the reason is largely about familiarity and suitability for the problem domain. Go's concurrent features work well in a context familiar to most programmers. Go enables simple, safe concurrent programming but does not forbid bad programming. We compensate by convention, training programmers to think about message passing as a version of ownership control. The motto is, "Don't communicate by sharing memory, share memory by communicating."
- the8472 7y agoIf you need thread-safety you must at least use atomics anyway Either your platform has transactional memory, double-wide cas or you need to fall back to locks.
- gpderetta 7y agoUsing double wide cas for atomic pointer store and loads is a big pessimization though.
- weberc2 7y agoI was of the impression that even regular pointers could allow for memory unsafety but I can’t recall exactly what I had heard that gave me that impression...
- _ieq6 7y agoI regret learning go as my first language. Every other language just looks awful.
- db48x 7y agoPeople say that about Lisp as well.
- weberc2 7y agoI think it’s for different reasons. Go as a language is just fine, but Go as a framework for building software is just fantastic. The tooling is comprehensive and easy to use, testing is built in, and the happy path is almost always highlighted for you. No need to figure out which documentation generator, style guideline/formatter, test framework, build system, package manager, etc to use and these are easy to use (with the notable exception of package management, which has been rocky but is improving). Lisp is a neat and powerful little language but the tooling and documentation are often lacking and it’s often difficult to figure out even which lisp is right for your project.
- db48x 7y agoExcept that most of the tools that come with Go are pretty mediocre. Go's debugger is worse than mediocre.
- weberc2 7y agoThe debugger isn’t great. Most things just work, and they just work well for the most popular use cases. Documentation is just comments—no special syntax to memorize and no need to maintain infrastructure to parse docstrings and publish to a web server. It also runs the examples to make sure they work. The build system doesn’t require you to learn a special (typically imperative) project configuration language or Makefile generator. It also outputs a statically-linked binary by default—no VMs or interpreters or libraries to shop separately. Although it doesn’t have a comprehensive assertion suite, Go ships with a unit test framework that just works, which is more than can be said for most languages. And all of these things are standard so you can pretty much jump into any project and build it, run its test suite, and begin contributing with little more than a text editor and the Go toolchain. So yeah, Go’s tooling is simply fantastic and no other mainstream language except Rust comes close. This isn’t a fanboy statement; there are lots of other factors to consider, but Go’s tooling is top notch.
- fulafel 7y agoInteresting that this post has been in the #1 place for so long. I don't use Go but I knew this already by having randomly read some things about the language. And slices are central language concepts after all. Is it that the Go documentation doesn't cover the underlying implementation at the machine word level?
- _Chief 7y agoDocs explain this, not as detailed as the post, but it does touch on slices referencing/wrapping an array. However, there is a blog post dedicated to slice internals https://blog.golang.org/go-slices-usage-and-internals https://blog.golang.org/go-slices-usage-and-internals that dives further in
- tangus 7y ago(In the same vein of other comments...) Algol 68 slices are also fat pointers. Only they also carry a `stride` field, since in Algol 68 you can slice multidimensional arrays in any direction.
- oconnor663 7y agoA couple questions about that design. Is it worth paying the cost of an extra word in every slice, if strided slicing is rare in most programs? And when you wrap OS APIs that don't understand striding, do you have to use a different pointer type?
- tangus 7y agoIt's a subjective question, but given that A68's slices are already burdened with carrying their lower bound wherever they go, not much is lost with adding another piece of data to them. They are already quite fat, and more with each dimension. I think the ability of taking a column and just apply any sequence function to it is well worth it. I don't think you could use OS APIs without boxing and unboxing data, but I think that's the case with every language except C.
- rwmj 7y agoAnother way to implement fat pointers is to keep the pointer representation the same but have another structure like an interval tree that stores a map of pointers to the extra information on bounds. That's how I implemented Bounds Checking GCC back in the day: https://www.doc.ic.ac.uk/~phjk/BoundsChecking.html https://www.doc.ic.ac.uk/~phjk/BoundsChecking.html It has the advantage that pointers remain compatible with code that wasn't specially compiled to know about fat pointers (such as system libraries).
- rocqua 7y agoSeems like that would hurt memory locality, with a commensurate increase in cache-misses.
- rwmj 7y agoWell Bounds Checking GCC had a huge overhead anyway (making code about 3-5 times slower) so memory locality wasn't our primary concern.
- wahern 7y agoThat's basically how Intel MPX works, https://en.wikipedia.org/wiki/Intel_MPX as well as TinyCC's Bounds Check, https://bellard.org/tcc/tcc-doc.html#Bounds which cites the aforementioned GCC patch. I think AddressSanitizer uses a shadow mapping structure more similar to Valgrind. Although your point about performance still stands. Intel MPX is dead--support removed from GCC, IIRC, because of hints Intel was abandoning it. We'll never know how well it could have been optimized in practice. I think ultimately we simply need proper fat pointers, but those might not become ubiquitous (in the sense of becoming a de facto standard part of shared, C-based platform ABIs) until we see 128-bit native pointers.
- floatboth 7y ago> For example, currently on x86-64, only the lower 48 bits of a pointer are actually used. The other 16 bits could carefully be used for other information Well, you can't dereference these fat pointers directly on amd64, you have to remove the tag. aarch64 actually has a Top Byte Ignore flag though :)
- blt 7y ago...yes, and? How else could you possibly implement slices? I don't disagree with any of this article at a factual level, I'm just trying to understand the author's message.
- gouggoug 7y agoFor people like me whose knowledge of C is close to 0, and had no idea what fat pointers were, that post was pretty interesting. I've now learned 2 things: what fat pointers are, and that go slices are fat pointer.
- metroholografix 7y agoSome errors I found: uintptr addr = (uintptr_t)buf & 0xffffffffffff; uintptr pack = (sizeof(buf) << 48) | p; should be “| addr” #define ARRAYPTR(array) \ ADDROF(array, COUNTOF(array)) should be FATPTR(array, COUNTOF(array))
- tsegratis 7y agoHere's my own attempt at implementing these ideas in c Basically feature complete, with unitests, and interop with c arrays https://tse.gratis/aArray/ https://tse.gratis/aArray/ A few changes for a later version: * Pure public domain license (it is that already, but the wording could be better) * Remove c++ support... Not sure about this * Let higher order map/filter functions take a void* payload when using plain c functions over clang blocks (or lambdas)
- svd4anything 7y agoMy favorite is Smart Fat Pointers. They are sexy!
- inlined 7y agoI’ve seen this technique used in old codebases for strings. A typedef was made for a char* whose -1 address was a count and there wasn’t a zero terminator. This was useful since string length checks were now O(1) and string manipulation can take a surprising amount of time in CPU bound programs. It was an interesting idea but you needed a whole new set of string functions and bridge functions. It takes a runtime (or codebase) wide commitment to make it work.
- firethief 7y agoThat sounds like Pascal strings. Arguably saner than C strings, but lacking the main advantage of slices: multiple slices of different lengths and/or different starting points can refer to parts of the same string, so you can "slice" things without copying.
- kazinator 7y agoYou can easily obtain convenient fat pointers with like the the 1990 dialect of C++ described here: https://www.amazon.ca/Annotated-C-Reference-Manual/dp/0201514591 https://www.amazon.ca/Annotated-C-Reference-Manual/dp/020151...
- codedokode 7y agoWhat surprises me in C programmers is that bugs like buffer overflow have been known for several decades but they still use raw pointers for strings and unsafe pointer arithmetics. At least in open source projects I often see this. C is really a language that doesn't move forward. Also, no proper package manager.