13 ms·

Shaving 40% Off Google’s B-Tree Implementation with Go Generics (2022)

114 points by 0xedb 3y ago

muglug 3y ago
(2022)
- dang 3y ago
  Added above. Thanks!
haolez 3y ago
Another way of seeing it is that "40% of the code became imaginary", in the sense that you have to figure out what the macro is expanding to. I'm not against generics. I was just wondering myself in a boring afternoon :)
- Ar-Curunir 3y ago
  Hm but the same argument can be made for anything the compiler does, no? Like I have no idea of how the compiler handles the `Interface`-based approach either.
- AaronFriel 3y ago
  The article is about performance or CPU time, not code size. Per the first paragraph, "In this blog post I’m going to show how, using the generics, we got a 40% performance gain in an already well optimized package, the Google B-Tree implementation."
  - hedora 3y ago
    I’m reasonably sure that running it through godbolt or using a coverage tool would show the (reachable) part of the program is smaller.
- nkozyra 3y ago
  In this case I don't think there's really any mystery or hidden code, though. Functions that operate on collections (or set-like structures) are what generics are most commonly used for, so there shouldn't be much surprise.
- deleted 3y ago
  [deleted]
- eru 3y ago
  > Another way of seeing it is that "40% of the code became imaginary", in the sense that you have to figure out what the macro is expanding to. The compiler does lots of internal 'expansion' steps in all kinds of different internal formats to spit out machine code at the end. We typically wonder what all those intermediate steps are. Why should we suddenly care, just because one of those internal formats can be interpreted as being compatible with an earlier version of the Go language? (I don't say, that the internal format _is_ the Go language, because I doubt their internal representation looks like the bytes you have in your .go file.)
jeffbee 3y ago
This may be confusing to those familiar with Google's libraries. The baseline is the Go BTree, which I personally never heard of until just now, not the C++ absl::btree_set. The benchmarks aren't directly comparable, but the C++ version also comes with good microbenchmark coverage. https://github.com/google/btree https://github.com/google/btree https://github.com/abseil/abseil-cpp/blob/master/absl/container/btree_set.h https://github.com/abseil/abseil-cpp/blob/master/absl/contai...
Pannoniae 3y ago
This feels like such a non-news. They've pretty much created a language which is deliberately dumbed down to be 20 years behind other languages, then they are proud that they could speed it up with a feature that was fairly well-known almost 20 years ago. Also the obsession with not providing tools for the programmer to use the stack, and rely on compiler internals to not heap-allocate everything.
- diogenes4 3y ago
  > 20 years behind other languages What a ridiculous attitude
- deleted 3y ago
  [deleted]
- yazzku 3y ago
  "There are many reasons to be excited about generics in Go." There were also many reasons to be excited about generics in C++, back in 1998 lol.
  - pjmlp 3y ago
    C++ compilers already had experimental template support in 1992, e.g. Turbo C++ for Windows 3.1.
  - eru 3y ago
    And C++ was already 25 years behind the times back then, because ML had generics in 1973.
- glotchimo 3y ago
  Because I genuinely don’t know, what do you mean when you say it’s 20 years behind other languages? Or rather, what features is it lacking that would make it up-to-date? And what languages are 20 years ahead of it?
  - eru 3y ago
    Have a look at https://news.ycombinator.com/item?id=943554 https://news.ycombinator.com/item?id=943554
dang 3y ago
Discussed at the time: Making Faster B-Trees with Go Generics - https://news.ycombinator.com/item?id=31182645 https://news.ycombinator.com/item?id=31182645 - April 2022 (44 comments)
softwarebeware 3y ago
The headline is dismal. Now writers can’t even be bothered to write what the improvement is? 40% of ______? “…Just trust us, 40% of something is ‘shaved’ …it’s good we promise.”
- deleted 3y ago
  [deleted]
kcudrevelc 3y ago
Hey, Google go b-tree implementation author here. A few important things: - this implementation was done by me while I worked at Google and needed a good ordered tree. It is not and never was supported by Google, just open sourced by the company and written on company time. - it now supports generics! Actually, iirc it did almost at the time that this article came out. In go 1.18 and higher, the original API uses a specialization of the generic underneath.
wtfishackernews 3y ago
I got similar improvements when porting hashicorp/golang-lru[1] name old time/op new time/op delta 2Q_Rand-16 1.22µs ±10% 0.52µs ± 8% -57.69% (p=0.000 n=20+19) 2Q_Freq-16 1.03µs ±10% 0.44µs ±12% -57.42% (p=0.000 n=18+20) ARC_Rand-16 1.51µs ± 9% 0.70µs ±15% -53.63% (p=0.000 n=20+20) ARC_Freq-16 1.22µs ±12% 0.54µs ± 7% -56.20% (p=0.000 n=20+20) LRU_Rand-16 401ns ± 9% 215ns ± 6% -46.46% (p=0.000 n=20+20) LRU_Freq-16 376ns ±13% 194ns ± 7% -48.51% (p=0.000 n=19+20) [1]: https://github.com/hashicorp/golang-lru/pull/111 https://github.com/hashicorp/golang-lru/pull/111

114 points by 0xedb 3y ago

muglug 3y ago

(2022)

dang 3y ago
Added above. Thanks!

haolez 3y ago

Another way of seeing it is that "40% of the code became imaginary", in the sense that you have to figure out what the macro is expanding to. I'm not against generics. I was just wondering myself in a boring afternoon :)

Ar-Curunir 3y ago
Hm but the same argument can be made for anything the compiler does, no? Like I have no idea of how the compiler handles the `Interface`-based approach either.
AaronFriel 3y ago
The article is about performance or CPU time, not code size. Per the first paragraph, "In this blog post I’m going to show how, using the generics, we got a 40% performance gain in an already well optimized package, the Google B-Tree implementation."
- hedora 3y ago
  I’m reasonably sure that running it through godbolt or using a coverage tool would show the (reachable) part of the program is smaller.
nkozyra 3y ago
In this case I don't think there's really any mystery or hidden code, though. Functions that operate on collections (or set-like structures) are what generics are most commonly used for, so there shouldn't be much surprise.
deleted 3y ago
[deleted]
eru 3y ago
> Another way of seeing it is that "40% of the code became imaginary", in the sense that you have to figure out what the macro is expanding to. The compiler does lots of internal 'expansion' steps in all kinds of different internal formats to spit out machine code at the end. We typically wonder what all those intermediate steps are. Why should we suddenly care, just because one of those internal formats can be interpreted as being compatible with an earlier version of the Go language? (I don't say, that the internal format _is_ the Go language, because I doubt their internal representation looks like the bytes you have in your .go file.)

jeffbee 3y ago

This may be confusing to those familiar with Google's libraries. The baseline is the Go BTree, which I personally never heard of until just now, not the C++ absl::btree_set. The benchmarks aren't directly comparable, but the C++ version also comes with good microbenchmark coverage. https://github.com/google/btree https://github.com/google/btree https://github.com/abseil/abseil-cpp/blob/master/absl/container/btree_set.h https://github.com/abseil/abseil-cpp/blob/master/absl/contai...

Pannoniae 3y ago

This feels like such a non-news. They've pretty much created a language which is deliberately dumbed down to be 20 years behind other languages, then they are proud that they could speed it up with a feature that was fairly well-known almost 20 years ago. Also the obsession with not providing tools for the programmer to use the stack, and rely on compiler internals to not heap-allocate everything.

diogenes4 3y ago
> 20 years behind other languages What a ridiculous attitude
deleted 3y ago
[deleted]
yazzku 3y ago
"There are many reasons to be excited about generics in Go." There were also many reasons to be excited about generics in C++, back in 1998 lol.
- pjmlp 3y ago
  C++ compilers already had experimental template support in 1992, e.g. Turbo C++ for Windows 3.1.
- eru 3y ago
  And C++ was already 25 years behind the times back then, because ML had generics in 1973.
glotchimo 3y ago
Because I genuinely don’t know, what do you mean when you say it’s 20 years behind other languages? Or rather, what features is it lacking that would make it up-to-date? And what languages are 20 years ahead of it?
- eru 3y ago
  Have a look at https://news.ycombinator.com/item?id=943554 https://news.ycombinator.com/item?id=943554

dang 3y ago

Discussed at the time: Making Faster B-Trees with Go Generics - https://news.ycombinator.com/item?id=31182645 https://news.ycombinator.com/item?id=31182645 - April 2022 (44 comments)

softwarebeware 3y ago

The headline is dismal. Now writers can’t even be bothered to write what the improvement is? 40% of ______? “…Just trust us, 40% of something is ‘shaved’ …it’s good we promise.”

deleted 3y ago
[deleted]

kcudrevelc 3y ago

Hey, Google go b-tree implementation author here. A few important things: - this implementation was done by me while I worked at Google and needed a good ordered tree. It is not and never was supported by Google, just open sourced by the company and written on company time. - it now supports generics! Actually, iirc it did almost at the time that this article came out. In go 1.18 and higher, the original API uses a specialization of the generic underneath.

wtfishackernews 3y ago

I got similar improvements when porting hashicorp/golang-lru[1] name old time/op new time/op delta 2Q_Rand-16 1.22µs ±10% 0.52µs ± 8% -57.69% (p=0.000 n=20+19) 2Q_Freq-16 1.03µs ±10% 0.44µs ±12% -57.42% (p=0.000 n=18+20) ARC_Rand-16 1.51µs ± 9% 0.70µs ±15% -53.63% (p=0.000 n=20+20) ARC_Freq-16 1.22µs ±12% 0.54µs ± 7% -56.20% (p=0.000 n=20+20) LRU_Rand-16 401ns ± 9% 215ns ± 6% -46.46% (p=0.000 n=20+20) LRU_Freq-16 376ns ±13% 194ns ± 7% -48.51% (p=0.000 n=19+20) [1]: https://github.com/hashicorp/golang-lru/pull/111 https://github.com/hashicorp/golang-lru/pull/111