search

Level / memdown

In-memory abstract-leveldown store for Node.js and browsers.
MIT License
287 stars 37 forks source link

Use a binary search to determine insert/delete position for _keys #7

Closed mhart closed 10 years ago

mhart commented 10 years ago

This results in a ~60x speed increase when dealing with thousands of items.

(it was taking 120s to insert only 10,000 items!)

Things still start to slow down a fair bit when dealing with >100k items, but you'd need to move to another data structure to support this I suspect (lsm-tree perhaps?)

I was considering making this a "private" function on the MemDOWN prototype, but wasn't sure that it really fit in with the other DB-related functions.

Also - the tests are failing - but they're the exact same ones that are failing on current master anyway...

juliangruber commented 10 years ago

lgtm, also if you already have a benchmark script and could at it, that would be killer!

rvagg commented 10 years ago

tests are probably failing because I've neglected to merge and release this https://github.com/rvagg/abstract-leveldown/pull/21

mhart commented 10 years ago

Unfortunately no direct benchmark I'm afraid - I was using this: https://github.com/mhart/dynalite/blob/master/test/bench.js - which writes to levelup behind the scenes (1m items - that still doesn't return in a reasonable time on memdown, but even 10k was struggling whereas now it's fine)

rvagg commented 10 years ago

added @mhart as collaborator, will get the tests running then publish

mhart commented 10 years ago

Added some vague benchmarks comparing the old and new strategies here: https://github.com/rvagg/memdown/pull/8

Doesn't directly measure _put and _delete as I wasn't really sure how you'd prefer to benchmark the old lib vs the new one.