Hacker News Reader

Comment by jitl | Hacker News Reader

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)

View on HN

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].

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.

It depends if they prefer array-of-structs versus struct-of-arrays layout. Isn't the latter usually faster?

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?

I think struct-of-arrays in this case would mean putting all the keys in one array and the values in a parallel array.

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?

Reply on news.ycombinator.com