Comment by akavel | Hacker News Reader

Comment by akavel | Hacker News Reader

Parent Full thread

I hold the source code of Go standard library & base distribution (i.e. compiler, etc.) in very high regard. Especially the standard library is, in my opinion, stunningly easy to read, explore and understand, while at the same time being well thought through, easy to use (great and astonishingly well documented APIs), of very good performance, and with huge amounts of (also well readable!) tests. The compiler (including the runtime library) is noticeably harder to read and understand (especially because of sparse comments and somewhat idiosyncratic naming conventions; that's partly explained by it being constantly in flux). But still doable for a human being, and I guess probably significantly easier than in most modern compilers. (Though I'd love to be proven wrong on this account!)

At the same time, the apparent simplicity should not be mistaken for lack of effort; on the contrary, I feel every line oozes with purpose, practicality, and to-the-point-ness, like a well sharpened knife, or a great piece of art where it's not about that you cannot add more, but that you cannot remove more.

This is one of the great things about many Go libraries; the language is so simple its difficult to overcomplicate a Go project. This makes reading any Go source code, projects, libraries, the stdlib, a joy. The only times I've found Go libraries to be a PITA to read is when they get autogenerated from some other language (protobuf compilations, parts of the compiler that came from C, AWS/GoogleCloud/Azure libraries, etc), but that's to be expected in every language.

Kubernetes is another great example of a project that is so unbelievably complex in its function, it should be completely impenetrable to anyone who isn't a language expert. But, go check it out; its certainly complex and huge, but actually grokable.

I would argue while Kubernetes is a great piece of software, and its definitely practical to go in with relatively little experience and tweak a single line or function, Kubernetes is not easy to grok or reproduce in its entirety for example it has its own implementation of generics and a custom type system [1].

[1]: https://medium.com/@arschles/go-experience-report-generics-i...

I'd agree, but only as far as aesthetics go. When you have to understand the time complexity and runtime characteristics of the standard library sorting algorithms, I think Go does a very bad job - the standard `sort.Sort(data sort.Interface)` will run poorly if the data is already mostly sorted. I expect these kinds of things to be documented properly.

Golang's `sort.Sort(data sort.Interface)` will sort mostly-sorted data in nearly its fastest possible time, because it basically uses median-of-three quicksort, falling back to insertion sort for small partitions. Median-of-three on sorted or nearly-sorted data picks the optimal or nearly optimal partitioning element for quicksort. The code is simple, readable, and well-commented. Moreover, its average and worst-case complexity is documented in the godoc.

In short, your comment is wrong from beginning to end. What led you to believe that anything in it was true?

It's guaranteed to run in O(n log n) time. Currently it uses quicksort with heapsort as a fallback to prevent quicksort's quadratic worst-case time.

https://golang.org/src/sort/sort.go?s=5414:5439#L206

I was pretty certain most libraries shuffle then quicksort. No need for documentation. Does go not do this?

JVM and Python use timsort, which is O(N) on mostly sorted data of all kinds.

timsort is full of win, and such a clever approach.

I'm sorry, but Timsort is a bit of a hack. It's a "this seems to work well" algorithm, and it shows. It took 13 years until its claimed running time was finally proven in 2015. The four (originally three) rules for merging sequences from the stack are rather arbitrary. Multiple issues were found well after it was already widely deployed.

Recently, it was also shown that Timsort doesn't optimally use the information it has about runs. As an alternative, powersort was proposed, which seems to outperform Timsort both on randomly ordered inputs as well as inputs with long runs: https://arxiv.org/pdf/1805.04154.pdf

Totally! And there are much better algorithms for the internet routing protocols, very well documented and tested and all, still just sitting on desks under paperweights...

> a bit of a hack

Isn't that most of computing?

Ever heard of Timsort?

People were still finding bugs in common implementations of timsort as of 3 years ago. It's not unreasonable to stick with a somewhat more conservative choice for a core library function until there's more reason to have confidence in the implementations of timsort.

This comment got me looking into timsort bugs. This was a really interesting read: http://envisage-project.eu/proving-android-java-and-python-s...

You know what, I'm not surprised at all.

Didn't one of the most simple algorithms, binary search, suffered of a bug in a standard library (was it Java?) a few years ago? If IIRC it was a corner case, I should check it because I don't recall the details, but it looked robust code.

Edit: I think it's this one https://ai.googleblog.com/2006/06/extra-extra-read-all-about...

If I recall correctly, the bug only applied for arrays/lists of length greater than 2 to the more-than-astronomical. Not something that anyone ever encountered in the wild, because current hardware doesn't have enough memory.

Edit: The article linked in the other comment says the Java dev team didn't even bother to implement the "proper" fix, but merely adjusted how much space is allocated.

Timsort always reminds me of monkeysort ( http://leonid-shevtsov.github.io/monkeysort/ )

Being pretty certain isn't the same as being certain. I really don't care what most libraries do as long as they document what exactly they have chosen to do. Go's `sort.Sort(data Interface)` definitely does not shuffle.

> standard library is, in my opinion, stunningly easy to read

Reading this brought to mind the JDK. All well structured, neatly formatted and well documented. I’ll often just click thru to the source to get the nitty-gritty on a function, I rarely need to consult the actual docs!

not c++ stl. Very obscure.

Some would consider that a virtue

How is hard to read code a virtue. ?

The fact that almost everyone uses the same style and standards through the go tools has made learning easy. I can dip into the most advanced package and make sense of what's going on quickly.

I think one of the things that makes Go library code so easy to read is the lack of generics. Everything you need to understand the code is right in front of you, without the barrier of having to learn new sets of complicated abstractions or worrying that some obscure code in some other file impacts/is invisibly called by the function. With large code bases written in other programming languages, I have to spend an inordinate amount of time studying the code base and object relations before making changes.

For me, code readability is such a high value that, on these grounds alone, I oppose the introduction of generics and hope the current proposals ultimately fail.

As far as I know, parts of the compiler are still code automatically translated from C, so this may be part of the reason.

It is not, the compiler has been pure Go since, I think, v1.4.

That doesn't invalidate the parent comment :) The code is pure Go, but parts of it originate in C by means of automatic translation during development of Go 1.4 (or whichever version it was).

Exactly, here's the tool that's been used: https://github.com/rsc/c2go

Reply on news.ycombinator.com