2019-10-21 22:34:48 +03:00
|
|
|
/**
|
2021-12-31 02:06:42 +03:00
|
|
|
* Copyright (c) Meta Platforms, Inc. and affiliates.
|
2019-10-21 22:34:48 +03:00
|
|
|
*
|
|
|
|
|
* This source code is licensed under the MIT license found in the
|
|
|
|
|
* LICENSE file in the root directory of this source tree.
|
|
|
|
|
*/
|
|
|
|
|
|
2020-05-14 00:53:33 +03:00
|
|
|
// RUN: %hermes -O -gc-max-heap=8M %s | %FileCheck --match-full-lines %s
|
2019-07-10 19:43:32 +03:00
|
|
|
|
|
|
|
|
print('ArrayBuffer')
|
|
|
|
|
// CHECK-LABEL: ArrayBuffer
|
|
|
|
|
|
|
|
|
|
// Smaller than max heap succeeds.
|
|
|
|
|
a = new ArrayBuffer(1000000);
|
|
|
|
|
|
|
|
|
|
// Even if done multiple times; GC should collect unused ones.
|
|
|
|
|
a = new ArrayBuffer(1000000);
|
|
|
|
|
a = new ArrayBuffer(1000000);
|
|
|
|
|
a = new ArrayBuffer(1000000);
|
|
|
|
|
a = new ArrayBuffer(1000000);
|
|
|
|
|
|
|
|
|
|
a = null;
|
|
|
|
|
|
|
|
|
|
// Larger than max heap fails
|
|
|
|
|
try {
|
2020-05-14 00:53:33 +03:00
|
|
|
a = new ArrayBuffer(12000000);
|
2019-07-10 19:43:32 +03:00
|
|
|
} catch (x) {
|
|
|
|
|
print(x)
|
|
|
|
|
// CHECK-NEXT: RangeError: Cannot allocate a data block for the ArrayBuffer
|
|
|
|
|
}
|
|
|
|
|
a = null;
|
|
|
|
|
|
|
|
|
|
print('ExternalStringPrimitive')
|
|
|
|
|
// CHECK-LABEL: ExternalStringPrimitive
|
|
|
|
|
|
buffered concatenation of string primitives
Summary:
Attempt to address the case where smaller strings are repeatedly
appended to a larger string. Example code might look like this:
var str = "";
for(let i = 0; i < 100000; ++i)
str += " ";
A naive execution of this code leads to quadratic behavior because it
requires an allocation and a copy of the string for each iteration.
Traditionally that is addressed by a tree-like data structure called a
"rope", which represents each string addition by a new heap object with
pointers to the "left" and "right" side of the addition. It can work
well performance-wise, but it has significant memory overhead because it
can require allocating an object per character. Additionally it
introduces significant complexity when the "rope" needs to be
"flattened" in order to be processed by traditional string functions.
We have chosen an alternative approach designed in a discussion with
David Detlefs and Riley Dulin. It relies on implicitly maintaining a
growable "concatenation buffer" where every new string is appended to
the buffer and the result of the concatenation is a new StringPrimitive
referencing a prefix of the buffer.
This approach can also produce a new object per appended character (the
result StringPrimitive), but unlike ropes, that object is not part of a
tree, so it potentially becomes garbage collectable very soon, usually
in the next young-gen collection.
There are two objects that represent this model at runtime:
- the concatenation buffer containing storage which doubles its
capacity when necessary.
- BufferedStringPrimitive containing a reference to the concatenation
buffer and a length. This represents the result of a single
concatenation.
The concatenation algorithm is very simple:
1. If the left part of the concatenation is already a
BufferedStringPrimitive, get its concatenation buffer, append the right
part to it, then allocate and return a new BufferedStringPrimitive with
the same buffer and the new length.
2. Otherwise, if the combined length of the two strings is above a
threshold, allocate a new buffer, initialize it with the the
concatenation of the two strings and return a new
BufferedStringPrimitive with the buffer and length.
(This ignores some details like ASCII and UTF16 strings, which do not
change the overall complexity.)
This algorithm is very simple and it results in strings that are already
flattened in memory, so they are usable immediately at any time.
This commit makes use of a further simplification: this optimization
primarily benefits "large" strings, which already live in native memory
and a represented by a `std::basic_string<>`. A `std::basic_string<>` is
already growable string storage and we even already have a heap object
that wraps it: `ExternalStringPrimitive<>`. So we can literally use
ExternalStringPrimitive<> to represent the concatenation buffer without
almost any changes.
There are several issues that need to be investigated more and possibly
addressed in future commits:
1. Perhaps this optimizations is beneficial at smaller strings sizes
too, which might mean that we also need a "in-GC-heap" representation of
the concatenation buffer.
2. Since all concatenation steps share the same buffer, it is possible
that an early step could keep alive in memory a significantly larger
concatenation buffer. This is unlikely but possible. One way to address
it would be to allocate a new concatenation buffer after some amount if
resizing, this putting an upper limit on how much each step can keep in
memory.
3. The std::basic_string<> excess capacity should probably be trimmed
during full collections.
The performance results are encouraging: pdfjs.js speeds up by a factor
of about 3x.
Reviewed By: mhorowitz
Differential Revision: D17955802
fbshipit-source-id: 9f4c365e86337ced8e30828c4bd39664883bb06f
2019-10-28 22:12:36 +03:00
|
|
|
// Note: use Array.join() instead of string concatenation to avoid the relative
|
|
|
|
|
// unpredictability of fast buffered concatenation.
|
2019-07-10 19:43:32 +03:00
|
|
|
var s10 = 'aaaaaaaaaa';
|
buffered concatenation of string primitives
Summary:
Attempt to address the case where smaller strings are repeatedly
appended to a larger string. Example code might look like this:
var str = "";
for(let i = 0; i < 100000; ++i)
str += " ";
A naive execution of this code leads to quadratic behavior because it
requires an allocation and a copy of the string for each iteration.
Traditionally that is addressed by a tree-like data structure called a
"rope", which represents each string addition by a new heap object with
pointers to the "left" and "right" side of the addition. It can work
well performance-wise, but it has significant memory overhead because it
can require allocating an object per character. Additionally it
introduces significant complexity when the "rope" needs to be
"flattened" in order to be processed by traditional string functions.
We have chosen an alternative approach designed in a discussion with
David Detlefs and Riley Dulin. It relies on implicitly maintaining a
growable "concatenation buffer" where every new string is appended to
the buffer and the result of the concatenation is a new StringPrimitive
referencing a prefix of the buffer.
This approach can also produce a new object per appended character (the
result StringPrimitive), but unlike ropes, that object is not part of a
tree, so it potentially becomes garbage collectable very soon, usually
in the next young-gen collection.
There are two objects that represent this model at runtime:
- the concatenation buffer containing storage which doubles its
capacity when necessary.
- BufferedStringPrimitive containing a reference to the concatenation
buffer and a length. This represents the result of a single
concatenation.
The concatenation algorithm is very simple:
1. If the left part of the concatenation is already a
BufferedStringPrimitive, get its concatenation buffer, append the right
part to it, then allocate and return a new BufferedStringPrimitive with
the same buffer and the new length.
2. Otherwise, if the combined length of the two strings is above a
threshold, allocate a new buffer, initialize it with the the
concatenation of the two strings and return a new
BufferedStringPrimitive with the buffer and length.
(This ignores some details like ASCII and UTF16 strings, which do not
change the overall complexity.)
This algorithm is very simple and it results in strings that are already
flattened in memory, so they are usable immediately at any time.
This commit makes use of a further simplification: this optimization
primarily benefits "large" strings, which already live in native memory
and a represented by a `std::basic_string<>`. A `std::basic_string<>` is
already growable string storage and we even already have a heap object
that wraps it: `ExternalStringPrimitive<>`. So we can literally use
ExternalStringPrimitive<> to represent the concatenation buffer without
almost any changes.
There are several issues that need to be investigated more and possibly
addressed in future commits:
1. Perhaps this optimizations is beneficial at smaller strings sizes
too, which might mean that we also need a "in-GC-heap" representation of
the concatenation buffer.
2. Since all concatenation steps share the same buffer, it is possible
that an early step could keep alive in memory a significantly larger
concatenation buffer. This is unlikely but possible. One way to address
it would be to allocate a new concatenation buffer after some amount if
resizing, this putting an upper limit on how much each step can keep in
memory.
3. The std::basic_string<> excess capacity should probably be trimmed
during full collections.
The performance results are encouraging: pdfjs.js speeds up by a factor
of about 3x.
Reviewed By: mhorowitz
Differential Revision: D17955802
fbshipit-source-id: 9f4c365e86337ced8e30828c4bd39664883bb06f
2019-10-28 22:12:36 +03:00
|
|
|
var s100 = [s10, s10, s10, s10, s10, s10, s10, s10, s10, s10].join("")
|
2019-07-10 19:43:32 +03:00
|
|
|
|
|
|
|
|
function strOfSize(n) {
|
|
|
|
|
if (n < 100) {
|
|
|
|
|
return s100.substring(0, n);
|
|
|
|
|
} else {
|
|
|
|
|
var leftSize = Math.floor(n / 2);
|
|
|
|
|
var left = strOfSize(leftSize);
|
|
|
|
|
// Don't allocate a string for rightSize -- that would mean exponential work,
|
|
|
|
|
// and live memory proportional to n before the final allocation.
|
|
|
|
|
if (leftSize * 2 == n) {
|
buffered concatenation of string primitives
Summary:
Attempt to address the case where smaller strings are repeatedly
appended to a larger string. Example code might look like this:
var str = "";
for(let i = 0; i < 100000; ++i)
str += " ";
A naive execution of this code leads to quadratic behavior because it
requires an allocation and a copy of the string for each iteration.
Traditionally that is addressed by a tree-like data structure called a
"rope", which represents each string addition by a new heap object with
pointers to the "left" and "right" side of the addition. It can work
well performance-wise, but it has significant memory overhead because it
can require allocating an object per character. Additionally it
introduces significant complexity when the "rope" needs to be
"flattened" in order to be processed by traditional string functions.
We have chosen an alternative approach designed in a discussion with
David Detlefs and Riley Dulin. It relies on implicitly maintaining a
growable "concatenation buffer" where every new string is appended to
the buffer and the result of the concatenation is a new StringPrimitive
referencing a prefix of the buffer.
This approach can also produce a new object per appended character (the
result StringPrimitive), but unlike ropes, that object is not part of a
tree, so it potentially becomes garbage collectable very soon, usually
in the next young-gen collection.
There are two objects that represent this model at runtime:
- the concatenation buffer containing storage which doubles its
capacity when necessary.
- BufferedStringPrimitive containing a reference to the concatenation
buffer and a length. This represents the result of a single
concatenation.
The concatenation algorithm is very simple:
1. If the left part of the concatenation is already a
BufferedStringPrimitive, get its concatenation buffer, append the right
part to it, then allocate and return a new BufferedStringPrimitive with
the same buffer and the new length.
2. Otherwise, if the combined length of the two strings is above a
threshold, allocate a new buffer, initialize it with the the
concatenation of the two strings and return a new
BufferedStringPrimitive with the buffer and length.
(This ignores some details like ASCII and UTF16 strings, which do not
change the overall complexity.)
This algorithm is very simple and it results in strings that are already
flattened in memory, so they are usable immediately at any time.
This commit makes use of a further simplification: this optimization
primarily benefits "large" strings, which already live in native memory
and a represented by a `std::basic_string<>`. A `std::basic_string<>` is
already growable string storage and we even already have a heap object
that wraps it: `ExternalStringPrimitive<>`. So we can literally use
ExternalStringPrimitive<> to represent the concatenation buffer without
almost any changes.
There are several issues that need to be investigated more and possibly
addressed in future commits:
1. Perhaps this optimizations is beneficial at smaller strings sizes
too, which might mean that we also need a "in-GC-heap" representation of
the concatenation buffer.
2. Since all concatenation steps share the same buffer, it is possible
that an early step could keep alive in memory a significantly larger
concatenation buffer. This is unlikely but possible. One way to address
it would be to allocate a new concatenation buffer after some amount if
resizing, this putting an upper limit on how much each step can keep in
memory.
3. The std::basic_string<> excess capacity should probably be trimmed
during full collections.
The performance results are encouraging: pdfjs.js speeds up by a factor
of about 3x.
Reviewed By: mhorowitz
Differential Revision: D17955802
fbshipit-source-id: 9f4c365e86337ced8e30828c4bd39664883bb06f
2019-10-28 22:12:36 +03:00
|
|
|
return [left, left].join("");
|
2019-07-10 19:43:32 +03:00
|
|
|
} else {
|
|
|
|
|
// n == 2 * leftSize + 1:
|
buffered concatenation of string primitives
Summary:
Attempt to address the case where smaller strings are repeatedly
appended to a larger string. Example code might look like this:
var str = "";
for(let i = 0; i < 100000; ++i)
str += " ";
A naive execution of this code leads to quadratic behavior because it
requires an allocation and a copy of the string for each iteration.
Traditionally that is addressed by a tree-like data structure called a
"rope", which represents each string addition by a new heap object with
pointers to the "left" and "right" side of the addition. It can work
well performance-wise, but it has significant memory overhead because it
can require allocating an object per character. Additionally it
introduces significant complexity when the "rope" needs to be
"flattened" in order to be processed by traditional string functions.
We have chosen an alternative approach designed in a discussion with
David Detlefs and Riley Dulin. It relies on implicitly maintaining a
growable "concatenation buffer" where every new string is appended to
the buffer and the result of the concatenation is a new StringPrimitive
referencing a prefix of the buffer.
This approach can also produce a new object per appended character (the
result StringPrimitive), but unlike ropes, that object is not part of a
tree, so it potentially becomes garbage collectable very soon, usually
in the next young-gen collection.
There are two objects that represent this model at runtime:
- the concatenation buffer containing storage which doubles its
capacity when necessary.
- BufferedStringPrimitive containing a reference to the concatenation
buffer and a length. This represents the result of a single
concatenation.
The concatenation algorithm is very simple:
1. If the left part of the concatenation is already a
BufferedStringPrimitive, get its concatenation buffer, append the right
part to it, then allocate and return a new BufferedStringPrimitive with
the same buffer and the new length.
2. Otherwise, if the combined length of the two strings is above a
threshold, allocate a new buffer, initialize it with the the
concatenation of the two strings and return a new
BufferedStringPrimitive with the buffer and length.
(This ignores some details like ASCII and UTF16 strings, which do not
change the overall complexity.)
This algorithm is very simple and it results in strings that are already
flattened in memory, so they are usable immediately at any time.
This commit makes use of a further simplification: this optimization
primarily benefits "large" strings, which already live in native memory
and a represented by a `std::basic_string<>`. A `std::basic_string<>` is
already growable string storage and we even already have a heap object
that wraps it: `ExternalStringPrimitive<>`. So we can literally use
ExternalStringPrimitive<> to represent the concatenation buffer without
almost any changes.
There are several issues that need to be investigated more and possibly
addressed in future commits:
1. Perhaps this optimizations is beneficial at smaller strings sizes
too, which might mean that we also need a "in-GC-heap" representation of
the concatenation buffer.
2. Since all concatenation steps share the same buffer, it is possible
that an early step could keep alive in memory a significantly larger
concatenation buffer. This is unlikely but possible. One way to address
it would be to allocate a new concatenation buffer after some amount if
resizing, this putting an upper limit on how much each step can keep in
memory.
3. The std::basic_string<> excess capacity should probably be trimmed
during full collections.
The performance results are encouraging: pdfjs.js speeds up by a factor
of about 3x.
Reviewed By: mhorowitz
Differential Revision: D17955802
fbshipit-source-id: 9f4c365e86337ced8e30828c4bd39664883bb06f
2019-10-28 22:12:36 +03:00
|
|
|
return [left, left, 'a'].join("");
|
2019-07-10 19:43:32 +03:00
|
|
|
}
|
|
|
|
|
}
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
// Smaller than max heap succeeds.
|
|
|
|
|
var s = strOfSize(1000000);
|
|
|
|
|
|
|
|
|
|
// Even if done multiple times; GC should collect unused ones.
|
|
|
|
|
s = strOfSize(1000000);
|
|
|
|
|
s = strOfSize(1000000);
|
|
|
|
|
s = strOfSize(1000000);
|
|
|
|
|
s = strOfSize(1000000);
|
|
|
|
|
s = null;
|
|
|
|
|
|
|
|
|
|
// Larger than max heap fails.
|
|
|
|
|
try {
|
|
|
|
|
s = strOfSize(6000000);
|
|
|
|
|
print('no exception');
|
|
|
|
|
} catch (x) {
|
|
|
|
|
print(x)
|
|
|
|
|
// CHECK-NEXT: RangeError: Cannot allocate an external string primitive.
|
|
|
|
|
}
|
