Hitchhiker trees: functional, persistent, off-heap sorted maps • Hacker News Board

Re: Hitchhiker trees: functional, persistent, off-heap sorted maps

#31

Post by dgrnbrg » Sat, Aug 06, 2016, 2:05 AM UTC

anorwell wrote: post #30

I'm not sure I understand this. The claim is that "we dramatically improve the performance of insertions without hurting the IO cost of queries" by writing to the root's event log. However, it seems to me that this is only delaying the eventual write to the leaf node, not avoiding it. As more items are written, eventually the log will overflow and write to its children, and so on, until it is written to the leaf. Thi…

It's not just the root's event log--it's all the event logs. The deferrals allow us to batch writes in an optimized way, and do so with a fully incremental algorithm. In the IO cost model, each "block" read or costs 1 IOP to perform, so we can reduce the IOP cost of writes by a factor of 100-1000x, but reads will still have the same # of nodes to fetch. The event logs augmenting the tree are an effective IO optimization on a B+ tree.

Re: Hitchhiker trees: functional, persistent, off-heap sorted maps

#32

Post by anorwell » Sat, Aug 06, 2016, 9:12 PM UTC

dgrnbrg wrote: post #31

anorwell wrote: post #30

I'm not sure I understand this. The claim is that "we dramatically improve the performance of insertions without hurting the IO cost of queries" by writing to the root's event log. However, it seems to me that this is only delaying the eventual write to the leaf node, not avoiding it. As more items are written, eventually the log will overflow and write to its children, and so on, until it is written to the leaf. Thi…

It's not just the root's event log--it's all the event logs. The deferrals allow us to batch writes in an optimized way, and do so with a fully incremental algorithm. In the IO cost model, each "block" read or costs 1 IOP to perform, so we can reduce the IOP cost of writes by a factor of 100-1000x, but reads will still have the same # of nodes to fetch. The event logs augmenting the tree are an effective IO optimizat…

Thanks, makes sense.

Re: Hitchhiker trees: functional, persistent, off-heap sorted maps

#33

Post by jasonwatkinspdx » Tue, Aug 09, 2016, 1:55 AM UTC

continuational wrote: post #26

jasonwatkinspdx wrote: post #25

Earlier quoted context omitted.

> Processing log(n) bits takes at least O(log(n)) time. No, because log(n) might be smaller than the word size of the machine, which is the common case for hash table implementations.

If you limit log(n) and thus n to a constant, like the word size of the machine, then every algorithm is constant time .

No, I am not forcing all n of any size to a constant, I'm saying that we can bottom out inductively for small n.

This is a very old discussion. Read Knuth's rationale. Then read the similar sections in Segwick et all or whatever other basic competence textbook on algorithms you like. Compare them, think about which contexts each approach is most useful in.

In other words, no, you have not somehow cleverly invalidated all of complexity analysis.