Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Object-based API #44

Closed
mourner opened this issue Jun 29, 2016 · 6 comments

Comments

@mourner
Copy link
Owner

commented Jun 29, 2016

I'm considering a breaking API change that will make RBush more performant, but also more verbose, by replacing internal representation of bounding boxes from a 4-length array to a 4-property object. V8 handles object literals faster, and this also allows simplifying some internal logic. API-wise, this would look like this:

// before
tree.insert([20, 40, 30, 50]);
tree.search([5, 6, 10, 12]);

// after
tree.insert({minX: 20, minY; 40, maxX: 30, maxY: 50});
tree.search({minX: 5, minY: 6, maxX: 10, maxY: 12});

You would still be able to configure a custom format for inserted items, but would have to change search to use object literals for bbox instead of arrays in any case.

The tree node JSON format would also change:

// before
{
  children: [...],
  height: 1,
  bbox: [0, 0, 20, 20],
  leaf: true
}

// after
{
  children: [...],
  height: 1,
  minX: 0,
  minY: 0,
  maxX: 20,
  maxY: 20,
  leaf: true
}

This is implemented in memory-perf branch that I'm increasingly using in my new algorithmic experiments. The benchmark results (in Node 6.2.2) are as follows:

# master, items: 1000000, nodeSize: 16
insert one by one: 4969.933ms
1000 searches 10%: 2534.136ms
1000 searches 1%: 472.504ms
1000 searches 0.01%: 61.429ms
remove 1000 one by one: 26.362ms
bulk-insert 1M more: 1506.807ms
1000 searches 1%: 839.277ms
1000 searches 0.01%: 107.652ms

# memory-perf, items: 1000000, nodeSize: 16
insert one by one: 3523.986ms
1000 searches 10%: 2202.467ms
1000 searches 1%: 345.745ms
1000 searches 0.01%: 31.921ms
remove 1000 one by one: 30.391ms
bulk-insert 1M more: 1226.326ms
1000 searches 1%: 610.299ms
1000 searches 0.01%: 71.066ms

@twpayne @tschaub @mbloch @oscarlorentzon @vkurchatkin @bhousel — does this sound acceptable? I would bump the major version for this of course.

@mourner mourner added the enhancement label Jun 29, 2016

@mourner mourner self-assigned this Jun 29, 2016

@IvanSanchez

This comment has been minimized.

Copy link
Contributor

commented Jun 29, 2016

@mourner I've tried to run the perf tests on FFX 46 (using the memory-perf branch @760a69b), but got the following error:

@mourner I've run the perf tests on FFX 46 and node v4.4.3 (using the memory-perf branch @782f05c), and the results are encouraging as well:

                            FFX 46     FFX 46      Node4.4.3  Node4.4.3
                            master   memory-perf     master  memory-perf

insert one by one:        3433.73ms   2072.36ms      3792ms     2989ms
1000 searches 10%:        5803.59ms   3028.95ms      1842ms     1537ms
1000 searches 1%:          616.49ms    437.36ms       365ms      271ms
1000 searches 0.01%:        57.58ms     31.21ms        41ms       26ms
remove 1000 one by one:     17.26ms     13.81ms        15ms       13ms
bulk-insert 1M more:      1042.14ms     432.7ms      1264ms      962ms
1000 searches 1%:         1166.48ms    820.88ms       627ms      474ms
1000 searches 0.01%:        94.59ms     58.78ms        70ms       49ms

@mourner mourner referenced this issue Jun 29, 2016

Merged

Object-based API with performance improvements #45

4 of 5 tasks complete

@mourner mourner added the in progress label Jun 29, 2016

@mourner

This comment has been minimized.

Copy link
Owner Author

commented Jun 29, 2016

The latest commit in #45 should make insertion 10% faster on top of this. So looks like the change is definitely worth breaking the API.

@bhousel

This comment has been minimized.

Copy link

commented Jun 29, 2016

That sounds great! nice find..

@vkurchatkin

This comment has been minimized.

Copy link

commented Jun 29, 2016

Amazing results! API change looks good to me

@oscarlorentzon

This comment has been minimized.

Copy link

commented Jun 29, 2016

Great! API change is fine.

@bryevdv

This comment has been minimized.

Copy link

commented Jun 29, 2016

+1 I would update the version Bokeh uses for sure.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
6 participants
You can’t perform that action at this time.