7 ms·

Go Data Structures (2009)

• eu 2y ago
  it’s a good read, but i think it should focus more on some of the common mistakes that people make when slicing a slice.
  • rednafi 2y ago
    Slicing a slice is full of gotchas. I tend to forget all the rules and avoid it whenever I can.
    • bborud 2y ago
      It is a suprisingly hard thing to implement well. I have no idea how many times I have implemented slice-like things in C (back in the 1990-2000s when I mostly wrote C) and it was one of those things I never managed to be happy with.
      • neonsunset 2y ago
        It can be done but that requires a better, more expressive type system.
        • rednafi 2y ago
          An expressive type system also often means slower build times. I dislike working with Rust for this exact reason. While most people highlight the difficulty of picking up the syntax, I find Rust to be an incredibly tedious language overall. Zig has a less expressive type system, but it compiles much faster (though not as fast as Go). I like what Zig and Odin folks are doing over there. I like the balance Go strikes between developer productivity and power, though I dearly miss union types in Go.
          • 4ad 2y ago
            An expressive type system absolutely, positively, unequivocally does not imply slower build times (especially with a Church-style type system). There are plenty of programming languages with advanced type systems which compile extremely quickly, even faster than Go, for example OCaml. Don't make the fallacy of conflating Rust's slow compile time with its "advanced" (not really, it's 80's tech) type system. Rust compilation is slow for unrelated reasons.
            • taurknaut 2y ago
              Old doesn't mean non-advanced. GraalVM is based on a paper (Futamura) from fifty years ago. Off the top of my head I can't think of many language features younger than the eighties—maybe green threading? That would be surprising but might fit. I suppose you could also say gradual typing. Haskell has many recent innovations, of course, but very few of those have seen much use elsewhere. Scala has its implicits, I guess, that's another one. Personally, I write java at my day job and the type system there makes me loooong for rust.
              • pjmlp 2y ago
                No need for Rust, when JVM has Haskell, Scala, Kotlin, Clojure, Common Lisp.
                • taurknaut 2y ago
                  I prefer rust to all of them, but I also come from a very systemsy background. Plus it has the benefit of being much easier to embed inside or compose around basically any runtime you'd like than managed code, which is why I chose rust rather than basically any managed language. But, it's just a tool, and the tools I choose reflect the type of stuff I want to build. The JVM is extremely impressive in its own right. You're just not going to to find any one runtime or ecosystem that hits every niche. I'm happy to leave the language favoritism to the junior devs—for the vast majority of situations, what you're building dictates which language makes the most sense, not vice versa.
          • 2y ago
      • pjmlp 2y ago
        Something that even Mesa and Modula-2 already supported by 1980's, maybe one day C will eventually get proper slices.
        • baranul 2y ago
          Good point. As for C and slices, doubt that many care, at this point. Many will use C alternatives that have slices or are long time C users that just deal with it.
    • rendaw 2y ago
      Appending a slice is also full of gotchas. Sometimes it modifies the slice in place, sometimes it reallocates and copies.
      • pstuart 2y ago
        Only really a gotcha if you pass a slice into a function and expect to see modifications in that slice after the function completes. It's helpful to remember that Go passes by value, not reference. That can be addressed by passing the slice as a pointer: https://go.dev/play/p/h9Cg8qL9kNL https://go.dev/play/p/h9Cg8qL9kNL
        • TheDong 2y ago
          > Only really a gotcha if you pass a slice into a function and expect to see modifications in that slice after the function completes. It's helpful to remember that Go passes by value, not reference. Slices are passed partly by value (the length), partly by reference (the data). func takeSlice(s []int) { slices.Sort(s) } From your explanation, you would expect that to not mutate the slice passed in, but it does. This can have other quite confusing gotchas, like: func f(s []int) { _ = append(s, 1) } func main() { s := []int{1, 2, 3} f(s[0:2]) fmt.Printf("%v\n", s) } I'm sure the output makes perfect intuitive sense https://go.dev/play/p/79gOzSStTp4 https://go.dev/play/p/79gOzSStTp4
          • silisili 2y ago
            Slices are passed only by value. It's just that the value is a struct containing a reference to the data. Once one understands that, the rest makes perfect sense. I can see why it trips up newcomers, but it feels pretty basic otherwise.
            • lsaferite 2y ago
              I say this as someone working with go every day. The fact that I can pass a slice to a func 'by value' and mutate the source slice outside the func is already surprising behavior to most people. The fact that it MIGHT mutate the source slice depending on the slice capacity is the part that really drives it home as bad ergonomics for me. Overall I enjoy working with go, but there are a few aspects that drive me up the wall, this is one of them.
    • adonovan 2y ago
      A slice operation s[i:] seems like it should be little more than an ADD instruction for a registerized slice where i is known to be in bounds, but a surprising little detail is that when i==cap(s) we really don't want to create an empty slice whose data pointer points one past the end of the original array, as this could keep some arbitrary object live. So the compiler generates a special branch-free sequence (NEG;SUB;ASR;AND) to compute the correct pointer increment, ((i - cap) >> 63) & (8 * i). https://go.dev/play/p/J2U4djvMVoY https://go.dev/play/p/J2U4djvMVoY
  • fmbb 2y ago
    Can you link some article about these common mistakes? Sounds like good learnings can be had.
• WolfCop 2y ago
  (2009)
  • rednafi 2y ago
    It's Go we're talking about. Other than 64-bit the dominant word size, nothing much has changed.
    • 4ad 2y ago
      The interface layout has changed since the article (although this specific article doesn't mention interfaces, a later article in the series does). Additionally Go now has generics. It's true that little has changed, but very little is changing in the data representation of any language, really. Even ones that are evolving rapidly.
      • Cthulhu_ 2y ago
        This is a truth that's easily overlooked; most languages are several levels beyond basic types to the point that people forget about the low level constructs involved. This is one reason why I like Go, it exposes and educates on fairly low-level mechanisms that are not unfamiliar to anyone who's studied computer science, but at the same time you don't have to worry too much about the lower level stuff like memory, pointers, zeroing, etc. I think it's a good tradeoff.
    • mseepgood 2y ago
      [flagged]
      • Cthulhu_ 2y ago
        HN is not primarily a news site though, despite the name.
• deleted 2y ago
  [deleted]
• zellyn 2y ago
  The most important thing to know is that Go slices are exactly how you would implement a dynamically growable slice in C if I asked you to. No less, but importantly, no more: a pointer to a piece of memory, and a current length and capacity. The classic slice mistake is to forget that append doesn't necessarily return a completely new slice backed by a disjoint piece of memory, especially easy if you've been using a language where variables are immutable by default. The problem is that it will often accidentally work; if you over-run the backing store, you will get a new piece of memory: a := make([]int, 1, 1) // a is backed by a one-element-long piece of memory a[0] = 42 b := append(a, 17) // this must allocate a new piece of memory c := append(a, 37) // this must also allocate a new piece of memory // At this point a == [42], b == [42, 17], c == [42, 37] The problem is when the existing capacity is sufficient: a := make([]int, 1, 10) // a is backed by a ten-element-long piece of memory a[0] = 42 b := append(a, 17) // no need to allocate: just use the existing memory c := append(a, 37) // no need to allocate: just (re)use the existing memory // At this point a == [42], b == [42, 37], c == [42, 37] // ^^^^^^^^^^^^^
  • BoingBoomTschak 2y ago
    That's not the "classic slice mistake", that's slices being one of the stupidest things Go ever decided upon. In C++, that'd be the equivalent of merging std::vector<T> and std::span<T, std::dynamic_extent> into a single structure for "reasons" ("simplicity"?). https://build-your-own.org/blog/20241125_go_slice_surprise/ https://build-your-own.org/blog/20241125_go_slice_surprise/ goes a bit further, but this is really the point where I decided I wouldn't be able to stand Go.
    • zellyn 2y ago
      In the period when Go was ready for production use and Rust wasn't, I couldn't wait for Rust to be ready, so that the response to everyone hating Go for not being a C++ equivalent could just be, "I think you want Rust." I think you want Rust.
  • kccqzy 2y ago
    I'd argue that the Go example is worse than the equivalent in C, because Go has a garbage collector and C does not. In C, precisely because of the lack of a garbage collector, people need to explicitly and carefully document who is responsible for deallocating the memory. This makes things clear who is owning that memory. And this by extension leads to an intuition on whether the append is acceptable on the original slice or not. If a C function returns such a slice and is documented that the caller should free it, you can call realloc and add to it; if the C function documents that the caller should not free it, you naturally wouldn't even try to append to it: you would copy it first. In Go, this garbage collector frees people from thinking about freeing memory. But it doesn't free people from thinking about owned vs borrowed memory. And that's where bugs can happen.