[vm, lib] Refine List copy loops
`growableList.toList()` was 10-50% faster than `List.of(growableList)`.
This change erases the performance difference.
The loops were slightly different. The faster version created
the _List backing store for the list rather than assigning to the
_GrowableList.
It is not clear if the speedup is from an easier type test (the _List is
'raw'), or from a less indirect assignment, or from a fixed length list
having an an easier-to-optimize bounds check, or whether a non-zero loop
trip count enables any hoisting.
This change uses the faster pattern in the _GrowableList._ofXXXList
methods.
I tried to simplify `toList` to delegate to one of the methods
with the faster loop, but it was 2-5% slower on ListCopy.toList.2,
presumably the extra call is significant for a short list. If there
was an annotation for aggressive inlining into `toList` perhaps that
would close the gap.
dart-aot-null armv8c, 0.5 noise and over
ListCopy.List.num.from.2 24.17% (1.6 noise)
ListCopy.List.of.2 28.08% (1.7 noise)
ListCopy.spread.num.2 28.73% (2.1 noise)
ListCopy.List.num.from.100 54.49% (1.9 noise)
ListCopy.List.of.100 55.55% (1.9 noise)
ListCopy.spread.num.100 55.77% (2.0 noise)
Change-Id: I7b780835faf50b673fd4b1a08a8c4e2d350d7d5b
Reviewed-on: https://dart-review.googlesource.com/c/sdk/+/224780
Reviewed-by: Alexander Markov <alexmarkov@google.com>
Commit-Queue: Stephen Adams <sra@google.com>
diff --git a/sdk/lib/_internal/vm/lib/array.dart b/sdk/lib/_internal/vm/lib/array.dart
index c897b67..ba48fbe 100644
--- a/sdk/lib/_internal/vm/lib/array.dart
+++ b/sdk/lib/_internal/vm/lib/array.dart
@@ -61,8 +61,11 @@
factory _List._ofGrowableList(_GrowableList<E> elements) {
final int length = elements.length;
final list = _List<E>(length);
- for (int i = 0; i < length; i++) {
- list[i] = elements[i];
+ // TODO(30102): Remove this loop zero-trip guard.
+ if (length > 0) {
+ for (int i = 0; i < length; i++) {
+ list[i] = elements[i];
+ }
}
return list;
}
@@ -70,8 +73,11 @@
factory _List._ofList(_List<E> elements) {
final int length = elements.length;
final list = _List<E>(length);
- for (int i = 0; i < length; i++) {
- list[i] = elements[i];
+ // TODO(30102): Remove this loop zero-trip guard.
+ if (length > 0) {
+ for (int i = 0; i < length; i++) {
+ list[i] = elements[i];
+ }
}
return list;
}
@@ -79,8 +85,11 @@
factory _List._ofImmutableList(_ImmutableList<E> elements) {
final int length = elements.length;
final list = _List<E>(length);
- for (int i = 0; i < length; i++) {
- list[i] = elements[i];
+ // TODO(30102): Remove this loop zero-trip guard.
+ if (length > 0) {
+ for (int i = 0; i < length; i++) {
+ list[i] = elements[i];
+ }
}
return list;
}
diff --git a/sdk/lib/_internal/vm/lib/growable_array.dart b/sdk/lib/_internal/vm/lib/growable_array.dart
index 516996f..c6d9e46 100644
--- a/sdk/lib/_internal/vm/lib/growable_array.dart
+++ b/sdk/lib/_internal/vm/lib/growable_array.dart
@@ -110,7 +110,10 @@
// Specialization of List.empty constructor for growable == true.
// Used by pkg/vm/lib/transformations/list_factory_specializer.dart.
@pragma("vm:prefer-inline")
- factory _GrowableList.empty() => _GrowableList(0);
+ factory _GrowableList.empty() {
+ // Specialization of `return _GrowableList(0);`.
+ return _GrowableList<T>._withData(_emptyList);
+ }
// Specialization of List.filled constructor for growable == true.
// Used by pkg/vm/lib/transformations/list_factory_specializer.dart.
@@ -154,43 +157,61 @@
factory _GrowableList._ofList(_List<T> elements) {
final int length = elements.length;
- final list = _GrowableList<T>(length);
- for (int i = 0; i < length; i++) {
- list[i] = elements[i];
+ if (length > 0) {
+ final data = _List(_adjustedCapacity(length));
+ for (int i = 0; i < length; i++) {
+ data[i] = elements[i];
+ }
+ final list = _GrowableList<T>._withData(data);
+ list._setLength(length);
+ return list;
}
- return list;
+ return _GrowableList<T>.empty();
}
factory _GrowableList._ofGrowableList(_GrowableList<T> elements) {
final int length = elements.length;
- final list = _GrowableList<T>(length);
- for (int i = 0; i < length; i++) {
- list[i] = elements[i];
+ if (length > 0) {
+ final data = _List(_adjustedCapacity(length));
+ for (int i = 0; i < length; i++) {
+ data[i] = elements[i];
+ }
+ final list = _GrowableList<T>._withData(data);
+ list._setLength(length);
+ return list;
}
- return list;
+ return _GrowableList<T>.empty();
}
factory _GrowableList._ofImmutableList(_ImmutableList<T> elements) {
final int length = elements.length;
- final list = _GrowableList<T>(length);
- for (int i = 0; i < length; i++) {
- list[i] = elements[i];
+ if (length > 0) {
+ final data = _List(_adjustedCapacity(length));
+ for (int i = 0; i < length; i++) {
+ data[i] = elements[i];
+ }
+ final list = _GrowableList<T>._withData(data);
+ list._setLength(length);
+ return list;
}
- return list;
+ return _GrowableList<T>.empty();
}
factory _GrowableList._ofEfficientLengthIterable(
EfficientLengthIterable<T> elements) {
final int length = elements.length;
- final list = _GrowableList<T>(length);
if (length > 0) {
+ final data = _List(_adjustedCapacity(length));
int i = 0;
for (var element in elements) {
- list[i++] = element;
+ data[i++] = element;
}
if (i != length) throw ConcurrentModificationError(elements);
+ final list = _GrowableList<T>._withData(data);
+ list._setLength(length);
+ return list;
}
- return list;
+ return _GrowableList<T>.empty();
}
factory _GrowableList._ofOther(Iterable<T> elements) {
@@ -358,11 +379,13 @@
// Use shared empty list as backing.
return _emptyList;
}
- // Round up size to the next odd number, since this is free
- // because of alignment requirements of the GC.
- return new _List(capacity | 1);
+ return _List(_adjustedCapacity(capacity));
}
+ // Round up size to the next odd number, since this is free
+ // because of alignment requirements of the GC.
+ static int _adjustedCapacity(int capacity) => capacity | 1;
+
// Grow from 0 to 3, and then double + 1.
int _nextCapacity(int old_capacity) => (old_capacity * 2) | 3;
@@ -501,14 +524,22 @@
}
List<T> toList({bool growable: true}) {
+ // TODO(sra): We should be able to replace the following with:
+ //
+ // return growable
+ // ? _GrowableList<T>._ofGrowableList(this)
+ // : _List<T>._ofGrowableList(this);
+ //
+ // However, the extra call causes a 5% regression in `ListCopy.toList.2`.
+
final length = this.length;
if (growable) {
if (length > 0) {
- final list = new _List(length);
+ final data = new _List(_adjustedCapacity(length));
for (int i = 0; i < length; i++) {
- list[i] = this[i];
+ data[i] = this[i];
}
- final result = new _GrowableList<T>._withData(list);
+ final result = new _GrowableList<T>._withData(data);
result._setLength(length);
return result;
}
