investigate linear and polynomial interpolation, b-trees for I.

Question

investigate linear and polynomial interpolation, b-trees for I.

moon-chilled opened this issue 2 years ago · 3 comments

Answer 1 · 2022-10-04T01:12:55.000Z

also eytzinger https://arxiv.org/pdf/1509.05053.pdf https://algorithmica.org/en/eytzinger cf

Answer 2 · 2022-10-19T11:22:58.000Z

eytzinger probably wastes bandwidth if we can do multiple searches in parallel; otoh, if we are bottlenecked by latency, then eytzinger is good because prefetches don't take up rob space

Answer 3 · 2022-10-25T10:54:35.000Z

b-tree budgets one gpr per key. Vs 2 with the current scheme, or 2 vectors w/gather (which I'm warming to considering the comparatively better performance on intel & with avx512). Gather exposes more parallelism, but b-tree is more memory-efficient. Not sure which wins, especially in the face of potential partitioning of y. b-tree requires preprocessing though, which is a win for gather at some size classes.