ryszard/goskiplist — pull request #4 by matttproud (2013-02-20 20:25:27+00:00)
Title: Support amortized traversal in forward seeking.

``Iterator`` has been updated to include ``Iterator.Seek``, which
follows the same protocol of ``SkipList.Seek``. This new ``Seek``
call allows users of goskiplist to amortize traversal costs in batched
forward scan operations. If the requested key occurs before the
current seek point's key, ``SkipList`` resumes the search from the head
of the list.

An overview of the performance characteristics are provided:

mtp:skiplist mtp$ go test -test.bench="." ./...
PASS
BenchmarkLookup16	5000000	243 ns/op
BenchmarkLookup256	5000000	556 ns/op
BenchmarkLookup65536	1000000	2239 ns/op
BenchmarkSet16	1000000	5305 ns/op
BenchmarkSet256	1000000	6356 ns/op
BenchmarkSet65536	1000000	5073 ns/op
BenchmarkRandomSeek	1000000	5105 ns/op
BenchmarkForwardSeek	1000000	2975 ns/op
BenchmarkForwardSeekReusedIterator	1000000	1881 ns/op
ok	github.com/ryszard/goskiplist/skiplist	96.178s

Compare ``BenchmarkForwardSeek`` versus
``BenchmarkForwardSeekReusedIterator``.

I have a use case where this type of seeking performance will be
tremendously beneficial in reducing operation latency.