Add treap ascending Iterators.

Add treap ascending Iterators.

Add ascending iterators. An Iterator retains a reference to a Treap and
returns successive values. It functions identically to VisitItemsAscend,
save that it retains its iteration state and can be invoked iteratively.

[dnj, 2016-12-27 23:30:47]

Description was changed from

==========
Add treap ascending Iterators.

Add ascending iterators. An Iterator retains a reference to a Treap and
returns successive values. It functions identially to VisitItemsAscend,
save that it retains its iteration state and can be invoked iteratively.

BUG=
==========

to

==========
Add treap ascending Iterators.

Add ascending iterators. An Iterator retains a reference to a Treap and
returns successive values. It functions identically to VisitItemsAscend,
save that it retains its iteration state and can be invoked iteratively.
==========

[dnj, 2016-12-27 23:50:34]

dnj@chromium.org changed reviewers:
+ hinoka@chromium.org, iannucci@chromium.org, vadimsh@chromium.org

[dnj, 2016-12-27 23:50:35]

PTAL.

This is part of a series of patches that I created today. For context and
motivation, see https://codereview.chromium.org/2601513007

Basically, there is no good way in "gkvlite" to not lose memory for the lifetime
of the impl/memory store when taking snapshots, making it defective by design
for our purposes. I'm proposing replacing it with a lightweight in-memory
"treapstore".

https://codereview.chromium.org/2604933002 (treap iterator)
https://codereview.chromium.org/2607663002 (treapstore)
https://codereview.chromium.org/2604943002 (replace gkvlite with treapstore)

[Vadim Sh., 2016-12-28 01:44:14]

lgtm with optional suggestion

https://codereview.chromium.org/2604933002/diff/1/treap.go
File treap.go (right):

https://codereview.chromium.org/2604933002/diff/1/treap.go#newcode221
treap.go:221: func (it *Iterator) Next() (Item, bool) {
this can totally be implemented as a goroutine and a (unbuffered) channel,
effectively offloading stack management to the golang runtime. It can probably
reuse VisitAscend method too. I wonder what would be the performance difference
when benchmarking (what's worse: manual stack management when using C-style
approach vs unnecessary channel synchronization overhead when using goroutine).

[dnj, 2016-12-28 02:40:03]

https://codereview.chromium.org/2604933002/diff/1/treap.go
File treap.go (right):

https://codereview.chromium.org/2604933002/diff/1/treap.go#newcode221
treap.go:221: func (it *Iterator) Next() (Item, bool) {
On 2016/12/28 01:44:14, Vadim Sh. wrote:
> this can totally be implemented as a goroutine and a (unbuffered) channel,
> effectively offloading stack management to the golang runtime. It can probably
> reuse VisitAscend method too. I wonder what would be the performance
difference
> when benchmarking (what's worse: manual stack management when using C-style
> approach vs unnecessary channel synchronization overhead when using
goroutine).

The thing that really turned me off from that is that the current implementation
has no dangling resources when the iterator is discarded, alleviating the need
to close things. The goroutine/channel implementation could potentially linger
indefinitely in that situation.

The Go runtime could be smart enough to note that nothing will ever read from
the channel and shut down the goroutine and channel. Do you know if it is?

[dnj, 2016-12-28 02:46:36]

> The thing that really turned me off from that is that the current
implementation
> has no dangling resources when the iterator is discarded, alleviating the need
> to close things. The goroutine/channel implementation could potentially linger
> indefinitely in that situation.
> 
> The Go runtime could be smart enough to note that nothing will ever read from
> the channel and shut down the goroutine and channel. Do you know if it is?

A few things that I'm reading suggest that it isn't, and that the goroutines and
channels will accumulate :( Please show me that I'm wrong here.

[Vadim Sh., 2016-12-28 09:00:30]

On 2016/12/28 02:46:36, dnj wrote:
> > The thing that really turned me off from that is that the current
> implementation
> > has no dangling resources when the iterator is discarded, alleviating the
need
> > to close things. The goroutine/channel implementation could potentially
linger
> > indefinitely in that situation.
> > 
> > The Go runtime could be smart enough to note that nothing will ever read
from
> > the channel and shut down the goroutine and channel. Do you know if it is?
> 
> A few things that I'm reading suggest that it isn't, and that the goroutines
and
> channels will accumulate :( Please show me that I'm wrong here.

Yeah, you are right. I think the goroutine would need to be stopped before GC
can collect the channel. Fine then.

[dnj, 2016-12-28 16:03:13]

On 2016/12/28 09:00:30, Vadim Sh. wrote:
> On 2016/12/28 02:46:36, dnj wrote:
> > > The thing that really turned me off from that is that the current
> > implementation
> > > has no dangling resources when the iterator is discarded, alleviating the
> need
> > > to close things. The goroutine/channel implementation could potentially
> linger
> > > indefinitely in that situation.
> > > 
> > > The Go runtime could be smart enough to note that nothing will ever read
> from
> > > the channel and shut down the goroutine and channel. Do you know if it is?
> > 
> > A few things that I'm reading suggest that it isn't, and that the goroutines
> and
> > channels will accumulate :( Please show me that I'm wrong here.
> 
> Yeah, you are right. I think the goroutine would need to be stopped before GC
> can collect the channel. Fine then.

Yeah :( My take on it is that the "stack" array is basically mirroring the Go
stack in the recursive version. It is probably a lot leaner, actually, since it
doesn't have to store as many variables per frame, but the expansion rate should
be the same.

Goroutine stacks are probably better at growing without reallocating, but the
number of frames and reuse properties are about the same.

[dnj, 2016-12-28 16:33:32]

Committed manually:
https://github.com/luci/gtreap/commit/35df89791e8f5560a1fa0c0e8b58709beda51722