[HN Gopher] Making Faster B-Trees with Go Generics
       ___________________________________________________________________
        
       Making Faster B-Trees with Go Generics
        
       Author : PeterCorless
       Score  : 57 points
       Date   : 2022-04-27 17:03 UTC (5 hours ago)
        
 (HTM) web link (www.scylladb.com)
 (TXT) w3m dump (www.scylladb.com)
        
       | mkesper wrote:
       | Interesting how useful generics seem to be vs typeless interfaces
       | and how long it took Go to incorporate them.
        
         | kjksf wrote:
         | 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.
        
       | jitl wrote:
       | 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)
        
         | f00_bar wrote:
         | 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.
        
       | judofyr wrote:
       | "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 wrote:
         | 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".
        
           | dataflow wrote:
           | Yup, there are also B+ and B* trees!
        
       | mort96 wrote:
       | 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 180deg 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 wrote:
         | 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.
        
       | robocat wrote:
       | 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.
        
       | opensrcken wrote:
       | As 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 wrote:
         | its worse. You can't do basic things like make a map method.
        
       ___________________________________________________________________
       (page generated 2022-04-27 23:01 UTC)