3 ms·
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
by jitl 5y ago
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 5y 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 5y 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 5y 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 5y agoIt depends if they prefer array-of-structs versus struct-of-arrays layout. Isn't the latter usually faster?
- jitl 5y 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 5y 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 5y 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 5y 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.
- jitl 5y agoI 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?