{"id":3191,"date":"2018-10-12T09:57:24","date_gmt":"2018-10-11T22:57:24","guid":{"rendered":"http:\/\/blog.mozilla.org\/nnethercote\/?p=3191"},"modified":"2018-10-12T09:57:24","modified_gmt":"2018-10-11T22:57:24","slug":"slimmer-and-simpler-static-atoms","status":"publish","type":"post","link":"https:\/\/blog.mozilla.org\/nnethercote\/2018\/10\/12\/slimmer-and-simpler-static-atoms\/","title":{"rendered":"Slimmer and simpler static atoms"},"content":{"rendered":"<p><a href=\"https:\/\/en.wikipedia.org\/wiki\/String_interning\">String interning<\/a> is:<\/p>\n<blockquote><p>a method of storing only one copy of each distinct <a title=\"String (computer science)\" href=\"https:\/\/en.wikipedia.org\/wiki\/String_(computer_science)\">string<\/a> value, which must be <a title=\"Immutable object\" href=\"https:\/\/en.wikipedia.org\/wiki\/Immutable_object\">immutable<\/a>. Interning strings makes some string processing tasks more time- or space-efficient at the cost of requiring more time when the string is created or interned. The distinct values are stored in a <b>string intern pool<\/b>. The single copy of each string is called its <strong>intern<\/strong>.<\/p><\/blockquote>\n<p>In Firefox&#8217;s code we use the term <em>atom<\/em> rather than <em>intern<\/em>, and\u00a0<em>atom table<\/em> rather than\u00a0<em>string intern pool<\/em>. I don&#8217;t know why; those names have been used for a long time.<\/p>\n<p>Furthermore, Firefox distinguishes between <em>static atoms<\/em>, which are those that are chosen at compile time and can be directly referred to via an identifier, and <em>dynamic atoms<\/em>, which are added on-demand at runtime. This post is about the former.<\/p>\n<p>In 2016, Firefox&#8217;s implementation of static atoms was complex and inefficient. I filed <a href=\"https:\/\/bugzilla.mozilla.org\/show_bug.cgi?id=1257126\">a bug<\/a>\u00a0about this that included the following ASCII diagram showing all the data structures involved for a single atom for the string &#8220;foobar&#8221;.<\/p>\n<pre>static nsFakeStringBuffer&lt;N=7&gt; foobar_buffer (.data, 8+2N bytes)\r\n\/-----------------------------------------\\ &lt;------+\r\n| int32_t mRefCnt = 1 \/\/ never reaches 0  |        | \r\n| uint32_t mSize = 14 \/\/ 7 x 16-bit chars |        | \r\n| u\"foobar\"           \/\/ the actual chars | &lt;----+ | \r\n\\-----------------------------------------\/      | | \r\n                                                 | | \r\nPermanentAtomImpl (heap, 32 bytes)               | | \r\n\/----------------------------------------------\\ | | &lt;-+\r\n| void* vtablePtr    \/\/ implicit               | | |   | \r\n| uint32_t mLength = 6                         | | |   | \r\n| uint32_t mHash = ...                         | | |   | \r\n| char16_t* mString = @------------------------|-+ |   | \r\n| uintptr_t mRefCnt  \/\/ from NS_DECL_ISUPPORTS |   |   | \r\n\\----------------------------------------------\/   |   | \r\n                                                   |   | \r\nstatic nsIAtom* foobar (.bss, 8 bytes)             |   | \r\n\/---\\ &lt;-----------------------------------+        |   | \r\n| @-|-------------------------------------|------------+\r\n\\---\/                                     |        |   | \r\n                                          |        |   | \r\nstatic nsStaticAtom (.d.r.ro.l, 16 bytes) |        |   | \r\n(this element is part of a larger array)  |        |   | \r\n\/------------------------------------\\    |        |   | \r\n| nsStringBuffer* mStringBuffer = O--|----|--------+   | \r\n| nsIAtom** mAtom = @----------------|----+            | \r\n\\------------------------------------\/                 | \r\n                                                       | \r\nAtomTableEntry (heap, ~2 x 16 bytes[*])                | \r\n(this entry is part of gAtomTable)                     | \r\n\/-------------------------\\                            | \r\n| uint32_t mKeyHash = ... |                            | \r\n| AtomImpl* mAtom = @-----|----------------------------+\r\n\\-------------------------\/                            | \r\n                                                       | \r\nStaticAtomEntry (heap, ~2 x 16 bytes[*])               | \r\n(this entry is part of gStaticAtomTable)               | \r\n\/-------------------------\\                            | \r\n| uint32_t mKeyHash = ... |                            | \r\n| nsIAtom* mAtom = @------|----------------------------+\r\n\\-------------------------\/\r\n\r\n[*] Each hash table is half full on average, so each entry takes up\r\napproximately twice its actual size.\r\n<\/pre>\n<p>There is a lot going on in that diagram, but putting that all together gave the following overhead per atom.<\/p>\n<ul>\n<li>Static shared: 0 bytes<\/li>\n<li>Static unshared: 8 + 2(length+1) + 8 + 16<\/li>\n<li>Dynamic: 32 + ~32 + ~32 bytes<\/li>\n<li>Total bytes: (2(length+1) + 64 + ~64) * num_processes<\/li>\n<\/ul>\n<p>(Although these atoms are &#8220;static&#8221; in the sense of being known at compile-time, a lot of the associated data was allocated dynamically.)<\/p>\n<p>At the time there were about 2,700 static atoms, and avg_length was about 11, so the overhead was roughly:<\/p>\n<ul>\n<li>0 bytes fixed, and<\/li>\n<li>\u00a0410,400 bytes per process. (Or more, depending on how the relocations required for the static pointers were represented, which depended on the platform.)<\/li>\n<\/ul>\n<p>Today, things have improved greatly and now look like the following.<\/p>\n<pre>const char16_t[7] (.rodata, 2(N+1) bytes)\r\n(this is detail::gGkAtoms.foobar_string)\r\n\/-----------------------------------------\\ &lt;--+\r\n| u\"foobar\"           \/\/ the actual chars |    | \r\n\\-----------------------------------------\/    | \r\n                                               | \r\nconst nsStaticAtom (.rodata, 12 bytes)         | \r\n(this is within detail::gGkAtoms.mAtoms[])     | \r\n\/-------------------------------------\\ &lt;---+  | \r\n| uint32_t mLength:30 = 6             |     |  | \r\n| uint32_t mKind:2 = AtomKind::Static |     |  | \r\n| uint32_t mHash = ...                |     |  | \r\n| uint32_t mStringOffset = @----------|-----|--+\r\n\\-------------------------------------\/     | \r\n                                            | \r\nconstexpr nsStaticAtom* (0 bytes) @---------+\r\n(this is nsGkAtoms::foobar)                 | \r\n                                            | \r\nAtomTableEntry (heap, ~2 x 16 bytes[*])     | \r\n(this entry is part of gAtomTable)          | \r\n\/-------------------------\\                 | \r\n| uint32_t mKeyHash = ... |                 | \r\n| nsAtom* mAtom = @-------|-----------------+\r\n\\-------------------------\/\r\n\r\n[*] Each hash table is half full on average, so each entry takes up\r\napproximately twice its actual size.\r\n\r\n<\/pre>\n<p>That gives the following overhead per atom.<\/p>\n<ul>\n<li>Static shared: 12 + 2(length+1) bytes<\/li>\n<li>Static unshared: 0 bytes<\/li>\n<li>Dynamic: ~32 bytes<\/li>\n<li>Total: 12 + 2(length+1) + ~32 * num_processes<\/li>\n<\/ul>\n<p>We now have about 2,300 static atoms and avg_length is still around 11, so the overhead is roughly:<\/p>\n<ul>\n<li>82,800 bytes fixed, and<\/li>\n<li>73,600 bytes per process.<\/li>\n<\/ul>\n<p>I won&#8217;t explain all the parts of the two diagrams, but it can be seen that we&#8217;ve gone from six pieces per static atom to four; the size and complexity of the remaining pieces are greatly reduced; there are no static pointers (only <code>constexpr<\/code> pointers and integral offsets) and thus no relocations; and there is a lot more interprocess sharing thanks to more use of <code>const<\/code>. Also, there is no need for a separate static atom table any more, because the main atom table is thread-safe and the HTML5 parser (the primary user of the separate static atom table) now has a small but highly effective static atoms cache.<\/p>\n<p>Things that aren&#8217;t visible from the diagrams: atoms are no longer exposed to JavaScript code via XPIDL, there are no longer any virtual methods involved, and all atoms are defined in a single place (with no duplicates) instead of 7 or 8 different places. Notably, the last few steps were blocked for some time by a <a href=\"https:\/\/developercommunity.visualstudio.com\/content\/problem\/223146\/constexpr-code-gneration-bug.html\">bug in MSVC<\/a> involving the handling of <code>constexpr<\/code>.<\/p>\n<p>The <a href=\"https:\/\/bugzilla.mozilla.org\/showdependencytree.cgi?id=1257126&amp;hide_resolved=0\">bug dependency tree<\/a>\u00a0gives a good indication of how many separate steps were involved in this work. If there is any lesson to be had here, it&#8217;s that small improvements add up over time.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>String interning is: a method of storing only one copy of each distinct string value, which must be immutable. Interning strings makes some string processing tasks more time- or space-efficient at the cost of requiring more time when the string is created or interned. The distinct values are stored in a string intern pool. The [&hellip;]<\/p>\n","protected":false},"author":139,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[30,4544,4546,617],"tags":[],"_links":{"self":[{"href":"https:\/\/blog.mozilla.org\/nnethercote\/wp-json\/wp\/v2\/posts\/3191"}],"collection":[{"href":"https:\/\/blog.mozilla.org\/nnethercote\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blog.mozilla.org\/nnethercote\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blog.mozilla.org\/nnethercote\/wp-json\/wp\/v2\/users\/139"}],"replies":[{"embeddable":true,"href":"https:\/\/blog.mozilla.org\/nnethercote\/wp-json\/wp\/v2\/comments?post=3191"}],"version-history":[{"count":0,"href":"https:\/\/blog.mozilla.org\/nnethercote\/wp-json\/wp\/v2\/posts\/3191\/revisions"}],"wp:attachment":[{"href":"https:\/\/blog.mozilla.org\/nnethercote\/wp-json\/wp\/v2\/media?parent=3191"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blog.mozilla.org\/nnethercote\/wp-json\/wp\/v2\/categories?post=3191"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blog.mozilla.org\/nnethercote\/wp-json\/wp\/v2\/tags?post=3191"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}