Summary:
Implement allocation into young gen, evacuation of young gen, and collection of old gen.
All of these are implemented sequentially right now, to get the basic structure working and tests passing.
Currently only marking and sweeping are done in the old gen, no compaction is done at all.
Concurrency will be added in later stages. It is expected that there will probably be some major changes to data structures and algorithms used during those changes.
For those reasons I have left some performance-related work as "TODO".
Currently this GC is not yet suitable to be activated, it is 2x slower on v8-splay (probably mostly from the naive free-list implementation), and is missing some fringe functionality (snapshots, tripwire, clearing DPM, etc.).
Reviewed By: davedets
Differential Revision: D20241740
fbshipit-source-id: 685eaa1e7bb9ad255e1b2a61efed270ddd29e3d3
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
Summary:
The standard MIT license header wasn't applied correctly to our JS files.
Run a linter to auto-fix all of them.
Reviewed By: zertosh
Differential Revision: D17741471
fbshipit-source-id: e507014bb23c8cfafa1172b3dec99224e77c9674
Andres Suarez
Riley Dulin
Tzvetan Mikov
Will Holen