Growable typed data buffers.

Growable typed data buffers.

Like growable lists, but with typed data.

Added to package:collection_helpers.

R=floitsch@google.com

Committed: https://code.google.com/p/dart/source/detail?r=30396
Reverted: r30412

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

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

[sra1, 2013-10-09 18:49:53]

I have concerns with this library.

1. These classes implement interfaces that in JavaScript have special
properties.
For example, the audio and web_gl APIs take JavaScript Float32Arrays, which
correspond directly to the fixed-length Float32List.
I'm worried that there might be no efficient way to make the browser APIs take
these new classes when compiling to JavaScript.
We need to be careful to avoid encouraging the development of programs on
Dartium that can't be made to run efficiently via dart2js.

Another example is postMessage which can post structures including browser typed
arrays, with semantics for shared structure via shared ArrayBuffers and
neutering of transferables.  We have not fully resolved this issue.  I believe
this CL will make coming to a design that incorporates transferables that works
property in Dartium and JavaScript will be considerably more difficult with the
extra constrains of this library.

Even if we can design something clean for the above cases, we will have to bloat
the browser APIs with code that does conversions from the new classes to ones
the browsers understand.


2. Having multiple classes that implement each of the interfaces, e.g.
Uint8ClampedList, will make it much more difficult for dart2js to generate
efficient code.  There is no way a user can force the compiler (by is-check) to
know only one of the two implementations reaches a piece of code.

3. We have no decent benchmarks for the problem in #2, and even if we did, the
benchmark would not encounter the hazard since it would be not be using new
classes that introduce the hazard.

https://codereview.chromium.org/26695002/diff/1/pkg/collection_helpers/lib/ty...
File pkg/collection_helpers/lib/typed_buffers.dart (right):

https://codereview.chromium.org/26695002/diff/1/pkg/collection_helpers/lib/ty...
pkg/collection_helpers/lib/typed_buffers.dart:36: if (index >= length) throw new
RangeError.range(index, 0, length - 1);
All other calls use length, not length - 1.
If you want to change what we mean by the third argument to RangeError, please
make that a separate CL.

It would be convenient for our many list-like collections indexable on
[0,length) to have

   new RangeError.list(index, list);

https://codereview.chromium.org/26695002/diff/1/pkg/collection_helpers/lib/ty...
pkg/collection_helpers/lib/typed_buffers.dart:88: if (newLength <
INITIAL_LENGTH) newLength = INITIAL_LENGTH;
This growth policy should be in one place (there is an identical *2 and clamping
in _grow)

https://codereview.chromium.org/26695002/diff/1/pkg/collection_helpers/lib/ty...
pkg/collection_helpers/lib/typed_buffers.dart:163: class Uint8ClampedBuffer
extends _IntBuffer implements Uint8ClampedList {
I'm concerned that having two concrete classes that implement Uint8ClampedList,
one that can be indexed in JavaScript and another that requires calling the
indexer defined above, will prevent dart2js from any meaningful optimizations.

[Lasse Reichstein Nielsen, 2013-10-10 05:54:41]

https://codereview.chromium.org/26695002/diff/1/pkg/collection_helpers/lib/ty...
File pkg/collection_helpers/lib/typed_buffers.dart (right):

https://codereview.chromium.org/26695002/diff/1/pkg/collection_helpers/lib/ty...
pkg/collection_helpers/lib/typed_buffers.dart:36: if (index >= length) throw new
RangeError.range(index, 0, length - 1);
The meaning if the third argument to RangeError.range is the last valid index,
it's inclusive. If you see any place where it is used differently, please say
so.

For lookup, the last valid index value is length -1.

For insert, and for ranges in general, we allow referring to the position after
the last element - we are referring to places between/besides elements, not to
elements themselves (good old fence-post problem). 

So, the value is correct.

https://codereview.chromium.org/26695002/diff/1/pkg/collection_helpers/lib/ty...
pkg/collection_helpers/lib/typed_buffers.dart:88: if (newLength <
INITIAL_LENGTH) newLength = INITIAL_LENGTH;
Ack, a generic _newLength would be better.

https://codereview.chromium.org/26695002/diff/1/pkg/collection_helpers/lib/ty...
pkg/collection_helpers/lib/typed_buffers.dart:163: class Uint8ClampedBuffer
extends _IntBuffer implements Uint8ClampedList {
I have no problem removing the "implements" here. It's still a List<int> and a
TypedData, which should be fine.

[sra1, 2013-10-15 02:11:40]

https://chromiumcodereview.appspot.com/26695002/diff/1/pkg/collection_helpers...
File pkg/collection_helpers/lib/typed_buffers.dart (right):

https://chromiumcodereview.appspot.com/26695002/diff/1/pkg/collection_helpers...
pkg/collection_helpers/lib/typed_buffers.dart:36: if (index >= length) throw new
RangeError.range(index, 0, length - 1);
On 2013/10/10 05:54:41, Lasse Reichstein Nielsen wrote:
> The meaning if the third argument to RangeError.range is the last valid index,
> it's inclusive. If you see any place where it is used differently, please say
> so.

There are dozens of places in the dart2js versions of libraries and in the
Dartium DOM libraries.

A problem here is that the documentation for RangeError.range is underspecified.
 It is not clear that [end] is inclusive:

  /** Create a new [RangeError] with a message for a value and a range. */
  RangeError.range(num value, num start, num end)

The DOM has 50 kinds of list. I would like to avoid repeated 'length - 1'
expressions since that will contribute to code size of likely dead code.

> 
> For lookup, the last valid index value is length -1.
> 
> For insert, and for ranges in general, we allow referring to the position
after
> the last element - we are referring to places between/besides elements, not to
> elements themselves (good old fence-post problem). 
> 
> So, the value is correct.

https://chromiumcodereview.appspot.com/26695002/diff/1/pkg/collection_helpers...
pkg/collection_helpers/lib/typed_buffers.dart:163: class Uint8ClampedBuffer
extends _IntBuffer implements Uint8ClampedList {
On 2013/10/10 05:54:41, Lasse Reichstein Nielsen wrote:
> I have no problem removing the "implements" here. It's still a List<int> and a
> TypedData, which should be fine.

TypedData corresponds to ArrayBufferView.
http://www.khronos.org/registry/typedarray/specs/latest/#6
http://www.khronos.org/registry/typedarray/specs/latest/#9.3

Not that the spec says so, but since ArrayBufferView is de facto abstract, it
should be OK.

[floitsch, 2013-10-15 15:28:05]

LGTM once Stephen's concerns are addressed.
You will probably have to update the status file since typed_data doesn't work
on all platforms.

https://codereview.chromium.org/26695002/diff/1/pkg/collection_helpers/lib/ty...
File pkg/collection_helpers/lib/typed_buffers.dart (right):

https://codereview.chromium.org/26695002/diff/1/pkg/collection_helpers/lib/ty...
pkg/collection_helpers/lib/typed_buffers.dart:36: if (index >= length) throw new
RangeError.range(index, 0, length - 1);
On 2013/10/15 02:11:41, sra1 wrote:
> On 2013/10/10 05:54:41, Lasse Reichstein Nielsen wrote:
> > The meaning if the third argument to RangeError.range is the last valid
index,
> > it's inclusive. If you see any place where it is used differently, please
say
> > so.
> 
> There are dozens of places in the dart2js versions of libraries and in the
> Dartium DOM libraries.
> 
> A problem here is that the documentation for RangeError.range is
underspecified.
>  It is not clear that [end] is inclusive:
> 
>   /** Create a new [RangeError] with a message for a value and a range. */
>   RangeError.range(num value, num start, num end)
> 
> The DOM has 50 kinds of list. I would like to avoid repeated 'length - 1'
> expressions since that will contribute to code size of likely dead code.
> 
> > 
> > For lookup, the last valid index value is length -1.
> > 
> > For insert, and for ranges in general, we allow referring to the position
> after
> > the last element - we are referring to places between/besides elements, not
to
> > elements themselves (good old fence-post problem). 
> > 
> > So, the value is correct.
> 
I agree with Stephen. I definitely didn't see it as "end is valid".

https://codereview.chromium.org/26695002/diff/1/pkg/collection_helpers/lib/ty...
pkg/collection_helpers/lib/typed_buffers.dart:58: _buffer[i] = defaultValue;
shouldn't these already be set to the default value?

https://codereview.chromium.org/26695002/diff/1/pkg/collection_helpers/lib/ty...
pkg/collection_helpers/lib/typed_buffers.dart:69: // Override default
implementation of add to not grow by one element at
We override the default ...

Otherwise it sounds like a suggestion: "if you don't want to grow by one
element, override...".

https://codereview.chromium.org/26695002/diff/1/pkg/collection_helpers/test/t...
File pkg/collection_helpers/test/typed_buffers_test.dart (right):

https://codereview.chromium.org/26695002/diff/1/pkg/collection_helpers/test/t...
pkg/collection_helpers/test/typed_buffers_test.dart:114:
expect(td.elementSizeInBytes, equals(bits >> 3));
~/ 8

create a "var bytes = bits ~/ 8" and use that instead of shifting in 3 places.

https://codereview.chromium.org/26695002/diff/1/sdk/lib/collection/list.dart
File sdk/lib/collection/list.dart (right):

https://codereview.chromium.org/26695002/diff/1/sdk/lib/collection/list.dart#...
sdk/lib/collection/list.dart:465: // TODO(lrn): How about having a marker
interface that promises that length
That should be done now.

[Lasse Reichstein Nielsen, 2013-11-18 14:32:51]

Addressed comments, added Int32x4Buffer. PTAL.

https://codereview.chromium.org/26695002/diff/1/pkg/collection_helpers/lib/ty...
File pkg/collection_helpers/lib/typed_buffers.dart (right):

https://codereview.chromium.org/26695002/diff/1/pkg/collection_helpers/lib/ty...
pkg/collection_helpers/lib/typed_buffers.dart:58: _buffer[i] = defaultValue;
Yes, they should, because we set the above.
Removing.

https://codereview.chromium.org/26695002/diff/1/pkg/collection_helpers/lib/ty...
pkg/collection_helpers/lib/typed_buffers.dart:69: // Override default
implementation of add to not grow by one element at
On 2013/10/15 15:28:05, floitsch wrote:
> We override the default ...
> 
> Otherwise it sounds like a suggestion: "if you don't want to grow by one
> element, override...".

Done.

https://codereview.chromium.org/26695002/diff/1/pkg/collection_helpers/lib/ty...
pkg/collection_helpers/lib/typed_buffers.dart:88: if (newLength <
INITIAL_LENGTH) newLength = INITIAL_LENGTH;
On 2013/10/10 05:54:41, Lasse Reichstein Nielsen wrote:
> Ack, a generic _newLength would be better.

Done.

https://codereview.chromium.org/26695002/diff/1/pkg/collection_helpers/test/t...
File pkg/collection_helpers/test/typed_buffers_test.dart (right):

https://codereview.chromium.org/26695002/diff/1/pkg/collection_helpers/test/t...
pkg/collection_helpers/test/typed_buffers_test.dart:114:
expect(td.elementSizeInBytes, equals(bits >> 3));
On 2013/10/15 15:28:05, floitsch wrote:
> ~/ 8
> 
> create a "var bytes = bits ~/ 8" and use that instead of shifting in 3 places.

Done.

[floitsch, 2013-11-18 18:03:40]

LGTM.
Please wait for Stephen.

https://codereview.chromium.org/26695002/diff/31001/pkg/collection_helpers/li...
File pkg/collection_helpers/lib/all.dart (right):

https://codereview.chromium.org/26695002/diff/31001/pkg/collection_helpers/li...
pkg/collection_helpers/lib/all.dart:14: * - `typed_bufers.dart`: Growable typed
data lists.
typed_buffers.dart

https://codereview.chromium.org/26695002/diff/31001/pkg/collection_helpers/li...
File pkg/collection_helpers/lib/typed_buffers.dart (right):

https://codereview.chromium.org/26695002/diff/31001/pkg/collection_helpers/li...
pkg/collection_helpers/lib/typed_buffers.dart:25: /// This is an Uint8List for
Uint8Buffer. It's both a List<E> and a TypedData,
a Uint8List

https://codereview.chromium.org/26695002/diff/31001/pkg/collection_helpers/li...
pkg/collection_helpers/lib/typed_buffers.dart:115: _buffer =
_createBiggerBuffer(null)..setRange(0, _length, _buffer);
Please split.

https://codereview.chromium.org/26695002/diff/31001/pkg/collection_helpers/li...
pkg/collection_helpers/lib/typed_buffers.dart:120: if (!identical(source, this))
{
You could also use an is-check against _TypedDataBuffer.

https://codereview.chromium.org/26695002/diff/31001/pkg/collection_helpers/te...
File pkg/collection_helpers/test/typed_buffers_test.dart (right):

https://codereview.chromium.org/26695002/diff/31001/pkg/collection_helpers/te...
pkg/collection_helpers/test/typed_buffers_test.dart:21: testUint(64, (l) => new
Uint64Buffer(l));  /// 01: ok
01: continued ?

https://codereview.chromium.org/26695002/diff/31001/pkg/collection_helpers/te...
pkg/collection_helpers/test/typed_buffers_test.dart:24:
testInt32x4Buffer(intSamples);
This works in dart2js ?

[sra1, 2013-11-18 22:16:35]

https://codereview.chromium.org/26695002/diff/31001/pkg/collection_helpers/li...
File pkg/collection_helpers/lib/typed_buffers.dart (right):

https://codereview.chromium.org/26695002/diff/31001/pkg/collection_helpers/li...
pkg/collection_helpers/lib/typed_buffers.dart:22: implements TypedData, List<E>
{
Is it possible to do this without implementing TypedData?

Implementing TypedData (which in dart2js's dart:typed_data maps to DOM typed
ArrayBufferView) means that serialization code can no longer detect typed arrays
with "is TypeData", and objects that answer "is TypedData" will have surprising
bugs when used with IndexDB or postMessage.

This is the same issue that I pointed out with implementing Int8List, just with
the parent class.

https://codereview.chromium.org/26695002/diff/31001/pkg/collection_helpers/li...
pkg/collection_helpers/lib/typed_buffers.dart:115: _buffer =
_createBiggerBuffer(null)..setRange(0, _length, _buffer);
On 2013/11/18 18:03:40, floitsch wrote:
> Please split.

Why? then you need a temporary to hold one of (old)buffer or (new)buffer.
The cascade expresses in one line what would take three otherwise.

[Lasse Reichstein Nielsen, 2013-11-19 10:31:24]

https://codereview.chromium.org/26695002/diff/31001/pkg/collection_helpers/li...
File pkg/collection_helpers/lib/all.dart (right):

https://codereview.chromium.org/26695002/diff/31001/pkg/collection_helpers/li...
pkg/collection_helpers/lib/all.dart:14: * - `typed_bufers.dart`: Growable typed
data lists.
Fixed.

https://codereview.chromium.org/26695002/diff/31001/pkg/collection_helpers/li...
File pkg/collection_helpers/lib/typed_buffers.dart (right):

https://codereview.chromium.org/26695002/diff/31001/pkg/collection_helpers/li...
pkg/collection_helpers/lib/typed_buffers.dart:22: implements TypedData, List<E>
{
On 2013/11/18 22:16:35, sra1 wrote:
> Is it possible to do this without implementing TypedData?

Ofcourse I can do that, but isn't it a problem that user code cannot implement
TypedData?
I don't expect myself to be the only one who would want to do it, so eventually
somebody will do it anyway, and stuff will break.

Or, in other words, if you need to detect the exact classes for any reason, I
don't think using a public interface is safe. Have you considered having an
internal "_RealTypedData" interface instead?

I've removed "TypedData" from the interface, but retained the fields. 
I wouldn't mind adding it again later, if we can find an amicable way to do it
without complicating dart2js too much.

https://codereview.chromium.org/26695002/diff/31001/pkg/collection_helpers/li...
pkg/collection_helpers/lib/typed_buffers.dart:25: /// This is an Uint8List for
Uint8Buffer. It's both a List<E> and a TypedData,
Good catch.

https://codereview.chromium.org/26695002/diff/31001/pkg/collection_helpers/li...
pkg/collection_helpers/lib/typed_buffers.dart:120: if (!identical(source, this))
{
That could work, yes.

https://codereview.chromium.org/26695002/diff/31001/pkg/collection_helpers/te...
File pkg/collection_helpers/test/typed_buffers_test.dart (right):

https://codereview.chromium.org/26695002/diff/31001/pkg/collection_helpers/te...
pkg/collection_helpers/test/typed_buffers_test.dart:21: testUint(64, (l) => new
Uint64Buffer(l));  /// 01: ok
True.

https://codereview.chromium.org/26695002/diff/31001/pkg/collection_helpers/te...
pkg/collection_helpers/test/typed_buffers_test.dart:24:
testInt32x4Buffer(intSamples);
Apparently. The test runs.

https://codereview.chromium.org/26695002/diff/31001/pkg/collection_helpers/te...
pkg/collection_helpers/test/typed_buffers_test.dart:27: testFloatBuffer(32,
roundedFloatSamples,    /// 02: ok
This should work in dart2js too now.

[Lasse Reichstein Nielsen, 2013-11-19 11:32:51]

Committed patchset #6 manually as r30396 (presubmit successful).

[Lasse Reichstein Nielsen, 2013-11-21 12:30:10]

Committed patchset #10 manually as r30514 (presubmit successful).

[Lasse Reichstein Nielsen, 2013-11-22 10:23:36]

Revert commit

[Lasse Reichstein Nielsen, 2013-11-22 10:32:03]

Committed patchset #16 manually as r30569 (presubmit successful).