6 ms·
Making Faster B-Trees with Go Generics
- mkesper 4y agoInteresting how useful generics seem to be vs typeless interfaces and how long it took Go to incorporate them.
- kjksf 4y agoThey 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.
- jitl 4y agoBut 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)
- f00_bar 4y agoInt 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.
- tidwall 4y agoInteger 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].
- jitl 4y agoThat’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.
- skybrian 4y agoIt depends if they prefer array-of-structs versus struct-of-arrays layout. Isn't the latter usually faster?
- jitl 4y agoI 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?
- skybrian 4y agoI think struct-of-arrays in this case would mean putting all the keys in one array and the values in a parallel array.
- jitl 4y agoHow 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.
- skybrian 4y ago"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.
- mort96 4y agoI 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.
- nemo1618 4y agoLike 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.
- jitl 4y agoA community is not a single person.
- avl999 4y agoA 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.
- robocat 4y agoiPad 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.
- PeterCorless 4y agoHi! 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.
- judofyr 4y ago"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.
- benhoyt 4y agoHuh, 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".
- dataflow 4y agoYup, there are also B+ and B* trees!
- PeterCorless 4y agoWe have a nice blog on that: The Taming of the B-Trees https://www.scylladb.com/2021/11/23/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."
- nanidin 4y agoHehehe, after reading this post I dug through my college projects to find my B+ tree implementation
- dataflow 4y agoI assume that was a "B+ tree" implementation and not a B+ "tree implementation"... :-)
- opensrcken 4y agoAs someone who tried out Go before generics and didn't like it, I'm curious how Go generics compare to generics in Java or Typescript.
- eweise 4y agoits worse. You can't do basic things like make a map method.
- liambowen 4y agoWhy can't you? https://github.com/samber/lo/blob/master/slice.go#L20 https://github.com/samber/lo/blob/master/slice.go#L20
- eweise 4y agoyou 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.
- jitl 4y agoTypescript “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.
- nicksardo 4y agoFormer 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.
- gkrimer 4y agoSadly not public, but for those with access, Nick's deep dive into B-tree performance: go/ganpati-state-mgmt-v7
- skybrian 4y agoIt sounds like btree could be further improved with a future version of generics that allows you to pass in array size constants statically?
- netheril96 4y agoGo 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.
- DeathArrow 4y agoThe two languages have different philosophies. C++ is targeted at performance while Go is intended to be easy to learn.
- redwood 4y agoAnyone 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
- blondin 4y agothis 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. nice usage of generics here.