A NodeManager implementation with encoding/decoding keys/values into pages.

A NodeManager implementation with encoding/decoding keys/values into pages.

R=brianwilkerson@google.com, paulberry@google.com
BUG=

Committed: https://code.google.com/p/dart/source/detail?r=37136

[Brian Wilkerson, 2014-06-09 21:08:31]

LGTM

[scheglov, 2014-06-09 21:13:12]

Committed patchset #2 manually as r37136 (presubmit successful).

[Paul Berry, 2014-06-10 18:39:09]

lgtm

https://codereview.chromium.org/324743003/diff/20001/pkg/analysis_server/lib/...
File pkg/analysis_server/lib/src/index/page_node_manager.dart (right):

https://codereview.chromium.org/324743003/diff/20001/pkg/analysis_server/lib/...
pkg/analysis_server/lib/src/index/page_node_manager.dart:84: final Map<int,
Uint8List> _pages = new HashMap<int, Uint8List>();
Kind of surprised that you're using a Map here, since pages are allocated in
order starting from page zero.  Wouldn't a List<Uint8List> have better
performance?

https://codereview.chromium.org/324743003/diff/20001/pkg/analysis_server/lib/...
pkg/analysis_server/lib/src/index/page_node_manager.dart:115: if
(!_pages.containsKey(id)) {
Might want to add a check here to verify that page.length == pageSizeInBytes.

https://codereview.chromium.org/324743003/diff/20001/pkg/analysis_server/lib/...
pkg/analysis_server/lib/src/index/page_node_manager.dart:143: * Reads the page
with the given identifier and returns its content.
Is the caller allowed to modify the contents of the returned object?  The usual
semantics for a "read" operation would say yes, but based on the implementation
in MemoryPageManager, it looks like the answer is no.  Can you add a comment to
clarify this?  (Or, alternatively, change MemoryPageManager.read() to return a
copy?)

https://codereview.chromium.org/324743003/diff/20001/pkg/analysis_server/lib/...
pkg/analysis_server/lib/src/index/page_node_manager.dart:157: class
PageNodeManager<K, V> implements NodeManager<K, V, int> {
To make it easier to understand (and use) this class, it would be nice to have
"maxIndexKeys" and "maxLeafKeys" getters, which compute their results based on
pageManager.pageSizeInBytes, keyCodec.sizeInBytes, and valueCodec.sizeInBytes. 
That way users of PageNodeManager (e.g. _treeWithPageNodeManager()) won't have
to rely on private implementation details of PageNodeManager when deciding how
big to make the nodes.

https://codereview.chromium.org/324743003/diff/20001/pkg/analysis_server/lib/...
pkg/analysis_server/lib/src/index/page_node_manager.dart:214: ByteData byteData
= new ByteData.view(page.buffer, offset);
I'm a little worried that creating all of these views deep inside an inner loop
is going to lead to inefficiency, but I don't really have a good alternative to
suggest.

https://codereview.chromium.org/324743003/diff/20001/pkg/analysis_server/test...
File pkg/analysis_server/test/index/page_node_manager_test.dart (right):

https://codereview.chromium.org/324743003/diff/20001/pkg/analysis_server/test...
pkg/analysis_server/test/index/page_node_manager_test.dart:47: int maxIndexKeys
= (pageSize - 64) ~/ (4 + 4);
What's the source of the "- 64"?

https://codereview.chromium.org/324743003/diff/20001/pkg/analysis_server/test...
pkg/analysis_server/test/index/page_node_manager_test.dart:56: Random random =
new Random();
Using Random() makes the unit test nondeterministic, which makes it difficult to
debug.  I'd recommend seeding the random number generator with a constant, so
that if a test failure occurs, it will be reproducible.

https://codereview.chromium.org/324743003/diff/20001/pkg/analysis_server/test...
pkg/analysis_server/test/index/page_node_manager_test.dart:81: }
Should we also verify that all the removed keys are gone?

https://codereview.chromium.org/324743003/diff/20001/pkg/analysis_server/test...
pkg/analysis_server/test/index/page_node_manager_test.dart:123: }
We should also test:
- Non-ASCII characters
- Unicode code points beyond UTF-16

[scheglov, 2014-06-10 20:12:13]

Paul,

This CL https://codereview.chromium.org/327003004 addresses some of your
comments.

https://codereview.chromium.org/324743003/diff/20001/pkg/analysis_server/lib/...
File pkg/analysis_server/lib/src/index/page_node_manager.dart (right):

https://codereview.chromium.org/324743003/diff/20001/pkg/analysis_server/lib/...
pkg/analysis_server/lib/src/index/page_node_manager.dart:84: final Map<int,
Uint8List> _pages = new HashMap<int, Uint8List>();
On 2014/06/10 18:39:08, Paul Berry wrote:
> Kind of surprised that you're using a Map here, since pages are allocated in
> order starting from page zero.  Wouldn't a List<Uint8List> have better
> performance?

I don't observe any performance difference with one and the other
implementations.

https://codereview.chromium.org/324743003/diff/20001/pkg/analysis_server/lib/...
pkg/analysis_server/lib/src/index/page_node_manager.dart:115: if
(!_pages.containsKey(id)) {
On 2014/06/10 18:39:08, Paul Berry wrote:
> Might want to add a check here to verify that page.length == pageSizeInBytes.

Done.

https://codereview.chromium.org/324743003/diff/20001/pkg/analysis_server/lib/...
pkg/analysis_server/lib/src/index/page_node_manager.dart:143: * Reads the page
with the given identifier and returns its content.
On 2014/06/10 18:39:08, Paul Berry wrote:
> Is the caller allowed to modify the contents of the returned object?  The
usual
> semantics for a "read" operation would say yes, but based on the
implementation
> in MemoryPageManager, it looks like the answer is no.  Can you add a comment
to
> clarify this?  (Or, alternatively, change MemoryPageManager.read() to return a
> copy?)

Done.

https://codereview.chromium.org/324743003/diff/20001/pkg/analysis_server/lib/...
pkg/analysis_server/lib/src/index/page_node_manager.dart:157: class
PageNodeManager<K, V> implements NodeManager<K, V, int> {
On 2014/06/10 18:39:08, Paul Berry wrote:
> To make it easier to understand (and use) this class, it would be nice to have
> "maxIndexKeys" and "maxLeafKeys" getters, which compute their results based on
> pageManager.pageSizeInBytes, keyCodec.sizeInBytes, and valueCodec.sizeInBytes.

> That way users of PageNodeManager (e.g. _treeWithPageNodeManager()) won't have
> to rely on private implementation details of PageNodeManager when deciding how
> big to make the nodes.

Yes, already done in one of the subsequent CLs.
I've made these constants private now.

https://codereview.chromium.org/324743003/diff/20001/pkg/analysis_server/test...
File pkg/analysis_server/test/index/page_node_manager_test.dart (right):

https://codereview.chromium.org/324743003/diff/20001/pkg/analysis_server/test...
pkg/analysis_server/test/index/page_node_manager_test.dart:47: int maxIndexKeys
= (pageSize - 64) ~/ (4 + 4);
On 2014/06/10 18:39:09, Paul Berry wrote:
> What's the source of the "- 64"?

Already cleaned up.

https://codereview.chromium.org/324743003/diff/20001/pkg/analysis_server/test...
pkg/analysis_server/test/index/page_node_manager_test.dart:56: Random random =
new Random();
On 2014/06/10 18:39:08, Paul Berry wrote:
> Using Random() makes the unit test nondeterministic, which makes it difficult
to
> debug.  I'd recommend seeding the random number generator with a constant, so
> that if a test failure occurs, it will be reproducible.

Done.

https://codereview.chromium.org/324743003/diff/20001/pkg/analysis_server/test...
pkg/analysis_server/test/index/page_node_manager_test.dart:81: }
On 2014/06/10 18:39:08, Paul Berry wrote:
> Should we also verify that all the removed keys are gone?

Done.

https://codereview.chromium.org/324743003/diff/20001/pkg/analysis_server/test...
pkg/analysis_server/test/index/page_node_manager_test.dart:123: }
On 2014/06/10 18:39:09, Paul Berry wrote:
> We should also test:
> - Non-ASCII characters
> - Unicode code points beyond UTF-16

IIRC Dart sources are UTF-8 encoded.
I've added some Russian string.