But this is like the best case optimization when converting old interface code to generics right? We’re able to convert a glob of pointers to a primitive value that fits in a register (…plus a hidden method dictionary somewhere), of course this is great.
But is BTree[int] really a real world test? Wouldn’t BTree[*struct {…}] be more common use-case? I wonder what the stats look like for that (with and without pointer indirection)
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].
That’s exactly my point, I would think BTree[struct { key int; val *whatever }] (index use case) or BTree[struct { key int; val inlineWhatever }] (heap use case) would be more common use cases than BTree[int] (int set use case), but probably less impressive delta on benchmarks.
I don’t understand your comment. What is “it”? Can you explain how BTree or each of the above use-cases relate to array-of-structs and struct-of-arrays concepts?
How do the two arrays you’re thinking of correspond to a BTree? If you’re thinking of two BTrees, how would that work? The BTree will sort the keys and values independently and they won’t line up - there’s nothing that maintains the associativity between the keys and values.
"Parallel" here means you don't change them independently. There is a constraint that they must always be in the same order, so key[i] corresponds to value[i]. Typically there is an API to do array operations like insert and delete that maintains this constraint.
So if you're sorting the keys and swap two of them, you make the same change to the values.
I know what struct-of-arrays is, but I am still wondering how struct-of-arrays relates to BTree. Are you imagining a BTree[key] and BTree[value]? How are associations maintained if the btrees sort independently?
I find it curious that the vocal parts of the Go community touted the lack of generics as a feature for so long, and that the language would be worse with them. It's nice that Go now does have the tools necessary to make usable, high-performance datastructures, but it's a bit frustrating to watch the apparent complete 180° flip from the community when the pro-generics parts were so vocally shouted down for so long.
I feel like so often, online discussions about these things become wars between the "X is the best thing ever and all the things you think are faults are actually features" camp and the "X is the worst thing ever because it lacks [single critical feature]" camp.
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 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.
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” :)
iPad only: If you are trying to read this on an iPad, use portrait. Landscape is utterly bokred (anyone here from Scylla, maybe mention to your site developer that the article doesn’t show at all, presumably same fault throughout site!?). Edit: or use reader mode. For some reason that option was greyed out when I first loaded the page.
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.
"40% faster?" Sure, but the original code doesn't make much sense. The whole purpose of a B-tree is that you store the keys in a contiguous array to take advantage of locality. If you're going to spread your data around behind pointers you're better suited using a node-based balanced binary search tree (red-black tree, AVL, treap).
This is of course still very exciting to see though! 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.
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".
"B+-trees have been supported since ScyllaDB Open Source 4.3, and our B-tree implementation was added in release 4.5. They are hidden, under-the-hood optimizations ScyllaDB users benefit from as we continue to evolve our infrastructure."
> 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.
you can do it that way but you can't add the map method to a struct like persons.map() which would allow you to chain methods. But I guess with the multiple return value convention, you can't chain anyway very nicely.
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.
Former Google engineer here. My team used the open source Go B-Tree implementation but I replaced it with a non-interface version over a year ago because of performance issues. The lack of generics at the time wasn't a problem because code generation is quite easy via Google's build system.
Replacing interfaces is only part of the performance improvement. When it comes to the B-Tree, you want to improve data locality as much as possible. My implementation also replaced slices with arrays (again using code gen to specify the tree degree). This means each node on the heap literally contained all the keys and, and in some cases, the values themselves. It also helped to split the key/values into separate arrays so all the values didn't interlace the keys.
The insert/retrieval benchmark times compared to the open source version were significantly faster. Since this version relied on codegen, I never bothered to push it publicly. Though, there are tons of B-tree implementations on github, each touting themselves as fastest.
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.
Anyone use Scylla? I've always been surprised there's room in the market for multiple Cassandra flavors--in general seems you don't see much adoption of pure play k/v stores outside of DynamoDB these days
this reminds me of Java. wrapper classes versus primitive types and their usage in collections. it was pretty much the same issue. having a Item struct wrapping an int versus using the int itself.
46 comments
[ 3.0 ms ] story [ 106 ms ] threadThe 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.
But is BTree[int] really a real world test? Wouldn’t BTree[*struct {…}] be more common use-case? I wonder what the stats look like for that (with and without pointer indirection)
type RingEntry struct { node *Node token Token }
There are few nodes and many tokens.
So if you're sorting the keys and swap two of them, you make the same change to the values.
I feel like so often, online discussions about these things become wars between the "X is the best thing ever and all the things you think are faults are actually features" camp and the "X is the worst thing ever because it lacks [single critical feature]" camp.
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.
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
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.
Citation needed. Afaik the actual reason was general lack of understanding how to effectively implement it within constraints of Go’s philosophy
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” :)
structs and functions on them are basically classes. golang lacks subclasses as you point out, otherwise everything is the same.
What concrete problems caused by the use of generics have you encountered? Do you see those problems coming to Go, as it now has generics, too?
Go seems to me a very verbose language and the addition of generics might improve things a bit in this direction.
Thanks!
-Pete.
This is of course still very exciting to see though! 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.
The Taming of the B-Trees https://www.scylladb.com/2021/11/23/the-taming-of-the-b-tree...
"B+-trees have been supported since ScyllaDB Open Source 4.3, and our B-tree implementation was added in release 4.5. They are hidden, under-the-hood optimizations ScyllaDB users benefit from as we continue to evolve our infrastructure."
Go's purpose is to be easy to learn, not to write high performance code.
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.
Replacing interfaces is only part of the performance improvement. When it comes to the B-Tree, you want to improve data locality as much as possible. My implementation also replaced slices with arrays (again using code gen to specify the tree degree). This means each node on the heap literally contained all the keys and, and in some cases, the values themselves. It also helped to split the key/values into separate arrays so all the values didn't interlace the keys.
The insert/retrieval benchmark times compared to the open source version were significantly faster. Since this version relied on codegen, I never bothered to push it publicly. Though, there are tons of B-tree implementations on github, each touting themselves as fastest.
But honestly, I really don’t understand why Go became this hyped.
nice usage of generics here.