How Strings Are Implemented In SpiderMonkey

0

In this article, I am going to explain how SpiderMonkey, the JavaScript engine used by Firefox, implements strings. Strings are an important part of any scripting language, and JavaScript is no exception. Because they are so important, JavaScript includes strings as a primitive data type. Primitive data types are directly supported by the language, and as such it is the responsibility of the engine to implement them.

Because most scripts make extensive use of them, it is important that strings are implemented as efficiently as possible. For instance, concatenating multiple strings is a common operation in most scripts. In a naive implementation, this operation would take O(n2) steps (where n is the sum of the lengths of the strings involved). In a more sophisticated implementation, this operation would take only O(n) steps.

SpiderMonkey’s string implementation is quite sophisticated. The current iteration has mostly been the work of Luke Wagner and Alan Pierce, two of our super smart engine hackers. Unfortunately, because it is so sophisticated, the implementation is also quite complex. To manage this complexity, the implementation has been broken up into multiple classes, and organized into a single inheritance hierarchy. This class hierarchy will be the subject of the first section.

For maximum efficiency, SpiderMonkey contains multiple string implementations, each of which corresponds to a different class. Because each implementation is appropriate in different situations, we want to be able to switch between implementations at run-time. This is something that is normally not possible without introducing another level of indirection. This extra level of indirection can be avoided by implementing inheritance with tagged unions instead of virtual functions. Tagged unions will be discussed in section two.

Class Hierarchy

In this section, I will give an overview of the different classes that make up SpiderMonkey’s string implementation, and how they are related to each other. All string classes are organized into a single inheritance hierarchy, as shown by the following class diagram:

At the top of the hierarchy, we find the class JSString. For each string in JavaScript, there is a corresponding instance of this class. Conceptually, a JSString is just an array of jschars with a given length. Under the hood, however, its implementation might be completely different; for maximum efficiency, SpiderMonkey contains multiple implementations of JSString, each of which is appropriate in different situations.

The boxes labeled in white represent concrete classes. Each concrete class corresponds to a particular implementation of JSString. For instance, JSRope is optimized to represent concatenated strings, and JSDependentString to represent substrings. Later in this article, each concrete class will be discussed in more detail.

The boxes labeled in gray represent abstract classes. Each abstract class establishes one or more invariants. An invariant is a guarantee that a concrete class must implement. For instance, any concrete class that inherits from JSLinearString must represent a string as a contiguous array of jschars. Abstract classes and their invariants will be discussed in a later section.

Tagged Unions

In the previous section, I introduced the class hierarchy that makes up SpiderMonkey’s string implementation. In this section, I will explain how inheritance is implemented in this hierarchy.

In C++, inheritance is traditionally implemented with virtual functions. Instead, we use something called tagged unions. Tagged unions have several advantages over virtual functions. First of all, they are often more efficient. More importantly, however, they allow an object to change it type at run-time. This allows us to switch string implementations without introducing another level of indirection.

To implement a class hierarchy with a tagged union, we need to know all the classes in the hierarchy up front. Then, instead of storing the representation of each class in the class itself, we store them in the class at the top of the hierarchy. Because only one representation is needed at once, we store all of them into a single union, combined with a type field that indicated the one currently in use. This combination of a type field and a union is what tagged unions derive their name from.

To better understand how tagged unions can be used to implement inheritance, consider the following example:

class A {
public:
    bool isB() const
    {
        return type == TYPE_B;
    }
 
    bool isC() const
    {
        return type == TYPE_C;
    }
 
    B& asB()
    {
        assert(isB());
        return *(B *) this;
    }
 
    C& asC()
    {
        assert(isC());
        return *(C *) this;
    }
 
    void f()
    {
        if (isB())// do stuff specific to B
        else {
            assert(isC());// do stuff specific to C
        }
    }
 
private:
    enum {
        TYPE_B,
        TYPE_C
    } type;
    union {
        struct {} B;
        struct {} C;
    } data;
};
 
class B : public A {
public:
    void g(); // do stuff specific to B};
 
class C : public A {
public:
    void h(); // do stuff specific to C};

Suppose we start out with a pointer to an object of class A. To access any of the methods in class B or C via this pointer, we first have to perform a run-time check whether the object it points to is actually of this type. This check is performed by calling the method A::isB or A::isC, respectively. Only when the check succeeds can we cast the object to the respective class, by calling the method A::asB or A::asC, respectively.

Abstract Classes

In the previous section I explained how tagged unions can be used to implement inheritance. We are now ready to take a closer look at the individual classes that make up SpiderMonkey’s string implementation. This section begins by introducing the abstract classes.

The abstract classes are JSString,  JSLinearString, and JSFlatString. These classes do not correspond with any particular string implementation. Instead, as I explained earlier, their purpose is to establish one or more invariants for the classes that inherit from it.

An invariant is a guarantee that a concrete class must implement, without any dynamic checks. Examples of such invariants are that the string must be represented as a contiguous arrays of jschars, or that it must be zero-terminated (neither of these invariants are true in general). As a general rule, the farther we go down in the class hierarchy, the stronger the invariants established by each class.

The class JSString, being at the top of the hierarchy, is the most abstract class. Classes that inherit from it are required to implement a string with a given length, but nothing else. The class JSLinearString, which inherits from JSString, establishes the same invariant, but adds the requirement that classes that inherit from it must represent this string as a single contiguous array of jschars. Similarly, the class JSFixedString establishes the same invariants as JSLinearString, but adds the requirement that the string must be zero-terminated.

The following table gives an overview of each abstract class and their corresponding invariants:

JSString provides two methods, ensureLinear and ensureFlat, that are used to ensure that its underlying implementation inherits from JSLinearString or JSFlatString, respectively. The general usage pattern when working with JSStrings is this:

  1. Establish the invariants that you want your string to have.
  2. Make sure the string satisfies these invariants by calling either ensureLinear or ensureFlat
  3. Use the string by accessing it through the resulting abstract class.

Let’s take a closer look at the implementation  of ensureLinear and ensureFlat:

JS_ALWAYS_INLINE JSLinearString *
JSString::ensureLinear(JSContext *cx)
{
    return isLinear()
           ? asLinear()
           : asRope().flatten(cx);
}
 
JS_ALWAYS_INLINE JSFlatString *
JSString::ensureFlat(JSContext *cx)
{  
    return isFlat()
           ? asFlat()
           : isDependent()
             ? asDependent().undepend(cx)
             : asRope().flatten(cx);
}

The methods JSRope::flatten and JSDependentString:: undepend convert a JSRope to a JSExtensibleString, and a JSDependentString to a JSFixedString, respectively, by changing the class of the object at run-time, something that is only possible because we implemented inheritance with tagged unions.

JSFixedString

In the previous section, I introduced the abstract classes, and explained how they are use. Now it’s time to move on to the concrete classes. This section begins by introducing the simplest concrete class, JSFixedString.

The class JSFixedString inherits from JSFlatString. Therefore, it must be implement a string with a given length that is represented as a contiguous, zero-terminated array of jschars. It does this by explicitly storing a length and a pointer to the zero-terminated array:

When working with pointers in C, an important concept is that of ownership. A pointer that has been obtained with a call to the function JS_malloc is said to be owned. The owner of a pointer is responsible for issuing the corresponding call to the function JS_free when the memory pointed to is no longer needed.

A JSFixedString is initialized with an owned pointer. That is, to initialize a JSFixedString, a block of memory is allocated with a call to JS_malloc, its contents initialized with a C-style string, and then a pointer to this block is passed as an argument to JSFixedString‘s constructor. On initialization, a JSFixedString is said to grab ownership of this pointer, which means that it becomes responsible for issuing the corresponding call to JS_free.

Because of a JSFixedString grabs ownership of its pointer, you should never initialize it with an unowned pointer, because such a pointer is by definition already owned by somebody else. Moreover, since a JSFixedString calls JS_free as soon as it’s finalized or converted into something else, you should never initialize it with a pointer that is used by other objects if the lifetime of those objects extends that of the JSFixedString itself. Otherwise, JSFixedString will call JS_free on this pointer, before the other objects are deleted, causing their copies of the pointer to become invalid.

The SpiderMonkey API provides two functions, JS_NewStringCopyN and JS_NewStringCopyZ, that can be used to create instances of JSFixedString.

JSExternalString

In the previous section, I introduced the class JSFixedString. I also explained that you shouldn’t try to initialize this class with an unowned pointer. In some cases, that is really what you want though, for instance when you have a pointer that is managed by some third party library over which you have no control (you could always make a copy of course, but that is needlessly inefficient).

This section introduces the class JSExternalString. This class is a specialization of JSFixedString; it behaves almost exactly the same, except for one difference: it does not grab ownership of its pointer. This means you can initialize a JSExternalString with an unowned pointer without having to make a copy:

The SpiderMonkey API provides a single function, JS_NewExternalString, that can be used to create instances of JSExternalString. Use this function with care though: since a JSExternalString never calls JS_free on its pointer, you are responsible for doing so.

Not calling JS_free on a pointer when it is no longer being used can easily lead to memory leaks, so even though JSExternalString is more efficient, it is almost always better to use JSFixedString, since that class keeps track of when to call JS_free for you. Sure, this takes one extra string copy, but the performance impact of this is almost always negligible.

If you do decide to use JSExternalString, though, you need to know when each instance is finalized. After all, you should not call JS_free on a pointer when it is still being used by an instance of JSExternalString. The SpiderMonkey API provides a single function JS_AddExternalStringFinalizer, which is used to register a callback that will be called each time an instance of JSExternalString is finalized.

JSInlineString

The previous sections introduced the classes JSFixedString and JSExternalString. These classes represent a string as a pointer to a block of memory on the heap. These blocks need to be allocated, and these allocations are relatively expensive. In particular, when dealing with large numbers of small strings, heap allocations can quickly become expensive.

This section introduces the class JSInlineString. This class is an optimization of JSFixedString; it represents a string as a pointer to a block of memory inside the object itself (hence the term inline):

Because we use a tagged union, every string class shares the same representation. Therefore, the representation of the simplest class has the same size as that of the most complex one. JSInlineString exploits this by using the unused part of the representation as inline storage. The number of characters that can be stored this way is 2 * sizeof(void *) / sizeof(jschar). Since jschars are 16-bit, on a platform with 32-bit pointers this allows us to store strings of up to 4 characters long.

The SpiderMonkey API does not provide any functions to create instances of JSInlineString. They are only created implicitly, as optimization in functions that are normally create instances of JSFixedString.

JSShortString

In the previous section, I introduced the class JSInlineString. This class can store strings of up to 4 characters long without allocating a memory block on the heap. The only problem is: 4 characters isn’t all that long. Most short strings are longer than 4 characters. This limits the usefulness over JSInlineString as an optimization.

This section introduces the class JSShortString. This class is a further optimization of JSInlineString; it can store most short strings without allocating a memory block on the heap:

Because JSInlineString already takes up the entire representation as inline storage, the only way for JSShortString to store longer strings is by increasing the size of its representation. When an instance JSShortString is created, it is allocated from a different memory pool than the other string classes, using a memory block that is twice as large.

The fact that instances of JSShortString are allocated from a different memory pool makes them somewhat special. In particular instances of JSShortString cannot change their type at run-time (since that would require them to move to the main memory pool). Fortunately, this is not a problem, since JSShortString already inherits from JSFlatString, and there is never a need to convert an object to a more abstract type.

As with JSInlineString, instances of JSShortString are only created implicitly.

JSDependentString

In this section, I will introduce the concrete class JSDependentString. This class is optimized to represent substrings. Before we can understand how and why it works, however, we must first know a few things about how substrings are created.

Let s be a string with length n. Suppose we want to create a substring s’ of s with length n’. The naive method to creating a substring consists of the following 3 steps:

  1. Allocate a memory block s’ of size n + 1:
  2. Copy n’ bytes from s to s’:
  3. Set the last byte of s’ to ‘\0′:

Now suppose we want to create a substring s” of the substring s’ with length n”. Again, using the same 3 steps as before:

  1. Allocate a memory block s” of size n” + 1:
  2. Copy n’ bytes from s’ to s”:
  3. Set the last byte of s” to ‘\0′:

To create a substring of a substring this way we had to allocate 2 blocks of memory and copy n’ + n” bytes. In general, to obtain the k-th substring of a string with length n would take O(n2) steps using this method.

Not surprisingly, the naive way to obtain substrings is needlessly inefficient. The intermediate result s’ is never used for anything other than computing the final result s’‘, so it would have been more efficient to compute s” directly. Unfortunately, we can’t tell if s’ will only be used as an intermediate result when it is created. Even if we could, we can’t simply skip its creation, because s” is defined in terms of s’, not s.

The solution here is to use something called lazy evaluation: instead of creating the substring immediately and storing the result, we store everything that is needed to create the substring at a later time, when the result is actually needed. When such a “delayed” substring is used to create another substring, they can be combined to form a single composite operation:

As you can see in the image above, this is exactly what JSDependentString does: it stores a pointer to the original string (the base), a pointer into the base string that marks the start of the substring, and the length of the substring, so that it can be obtained at a later time. The base is an instance of JSLinearString.

Since JSDependentString inherits from JSLinearString, it can serve as the base of another substring, thus creating a composite operation. When the substring is actually needed inside the engine, a JSDependentString can be converted to a JSFixedString, by calling the internal method JSDependentString::undepend.

The SpiderMonkey API provides a single function, JS_NewDependentString, that can be used to obtain instances of JSDependentString. As should be obvious by now, it is recommended to use this function whenever possible, since it is often more efficient than creating a substring directly.

JSRope

In this section, I will introduce the concrete class JSRope. This class is optimized to represent concatenations. Before we can understand how and why it works, however, we must first know a few things about how concatenations are created.

Let s1, s2 and s3 be strings with lengths n1, n2 and n3, respectively. Suppose we want to concatenate s1 and s2 to form the string s1s2. The naive method to concatenate two strings consists of the following 4 steps:

  1. Allocate a memory block s1s2 of size n1 + n2:
  2. Copy s1 to the first n1 bytes of s1s2:
  3. Copy s2 to the next n2 bytes of s1s2:
  4. Set the last byte of s1s2 to ‘\0′:

Now suppose we want to concatenate s1s2 and s3 to form the string s1s2s3. Again, using the same 4 steps as before:

  1. Allocate a memory block s1s2s3 of size n1 + n2 + n3 + 1:
  2. Copy s1s2 to the first n1 + n2 bytes of s1s2s3:
  3. Copy s3 to the next n3 bytes of s1s2s3:
  4. Set the last byte of s1s2s3 to ‘\0′:

To concatenate 3 strings this way we had to allocate 2 blocks of memory and copy 2 * (n1 + n2) + n3 + 1 bytes. In general, to concatenate k strings s1, s2, …, sk with lengths n1, n2, …, nk, respectively, would take O(N2) steps using this method (where N = n1 + n2 + … + nk).

Obviously, for large N, the naive method to concatenate strings quickly becomes too expensive. Can we do better? It turns out that we can. To understand how, let’s take another look at our previous example of concatenating 3 strings. It should be obvious that the intermediate result in this computation, s1s2, is never used for anything other than computing the final result s1s2s3.

The creation of s1s2 could have been avoided had we known the lengths of all the strings to be concatenated in advance. In that case, we could have concatenated all three strings at once, using the following 5 steps:

  1. Allocate a memory block s1s2s3 of size n1 + n2 + n3 + 1:
  2. Copy s1 to the first n1 bytes of s1s2s3:
  3. Copy s2 to the next n2 bytes of s1s2s3:
  4. Copy s3 to the next n3 bytes of s1s2s3:
  5. Set the last byte of s1s2s3 to ‘\0′:

To concatenate 3 strings this way we had to allocate 1 block of memory and copy n1 + n2 + n3 + 1 bytes. In general, to concatenate k strings s1, s2, …, sk with lengths n1, n2, …, nk, respectively, would take O(N) steps using this method (where N = n1 + n2 + … + nk).

It should be obvious that the above method to concatenate strings is much more efficient than the naive one. However, it critically depends on the assumption that the lengths of all the strings to be concatenated are known in advance. Unfortunately, in most code, this assumption simply does not hold, as the following example shows:

while (...)
    s += ...

The solution here is to use lazy evaluation again: instead of creating the concatenation immediately and storing the result, we store everything that is needed to create the concatenation at a later time, when the result is actually required. When such a “delayed” concatenation is used to create another concatenation, they can be combined to form a single composite operation:

As you can see in the image above, is is exactly what JSRope does: it stores a pointer to the left and right hand sides of a concatenation, so that it can be performed at a later time. Both sides of the concatenation are instances of JSString.

Since JSRope inherits from JSString, it can serve as the left or right hand side of another concatenation, thus creating a composite operation. When the concatenation of the concatenation is actually needed inside the engine, a JSRope can be converted to an JSExtensibleString, by calling the internal method JSRope::flatten (the reason why we convert to aJSExtensibleString instead of a JSFixedString will become clear in the next section).

The SpiderMonkey API provides a single function, JS_ConcatStrings, that can be used to concatenate strings using JSRope (note that JS_ConcatString does not always create a JSRope though, since it contains several other optimizations).

JSExtensibleString

In this section I will introduce the cass JSExtensibleString. This class implements a performance optimization for the JSRope::flatten algorithm. To understand why we need this optimization, and how it works, read on below.

As we’ve seen in the previous section, by using JSRope, we can reduce the complexity of code that exhibits the pattern here below from O(N2) to O(N):

while (...)
    s += ...

Traditionally, most engines, including SpiderMonkey, have also been able to run code that exhibits the pattern here below with a complexity of O(N):

while (...) {
    s += ...
    s.flatten()
}

Using JSRope doesn’t save us in this case, since it’s flattened immediately after it’s creation. Without JSRope, we can’t tell the lengths of all the strings to be concatenated in advance, so we have to fall back to the naive method for concatenating strings.

Let s1, s2 and s3 be strings with lengths n1, n2 and n3, respectively. Suppose we want to concatenate them to form the string s1s2s3. Using the naive method for concatenating strings, we would first have to create the intermediate string s1s2:

However, we can improve the performance of the naive algorithm at this point by allocating a larger block of memory for s1s2 than strictly necessary in the first step, say 2p bytes, where p is the smallest integer such that n1 + n2 + 1 <= 2p:

If we are lucky, n1 + n2 + n3 + 1 <= 2as well, so that when we want to concatenate  s1s2 and s3 to form s1s2s3, we can simply copy s3 into s1s2‘s extra space, thus avoiding both an allocation and a string copy:

Because sometimes n1 + n2 + n3 + 1 > 2p, this optimization doesn’t always work. However, by allocating memory in this manner, as the smallest power of two that is still large enough to contain the result, we have reduced the complexity to O(N) on average (where N is the total length of the strings to be concatenated), even though some operations are more expensive than others.

The class JSExtensibleString is responsible for implementing the above performance optimization. It is very similar to JSFixedString, except that it allocates its own memory (so it can never contain external pointers), and stores an additional capacity, which is the actual amount of memory it allocated (as opposed to the amount it actually needs, i.e. the length + 1):

Perhaps surprisingly, the SpiderMonkey API does not provide any functions to create instances of JSExtensibleString. They are only created indirectly, as a result of calling the internal method JSRope::flatten on a JSRope.

Categories: Uncategorized

No responses {+}

Post Your Comment