Making Faster B-Trees with Go Generics

Sadly not public, but for those with access, Nick's deep dive into B-tree performance: go/ganpati-state-mgmt-v7

It sounds like btree could be further improved with a future version of generics that allows you to pass in array size constants statically?

Go supporters see C++ templates as abomination, yet these performance problems can be easily solved by C++ templates. C++ templates can have integer value in its template parameter, so if we implement that B-Tree in C++, we don't have to resort to codegen at all, as the language is powerful enough.

Huh, today I learned that there's a difference between a B-tree and a binary (search) tree, or at least, that the B-tree is a generalization of a binary tree where the nodes have multiple elements for efficiency. I'd always thought B-tree was just short for "binary tree".

> It's a great demonstration that there's some data structures that was impossible to implement properly (and generically) without native support in the language.

Go's purpose is to be easy to learn, not to write high performance code.

Int is a type used in Google own benchmarks, and yes it is a practical application. For example we use it with.

type RingEntry struct { node *Node token Token }

There are few nodes and many tokens.

Integer keys are not uncommon. It's just that they are usually combined as key/value map entry, like the BTreeMap in Rust, such as BTreeMap[int, *myObj] or BTreeMap[string, string]. Another interesting use is ordered set like BTreeSet[int].

Like many things, it's a spectator sport. Most people just parroted the opinions of the Go team -- which isn't a bad strategy, given how smart they are!

Don't worry, the anti-generics crowd is still here, waiting to see how things shake out. It will take years before we can confidently assess the impact of generics on the language and ecosystem.

A community is not a single person.

A lot of it is cargo-culting based on comments of the go-team members and applying the advice of go team members as a blanket as opposed to applying it more surgically in the context of your application.

For example I used to get a lot of pushback from the go community when using an assertion library, for those not familiar, go's testing library doesn't have support for asserts so you end up writing a lot of code like

  if  want != got {
    t.Fatalf(....)
  }

this gets esp annoying as you deal with more complex objects. Many in the go community criticize using an assertion library to write simple assertions as in other languages for your tests, citing that the go team members are against casually bringing dependencies in your project. Not realizing the intent Go Team's "statement against dependencies" is a targeted word of caution urging people to think about the dependencies they bring into their project rather than a blanket attitude against dependencies.

Almost certainly Go Team would not advise against bringing in a build time time dependency that is not even gonna be part of the binary you ship that will make your tests easier to write and error messages consistent.

> I find it curious that the vocal parts of the Go community touted the lack of generics as a feature for so long

Citation needed. Afaik the actual reason was general lack of understanding how to effectively implement it within constraints of Go’s philosophy

Your last paragraph is exactly right.

Contrary to your first statement though, there’s very little turnabout in the Go community and your Go-hating child posts fit into the two camps you mention at the end. We wanted it too, even feeling hamstrung!

I’m an old Gopher and I’ve spent a lot of my career in C++ and, now, Rust, so it’s not like I don’t understand generics. But I’ve also seen the space-cadet architectures that come out of overuse thereof. (Rust has a latent version of this, what with Arc<Mutex<T>> being the only way to get things done, come at me).

A common argument from the peanut gallery is that Go folks hate generics. No. I just hate the overly meta use thereof. I’ve long wanted an honest generic in Go for a few container types. This shows up as a desperate need, eh, maybe twice a sizeable project (and in a different way each time!). And I hate working around it but I do.

So it’s disingenuous at best to say Go folks don’t understand generics or are buying a party line thereof. We know it well, and know the nightmares it can lead to. So maybe appreciate some caution in giving the mice a cookie?

This isn’t the first iteration of this war, even. Another thing Go eschewed (that I rarely hear argued) is classes and, particularly, subclasses! Yet, every so often (including a recent project) that would be a really useful paradigm. But OOP is not “in vogue” and so that’s not one of the BS battlegrounds. Point is, all languages have pros and cons and there’s no one right way.

To quote a famous film, “Life is pain. Anyone who says otherwise is selling something” :)

Hi! OP here. Can you email me a screen shot of what you're seeing? We've been trying with a few iPads, and haven't been able to replicate the issue. peter at ScyllaDB dot com. Also let me know your device type, screen size, etc.

Thanks!

-Pete.

its worse. You can't do basic things like make a map method.

Typescript “generics” (type parameters) are probably the most powerful such feature in a mainstream language at the type level. Of course neither Java or Typescript generics improve code performance versus the T<any> or T<Object> version; whereas the Go version will improve performance due to memory stenciling or whatever they call it - memory allocation shape is improved and data is actually inlined into the container struct, so you can avoid pointer chasing all together if that’s your goal.

But there are two major drawbacks in Go generics now:

1. Methods cannot be generic, so you can’t do any chaining-style interfaces like thing.Map(…).Reduce(…) if you want to output a different type.

2. Possibly even worse: you cannot cast from Container[ConcreteType] to Container[any], or from Container[any] to Container[ConcreteType]. In my limited experimentation this was the most surprising blocker for me since it’s quite natural to work with Container<unknown> in Typescript, and possible (although I’m not sure how idiomatic) to do Container<Object> or Container<*> in Java/Kotlin.

Still when writing “normal” Go (as opposed to trying to abuse the type system), the generic slices package is a noticeable pain relief. But I actually don’t find myself implementing generic containers too much in the Go domain.

Coming from a C++, C#, Java background, the implementation of generics in Go seems half baked and less useful. Of course, it is better this way than no generics at all.

They are not typeless but dynamically typed. It's an important distinction.

The values have types it's just types aren't visible at compile time but can (must) be queried at run time to do anything useful with those values.