type Ruleset []Rule
func (r Ruleset) Match(path string) (*Rule, error)
I understand why the author says they can’t change Ruleset to []*Rule or Match to func(string) (Rule, error), but in my experience, taking a pointer *T from a slice []T is pretty much always an “optimization” I end up regretting because it inevitably gets broken when you innocently append to the slice later. “Oh, I’m not mutating the interior of the slice, just adding onto the end, it should be fine.” Nope, it will not be fine. So many subtle bugs that way. Either make the slice a slice of pointers or return a value copy, but don’t take pointer to a slice of values because you will get bugs later.
Yeah returning a reference to an element if a mutable slice doesn’t feel great given the slice can be reallocated. That said I think that if the slice is reallocated the reference that’s returned will keep the GC from cleaning up the old block of memory. So while you do hang on to some extra memory, at least there isn’t a true dangling pointer causing a memory safety issue. Does that match your understanding?
That’s correct, but it means that things work most of the time until they don’t. It’s the worst kind of bug because it only happens sometimes that you miss updates or unexpectedly overwrite an existing element.
I see what you’re saying—the issue isn’t a dangling pointer, it’s that mutations through the pointer will only be reflected in the slice if the slice hasn’t been reallocated. Yeah that’d be a super subtle bug to track down, thanks for pointing that out.
I don’t quite know why, but I very rarely mutate arrays (including appends) in the first place–or rather, I’ll build some slice by doing a bunch of appends (although I prefer to do a make([]T, size) upfront if possible) but by the time someone else has a reference to the slice, it’s functionally immutable so I don’t need to worry about this sort of append scenario.
Ideally Go would have enforced immutability semantics so we could express that a slice can’t be changed and it’s safe to take references to its items, but programming in this style seems like the next best thing (returning copies is good, but copies can contain pointers to other things, so leaning hard on copies for safety can be a different kind of pain).
What if you need to sort the slice? Or filter in place? That’s been a pain point for me because they seem like they should work, but you just messed up any pointers you already returned.
I think I concur with weberc2, I treat any slice that crosses a callstack boundary as essentially immutable, e.g.
Any code that receives a slice treats it as immutable, if e.g. I want to make changes to a received slice, I allocate a new slice, fill it by walking the input slice, and operate on the fresh value
Any code that returns a slice should return a unique value, if e.g. a method on a struct wants to return what is ultimately a field of that struct which is a slice, I always make a new slice in the method, copy elements over, and return the fresh value
Sorting a slice is something that I’d do prior to returning that slice. If a caller receives a slice, they’re free to do whatever to it, including appending and sorting, until they return it themselves. Filtering always looks like e.g.
orig := f()
var filtered []int // by default, or...
//filtered := make([]int, 0, len(orig)) // ...if profiling supports it
for _, v := range orig {
if filterPass(v) { filtered = append(filtered, v) }
}
Usually they’re sorted before I hand out pointers. I have a static site generator that does this—I load up all of my posts into a slice, sort by date, and then pass out pointers for further processing. I’m not sure when I would sort or append after I had already passed out pointers.
A value method receiver like (r Ruleset) expresses that the method doesn’t mutate the receiver. That expectation is violated if the receiver is a reference type (e.g. a slice) and the method returns a pointer to an interior member of that receiver (e.g. a pointer to an element of that slice).
Things get even trickier when you consider callers who might call stuff that defines new slice 3-tuples which happen to re-use (part of) the backing array of that original slice. Here be dragons!
Are there any static tools that can analyze and point these things out? “You’re copying and then returning a reference to that copy” should probably be a check that happens at build time if you enable it..
Probably not because it’s possibly desirable, for example, you might not want callers to be able to mutate the original, so you allocate a copy and return a reference to it. If Go had immutability semantics, it might be a different story, but alas…
Oh, I fully agree. I guess I misunderstood your original proposal and was imagining a linter that errored when it found these. But I definitely think it would be cool, totally feasible, and immensely valuable to make an IDE plugin that highlighted these allocation points.
I teach classes on Go at Google, but I am not a language author so don’t take my word for it.
I have found it pays to always pass pointers to structs, never copy. It’s very easy to pass a struct to a function with a copy, mutate the struct, and then find out (much) later that the original doesn’t mutate because you mutated the copy. Many hours can be wasted debugging this.
There’s little value in copying, Go doesn’t have consts and pretending it is immutable will get you into trouble. I have seen some “experts” saying to use copies to try and create immutability, but this is trying to shoehorn something into the language that doesn’t exist. It makes code very hard to read and reason about. If the compiler can’t help you – which the Go compiler can’t because there’s no const keyword – then you shouldn’t try it. Note if you pass a copied struct but that struct itself contains a field that’s a pointer, then that field isn’t immutable and so you’re still in the same spot.
I have found it pays to always pass pointers to structs, never copy.
+1 to your intuition here — I always default to operating on struct pointers, and only opt-in to struct values as special cases.
Go doesn’t have consts and pretending it is immutable will get you into trouble. I have seen some “experts” saying to use copies to try and create immutability, but this is trying to shoehorn something into the language that doesn’t exist.
+1 to your judgment here, too — I’d be very surprised to see any Go “expert” suggest such a thing!
FWIW, to prevent the bug where a = b is slow for big types, Google’s C++ style guide used to mandate DISALLOW_COPY_AND_ASSIGN (which used to be DISALLOW_EVIL_CONSTRUCTORS I think) on all types (most types?)
Instead you would do something like a = b.Clone() I believe
Looks like that’s been gone for awhile in favor of C++ 11 stuff, which I don’t really like:
Indeed, C++ also makes it easy to create accidental copies, because it’s kind of the default. Relevant example:
for (const auto accidental_copy : collection) {}
Rust is like you describe with Google’s style guide: No implicit copying, but a clone trait you can implement and call. It’s one of those things that make the language a bit harder, but mostly because it makes mistakes harder.
Even python seems to agree, in principle:
> python -c 'import this' | grep Explicit
Explicit is better than implicit.
Rust’s plain-data types can opt in to implicit copies (derive Copy). But it’s really nice to have no copies as the default.
Also ability to return a temporary read-only reference helps in cases like this, because you can give access to an element without copying it and without risk of the caller modifying it or being left with a dangling pointer.
You’re supposed to not derive Copy unless your type can be blitted (or just memcpy’d) rather than needing actual construction. I don’t know if implementing it when you’re not supposed to can break compiler assumptions (as I’ve observed Clone still gets called) but as a rule, it would avoid the worst of these slow copy cases.
Yeah, Copy types are the exception that proves the rule.
They aren’t a performance concern in the same way, because they can’t own a resource (because of that memcpy copyability: if it needs a destructor, it should need a custom clone function).
Because this exception is really a sensible distinction, you can still search the codebase for “clone” and be confident you aren’t copying resources, which is what mostly matters, and is more readable than C++, where you have to delete operators to see if they are being called, which is easier said than done for non-custom types.
C++ got here via a very complex path. First, C had structures and structure assignment was defined as memcpy. Removing that would break compatibility with any C headers that contained functions or macros that do structure assignment. Then C++ decided that struct and class were equivalent except for the default visibility, which meant that the rule applied for any C++ object as well as any C structure. But some C++ classes needed to do non-trivial things (not just memcpy) on copy, and so added copy constructors and copy assignment.
Smalltalk-derived languages assumed garbage collection and so required all objects to be allocated on the heap, but C++ did not want to do this (and couldn’t for C compatibility) and so came with the additional constraint that you had to be able to copy an object into space reserved by the caller of the copy operation (this includes copying objects into globals and onto the stack). This meant that you coudn’t implement something like clone(), where the return type depends on subclass relationship, you had to model these things as separate allocation and initialisation.
This is further complicated by the fact that returning a structure is, in C++, modelled as copying the structure to the caller. For a long time, this copy has been optional (compilers may elide it - if you declare a local structure then return it then it will actually be created in the space that the caller passes down the stack). This was fun because copy constructors can have side effects and so it was observable in the abstract machine whether the compiler did this optimisation. C++17 made this mandatory, but this meant that any object that you wanted to return as an on-stack value needed to have a copy constructor.
So now we’re in a state where you need copy constructors and you need them to exist by default and where deleting them breaks some language features. Now C++11 came along with auto types. C++ has syntactic modifiers to say ‘pointer-to-X and 'reference-to-X but nothing (outside of exciting type_traits things) to say bare-type-that-this-reference-thing-applies-to. If auto deduces T, then you can modify it to a reference by adding &, but if auto deduces T& then it’s hard to modify it back to T. This meant that auto had to default to deducing T, which meant that it was very easy to accidentally copy things. Compilers try to warn about this.
Are also some interesting corner cases. You can make copy constructors explicit (so they won’t be invoked without explicit syntax saying that you meant to call them) but you can’t do the same for copy assignment. Herb’s new syntax cleans up a lot of this but the Rust approach (which doesn’t have any of the legacy baggage) is much better than the current state of C++.
I actually am glad that auto usually gives T and not &T in these contexts - imagine how hard it would be to tell at a glance if a copy was being made or not (even if avoiding the copy requires an extra symbol in the soup).
It is really hard to create a type in Go where copies like this are slow, because almost all primitive Go types have reference semantics. In practice the only way is to define types containing arrays (not slices) of substantial size. I haven’t seen a lot of Go code that has e.g. type x struct with buf [10000]uintptr or whatever.
Yeah that is an interesting difference, but I wouldn’t say “really hard” – since the OP had the problem, and someone else pointed to a comment where Russ Cox fixed the same problem in the Go standard library for a 40 byte struct, which was presumably all primitives
Digression …. I think contrasting the languages is interesting:
Rust: opt in to a = b being a copy for value types
C++: opt out of a = b being a copy for value types
Go: a = b is always a copy for value types
Thinking about it a bit more, I think it’s a misfeature to reuse the same syntax for 2 different things
a = b is a pointer assignment – O(1) with respect to the size of the type
a = b is a value assignment – O(N) with respect to the size of the type
e.g. in my head I have been making a big list of things where “syntax doesn’t match semantics”, and it hadn’t occurred to me that this is one
I get your caveat that Go and C++/Rust structs aren’t equivalent though
A perf bug I have fixed repeatedly in other people’s Python code is:
if item in L: # linear search through list
pass
if item in D: # dict or set membership
pass
If this is in a loop, then the first one is O(N^2), whereas the second is O(N), and I’ve seen that make scripts go from a 5 minute runtime to a second or so..
So that is very similar to a = b, the syntax is too close for operations that mean different things. Most people just look at the syntax and don’t “visualize” what’s going on underneath, which is very different.
A really trivial one that I remember someone having an extremely hard time with: static means 3 or 4 different things in C and C++:
static void f();
static int x;
A Java programmer simply couldn’t wrap his head around the fact that the annotation on f() means “local to this translation unit” / not exposed to the linker. It’s a gratuitous “pun” because they didn’t want to reserve a new keyword, which is extremely confusing.
A lot of these syntactic conflicts are about shell. For example it took me a long time to realize that quoting means different things in different contexts in shell!
echo $x
echo "$x"
echo hi > $x
echo hi > "$x"
a=$x
a="$x"
local a=$x
local a="$x"
I never wrote a blog post about that, but most shell experts won’t be able to tell you the difference between them. Most of all because common shells don’t even agree on what they mean :)
I understand why the author says they can’t change Ruleset to
[]*Ruleor Match tofunc(string) (Rule, error), but in my experience, taking a pointer*Tfrom a slice[]Tis pretty much always an “optimization” I end up regretting because it inevitably gets broken when you innocently append to the slice later. “Oh, I’m not mutating the interior of the slice, just adding onto the end, it should be fine.” Nope, it will not be fine. So many subtle bugs that way. Either make the slice a slice of pointers or return a value copy, but don’t take pointer to a slice of values because you will get bugs later.Yeah returning a reference to an element if a mutable slice doesn’t feel great given the slice can be reallocated. That said I think that if the slice is reallocated the reference that’s returned will keep the GC from cleaning up the old block of memory. So while you do hang on to some extra memory, at least there isn’t a true dangling pointer causing a memory safety issue. Does that match your understanding?
That’s correct, but it means that things work most of the time until they don’t. It’s the worst kind of bug because it only happens sometimes that you miss updates or unexpectedly overwrite an existing element.
I see what you’re saying—the issue isn’t a dangling pointer, it’s that mutations through the pointer will only be reflected in the slice if the slice hasn’t been reallocated. Yeah that’d be a super subtle bug to track down, thanks for pointing that out.
I don’t quite know why, but I very rarely mutate arrays (including appends) in the first place–or rather, I’ll build some slice by doing a bunch of appends (although I prefer to do a
make([]T, size)upfront if possible) but by the time someone else has a reference to the slice, it’s functionally immutable so I don’t need to worry about this sort of append scenario.Ideally Go would have enforced immutability semantics so we could express that a slice can’t be changed and it’s safe to take references to its items, but programming in this style seems like the next best thing (returning copies is good, but copies can contain pointers to other things, so leaning hard on copies for safety can be a different kind of pain).
What if you need to sort the slice? Or filter in place? That’s been a pain point for me because they seem like they should work, but you just messed up any pointers you already returned.
I think I concur with weberc2, I treat any slice that crosses a callstack boundary as essentially immutable, e.g.
Any code that receives a slice treats it as immutable, if e.g. I want to make changes to a received slice, I allocate a new slice, fill it by walking the input slice, and operate on the fresh value
Any code that returns a slice should return a unique value, if e.g. a method on a struct wants to return what is ultimately a field of that struct which is a slice, I always make a new slice in the method, copy elements over, and return the fresh value
Sorting a slice is something that I’d do prior to returning that slice. If a caller receives a slice, they’re free to do whatever to it, including appending and sorting, until they return it themselves. Filtering always looks like e.g.
Usually they’re sorted before I hand out pointers. I have a static site generator that does this—I load up all of my posts into a slice, sort by date, and then pass out pointers for further processing. I’m not sure when I would sort or append after I had already passed out pointers.
💯
A value method receiver like
(r Ruleset)expresses that the method doesn’t mutate the receiver. That expectation is violated if the receiver is a reference type (e.g. a slice) and the method returns a pointer to an interior member of that receiver (e.g. a pointer to an element of that slice).Things get even trickier when you consider callers who might call stuff that defines new slice 3-tuples which happen to re-use (part of) the backing array of that original slice. Here be dragons!
Are there any static tools that can analyze and point these things out? “You’re copying and then returning a reference to that copy” should probably be a check that happens at build time if you enable it..
Probably not because it’s possibly desirable, for example, you might not want callers to be able to mutate the original, so you allocate a copy and return a reference to it. If Go had immutability semantics, it might be a different story, but alas…
It’d still help to automatically point these things out! Then the programmer can decide if it’s a good optimization or not.
Oh, I fully agree. I guess I misunderstood your original proposal and was imagining a linter that errored when it found these. But I definitely think it would be cool, totally feasible, and immensely valuable to make an IDE plugin that highlighted these allocation points.
Someone on the orange site pointed out a similar example involving Go’s
regexppackage in the standard library:I teach classes on Go at Google, but I am not a language author so don’t take my word for it.
I have found it pays to always pass pointers to structs, never copy. It’s very easy to pass a struct to a function with a copy, mutate the struct, and then find out (much) later that the original doesn’t mutate because you mutated the copy. Many hours can be wasted debugging this.
There’s little value in copying, Go doesn’t have consts and pretending it is immutable will get you into trouble. I have seen some “experts” saying to use copies to try and create immutability, but this is trying to shoehorn something into the language that doesn’t exist. It makes code very hard to read and reason about. If the compiler can’t help you – which the Go compiler can’t because there’s no
constkeyword – then you shouldn’t try it. Note if you pass a copied struct but that struct itself contains a field that’s a pointer, then that field isn’t immutable and so you’re still in the same spot.+1 to your intuition here — I always default to operating on struct pointers, and only opt-in to struct values as special cases.
+1 to your judgment here, too — I’d be very surprised to see any Go “expert” suggest such a thing!
Can confirm I went to a workshop at Gophercon where the “copy for immutability” was espoused. Names withheld to protect the guilty :)
:o
FWIW, to prevent the bug where
a = bis slow for big types, Google’s C++ style guide used to mandate DISALLOW_COPY_AND_ASSIGN (which used to be DISALLOW_EVIL_CONSTRUCTORS I think) on all types (most types?)Instead you would do something like
a = b.Clone()I believeLooks like that’s been gone for awhile in favor of C++ 11 stuff, which I don’t really like:
https://google.github.io/styleguide/cppguide.html#Copyable_Movable_Types
A lot of good software was written in that style, but it has grown bureaucratic over time, and as the C++ language evolved
Indeed, C++ also makes it easy to create accidental copies, because it’s kind of the default. Relevant example:
Rust is like you describe with Google’s style guide: No implicit copying, but a clone trait you can implement and call. It’s one of those things that make the language a bit harder, but mostly because it makes mistakes harder.
Even python seems to agree, in principle:
Rust’s plain-data types can opt in to implicit copies (derive
Copy). But it’s really nice to have no copies as the default.Also ability to return a temporary read-only reference helps in cases like this, because you can give access to an element without copying it and without risk of the caller modifying it or being left with a dangling pointer.
You’re supposed to not derive
Copyunless your type can be blitted (or just memcpy’d) rather than needing actual construction. I don’t know if implementing it when you’re not supposed to can break compiler assumptions (as I’ve observedClonestill gets called) but as a rule, it would avoid the worst of these slow copy cases.Yeah, Copy types are the exception that proves the rule. They aren’t a performance concern in the same way, because they can’t own a resource (because of that
memcpycopyability: if it needs a destructor, it should need a custom clone function).Because this exception is really a sensible distinction, you can still search the codebase for “clone” and be confident you aren’t copying resources, which is what mostly matters, and is more readable than C++, where you have to delete operators to see if they are being called, which is easier said than done for non-custom types.
C++ got here via a very complex path. First, C had structures and structure assignment was defined as
memcpy. Removing that would break compatibility with any C headers that contained functions or macros that do structure assignment. Then C++ decided thatstructandclasswere equivalent except for the default visibility, which meant that the rule applied for any C++ object as well as any C structure. But some C++ classes needed to do non-trivial things (not justmemcpy) on copy, and so added copy constructors and copy assignment.Smalltalk-derived languages assumed garbage collection and so required all objects to be allocated on the heap, but C++ did not want to do this (and couldn’t for C compatibility) and so came with the additional constraint that you had to be able to copy an object into space reserved by the caller of the copy operation (this includes copying objects into globals and onto the stack). This meant that you coudn’t implement something like
clone(), where the return type depends on subclass relationship, you had to model these things as separate allocation and initialisation.This is further complicated by the fact that returning a structure is, in C++, modelled as copying the structure to the caller. For a long time, this copy has been optional (compilers may elide it - if you declare a local structure then return it then it will actually be created in the space that the caller passes down the stack). This was fun because copy constructors can have side effects and so it was observable in the abstract machine whether the compiler did this optimisation. C++17 made this mandatory, but this meant that any object that you wanted to return as an on-stack value needed to have a copy constructor.
So now we’re in a state where you need copy constructors and you need them to exist by default and where deleting them breaks some language features. Now C++11 came along with
autotypes. C++ has syntactic modifiers to say ‘pointer-to-Xand 'reference-to-Xbut nothing (outside of excitingtype_traitsthings) to saybare-type-that-this-reference-thing-applies-to. IfautodeducesT, then you can modify it to a reference by adding&, but ifautodeducesT&then it’s hard to modify it back toT. This meant thatautohad to default to deducingT, which meant that it was very easy to accidentally copy things. Compilers try to warn about this.Are also some interesting corner cases. You can make copy constructors
explicit(so they won’t be invoked without explicit syntax saying that you meant to call them) but you can’t do the same for copy assignment. Herb’s new syntax cleans up a lot of this but the Rust approach (which doesn’t have any of the legacy baggage) is much better than the current state of C++.I actually am glad that
autousually gives T and not&Tin these contexts - imagine how hard it would be to tell at a glance if a copy was being made or not (even if avoiding the copy requires an extra symbol in the soup).Yeah I definitely like opt-in better than opt-out, especially since code is generated! Too bad Go doesn’t have a mechanism for either one.
It is really hard to create a type in Go where copies like this are slow, because almost all primitive Go types have reference semantics. In practice the only way is to define types containing arrays (not slices) of substantial size. I haven’t seen a lot of Go code that has e.g.
type x structwithbuf [10000]uintptror whatever.Yeah that is an interesting difference, but I wouldn’t say “really hard” – since the OP had the problem, and someone else pointed to a comment where Russ Cox fixed the same problem in the Go standard library for a 40 byte struct, which was presumably all primitives
Digression …. I think contrasting the languages is interesting:
a = bbeing a copy for value typesa = bbeing a copy for value typesa = bis always a copy for value typesThinking about it a bit more, I think it’s a misfeature to reuse the same syntax for 2 different things
a = bis a pointer assignment – O(1) with respect to the size of the typea = bis a value assignment – O(N) with respect to the size of the typee.g. in my head I have been making a big list of things where “syntax doesn’t match semantics”, and it hadn’t occurred to me that this is one
I get your caveat that Go and C++/Rust structs aren’t equivalent though
I’m interested: what else is on that list?
A perf bug I have fixed repeatedly in other people’s Python code is:
If this is in a loop, then the first one is O(N^2), whereas the second is O(N), and I’ve seen that make scripts go from a 5 minute runtime to a second or so..
So that is very similar to
a = b, the syntax is too close for operations that mean different things. Most people just look at the syntax and don’t “visualize” what’s going on underneath, which is very different.A really trivial one that I remember someone having an extremely hard time with:
staticmeans 3 or 4 different things in C and C++:A Java programmer simply couldn’t wrap his head around the fact that the annotation on f() means “local to this translation unit” / not exposed to the linker. It’s a gratuitous “pun” because they didn’t want to reserve a new keyword, which is extremely confusing.
A lot of these syntactic conflicts are about shell. For example it took me a long time to realize that quoting means different things in different contexts in shell!
I never wrote a blog post about that, but most shell experts won’t be able to tell you the difference between them. Most of all because common shells don’t even agree on what they mean :)
Another example: People don’t know how to use the
findcommand because its syntax doesn’t match what they are used to for expression semantics: https://www.oilshell.org/blog/2021/04/find-test.htmlMore:
https://github.com/oilshell/oil/wiki/Shell-WTFs
https://github.com/oilshell/oil/wiki/Language-Design-Principles