Chromium Code Reviews
|
|
Chromium Code Reviews
Issue
1564913004:
Initial flat buffers implementation. (Closed)
|
Created:
4 years, 11 months ago by scheglov Modified:
4 years, 11 months ago Reviewers:
Paul Berry CC:
reviews_dartlang.org Base URL:
git@github.com:dart-lang/sdk.git@master Target Ref:
refs/heads/master Visibility:
Public. |
DescriptionInitial flat buffers implementation.
It supports tables and lists.
Virtual tables are not shared yet.
Construction is done forward.
R=paulberry@google.com
BUG=
Committed: https://github.com/dart-lang/sdk/commit/5d7e5cc4bdf27b429747d1821717aa97ab4af5e4
Patch Set 1 #
Total comments: 17
Patch Set 2 : Rewrite using backward construction approach. #
Total comments: 7
Patch Set 3 : Fixes for review comments. #
Total comments: 2
Messages
Total messages: 9 (1 generated)
I'm concerned about the decision to write the output in forward order rather than reverse order. Writing the output in reverse order gives two big advantages: (1) it allows object pointers to use unsigned offsets, which complies with the flatbuffer spec, so we can use existing flatbuffer tools to validate our code and our data. (2) it ensures that when the data is *read*, memory is being accessed in the forward direction, which is more cache efficient since CPU caches are optimized for sequential forward memory access. https://codereview.chromium.org/1564913004/diff/1/pkg/analyzer/lib/src/summar... File pkg/analyzer/lib/src/summary/flat_buffers.dart (right): https://codereview.chromium.org/1564913004/diff/1/pkg/analyzer/lib/src/summar... pkg/analyzer/lib/src/summary/flat_buffers.dart:15: ByteBuffer byteBuffer = new Int8List.fromList(byteList).buffer; It seems unfortunate that this constructor always makes a copy of byteList. In practice we'll always be creating a BufferPointer from a buffer we've read from a file (in which case it will already be a Uint8List*), so no copy should be necessary. (*Note: this fact is, sadly, not documented in the SDK) https://codereview.chromium.org/1564913004/diff/1/pkg/analyzer/lib/src/summar... pkg/analyzer/lib/src/summary/flat_buffers.dart:22: BufferPointer derefObject() => _derefSOffset(); This is incorrect. Offsets to objects should be unsigned. See http://google.github.io/flatbuffers/md__internals.html, under the heading "Offsets". https://codereview.chromium.org/1564913004/diff/1/pkg/analyzer/lib/src/summar... pkg/analyzer/lib/src/summary/flat_buffers.dart:33: return _advance(sOffset); This should be _advance(-sOffset). Signed offsets are only used for vtables, and in that case the offset is subtracted rather than added (see section "tables" of http://google.github.io/flatbuffers/md__internals.html). https://codereview.chromium.org/1564913004/diff/1/pkg/analyzer/lib/src/summar... pkg/analyzer/lib/src/summary/flat_buffers.dart:112: _buf.setInt32( This isn't right. Offsets are unsigned and always positive; with your implementation they will be signed and always negative (because you output the buffer in forward order and the thing being pointed to is always written before the pointer). Would you mind adding a TODO comment to remind us to come back and fix this? https://codereview.chromium.org/1564913004/diff/1/pkg/analyzer/lib/src/summar... pkg/analyzer/lib/src/summary/flat_buffers.dart:127: // Prepare for writing the VTable. Add a TODO comment to note that we shouldn't output the vtable if it's the same as a vtable we've output previously. https://codereview.chromium.org/1564913004/diff/1/pkg/analyzer/lib/src/summar... pkg/analyzer/lib/src/summary/flat_buffers.dart:135: _buf.setInt32(_currentTableOffset, vTableOffset - _currentTableOffset, This should be _currentTableOffset - vTableOffset. See section "Tables" of http://google.github.io/flatbuffers/md__internals.html, which says "This offset is substracted (not added) from the object start to arrive at the vtable start." https://codereview.chromium.org/1564913004/diff/1/pkg/analyzer/lib/src/summar... pkg/analyzer/lib/src/summary/flat_buffers.dart:144: * root object offset, and usually references directly of indirectly every s/of/or/ https://codereview.chromium.org/1564913004/diff/1/pkg/analyzer/lib/src/summar... pkg/analyzer/lib/src/summary/flat_buffers.dart:162: _buf.setUint32(_offset, -1, Endianness.LITTLE_ENDIAN); It seems weird to pass a literal -1 to setUint32, since it is guaranteed to underflow. This is just a placeholder value anyhow--how about just writing 0? https://codereview.chromium.org/1564913004/diff/1/pkg/analyzer/lib/src/summar... pkg/analyzer/lib/src/summary/flat_buffers.dart:177: _buf.setUint32(_offset, -1, Endianness.LITTLE_ENDIAN); Similar comment here. https://codereview.chromium.org/1564913004/diff/1/pkg/analyzer/lib/src/summar... pkg/analyzer/lib/src/summary/flat_buffers.dart:195: _buf.setInt32(_offset, value._offset - _offset, Endianness.LITTLE_ENDIAN); As with line 112 this disagrees with the flatbuffer spec. Offsets should be unsigned and always positive. https://codereview.chromium.org/1564913004/diff/1/pkg/analyzer/lib/src/summar... pkg/analyzer/lib/src/summary/flat_buffers.dart:217: for (int b in bytes) { In practice UTF8.encode() will always return a Uint8List (sadly, this isn't documented either), so we ought to be able to do a much more efficient copy than this.
PTAL https://codereview.chromium.org/1564913004/diff/1/pkg/analyzer/lib/src/summar... File pkg/analyzer/lib/src/summary/flat_buffers.dart (right): https://codereview.chromium.org/1564913004/diff/1/pkg/analyzer/lib/src/summar... pkg/analyzer/lib/src/summary/flat_buffers.dart:15: ByteBuffer byteBuffer = new Int8List.fromList(byteList).buffer; On 2016/01/07 15:55:03, Paul Berry wrote: > It seems unfortunate that this constructor always makes a copy of byteList. In > practice we'll always be creating a BufferPointer from a buffer we've read from > a file (in which case it will already be a Uint8List*), so no copy should be > necessary. > > (*Note: this fact is, sadly, not documented in the SDK) Done. If Uint8List is given, we create a view on it, without creating a copy. https://codereview.chromium.org/1564913004/diff/1/pkg/analyzer/lib/src/summar... pkg/analyzer/lib/src/summary/flat_buffers.dart:22: BufferPointer derefObject() => _derefSOffset(); On 2016/01/07 15:55:03, Paul Berry wrote: > This is incorrect. Offsets to objects should be unsigned. See > http://google.github.io/flatbuffers/md__internals.html, under the heading > "Offsets". OK, rewritten to use backward building. https://codereview.chromium.org/1564913004/diff/1/pkg/analyzer/lib/src/summar... pkg/analyzer/lib/src/summary/flat_buffers.dart:127: // Prepare for writing the VTable. On 2016/01/07 15:55:03, Paul Berry wrote: > Add a TODO comment to note that we shouldn't output the vtable if it's the same > as a vtable we've output previously. Done. https://codereview.chromium.org/1564913004/diff/1/pkg/analyzer/lib/src/summar... pkg/analyzer/lib/src/summary/flat_buffers.dart:144: * root object offset, and usually references directly of indirectly every On 2016/01/07 15:55:03, Paul Berry wrote: > s/of/or/ Done. https://codereview.chromium.org/1564913004/diff/1/pkg/analyzer/lib/src/summar... pkg/analyzer/lib/src/summary/flat_buffers.dart:217: for (int b in bytes) { On 2016/01/07 15:55:03, Paul Berry wrote: > In practice UTF8.encode() will always return a Uint8List (sadly, this isn't > documented either), so we ought to be able to do a much more efficient copy than > this. I measured times to write using this cycle vs. using _buf.buffer.asUint8List().setAll(offset, bytes) and the cycle is about 10% faster.
Thanks, Konstantin! Lgtm with some minor nits. https://codereview.chromium.org/1564913004/diff/1/pkg/analyzer/lib/src/summar... File pkg/analyzer/lib/src/summary/flat_buffers.dart (right): https://codereview.chromium.org/1564913004/diff/1/pkg/analyzer/lib/src/summar... pkg/analyzer/lib/src/summary/flat_buffers.dart:217: for (int b in bytes) { On 2016/01/07 22:07:40, scheglov wrote: > On 2016/01/07 15:55:03, Paul Berry wrote: > > In practice UTF8.encode() will always return a Uint8List (sadly, this isn't > > documented either), so we ought to be able to do a much more efficient copy > than > > this. > > I measured times to write using this cycle vs. using > _buf.buffer.asUint8List().setAll(offset, bytes) and the cycle is about 10% > faster. Fair enough. Thanks for checking. https://codereview.chromium.org/1564913004/diff/20001/pkg/analyzer/lib/src/su... File pkg/analyzer/lib/src/summary/flat_buffers.dart (right): https://codereview.chromium.org/1564913004/diff/20001/pkg/analyzer/lib/src/su... pkg/analyzer/lib/src/summary/flat_buffers.dart:27: int uOffset = _getInt32(); Should be _getUint32(). https://codereview.chromium.org/1564913004/diff/20001/pkg/analyzer/lib/src/su... pkg/analyzer/lib/src/summary/flat_buffers.dart:69: int _maxAlign; To help future maintainers, let's document what _maxAlign, _tail, and _currentEndTail mean. I think their meaning is as follows (please correct me if I'm wrong): _maxAlign: the maximum alignment that has been seen so far. If _buf has to be reallocated in the future (to insert room at its start for more bytes) the reallocation will need to be a multiple of this many bytes. _tail: the number of bytes that have been written to the buffer so far. The most recently written byte is this many bytes from the end of _buf. _currentTableEndTail: the location of the end of the current table, measured in bytes from the end of _buf, or null if a table is not currently being built. https://codereview.chromium.org/1564913004/diff/20001/pkg/analyzer/lib/src/su... pkg/analyzer/lib/src/summary/flat_buffers.dart:244: newCapacity += (-newCapacity) % _maxAlign; There's a bug here. The important thing is *not* to make sure newCapacity is a multiple of _maxAlign. Instead, we need to make sure deltaCapacity is a multiple of _maxAlign (otherwise we will ruin the alignment of bytes we've already written). If the old capacity was not a multiple of _maxAlign, then there's no guarantee that deltaCapacity will be a multiple of _maxAlign. I think what we want instead is something like this: int desiredNewCapacity = (oldCapacity + bufSize) * 2; int deltaCapacity = desiredNewCapacity - oldCapacity; deltaCapacity += (-deltaCapacity) % _maxAlign; int newCapacity = oldCapacity + deltaCapacity; ByteData newBuf = new ByteData(newCapacity); newBuf.buffer.asUint8List().setAll(...); _buf = newBuf; (My apologies if you inherited this bug from my early prototype implementation). https://codereview.chromium.org/1564913004/diff/20001/pkg/analyzer/test/src/s... File pkg/analyzer/test/src/summary/flat_buffers_test.dart (right): https://codereview.chromium.org/1564913004/diff/20001/pkg/analyzer/test/src/s... pkg/analyzer/test/src/summary/flat_buffers_test.dart:86: // byteList.asMap().forEach((i, v) => print('${1000 + i}: $v')); Looks like this was left in by accident.
https://codereview.chromium.org/1564913004/diff/20001/pkg/analyzer/lib/src/su... File pkg/analyzer/lib/src/summary/flat_buffers.dart (right): https://codereview.chromium.org/1564913004/diff/20001/pkg/analyzer/lib/src/su... pkg/analyzer/lib/src/summary/flat_buffers.dart:27: int uOffset = _getInt32(); On 2016/01/07 22:44:54, Paul Berry wrote: > Should be _getUint32(). Done. https://codereview.chromium.org/1564913004/diff/20001/pkg/analyzer/lib/src/su... pkg/analyzer/lib/src/summary/flat_buffers.dart:69: int _maxAlign; On 2016/01/07 22:44:53, Paul Berry wrote: > To help future maintainers, let's document what _maxAlign, _tail, and > _currentEndTail mean. I think their meaning is as follows (please correct me if > I'm wrong): > > _maxAlign: the maximum alignment that has been seen so far. If _buf has to be > reallocated in the future (to insert room at its start for more bytes) the > reallocation will need to be a multiple of this many bytes. > > _tail: the number of bytes that have been written to the buffer so far. The > most recently written byte is this many bytes from the end of _buf. > > _currentTableEndTail: the location of the end of the current table, measured in > bytes from the end of _buf, or null if a table is not currently being built. Done. https://codereview.chromium.org/1564913004/diff/20001/pkg/analyzer/lib/src/su... pkg/analyzer/lib/src/summary/flat_buffers.dart:244: newCapacity += (-newCapacity) % _maxAlign; On 2016/01/07 22:44:53, Paul Berry wrote: > There's a bug here. The important thing is *not* to make sure newCapacity is a > multiple of _maxAlign. Instead, we need to make sure deltaCapacity is a > multiple of _maxAlign (otherwise we will ruin the alignment of bytes we've > already written). If the old capacity was not a multiple of _maxAlign, then > there's no guarantee that deltaCapacity will be a multiple of _maxAlign. > > I think what we want instead is something like this: > > int desiredNewCapacity = (oldCapacity + bufSize) * 2; > int deltaCapacity = desiredNewCapacity - oldCapacity; > deltaCapacity += (-deltaCapacity) % _maxAlign; > int newCapacity = oldCapacity + deltaCapacity; > ByteData newBuf = new ByteData(newCapacity); > newBuf.buffer.asUint8List().setAll(...); > _buf = newBuf; > > (My apologies if you inherited this bug from my early prototype implementation). Done. Thank you for catching this!
Description was changed from ========== Initial flat buffers implementation. It supports tables and lists. Virtual tables are not shared yet. Construction is done forward. R=paulberry@google.com BUG= ========== to ========== Initial flat buffers implementation. It supports tables and lists. Virtual tables are not shared yet. Construction is done forward. R=paulberry@google.com BUG= Committed: https://github.com/dart-lang/sdk/commit/5d7e5cc4bdf27b429747d1821717aa97ab4af5e4 ==========
Message was sent while issue was closed.
Committed patchset #3 (id:40001) manually as 5d7e5cc4bdf27b429747d1821717aa97ab4af5e4 (presubmit successful).
Message was sent while issue was closed.
https://codereview.chromium.org/1564913004/diff/40001/pkg/analyzer/lib/src/su... File pkg/analyzer/lib/src/summary/flat_buffers.dart (right): https://codereview.chromium.org/1564913004/diff/40001/pkg/analyzer/lib/src/su... pkg/analyzer/lib/src/summary/flat_buffers.dart:173: int alignedTail = _tail + ((-_tail) % _maxAlign); I think this isn't going to do what you want. Consider what happens if _maxAlign is 8 and _tail is 64 on entry to this method. _prepare will change _tail to 68, so _setUint32AtTail will store a value at a tail offset of 68. Then we will compute a value of 72 for alignedTail. As a result, the returned buffer will begin with 4 bytes of padding, followed by the offset to the root object.
Message was sent while issue was closed.
https://codereview.chromium.org/1564913004/diff/40001/pkg/analyzer/lib/src/su... File pkg/analyzer/lib/src/summary/flat_buffers.dart (right): https://codereview.chromium.org/1564913004/diff/40001/pkg/analyzer/lib/src/su... pkg/analyzer/lib/src/summary/flat_buffers.dart:173: int alignedTail = _tail + ((-_tail) % _maxAlign); On 2016/01/07 23:50:28, Paul Berry wrote: > I think this isn't going to do what you want. Consider what happens if > _maxAlign is 8 and _tail is 64 on entry to this method. _prepare will change > _tail to 68, so _setUint32AtTail will store a value at a tail offset of 68. > Then we will compute a value of 72 for alignedTail. As a result, the returned > buffer will begin with 4 bytes of padding, followed by the offset to the root > object. Ah... Right. At the moment we don't cannot write Int64, but yes, I see how it may be a problem. We need to write the root object reference at alignedTail. https://codereview.chromium.org/1571593002/ should fix it. |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
