IndexedDB: Replace transaction's AVLTree with std::map

IndexedDB: Replace transaction's AVLTree with std::map

When porting the transaction back-end from Blink we brought
along an AVLTree implementation for the in-memory key/value
store for transactions. Replace this with a std::map since
it provides similar performance guarantees (red-black tree)
and we like to delete code.

TBR=jam@chromium.org
R=alecflett@chromium.org

Committed: https://src.chromium.org/viewvc/chrome?view=rev&revision=223493

[jsbell, 2013-06-19 20:29:34]

This is doing more data copying than before. Get perf numbers, compare, and
optimize before taking this seriously.

[jsbell, 2013-06-19 23:40:48]

Just for kicks, this is what the patch would look like.

Works and everything! However, performance is NOT tested yet, and likely much
worse since there are extra vector->string copies when adding to the tree.

[jsbell, 2013-06-27 18:36:06]

Performance runs on linux show this to be slightly slower across the board (just
a few %). Not as bad as expected, but will need performance work.

[jsbell, 2013-08-13 23:23:32]

Dusted this off. It now stores node by pointer rather than by value to avoid
copies. Will redo the perf tests.

[jsbell, 2013-08-14 00:07:13]

So far as I can tell, the performance difference here is in the noise. But our
tests are very noisy, even running against a user profile on a ramdisk. *sigh*

[jsbell, 2013-09-10 00:20:11]

alecflett@, dgrogan@, ericu@ - any thoughts on whether or not this is worth
pursuing?

[ericu, 2013-09-10 01:00:40]

The code's not all that much smaller [the .cc file, anyway], but it is easier to
read without having to know what the AVLTree implementation is like.  Everybody
knows what an std::map is.  If the speed difference is really in the noise, I'd
go for it.

That's not a full review of this CL, BTW, just a gut feel.

https://codereview.chromium.org/17462005/diff/15001/content/browser/indexed_d...
File content/browser/indexed_db/leveldb/leveldb_transaction.cc (right):

https://codereview.chromium.org/17462005/diff/15001/content/browser/indexed_d...
content/browser/indexed_db/leveldb/leveldb_transaction.cc:149: TreeNode dummy;
How about map::lower_bound or map::equal_range?

https://codereview.chromium.org/17462005/diff/15001/content/browser/indexed_d...
File content/browser/indexed_db/leveldb/leveldb_transaction.h (right):

https://codereview.chromium.org/17462005/diff/15001/content/browser/indexed_d...
content/browser/indexed_db/leveldb/leveldb_transaction.h:47: class
TreeComparator {
How about removing the word "Tree" everywhere?

[alecflett, 2013-09-10 16:46:40]

seems like there are a few new copies going on here, are they avoidable?

https://codereview.chromium.org/17462005/diff/15001/content/browser/indexed_d...
File content/browser/indexed_db/leveldb/leveldb_transaction.cc (right):

https://codereview.chromium.org/17462005/diff/15001/content/browser/indexed_d...
content/browser/indexed_db/leveldb/leveldb_transaction.cc:70: std::string
string_key(key.begin(), key.end() - key.begin());
Not that this is particularly expensive, but can you use StringPiece here?

https://codereview.chromium.org/17462005/diff/15001/content/browser/indexed_d...
content/browser/indexed_db/leveldb/leveldb_transaction.cc:77: *value =
it->second->value;
it's too bad there's no way to swap or something here, as the value is going to
probably be the expensive option. Is it kosher for Get() to "return" a
StringPiece* here?

https://codereview.chromium.org/17462005/diff/15001/content/browser/indexed_d...
content/browser/indexed_db/leveldb/leveldb_transaction.cc:82: bool ok =
db_->Get(key, value, found, &snapshot_);
I guess you'd have to propagate the stringpiece stuff here too then.. hrmm.

https://codereview.chromium.org/17462005/diff/15001/content/browser/indexed_d...
content/browser/indexed_db/leveldb/leveldb_transaction.cc:145: std::string
key(target.begin(), target.end() - target.begin());
copying on a seek seems bad?

[jsbell, 2013-09-10 17:00:06]

https://codereview.chromium.org/17462005/diff/15001/content/browser/indexed_d...
File content/browser/indexed_db/leveldb/leveldb_transaction.cc (right):

https://codereview.chromium.org/17462005/diff/15001/content/browser/indexed_d...
content/browser/indexed_db/leveldb/leveldb_transaction.cc:70: std::string
string_key(key.begin(), key.end() - key.begin());
On 2013/09/10 16:46:40, alecflett wrote:
> Not that this is particularly expensive, but can you use StringPiece here?

StringPiece doesn't own its storage, and map::find() takes const key_type& - it
wasn't apparent to me how to avoid key copies.

A more intrusive change would be change this method to take a const string&,
since that probably exists on the stack already.

https://codereview.chromium.org/17462005/diff/15001/content/browser/indexed_d...
content/browser/indexed_db/leveldb/leveldb_transaction.cc:77: *value =
it->second->value;
On 2013/09/10 16:46:40, alecflett wrote:
> it's too bad there's no way to swap or something here, as the value is going
to
> probably be the expensive option. Is it kosher for Get() to "return" a
> StringPiece* here?

Nope, since the the storage is owned by the tree and could go away at any time.
(Note that there was a copy here in the old code.)

https://codereview.chromium.org/17462005/diff/15001/content/browser/indexed_d...
content/browser/indexed_db/leveldb/leveldb_transaction.cc:82: bool ok =
db_->Get(key, value, found, &snapshot_);
On 2013/09/10 16:46:40, alecflett wrote:
> I guess you'd have to propagate the stringpiece stuff here too then.. hrmm.

... but if key is passed in as a string that's not a problem. I'll play with
that.

https://codereview.chromium.org/17462005/diff/15001/content/browser/indexed_d...
content/browser/indexed_db/leveldb/leveldb_transaction.cc:145: std::string
key(target.begin(), target.end() - target.begin());
On 2013/09/10 16:46:40, alecflett wrote:
> copying on a seek seems bad?

I'll look at changing this API here to take a const string& instead, too.

https://codereview.chromium.org/17462005/diff/15001/content/browser/indexed_d...
content/browser/indexed_db/leveldb/leveldb_transaction.cc:149: TreeNode dummy;
On 2013/09/10 01:00:41, ericu wrote:
> How about map::lower_bound or map::equal_range?

lower_bound should work - it looks like exactly what I needed, and definitely
better than modifying the tree! I must have missed that when reviewing the
std::map interface. (Or I'll rediscover soon why it won't work here, once I page
everything back into my brain.)

https://codereview.chromium.org/17462005/diff/15001/content/browser/indexed_d...
File content/browser/indexed_db/leveldb/leveldb_transaction.h (right):

https://codereview.chromium.org/17462005/diff/15001/content/browser/indexed_d...
content/browser/indexed_db/leveldb/leveldb_transaction.h:47: class
TreeComparator {
On 2013/09/10 01:00:41, ericu wrote:
> How about removing the word "Tree" everywhere?

Yeah, I suppose once the names are changed at all it doesn't help to keep the
old scheme.

[jsbell, 2013-09-10 21:29:36]

https://codereview.chromium.org/17462005/diff/15001/content/browser/indexed_d...
File content/browser/indexed_db/leveldb/leveldb_transaction.cc (right):

https://codereview.chromium.org/17462005/diff/15001/content/browser/indexed_d...
content/browser/indexed_db/leveldb/leveldb_transaction.cc:70: std::string
string_key(key.begin(), key.end() - key.begin());
On 2013/09/10 17:00:06, jsbell wrote:
> On 2013/09/10 16:46:40, alecflett wrote:
> > Not that this is particularly expensive, but can you use StringPiece here?
> 
> StringPiece doesn't own its storage, and map::find() takes const key_type& -
it
> wasn't apparent to me how to avoid key copies.
> 
> A more intrusive change would be change this method to take a const string&,
> since that probably exists on the stack already.

That turned out to be tricky due to upstream callers that only had slices
themselves, so I went a different direction. 

The map record now holds both the key and value as std::strings, and the map
keys are changed to StringPieces. A record's key is always a StringPiece
pointing at the record's own key property.

Pulling at this thread reveals that key_ is held on to by iterators so they can
be reset if the tree changes. But std::map iterators aren't invalidated by tree
changes (except deletes, which aren't used here) so further simplification is
possible.

[jsbell, 2013-09-13 18:08:05]

oops, forgot to say: 

alecflett@, ericu@ - PTAL again?

[alecflett, 2013-09-13 20:22:07]

lgtm

[commit-bot: I haz the power, 2013-09-16 19:18:48]

CQ is trying da patch. Follow status at
https://chromium-status.appspot.com/cq/jsbell@chromium.org/17462005/36009

[commit-bot: I haz the power, 2013-09-16 19:42:04]

Retried try job too often on chromium_presubmit for step(s) presubmit
http://build.chromium.org/p/tryserver.chromium/buildstatus?builder=chromium_p...

[commit-bot: I haz the power, 2013-09-16 20:35:49]

CQ is trying da patch. Follow status at
https://chromium-status.appspot.com/cq/jsbell@chromium.org/17462005/36009

[commit-bot: I haz the power, 2013-09-17 00:50:31]

Change committed as 223493

[hans, 2013-09-24 15:53:01]

On 2013/09/17 00:50:31, I haz the power (commit-bot) wrote:
> Change committed as 223493

w00t!