Chromium Code Reviews
|
|
Chromium Code Reviews
Issue
2637863002:
Fix ReadableStream scalability issue (Closed)
DescriptionFix ReadableStream scalability issue
ReadableStream becomes very slow when 56720 or more chunks are in the
queue. Instead of one InternalPackedArray as the queue, use a
single-linked list of InternalPackedArrays. If adding a chunk would
cause the array at the back to grow to more than 16384 chunks, add a
new node to the list instead.
The new Queue class hasn't had any particular optimisation, but
informal benchmarks show it slightly slower for small queues, faster
for medium-size queues and drastically faster where the old
implementation fell off the performance cliff.
Thanks to Jakob Kummerow for suggesting the cursor mechanism:
https://groups.google.com/d/msg/v8-users/Hj78A4yhQS4/edz6-NsyCAAJ
Alternatives considered:
* Array-backed circular buffer. Rejected because
it would cause additional overhead in the case of a small queue.
* Polymorphically switching between old and new queue representations
at some threshold. Rejected for complexity.
BUG=681493
Review-Url: https://codereview.chromium.org/2637863002
Cr-Commit-Position: refs/heads/master@{#445717}
Committed: https://chromium.googlesource.com/chromium/src/+/9106f36b383c3e366fa8bb9db1c5b9b1c426491a
Patch Set 1 #
Total comments: 2
Patch Set 2 : Use cursor in Queue. Use Queue for [[readRequests]] slot. #
Total comments: 4
Patch Set 3 : Remove unreachable code and use constant #Messages
Total messages: 27 (16 generated)
ricea@chromium.org changed reviewers: + yhirano@chromium.org
+yhirano, could you take a look at this? I want to validate that the approach is okay before I extend it to [[readRequests]] and WritableStream.
looks good. https://codereview.chromium.org/2637863002/diff/1/third_party/WebKit/Source/c... File third_party/WebKit/Source/core/streams/ReadableStream.js (right): https://codereview.chromium.org/2637863002/diff/1/third_party/WebKit/Source/c... third_party/WebKit/Source/core/streams/ReadableStream.js:812: get length() { How about having |empty| predicate?
https://codereview.chromium.org/2637863002/diff/1/third_party/WebKit/Source/c... File third_party/WebKit/Source/core/streams/ReadableStream.js (right): https://codereview.chromium.org/2637863002/diff/1/third_party/WebKit/Source/c... third_party/WebKit/Source/core/streams/ReadableStream.js:812: get length() { On 2017/01/17 08:23:37, yhirano wrote: > How about having |empty| predicate? I am hoping to get feedback from someone more knowledgeable about v8 whether avoiding polymorphism is really necessary. Until then, I want to keep the API as a subset of Array.
Description was changed from ========== Possible fix for ReadableStream scalability issue ReadableStream becomes very slow when 56720 or more chunks are in the queue. Instead of one InternalPackedArray as the queue, use a single-linked list of InternalPackedArrays. If adding a chunk would cause the array at the back to grow to more than 32767 chunks, add a new node to the list instead. For small queues this reduces to a single array with a bit of extra indirection. The implementation avoids polymorphism (ie. using an array directly for small queues) based on the assumptions that it would cause deopt and that deopt would be bad. BUG=681493 ========== to ========== Possible fix for ReadableStream scalability issue ReadableStream becomes very slow when 56720 or more chunks are in the queue. Instead of one InternalPackedArray as the queue, use a single-linked list of InternalPackedArrays. If adding a chunk would cause the array at the back to grow to more than 32767 chunks, add a new node to the list instead. For small queues this reduces to a single array with a bit of extra indirection. The implementation avoids polymorphism (ie. using an array directly for small queues) based on the assumptions that it would cause deopt and that deopt would be bad. Alternatives considered: Array-backed circular buffer. Rejected because it would cause additional overhead in the case of a small queue. BUG=681493 ==========
Description was changed from ========== Possible fix for ReadableStream scalability issue ReadableStream becomes very slow when 56720 or more chunks are in the queue. Instead of one InternalPackedArray as the queue, use a single-linked list of InternalPackedArrays. If adding a chunk would cause the array at the back to grow to more than 32767 chunks, add a new node to the list instead. For small queues this reduces to a single array with a bit of extra indirection. The implementation avoids polymorphism (ie. using an array directly for small queues) based on the assumptions that it would cause deopt and that deopt would be bad. Alternatives considered: Array-backed circular buffer. Rejected because it would cause additional overhead in the case of a small queue. BUG=681493 ========== to ========== Possible fix for ReadableStream scalability issue ReadableStream becomes very slow when 56720 or more chunks are in the queue. Instead of one InternalPackedArray as the queue, use a single-linked list of InternalPackedArrays. If adding a chunk would cause the array at the back to grow to more than 32767 chunks, add a new node to the list instead. For small queues this reduces to a single array with a bit of extra indirection. The implementation avoids polymorphism (ie. using an array directly for small queues) based on the assumptions that it would cause deopt and that deopt would be bad. Alternatives considered: Array-backed circular buffer. Rejected because it would cause additional overhead in the case of a small queue. BUG=681493 ==========
lgtm
Description was changed from ========== Possible fix for ReadableStream scalability issue ReadableStream becomes very slow when 56720 or more chunks are in the queue. Instead of one InternalPackedArray as the queue, use a single-linked list of InternalPackedArrays. If adding a chunk would cause the array at the back to grow to more than 32767 chunks, add a new node to the list instead. For small queues this reduces to a single array with a bit of extra indirection. The implementation avoids polymorphism (ie. using an array directly for small queues) based on the assumptions that it would cause deopt and that deopt would be bad. Alternatives considered: Array-backed circular buffer. Rejected because it would cause additional overhead in the case of a small queue. BUG=681493 ========== to ========== Fix ReadableStream scalability issue ReadableStream becomes very slow when 56720 or more chunks are in the queue. Instead of one InternalPackedArray as the queue, use a single-linked list of InternalPackedArrays. If adding a chunk would cause the array at the back to grow to more than 16384 chunks, add a new node to the list instead. The new Queue class hasn't had any particular optimisation, but informal benchmarks show it slightly slower for small queues, faster for medium-size queues and drastically faster where the old implementation fell off the performance cliff. Alternatives considered: * Array-backed circular buffer. Rejected because it would cause additional overhead in the case of a small queue. * Polymorphically switching between old and new queue representations at some threshold. Rejected for complexity. BUG=681493 ==========
The CQ bit was checked by ricea@chromium.org to run a CQ dry run
Dry run: CQ is trying da patch. Follow status at https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...
Description was changed from ========== Fix ReadableStream scalability issue ReadableStream becomes very slow when 56720 or more chunks are in the queue. Instead of one InternalPackedArray as the queue, use a single-linked list of InternalPackedArrays. If adding a chunk would cause the array at the back to grow to more than 16384 chunks, add a new node to the list instead. The new Queue class hasn't had any particular optimisation, but informal benchmarks show it slightly slower for small queues, faster for medium-size queues and drastically faster where the old implementation fell off the performance cliff. Alternatives considered: * Array-backed circular buffer. Rejected because it would cause additional overhead in the case of a small queue. * Polymorphically switching between old and new queue representations at some threshold. Rejected for complexity. BUG=681493 ========== to ========== Fix ReadableStream scalability issue ReadableStream becomes very slow when 56720 or more chunks are in the queue. Instead of one InternalPackedArray as the queue, use a single-linked list of InternalPackedArrays. If adding a chunk would cause the array at the back to grow to more than 16384 chunks, add a new node to the list instead. The new Queue class hasn't had any particular optimisation, but informal benchmarks show it slightly slower for small queues, faster for medium-size queues and drastically faster where the old implementation fell off the performance cliff. Thanks to Jakob Kummerow for suggesting the cursor mechanism: https://groups.google.com/d/msg/v8-users/Hj78A4yhQS4/edz6-NsyCAAJ Alternatives considered: * Array-backed circular buffer. Rejected because it would cause additional overhead in the case of a small queue. * Polymorphically switching between old and new queue representations at some threshold. Rejected for complexity. BUG=681493 ==========
yhirano: I'm ready to submit. PTAL at PS2.
The CQ bit was unchecked by commit-bot@chromium.org
Dry run: This issue passed the CQ dry run.
On 2017/01/19 12:23:38, Adam Rice wrote: > yhirano: I'm ready to submit. PTAL at PS2. Friendly ping.
Sorry! https://codereview.chromium.org/2637863002/diff/20001/third_party/WebKit/Sour... File third_party/WebKit/Source/core/streams/ReadableStream.js (right): https://codereview.chromium.org/2637863002/diff/20001/third_party/WebKit/Sour... third_party/WebKit/Source/core/streams/ReadableStream.js:814: if (this.back.elements.length === 16384) { [optional] Having a constant might be good given that we are using it in assert comments. https://codereview.chromium.org/2637863002/diff/20001/third_party/WebKit/Sour... third_party/WebKit/Source/core/streams/ReadableStream.js:830: if (this.front.next !== undefined) { this.front.next === undefined && this.front.elements.length === this.cursor means the queue is empty, which must not happen. Maybe assert(this.front.next !== undefined) is enough?
https://codereview.chromium.org/2637863002/diff/20001/third_party/WebKit/Sour... File third_party/WebKit/Source/core/streams/ReadableStream.js (right): https://codereview.chromium.org/2637863002/diff/20001/third_party/WebKit/Sour... third_party/WebKit/Source/core/streams/ReadableStream.js:814: if (this.back.elements.length === 16384) { On 2017/01/24 11:14:13, yhirano wrote: > [optional] Having a constant might be good given that we are using it in assert > comments. I didn't do this because I wasn't sure that v8 would perform constant folding. But that was just a premature optimisation. Done. https://codereview.chromium.org/2637863002/diff/20001/third_party/WebKit/Sour... third_party/WebKit/Source/core/streams/ReadableStream.js:830: if (this.front.next !== undefined) { On 2017/01/24 11:14:13, yhirano wrote: > this.front.next === undefined && this.front.elements.length === this.cursor > means the queue is empty, which must not happen. Maybe assert(this.front.next > !== undefined) is enough? You are right. Done.
The CQ bit was checked by ricea@chromium.org to run a CQ dry run
Dry run: CQ is trying da patch. Follow status at https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...
lgtm
The CQ bit was unchecked by commit-bot@chromium.org
Dry run: Try jobs failed on following builders: cast_shell_linux on master.tryserver.chromium.linux (JOB_FAILED, http://build.chromium.org/p/tryserver.chromium.linux/builders/cast_shell_linu...)
The CQ bit was checked by ricea@chromium.org
CQ is trying da patch. Follow status at https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...
CQ is committing da patch.
Bot data: {"patchset_id": 40001, "attempt_start_ts": 1485266195970930,
"parent_rev": "673842136e3567693a64c20dc6aa7b9530b26abc", "commit_rev":
"9106f36b383c3e366fa8bb9db1c5b9b1c426491a"}
Message was sent while issue was closed.
Description was changed from ========== Fix ReadableStream scalability issue ReadableStream becomes very slow when 56720 or more chunks are in the queue. Instead of one InternalPackedArray as the queue, use a single-linked list of InternalPackedArrays. If adding a chunk would cause the array at the back to grow to more than 16384 chunks, add a new node to the list instead. The new Queue class hasn't had any particular optimisation, but informal benchmarks show it slightly slower for small queues, faster for medium-size queues and drastically faster where the old implementation fell off the performance cliff. Thanks to Jakob Kummerow for suggesting the cursor mechanism: https://groups.google.com/d/msg/v8-users/Hj78A4yhQS4/edz6-NsyCAAJ Alternatives considered: * Array-backed circular buffer. Rejected because it would cause additional overhead in the case of a small queue. * Polymorphically switching between old and new queue representations at some threshold. Rejected for complexity. BUG=681493 ========== to ========== Fix ReadableStream scalability issue ReadableStream becomes very slow when 56720 or more chunks are in the queue. Instead of one InternalPackedArray as the queue, use a single-linked list of InternalPackedArrays. If adding a chunk would cause the array at the back to grow to more than 16384 chunks, add a new node to the list instead. The new Queue class hasn't had any particular optimisation, but informal benchmarks show it slightly slower for small queues, faster for medium-size queues and drastically faster where the old implementation fell off the performance cliff. Thanks to Jakob Kummerow for suggesting the cursor mechanism: https://groups.google.com/d/msg/v8-users/Hj78A4yhQS4/edz6-NsyCAAJ Alternatives considered: * Array-backed circular buffer. Rejected because it would cause additional overhead in the case of a small queue. * Polymorphically switching between old and new queue representations at some threshold. Rejected for complexity. BUG=681493 Review-Url: https://codereview.chromium.org/2637863002 Cr-Commit-Position: refs/heads/master@{#445717} Committed: https://chromium.googlesource.com/chromium/src/+/9106f36b383c3e366fa8bb9db1c5... ==========
Message was sent while issue was closed.
Committed patchset #3 (id:40001) as https://chromium.googlesource.com/chromium/src/+/9106f36b383c3e366fa8bb9db1c5... |
