Slimmer and faster JavaScript strings in Firefox

https://blog.mozilla.org/javascript/2014/07/21/slimmer-and-faster-javascript-strings-in-firefox/

by evilpie • 12 years ago

191 66 12 years ago

blog.mozilla.org

thomersch_• 12 years ago

Latin1? I hoped it would die some day.

kannanvijayan• 12 years ago

This is an internal representation. JS strings do and continue to behave as sequences of 16-bit integers.

This change takes advantage of the fact that most JS strings fit into an 8-bit charspace, so for those that do, it uses a more compact representation internally.

This optimization is simply: if we have a string and we know that all of the uint16_ts in the string are <= 255, then just store it as a sequence of uint8_ts.

angersock3• 12 years ago

ES6.1 wishlist: UTF8 strings, full stop.

TheLoneWolfling3• 12 years ago

My personal ideal representation of strings.

Modified rope-like tree, where each node stores a flat array of characters, with the caveat that "characters" within a node must have the same encoding, with the node storing the encoding. Yes, this means that a string can have multiple encodings within it. The internal "default" representation is a flat array of a (modified) UTF-8 encoding, at a fixed number of bytes per character (stored in the encoding) using overlong encodings if necessary. (So if you change a character in a node composed of two-byte characters into a single-byte character, you don't need to regenerate the node if it doesn't make sense.)

nostrademons• 12 years ago

Ropes are great when constructing a large string, but can be much slower and more memory-heavy for comparison, iteration, indexing, and matching. In a typical program, where many of the strings are small literals being matched against or tokenized from a large input, this is often a poor trade-off.

My personal ideal representation of strings, if I were ever doing a new language:

Length-prefixed (in characters) UTF-8, with a redundant null terminator so that the buffer can be passed directly to C libraries without being copied or re-encoded. Assume that heap objects have their size in bytes automatically prefixed (GC requires this), so that it's also possible to get the byte length of the string. Small strings (<7 bytes of UTF-8 on 64-bit, or <3 bytes on 32-bit) are stored immediately; the assumption is the language runtime would use tagged values much like Lisp, so a small string gets a tag value of 0b10 and uses 4 bits or so in that last byte to indicate the length. No null terminator on immediate strings; when they're that small, the cost of copying them to C is negligible (although hmm, the memory management kinda sucks. It'll suck anyway though, as some C libraries expect to take ownership of the string and some don't...and for ones that don't, you could just zero out the tag byte and pass the word directly, then reset the tag when the call completes).

Ropes are available as a standard library data structure with an API identical to strings, but different performance characteristics. All of these are immutable; concatenation and modification result in a copy (in a rope's case, with much shared structure).

Give up on O(1) indexing and slicing, but indexing should always return the complete codepoint at that position in the string and never a corrupted character. Most of the time, indexing or slicing usually involves looking a small number of characters from the beginning or the end, so you can use linear search of UTF-8 codepoints from the nearest endpoint and N ~= 3-10. The exception is finding the midpoint, which should be provided as an API function (bisect?) that takes the midpoint in bytes and then uses UTF-8's self-synchronizing property to find the nearest legal codepoint. indexOf uses Boyer-Moore on bytes, startsWith/endsWith/equals are also byte-wise (well, word-wise, you can significantly speed up string equality tests by comparing by word and then using duff's device on the remainder) with some special casing to handle immediate values above. Split() is basically repeated indexOf with a copy, join() allocates the full string length and then copies in the data. Regexps use a DFA on bytes.

I'm wondering if it's worth introducing a separate data structure (same API) that is analogous to a Slice in Go - a pointer and index into an existing buffer - but my experience is that these often result in subtle memory leaks in GC'd languages. You hold onto a reference to 3 characters in a 300K buffer, and suddenly your program needs to keep all 300K live. It definitely makes split and slice very fast, though.

Also, there should be a separate standard-library type for []bytes, and all I/O should operate on that, with explicit encoding/decoding operations. Encoding happens at program boundaries, all strings inside the language should be UTF-8. Would be cool to allow vectored I/O directly from ropes, too, it'd make for great templating engines & web frameworks.

TheLoneWolfling3• 12 years ago

You can just fall back to a "rope" consisting of a single node for small strings.

One of the things I really like about what I call "pseudo-immutable" ropes (ropes that are not truly immutable, but to all appearances are - when you take a slice it modifies the original rope to maximize structure-sharing.) is that you get immunity to those subtle memory leaks on slicing "for free".

I agree fully on length-prefixed strings. They are a lot better than null-terminated strings, in a bunch of ways. Regexes using DFAs though can be... problematic. You really want a NFA that's converted to a DFA on-the-fly, with caching, or else you can end up with exponential blowup when constructing the DFA (a[<some large character class>]{1000}a, for example.). A DFA-based regex also doesn't handle a number of things.

As for slicing, I had a thought on that matter. Make slices reference the main array weakly, and have (weak) backreferences to any slices made of an array. When an array comes up for GC, if it has any slices made of it, copy out the slices to new arrays. There are a bunch of heuristics that can be tuned here, of course (don't do weakref / backref at all on smaller arrays, don't copy out slices if it won't reduce memory usage, etc.), but it prevents the worst case at least.

The big advantage of slices is that it means that programmers don't need to sacrifice readability for efficiency. It's much easier to be able to pass in arr[7:10000] to a function than to either have to modify the function to take index parameters (which you can't always do) or have to do a temporary copy. It also prevents the O(n^2) behavior associated with doing simple tokenizing (the change to Java's substring behaviour, for example)

I disagree strongly with "Encoding happens at program boundaries". The (major) problem with that is that there becomes no good way to pass strings through the language without going through an encoding pass. Try to implement cat in Python 3, for example. Encoding should happen when you ask for it.

deathanatos4• 12 years ago

Honestly, I really couldn't care how a string is stored internally. It matters much more to me that it exposes, at a bare minimum, the ability to iterate over Unicode code points — something JavaScript and so many other languages do not do. From there I can perhaps build up to something actually useful (like a concept of a character).

roel_v2• 12 years ago

For what purposes would you use this?

jeltz2• 12 years ago

Most languages designed today use UTF-8 so in those you should be able to iterate over the code points.

TheLoneWolfling3• 12 years ago

Agreed.

Also, a related operation that would be useful is being able to do operations on "logical characters" - I believe the technical term is "grapheme clusters".

tolmasky• 12 years ago

Linear-time indexing: operations like charAt require character indexing to be fast. We discussed solving this by adding a special flag to indicate all characters in the string are ASCII, so that we can still use O(1) indexing in this case. This scheme will only work for ASCII strings, though, so it’s a potential performance risk. An alternative is to have such operations inflate the string from UTF8 to TwoByte, but that’s also not ideal.

Perhaps I'm missing something (quite likely, as I am certainly no expert when it comes to unicode), but I was under the impression that this would already have to be the case since UTF16 is also variable length.

sheetjs• 12 years ago

Technically, for characters whose codepoint exceeds 0xFFFF, javascript treats them as two characters. To see that, consider the Sushi character "🍣" (U+1f363):

    "🍣".length // 2
    "🍣".charCodeAt(0) // 55356
    "🍣".charCodeAt(1) // 57187

iopq2• 12 years ago

That's a bad interface that allows you to split strings at useless codepoints and get illegal UTF-16 strings as the result.

seszett2• 12 years ago

Funny how this Sushi character appears as nigiri or as maki depending on the font.

I can't say I'm really satisfied with the current state of emojis in Unicode.

lukasm3• 12 years ago

UTF-8, UTF-16 is variable length, UTF-32 is not. JS spec says you can use UCS-2 or UTF-16. I believe the author meant to say: If you have UTF-16, on average, your operations are faster, but use more memory. With UTF-8 you use less memory, but operations are slower in the web environment.

lukasm3• 12 years ago

anybody care to explain the downvotes?

ceronman3• 12 years ago

Note that you don't necessarily use less memory using UTF-8. It only saves memory for languages that can be represented in latin1. Non-western languages usually end up using more memory in UTF-8 than in UTF-16.

thristian• 12 years ago

UTF-16 is variable-length in that a Unicode code-point can take up one or two UTF-16 code-units. However, for backward-compatibility reasons "charAt()" is defined to return a UTF-16 code-unit (regardless of whether or not it's a useless half-a-code-point) so effectively it's O(1) indexing.

tracker1• 12 years ago

Why wouldn't UTF-8 offer the same O(1) indexing? I still think they should fix regex/charCodeAt etc to support the newer characters above 0xFFFF as demonstrated, it would see dramatic memory improvements and remove the need for hacks to detect surrogate pairs.

ch0wn• 12 years ago

Is this similar to the Flexible String Representation[0] in Python 3.3?

[0] http://legacy.python.org/dev/peps/pep-0393/

AnkhMorporkian• 12 years ago

Nearly the same, save for the fact that python also gives an option for UTF-32.

deathanatos4• 12 years ago

I wouldn't say it's an option: the string's internal representation might be UTF-32, but whether or not it is is transparent to you the coder. (Just as the JS change is transparent to the JS coder.)

However, the Python change wasn't entirely transparent: len() on a string now returns the length of the string in code points, whereas previously it returned the length in code units. Further, previously Python could be built with one of two internal string representations, so len(s) for a constant s could return different answers depending on your build. Now it doesn't, and len returning code points is much more useful.

userbinator• 12 years ago

For every JS string we allocate a small, fixed-size structure (JSString) on the gc-heap. Short strings can store their characters inline (see the Inline strings section below), longer strings contain a pointer to characters stored on the malloc-heap.

I wonder what the reason is for this roundabout way of doing it - couldn't the whole string be stored as a variable-length block (header with length, and then the content bytes), all on one heap? Incidentally this is also one of the things I think is broken about the malloc() interface; there is no portable way to get the size of an allocated block with only a pointer to it, despite that information being available somewhere - free() has to know, after all. Thus to do it the "correct, portable" way you have to end up essentially duplicating that length somewhere else. The fact that people are getting told that it's not something they need to know (e.g. http://stackoverflow.com/questions/5451104/how-to-get-memory... ) doesn't help either.

I've written a "nonportable" (in reality, all that would be needed is to change the function that gets the length from the block header) string implementation that uses this technique, and it definitely works well.

Some operations like eval currently inflate Latin1 to a temporary TwoByte buffer, because the parser still works on TwoByte strings and making it work on Latin1 would be a pretty big change.

I haven't looked at their code but if the parser expects the whole string to be available and accesses it randomly it would certainly be a big rewrite; otherwise, if it's more like a getchar(), it wouldn't be so hard to have a function expand each character from the source string as the parser consumes it.

The main goal was saving memory, but Latin1 strings also improved performance on several benchmarks.

With modern processors having multilevel cache hierarchies and increasing memory latencies, smaller almost always is faster - it's well worth spending a few extra cycles in the core to avoid the few hundred cycles (or more) of a cache miss.

quotemstr• 12 years ago

Remember that malloc is a least-common-denominator interface. It needs to work everywhere. In a lot of places, it could be hard to justify the complexity.

Anyway, on glibc systems, you can use malloc_usable_size. On Windows systems (Windows gets the heap very right), you can use the HeapSize function.

kevingadd• 12 years ago

SpiderMonkey uses one of the rather elaborate, carefully-tuned modern allocators (tcmalloc or jemalloc, I forget which) that's designed around clustering allocations into 'size categories', and carving allocations out of those categories. As a result, a given allocation will end up with overhead based on the size bucket it's put into, and certain buckets may perform better.

In this environment it's very useful for each type to be fixed-size (within reason) and be consistently sized. You'll end up with all your JSStrings allocated out of the same size bucket and other things get simpler and faster.

For example, with fixed-size JSStrings allocating out of a fixed-size allocation bucket, perhaps thread-local, you can allocate a string by atomically incrementing a pointer. Speedy!

pcwalton2• 12 years ago

In general Firefox uses jemalloc, so shipping builds of SpiderMonkey do as well. However, individual JavaScript objects are allocated using a custom SpiderMonkey-specific allocator that uses fixed-size bins, knows about garbage collection information, and (as of this year) supports multiple generations. No production-quality JavaScript engine uses the C malloc interface for individual JS objects; you'd get killed in the benchmarks if you tried.

gsg• 12 years ago

The size of the allocated block is often not the same as the size passed to malloc, so the "duplicated" length is usually actually necessary.

codewiz• 12 years ago

Lazily converting UTF-8 (or latin1) to UTF-16 as needed is indeed an old trick employed by many string classes.

It's even a bit surprising that a codebase as popular and performance-critical as SpiderMonkey hadn't picked up such as a simple and high-yield optimization several years ago.

By the way, other implementations are even lazier: the string is kept in its original encoding (utf-8 or 7-bit ascii) until someone calls a method requiring indexed access to characters, such as the subscript operator. At this point, you convert to UTF-16 to for O(1) random access.

Indexing characters in a localized string is rarely useful to applications and often denotes a bug (did they want the N-th grapheme, glyph or code-point?). It's best to use higher-level primitives for collating, concatenating and splitting localized text.

Granted, a JavaScript interpreter must remain bug-by-bug compatible with existing code, thus precluding some of the most aggressive optimizations.

nitrogen• 12 years ago

What do the lazily converting string classes do for characters that don't fit in UTF-16? Would they convert to UTF-32, or just fall back to an O(n) index?

Example: ☃

hdevalence• 12 years ago

There are, by definition, no Unicode characters that don't fit in UTF-16.

UTF-16 has surrogate pairs; it's an extension of UCS-2, which doesn't.

Incidentally, this is why UTF-16 is a poor choice for a character encoding: you take twice the memory but you don't actually get O(1) indexing, you only think you do, and then your program breaks badly when someone inputs a surrogate pair.

See also elsewhere in the thread: https://news.ycombinator.com/item?id=8066284

ceronman3• 12 years ago

String classes rarely use UTF-16 because it doesn't have fixed length code point representation. UCS-2 is often used instead, which uses two bytes to represent all the unicode points in the Basic Multilingual Plane (BMP), which is enough for 99.99% of the use cases.

One example of this is Python, which used UCS-2 until version 3.3. There was a compile time option to use UCS-4, but UCS-2 was enough for most cases because the BMP contains all the characters of all the languages currently in use.

hexleo• 12 years ago

Why not compared with other browser like chrome etc?

nnethercote• 12 years ago

In Firefox you can easily answer questions like "how much memory are strings taking up on this page", thanks to the fine-grained measurements available in about:memory.

I don't know of a way to get these measurements in other browsers. Chrome's about:memory page contains much coarser measurements, for example.

szatkus• 12 years ago

Chrome has the memory profiler for that.

greggman2• 12 years ago

I know this will probably get downvoted into oblivious but is string space really an issue in the browser?

For example, this page at the time of this post has 68k of html so 68k of text. Let's assume it's all ASCII but we store it at 32bits per character so it's 4x in memory or 270k. Checking Chrome's task manager this page is using 42meg of ram. Do I really care about 68k vs 270k when something else is using 42meg of ram for this page? Firefox is also at a similar level.

Why optimize this? It seems like wrong thing to optimize? Especially for the complexity added to the code.

jtc331• 12 years ago

I'd guess that it's actually quite an issue for JS heavy pages. This would probably benefit anyone doing signification in-browser apps in JS.

greggman2• 12 years ago

Hmmm, checking for example Gmail which is arguably a heavy page it's got 4meg of requests for various js + html files. So 16meg if expanded to 32bits per code point. But it's using 160meg of ram. Strings are not where all the space is going it would seem.

jeltz2• 12 years ago

Strings using less memory will also speed up string operations as you can see from their 36% win in the regexp-dna benchmark.

richdougherty• 12 years ago

Browsers and JS VMs are so widely deployed now that anything that can be done to make them faster or use less memory has a tremendous effect in the aggregate. What's really cool is that you can update a browser and suddenly the web starts working better for everyone who uses the browser.

Browser memory usage does tend to creep up unless there is active work to keep it under control. So I think it is important to try and trim the fat where possible. Just look at Are we slim yet? to see Firefox's memory usage slowly growing over time.

https://areweslimyet.com/

By the way, JS engine optimisation does seem like it is getting more and more complicated. I suppose most of the easy optimisations have already been done. Look at Safari adding a fourth layer to its JIT!

https://www.webkit.org/blog/3362/introducing-the-webkit-ftl-...

It's kind of crazy, but totally worth it! (IMO)

The string slimming work in IonMonkey sounds like it got some memory improvements without too much more complexity. Remember the string logic is already complicated—around 6 different string types. The kinds of pages where I think you'd see a real memory improvements would be in JS-heavy pages which store lots of data in memory. These types of pages are becoming more and more common.

I imagine it would also be a big improvement for any software running on Firefox OS. It would be especially noticeable because Firefox OS is targeted at low cost mobile devices.

Slimmer and faster JavaScript strings in Firefox

Related Stories