9 ms·

Slimmer and faster JavaScript strings in Firefox

• thomersch_ 12y ago
  Latin1? I hoped it would die some day.
  • kannanvijayan 12y 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.
    • angersock 12y ago
      ES6.1 wishlist: UTF8 strings, full stop.
      • Ygg2 12y ago
        Be careful what you wish for. Unicode strings are fucking complex. UTF8 double so. For example which of the four Unicode character normalization interests you most? Or you need grapheme clusters? Or you need code points? Or byte values?
        • angersock 12y ago
          I don't want UTF32, UCS-2, UTF16, or endian issues--that much I know for sure. :)
        • kzrdude 12y ago
          Those are general Unicode issues, not UTF-8 issues.
        • iopq 12y ago
          You already have UTF16 which is both complex and inefficient (because of two byte representations of Latin characters)
      • pjscott 12y ago
        I want Unicode strings that support 1. Opaque cursors pointing somewhere in the conceptual sequence of code points, with constant-time dereferencing, 2. Ranges, defined by starting and ending cursors, and 3. The ability to move cursors forward or backward by either code points or composed grapheme clusters. This would be a saner interface than any other I've seen, and it puts very few constraints on the underlying encoding.
        • jahewson 12y ago
          1, 2. Grapheme clusters are not normative in Unicode, they can be tailored for specific languages. There's a default cluster finding algorithm but it's not suitable in all cases. There's no "one size fits all" approach. 3. Forward and backward are likewise language and tailoring dependent because they depend on graphemes. There may also be application-specific tailoring such as the handling of combining marks, in some scripts "forward" and "backward" are not clearly defined.
        • angersock 12y ago
          That's great stuff...that should be done after standardizing on UTF8.
• TheLoneWolfling 12y 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 12y 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.
• tolmasky 12y 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 12y 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
    • iopq 12y ago
      That's a bad interface that allows you to split strings at useless codepoints and get illegal UTF-16 strings as the result.
      • pcwalton 12y ago
        It's needed for compatibility with the Web, unfortunately.
      • TazeTSchnitzel 12y ago
        I think JS may be from the time when UCS-2 was all there was and there were only 65535 Unicode characters.
      • dbaupp 12y ago
        It's the historical interface which websites now rely on, changing it would be like writing a libc with strcmp operating on Pascal strings. In any case, a Javascript String is not actually designed to be UTF-16, it is essentially just an `uint16_t[]`. Even textual strings just store UTF-16 code units, not full UTF-16 data. Relevant snippets from the standard: The String type is the set of all finite ordered sequences of zero or more 16-bit unsigned integer values ("elements"). When a String contains actual textual data, each element is considered to be a single UTF-16 code unit. [...] All operations on Strings (except as otherwise stated) treat them as sequences of undifferentiated 16-bit unsigned integers; they do not ensure the resulting String is in normalised form, nor do they ensure language-sensitive results. See also: - Section 8.4 http://www.ecma-international.org/publications/files/ECMA-ST/Ecma-262.pdf http://www.ecma-international.org/publications/files/ECMA-ST... - http://mathiasbynens.be/notes/javascript-encoding http://mathiasbynens.be/notes/javascript-encoding
• ch0wn 12y ago
  Is this similar to the Flexible String Representation[0] in Python 3.3? [0] http://legacy.python.org/dev/peps/pep-0393/ http://legacy.python.org/dev/peps/pep-0393/
  • AnkhMorporkian 12y ago
    Nearly the same, save for the fact that python also gives an option for UTF-32.
    • deathanatos 12y 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.
• deleted 12y ago
  [deleted]
• userbinator 12y 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-block-length-after-malloc 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 12y 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 12y ago
• codewiz 12y 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 12y 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 12y 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 https://news.ycombinator.com/item?id=8066284
    • ceronman 12y 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 12y ago
  Why not compared with other browser like chrome etc?
  • nnethercote 12y 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 12y ago
      Chrome has the memory profiler for that.
      • rockdoe 12y ago
        Does that even work for memory usage by native code?
• greggman 12y 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.
  • jeltz 12y ago
    Strings using less memory will also speed up string operations as you can see from their 36% win in the regexp-dna benchmark.
  • jtc331 12y 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.
    • greggman 12y 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.
      • dbaupp 12y ago
        The raw source code is not the only strings in an application. Gmail especially will be heavily manipulating the DOM and a variety of other things (JS properties, JSON requests) which use Strings internally.
      • bzbarsky 12y ago
        If you actually read the linked article, it has measurements for how much RAM strings use in Gmail. For the particular case of the article's author, it was about 11MB of strings before the changes he made; it was about 6-7MB of strings afterward. Your mileage will vary depending on what actual mails you have, of course. Note also that comparing this to the Chrome numbers for overall Gmail memory usage is comparing apples and oranges: Firefox tends to use less memory than Chrome. You'd want to look at about:memory in Firefox to see how much memory that gmail page is likely using.