Red black tree as data structure

[calvinmetcalf]

25

[juliangruber]

lgtm :) would you mind sharing your benchmark results also?

[nolanlawson]

here's what @calvinmetcalf posted in IRC: before and after

those are the pouchdb performance tests; our CONTRIBUTING.md explains what they're doing. looks very good to me though :)

[calvinmetcalf]

• memdown
• redblackdown

the numbers are

memdown:

Testing PouchDB version 3.0.7-prerelease, using adapter: memory

Starting suite: basics

Starting test: basic-inserts with 1 assertions and 1000 iterations... done in 1164ms
Starting test: bulk-inserts with 1 assertions and 100 iterations... done in 6746ms
Starting test: basic-gets with 1 assertions and 10000 iterations... done in 3299ms
Starting test: all-docs-skip-limit with 1 assertions and 50 iterations... done in 34656ms
Starting test: all-docs-startkey-endkey with 1 assertions and 50 iterations... done in 1260ms

Tests Complete!

Starting suite: views

Starting test: temp-views with 1 assertions and 10 iterations... done in 2770ms
Starting test: persisted-views with 1 assertions and 10 iterations... done in 133ms
Starting test: persisted-views-stale-ok with 1 assertions and 10 iterations... done in 110ms

Tests Complete!

redblackdown:

Testing PouchDB version 3.0.7-prerelease, using adapter: redblack

Starting suite: basics

Starting test: basic-inserts with 1 assertions and 1000 iterations... done in 862ms
Starting test: bulk-inserts with 1 assertions and 100 iterations... done in 3427ms
Starting test: basic-gets with 1 assertions and 10000 iterations... done in 2401ms
Starting test: all-docs-skip-limit with 1 assertions and 50 iterations... done in 18437ms
Starting test: all-docs-startkey-endkey with 1 assertions and 50 iterations... done in 766ms

Tests Complete!

Starting suite: views

Starting test: temp-views with 1 assertions and 10 iterations... done in 1861ms
Starting test: persisted-views with 1 assertions and 10 iterations... done in 140ms
Starting test: persisted-views-stale-ok with 1 assertions and 10 iterations... done in 64ms

Tests Complete!

[calvinmetcalf]

The redblack one isn't identical to this pull as it uses https://github.com/calvinmetcalf/immediate instead of the browserify nextTick shim. Will need to perf with this pull specifically On Sep 29, 2014 3:37 PM, "Nolan Lawson" notifications@github.com wrote:

here's what @calvinmetcalf https://github.com/calvinmetcalf posted in IRC: before https://www.irccloud.com/pastebin/p0K03Oob.raw and after https://www.irccloud.com/pastebin/MjBAChe7.raw

those are the pouchdb performance tests; our CONTRIBUTING.md explains what they're doing. looks very good to me though :)

— Reply to this email directly or view it on GitHub https://github.com/rvagg/memdown/pull/26#issuecomment-57216130.

[calvinmetcalf]

How I read this:

inserts get a big speedup because the splices are avoided, iteration gets a speedup due to not having to copy all the keys

[juliangruber]

awesome! great work :)

[calvinmetcalf]

yea gods, a shockily large amount of the speed up is due to subbing in immediate instead of using the browserify version of process.nextTick, like all of it, it's actually marginally slower, so lets not focus on performance improvments as much as snapshots and batches that roll back on error in batch updates

[calvinmetcalf]

see defunctzombie/node-process#21 for improving the browserify next tick shim, also I forgot to mention f2dbb161c6570530c16f179c797a2e3b48c2012b which will only apply the results of a batch operation if there was no error, e.g. atomic batch updates even if it's the last one that has an error.

[nolanlawson]

A test for atomic batch updates in abstract-leveldown would be ace. I am 99% sure that localstorage-down doesn't do that correctly, and yet the tests pass.

[rvagg]

if there's speed to be had then I'm fine with this, please fix up style issues first:

• space after function before the (
• more vertical whitespace in general, after functions, if(){} blocks, etc.
• no braces for near-trivial if and if/else blocks, only braces if either section spills into >1 line
• no semicolons
• no single-line if statements (just add a newline after the if ())

[calvinmetcalf]

ok fixed up the style, there isn't likely to be a speedup with this compared to current code, all the speed gains I got were due to avoiding the browserify nextTick implementation, the gains would be in snapshots and atomic batches.

[nolanlawson]

needs a rebase, but I'm +1 after that and assuming both the pouchdb tests and tests here are green

[calvinmetcalf]

Ok will look into it later in the week On Oct 26, 2014 10:23 AM, "Nolan Lawson" notifications@github.com wrote:

needs a rebase, but I'm +1 after that and assuming both the pouchdb tests and tests here are green

— Reply to this email directly or view it on GitHub https://github.com/rvagg/memdown/pull/26#issuecomment-60518890.

[calvinmetcalf]

@nolanlawson those destroy tests weren't measuring what you thought they where

[nolanlawson]

awesome, +1 if green in pouchdb as well.

[calvinmetcalf]

tested against pouchdb and passes

[nolanlawson]

go for it. 1.0.0?

[calvinmetcalf]

are there going to be issues with the getter and setter ?

On Tue, Oct 28, 2014 at 8:04 AM, Nolan Lawson notifications@github.com wrote:

go for it. 1.0.0?

— Reply to this email directly or view it on GitHub https://github.com/rvagg/memdown/pull/26#issuecomment-60745045.

-Calvin W. Metcalf

[nolanlawson]

Merged and published 1.0.0. Tests passed in npm test and PouchDB, so LGTM.

Semver ahoy!

[juliangruber]

aw yes! great work!