Register a SA Forums Account here!
JOINING THE SA FORUMS WILL REMOVE THIS BIG AD, THE ANNOYING UNDERLINED ADS, AND STUPID INTERSTITIAL ADS!!!

You can: log in, read the tech support FAQ, or request your lost password. This dumb message (and those ads) will appear on every screen until you register! Get rid of this crap by registering your own SA Forums Account and joining roughly 150,000 Goons, for the one-time price of $9.95! We charge money because it costs us money per month for bills, and since we don't believe in showing ads to our users, we try to make the money back through forum registrations.
 
  • Post
  • Reply
Coffee Mugshot
Jun 26, 2010

by Lowtax
We changed that because people started writing tests in Google that explicitly relied on default map ordering and then complained when it was modified by the runtime in following releases for their production binaries. Also, since the Go spec does not define the ordering, the two implementations of the compiler, gc and gccgo, had two different default orderings. GCC picks a default the last time I worked on it, at least. So, at the time, within Google, we had people building ppc and arm binaries with gccgo where their ordering assumptions were now wrong. Overall, we never found the real intention behind relying on a consistent default ordering. If you wanted a particular ordering, it seems like you would necessarily need to sort the data in some way. Anyways, it wasn't some random decision and I think Russ agreed with your reasoning around go1.3, before we noticed how misused this "feature" was.

Adbot
ADBOT LOVES YOU

TheBlackVegetable
Oct 29, 2006
I don't know Go, but maybe if iterating the elements of a Hashtable doesn't makes sense unless they are sorted first, then it should only be possible if you call a .sort () method to return a (k*v) list?

Not that I can think of a programming language that does this though.

Coffee Mugshot
Jun 26, 2010

by Lowtax

TheBlackVegetable posted:

I don't know Go, but maybe if iterating the elements of a Hashtable doesn't makes sense unless they are sorted first, then it should only be possible if you call a .sort () method to return a (k*v) list?

Not that I can think of a programming language that does this though.

Would this mean that maps, in general, would not be able to be iterable unless they were sorted? It's not that iterating elements of a hashtable doesn't make sense, but relying on a particular order without specifying it directly in code (with a comparator, for example) is probably a bug or a bad assumption.

Munkeymon
Aug 14, 2003

Motherfucker's got an
armor-piercing crowbar! Rigoddamndicu𝜆ous.



Coffee Mugshot posted:

Would this mean that maps, in general, would not be able to be iterable unless they were sorted? It's not that iterating elements of a hashtable doesn't make sense, but relying on a particular order without specifying it directly in code (with a comparator, for example) is probably a bug or a bad assumption.

for k, v := range mahMap using sort.Ints seems pretty readable. orderby instead of using, if you feel like it. IDK what all the reserved words are in Go

Eela6
May 25, 2007
Shredded Hen

Coffee Mugshot posted:

Would this mean that maps, in general, would not be able to be iterable unless they were sorted? It's not that iterating elements of a hashtable doesn't make sense, but relying on a particular order without specifying it directly in code (with a comparator, for example) is probably a bug or a bad assumption.

You can iterate through a map no problem by simply going through all the keys. Since keys are unique, there's no danger of missing or repeating a key unless you modify the map mid-way.

There are map implementations that preserve insert order; such as the one that Python 3.6+ uses.. This is both predictable and occasionally useful. If there's no runtime cost, why not have a default that makes sense?

Note: in Python 3.6, this is currently an implementation detail and your code should use collections.OrderedDict to specify your intent.

Eela6 fucked around with this message at 21:46 on Jul 6, 2017

QuarkJets
Sep 8, 2008

ullerrm posted:

It's actually even worse than that -- it's "programmers are uniformly stupid and will blown their own arm off given the chance, so let's make a language even more stupid as the programmers that makes it hard as possible to blow off their arms." For example: If you iterate over the keys in a map, what order do they come in? In most languages, it's either "ordered ascending" (because the map is backed by a red-black tree) or "implementation-defined" which means unknown but consistent (because the map is backed by a hash table).

In Go? It's randomized at runtime. The standard implementation of Go's map is a hash table, but it picks a random index at in the bucket list as the start point for iterating over the keys, so that not only is it implementation-defined, it's unpredictable. They did this by design because they figured it'd be impossible for programmers to notice and depend on an implementation-defined key ordering, if there was none.

At times, Go feels like Google's last resort because they couldn't convince college grads to program in a nice safe harmless language like LOGO.

That's fascinating, are there more of these that you could summarize? I tried looking around for articles complaining about other weird Go design features but could only find things there were like "Go has pointers, I have to google for Golang instead of Go, a bloo bloo bloo :qq:"

TheBlackVegetable
Oct 29, 2006

Coffee Mugshot posted:

Would this mean that maps, in general, would not be able to be iterable unless they were sorted? It's not that iterating elements of a hashtable doesn't make sense, but relying on a particular order without specifying it directly in code (with a comparator, for example) is probably a bug or a bad assumption.

It would. Maybe couple it with an .unsortedkeys method I dunno. Basically, make invalid code unrepresentable.

Edit: or at least explicit.

TheBlackVegetable fucked around with this message at 21:50 on Jul 6, 2017

Jaded Burnout
Jul 10, 2004


TheBlackVegetable posted:

I don't know Go, but maybe if iterating the elements of a Hashtable doesn't makes sense unless they are sorted first, then it should only be possible if you call a .sort () method to return a (k*v) list?

Not that I can think of a programming language that does this though.

Iterating a hash does make sense without ordering semantics as long as whatever operation you're doing isn't interested in the order. Ruby does exactly what you suggested when ordering is requested:
code:
irb(main):001:0> {b: 1, a: 2}.sort
=> [[:a, 2], [:b, 1]]
Otherwise it iterates in insertion order (as of around 2009). I don't know anyone who actually relies on that, though.

Eela6
May 25, 2007
Shredded Hen

QuarkJets posted:

That's fascinating, are there more of these that you could summarize? I tried looking around for articles complaining about other weird Go design features but could only find things there were like "Go has pointers, I have to google for Golang instead of Go, a bloo bloo bloo :qq:"

Well, suppose I wanted to iterate through a map of an arbitrary type, sorted by the map value.

Suppose it's a map called "teams": [Player] -> [Team]. We want to iterate through sorted by team color, then name as a fallback.

Here it is in python:

Python code:
for player, team in sorted(teams.items(), key=lambda x: x[1].color, x[1].name):
    (code)
And here it is in go:
code:
var teams map[Player]Team
type byColorAndName []Player


func (players byColorAndName) Len() int {
	return len(teams)
}
func (players byColorAndName) Less(i, j int) bool {
	ti, tj := teams[players[i]], teams[players[j]]
	return ti.color < tj.color || (ti.color == tj.color && ti.name < tj.name)
}

func (teams byColorAndName) Swap(i, j int) {
	teams[i], teams[j] = teams[j], teams[i]
}

var sortedPlayers byColorAndName

for player := range teams {
		sortedPlayers = append(sortedPlayers, player)
	}
	sort.Sort(sortedPlayers)
	for _, player := range sortedPlayers {
		team := teams[player]
		// some code
	}
If I want to change how I sort, I have to create an entire new type and do the whole song and dance.

Eela6 fucked around with this message at 22:17 on Jul 6, 2017

TooMuchAbstraction
Oct 14, 2012

I spent four years making
Waves of Steel
Hell yes I'm going to turn my avatar into an ad for it.
Fun Shoe

Eela6 posted:

If I want to change how I sort, I have to create an entire new type and do the whole song and dance.

There's sort.Slice now, which takes a comparison function. If you're really lucky, it'll actually be available on your target system! :shepface:

(It is not available on our target system, which means we have sortableInt32, sortableInt64, etc. types in our codebase just so we can sort a goddamn list of numbers)

Eela6
May 25, 2007
Shredded Hen

TooMuchAbstraction posted:

(It is not available on our target system, which means we have sortableInt32, sortableInt64, etc. types in our codebase just so we can sort a goddamn list of numbers)

there you have it, folks

TwoDice
Feb 11, 2005
Not one, two.
Grimey Drawer

Coffee Mugshot posted:

We changed that because people started writing tests in Google that explicitly relied on default map ordering and then complained when it was modified by the runtime in following releases for their production binaries. Also, since the Go spec does not define the ordering, the two implementations of the compiler, gc and gccgo, had two different default orderings. GCC picks a default the last time I worked on it, at least. So, at the time, within Google, we had people building ppc and arm binaries with gccgo where their ordering assumptions were now wrong. Overall, we never found the real intention behind relying on a consistent default ordering. If you wanted a particular ordering, it seems like you would necessarily need to sort the data in some way. Anyways, it wasn't some random decision and I think Russ agreed with your reasoning around go1.3, before we noticed how misused this "feature" was.

If you rely on the iteration order of an explicitly unordered data structure (like a java HashMap) you should probably be shot into space. I'm not a huge fan of go, but randomizing the order of maps is awesome.

FrantzX
Jan 28, 2007
That seems OK to me as well. If iteration order is not defined or guaranteed, then randomizing the order is perfectly acceptable. I suppose randomization does have a performance cost, but would it matter on a practical level?

Jabor
Jul 16, 2010

#1 Loser at SpaceChem
FWIW, in Java you get to choose between a HashMap (which has no defined iteration order), and a LinkedHashMap which has some additional bookkeeping overhead but iterates elements in the order they were inserted.

Of course, even if it wasn't part of the library, you could implement that sort of utility yourself if you really needed it. If only Go had the mechanisms that would allow people to implement their own collections libraries for niche things that aren't built-in to the language.

boo_radley
Dec 30, 2005

Politeness costs nothing

Coffee Mugshot posted:

We changed that because people started writing tests in Google that explicitly relied on default map ordering
This seems like a bonkers thing to do. It's always been my assumption that in hashes, the ordering and storage of elements in part of the black box and subject to the whims of designers, compilers and etc. etc. etc. all the time.

Coffee Mugshot posted:

Overall, we never found the real intention behind relying on a consistent default ordering.
This makes it sound like some programmers were creating -- not sure what to call it -- stunt tests? things that go far beyond what's expected of a typical unit test for extra credit.

Coffee Mugshot posted:

If you wanted a particular ordering, it seems like you would necessarily need to sort the data in some way.
Yep! If you need reliable ordering, it's incumbent on you to make it reliable when you pull it out of the hash.

TooMuchAbstraction
Oct 14, 2012

I spent four years making
Waves of Steel
Hell yes I'm going to turn my avatar into an ad for it.
Fun Shoe

boo_radley posted:

This seems like a bonkers thing to do. It's always been my assumption that in hashes, the ordering and storage of elements in part of the black box and subject to the whims of designers, compilers and etc. etc. etc. all the time.

It's very easy to make a test that accidentally relies on ordering; just have a function that outputs a list of items, in the order in which it iterates over the contents of a hashmap, and then compare that list to your test value. Surprise, your test now relies on the ordering of keys in a hashmap, even though you don't really care about that ordering, only that the two lists have the same items in them. Literally every time Go has broken my tests due to randomized hash iteration order, it's been due to that type of thing. The actual behavior was just fine, it just wasn't consistently verifiable, and it was easier to say "gently caress it, we sort the drat keys" than it was to write a set-comparison function that takes two lists of <whatevers>.

I mean, the tests are broken either way, you shouldn't rely on ordering of hash iteration.

CPColin
Sep 9, 2003

Big ol' smile.
Yeah, I get the motivation behind the library enforcing, "No really, the iteration order is effectively random!" but I'm wary of a language where the designers come up with that as a solution to the problem of programmers relying on undefined behavior. (Now that the behavior is defined, it's documented, right?)

ulmont
Sep 15, 2010

IF I EVER MISS VOTING IN AN ELECTION (EVEN AMERICAN IDOL) ,OR HAVE UNPAID PARKING TICKETS, PLEASE TAKE AWAY MY FRANCHISE

CPColin posted:

(Now that the behavior is defined, it's documented, right?)

...the behavior is still not defined - the ordering can be anything.

Bongo Bill
Jan 17, 2012

Here's the question that leads to further horror: is the ordering's randomness of cryptographic quality?

sarehu
Apr 20, 2007

(call/cc call/cc)
Avoiding delivering any behaviors that people might rely upon is sensible practice, despite the howling of some noobs ITC. Even with an ordered map holding the data I've had occasion to return elements in reverse order, just to keep API consumers on edge.

UraniumAnchor
May 21, 2006

Not a walrus.

CPColin posted:

Yeah, I get the motivation behind the library enforcing, "No really, the iteration order is effectively random!" but I'm wary of a language where the designers come up with that as a solution to the problem of programmers relying on undefined behavior. (Now that the behavior is defined, it's documented, right?)

I mean I would almost prefer this sort of thing in debug/test builds because it would expose unintentional reliance on unspecified behavior, but being unable to turn it off in release builds seems like a big red flag.

The Laplace Demon
Jul 23, 2009

"Oh dear! Oh dear! Heisenberg is a douche!"

TooMuchAbstraction posted:

It's very easy to make a test that accidentally relies on ordering; just have a function that outputs a list of items, in the order in which it iterates over the contents of a hashmap, and then compare that list to your test value. Surprise, your test now relies on the ordering of keys in a hashmap, even though you don't really care about that ordering, only that the two lists have the same items in them. Literally every time Go has broken my tests due to randomized hash iteration order, it's been due to that type of thing. The actual behavior was just fine, it just wasn't consistently verifiable, and it was easier to say "gently caress it, we sort the drat keys" than it was to write a set-comparison function that takes two lists of <whatevers>.

I mean, the tests are broken either way, you shouldn't rely on ordering of hash iteration.

Why would I use a language without a set type where I can make that mistake in the first place? Why should I have to write code to sort a hash map when I want to see if two sets are equal? How is that simple?

QuarkJets
Sep 8, 2008

TooMuchAbstraction posted:

It's very easy to make a test that accidentally relies on ordering; just have a function that outputs a list of items, in the order in which it iterates over the contents of a hashmap, and then compare that list to your test value. Surprise, your test now relies on the ordering of keys in a hashmap, even though you don't really care about that ordering, only that the two lists have the same items in them. Literally every time Go has broken my tests due to randomized hash iteration order, it's been due to that type of thing. The actual behavior was just fine, it just wasn't consistently verifiable, and it was easier to say "gently caress it, we sort the drat keys" than it was to write a set-comparison function that takes two lists of <whatevers>.

I mean, the tests are broken either way, you shouldn't rely on ordering of hash iteration.

But it's a hash map; I'm assuming it's just as easy to iterate through your list of test values and check whether each one is also a key in the hashmap as it is to check whether the list of keys returned by the hashmap is the same as your test list

e: Are the hashmap keys not also a set?

QuarkJets fucked around with this message at 06:40 on Jul 7, 2017

Snak
Oct 10, 2005

I myself will carry you to the Gates of Valhalla...
You will ride eternal,
shiny and chrome.
Grimey Drawer

QuarkJets posted:

But it's a hash map; I'm assuming it's just as easy to iterate through your list of test values and check whether each one is also in the hashmap as it is to check whether the list of items returned by the hashmap is the same as your test list

Yeah, surely that would be faster than sorting and then comparing...

edit: hmm, not necessarily. I am dumb.

CPColin
Sep 9, 2003

Big ol' smile.

ulmont posted:

...the behavior is still not defined

Sure it is:

ulmont posted:

the ordering can be anything.

(What I'm suggesting is that if an implementation is purposefully avoiding having a consistent iteration order, it might help to state that in the documentation.)

CPColin fucked around with this message at 06:49 on Jul 7, 2017

Absurd Alhazred
Mar 27, 2010

by Athanatos

Bongo Bill posted:

Here's the question that leads to further horror: is the ordering's randomness of cryptographic quality?

You can't fix stupiddevelopers/testers depending on discovered behavior, defined by spec or not!

comedyblissoption
Mar 15, 2006

What's the overhead of having to generate a random number without data races for iteration?

What's the overhead of increasing memory cache misses on iteration?

I think it's an okay philosophy for the standard library to incur performance penalties to make it easier to do the right thing, but it becomes a dumb philosophy when you can't roll your own without the performance penalties.

redleader
Aug 18, 2005

Engage according to operational parameters
The .NET System.String type explicitly states that a string's hash code is not guaranteed to be stable and should not be relied on or persisted anywhere, etc. The docs are filled with warnings about this.

Relying on a stable string hash code got to be such a problem within Microsoft that they took a drastic approach to preventing MS devs from trusting it:
code:

hash1 ^= ThisAssembly.DailyBuildNumber;

I won't award points to anyone who can guess why I know this.

Hammerite
Mar 9, 2007

And you don't remember what I said here, either, but it was pompous and stupid.
Jade Ear Joe
Enforcing a random order - at least in debug - so that people are likely to notice when they've written broken code seems like such an obviously good idea that I'm surprised it's proving controversial in this thread. I'm not sure what the alternatives are supposed to be, besides "don't have implementation-defined behaviour in the language" (unnecessarily constricting) or "programmers should just be good enough at their jobs that they don't need that" (good luck with that).

Internet Janitor
May 17, 2008

"That isn't the appropriate trash receptacle."
Alternatives to the current design problem include:

  • Using a map implementation which preserves insertion order. That some programmers are writing code that depends on order suggests this is a desirable property, and it is not necessarily very expensive to provide.
  • Offering a built-in Set datatype with an appropriate method for comparing equality. This would permit easily writing tests which were insensitive to order.
  • Offering the ability to write one's own first-class data structures so that either of the above could be written as a library.

I think that this is a good example of Go boxing itself into a language-design corner in pursuit of Rob Pike's weird definition of "simplicity".

TwoDice
Feb 11, 2005
Not one, two.
Grimey Drawer

Internet Janitor posted:

Alternatives to the current design problem include:

  • Using a map implementation which preserves insertion order. That some programmers are writing code that depends on order suggests this is a desirable property, and it is not necessarily very expensive to provide.
  • Offering a built-in Set datatype with an appropriate method for comparing equality. This would permit easily writing tests which were insensitive to order.
  • Offering the ability to write one's own first-class data structures so that either of the above could be written as a library.

I think that this is a good example of Go boxing itself into a language-design corner in pursuit of Rob Pike's weird definition of "simplicity".

otoh forcing everyone to use an ordered map unnecessarily hurts performance for most use cases

Spatial
Nov 15, 2007

That's why you have more than one type of map, my man.

Munkeymon
Aug 14, 2003

Motherfucker's got an
armor-piercing crowbar! Rigoddamndicu𝜆ous.



I just realized that this reminds me of picking a random initial partition location in quicksort, which can be good practice.

TooMuchAbstraction posted:

It's very easy to make a test that accidentally relies on ordering; just have a function that outputs a list of items, in the order in which it iterates over the contents of a hashmap, and then compare that list to your test value. Surprise, your test now relies on the ordering of keys in a hashmap, even though you don't really care about that ordering, only that the two lists have the same items in them. Literally every time Go has broken my tests due to randomized hash iteration order, it's been due to that type of thing. The actual behavior was just fine, it just wasn't consistently verifiable, and it was easier to say "gently caress it, we sort the drat keys" than it was to write a set-comparison function that takes two lists of <whatevers>.

I mean, the tests are broken either way, you shouldn't rely on ordering of hash iteration.

But isn't this only a problem because Go doesn't have an easy way to check for list membership?

comedyblissoption posted:

What's the overhead of having to generate a random number without data races for iteration?

What's the overhead of increasing memory cache misses on iteration?

I think it's an okay philosophy for the standard library to incur performance penalties to make it easier to do the right thing, but it becomes a dumb philosophy when you can't roll your own without the performance penalties.

Sounds like it only picks a random initial bucket when the map is created, which wouldn't be a big deal. https://github.com/golang/go/issues/5362#issuecomment-66078620

JawnV6
Jul 4, 2004

So hot ...

Hammerite posted:

"programmers should just be good enough at their jobs that they don't need that" (good luck with that).

I kinda have a hard time understanding how Googlers are at the absolute pinnacle of the profession, top notch in every way, incredibly high bar for any applicant, except their in-house language keeps having to file down anything sharper than a marble. FWIW I like all of IJ's solutions, especially sets if the root cause is testers don't have an easy way to check lists.

TooMuchAbstraction
Oct 14, 2012

I spent four years making
Waves of Steel
Hell yes I'm going to turn my avatar into an ad for it.
Fun Shoe

QuarkJets posted:

But it's a hash map; I'm assuming it's just as easy to iterate through your list of test values and check whether each one is also a key in the hashmap as it is to check whether the list of keys returned by the hashmap is the same as your test list

e: Are the hashmap keys not also a set?

You can fake a set in Go by using map[whatever]bool, so long as you only care about membership (and not intersection/unity/set equality/etc.). But note that I said the code was outputting a list of elements, that happened to be ordered based on the order in which the code iterated over a map. So basically our options were either a) sort the map keys, to enforce a consistent order in the output list, or b) write a comparison function that takes two input lists, sorts them (or converts them to maps, etc.), then iterates over both of them to ensure that every element in each is also in the other.

It happens that this pattern shows up many times in our codebase, and that the keys are always int32s (they're database primary keys, and yes, 4 billion of them should be enough for many, many years), so we just implemented SortableInt32. We still have to remember to sort the keys every time we iterate over a map that's feeding into a result list, lest our tests break, though.

leper khan
Dec 28, 2010
Honest to god thinks Half Life 2 is a bad game. But at least he likes Monster Hunter.

TooMuchAbstraction posted:

You can fake a set in Go by using map[whatever]bool, so long as you only care about membership (and not intersection/unity/set equality/etc.). But note that I said the code was outputting a list of elements, that happened to be ordered based on the order in which the code iterated over a map. So basically our options were either a) sort the map keys, to enforce a consistent order in the output list, or b) write a comparison function that takes two input lists, sorts them (or converts them to maps, etc.), then iterates over both of them to ensure that every element in each is also in the other.

It happens that this pattern shows up many times in our codebase, and that the keys are always int32s (they're database primary keys, and yes, 4 billion of them should be enough for many, many years), so we just implemented SortableInt32. We still have to remember to sort the keys every time we iterate over a map that's feeding into a result list, lest our tests break, though.

Why are you using this language if it's painful to do anything in?

Eela6
May 25, 2007
Shredded Hen
Go is a terrible language but a decent back-end environment. Easy deployment and compilation to small native code binaries is often worth a lot of hassle.

It's in many ways the opposite of Python, which is an excellent language but often hellish to deploy. That's not quite as easy to point and laugh at in this thread, however.

Despite all my complaints about Go, I'd rather work in it than, say, C, C++, or Javascript. The problem with Go is that it's so close to being a truly excellent language, and then you run right into :stonk:

For example, the entire math library. Why the gently caress is doing basic math such a nightmare in go.

It's just easy to complain about because so much of this stuff would be trivial to fix, but it would ruin rob pike's dumb vision. If go were just bad it would be easy to ignore. It's the mixture of good and bad that makes it infuriating.

Eela6 fucked around with this message at 17:37 on Jul 7, 2017

Lordshmee
Nov 23, 2007

I hate you, Milkman Dan
I want to, ever so slowly, strangle to death the bastard that decided to not only implement a Repository pattern for this jank-rear end website but hid it under *3* interfaces. Shift-F12, Shift-F12, Shift-F12, gently caress YOU!

Space Kablooey
May 6, 2009


Wait. Go doesn't have any built-in Sets?

Adbot
ADBOT LOVES YOU

TooMuchAbstraction
Oct 14, 2012

I spent four years making
Waves of Steel
Hell yes I'm going to turn my avatar into an ad for it.
Fun Shoe

HardDiskD posted:

Wait. Go doesn't have any built-in Sets?

Its built-in data structures are array, slice, map, and struct.

  • 1
  • 2
  • 3
  • 4
  • 5
  • Post
  • Reply