{"id":3906,"date":"2023-05-12T09:14:52","date_gmt":"2023-05-12T17:14:52","guid":{"rendered":"https:\/\/devblogs.microsoft.com\/typescript\/?p=3906"},"modified":"2023-05-12T09:14:52","modified_gmt":"2023-05-12T17:14:52","slug":"introducing-deopt-explorer","status":"publish","type":"post","link":"https:\/\/devblogs.microsoft.com\/typescript\/introducing-deopt-explorer\/","title":{"rendered":"Introducing Deopt Explorer"},"content":{"rendered":"<p>Over the past few months, during the lead-up to the TypeScript 5.0 beta, our team spent a good portion of our time\nlooking for ways to improve the performance of our compiler so that your projects build faster. One of the ways we\nimproved was by looking into an oft overlooked aspect of many JavaScript VMs: <em>inline caching<\/em>.<\/p>\n<h2>A Brief Primer on Inline Caching<\/h2>\n<p><a href=\"https:\/\/en.wikipedia.org\/wiki\/Inline_caching\">Inline caching<\/a> is an optimization often used in both statically typed\nand dynamically typed languages. An inline cache, or <strong>IC<\/strong>, is a set of instructions whose goal is to speed up\noperations like method calls and property lookups. It does this by taking a slow operation, like walking an object&#8217;s\nprototype chain and scanning through its named properties, and caches a fast path for subsequent lookups of that\nproperty on the same object type. If you&#8217;re curious about the inner workings of ICs,\n<em><a href=\"https:\/\/mrale.ph\/blog\/2012\/06\/03\/explaining-js-vms-in-js-inline-caches.html\">Explaining JavaScript VMs in JavaScript &#8211; Inline Caches<\/a><\/em> by <a href=\"https:\/\/mrale.ph\">Vyacheslav Egorov<\/a> goes into far\nmore depth on ICs in JavaScript than I will here. Egorov, a Senior Staff Software Engineer at Google, currently works\non the Dart programming language and previously worked on the V8 JavaScript engine.<\/p>\n<p>ICs significantly improve the performance of property lookups when the VM always sees a single type of object. However,\nIC performance degrades as an operation becomes more <em>polymorphic<\/em>. As the VM encounters more types of objects for that\noperation, it triggers deoptimizations, switching to less efficient IC implementations. Today in V8, an inline cache\nessentially comes in three flavors:<\/p>\n<ul>\n<li><em>Monomorphic<\/em> \u2014 The VM only ever observed a single type of object.<\/li>\n<li><em>Polymorphic<\/em> \u2014 The VM observed between two and four types of objects.<\/li>\n<li><em>Megamorphic<\/em> \u2014 The VM observed more than four types of objects.<\/li>\n<\/ul>\n<p>Monomorphic ICs are the fastest, as they only need to compare the type identity of the current value to the one\npreviously recorded in the cache. Polymorphic ICs are somewhat slower, as they must match the type identity of the value\nagainst a small number of potential targets. Megamorphic ICs are the slowest as the cache is moved to the heap, is a\nfixed size, and its contents can be easily overwritten. These are fairly gross approximations of actual IC behavior, so\nif you would like more detail on the subject I would encourage you to read <em><a href=\"https:\/\/mrale.ph\/blog\/2015\/01\/11\/whats-up-with-monomorphism.html\">What&#8217;s up with monomorphism?<\/a><\/em>, also by\nEgorov.<\/p>\n<h2>The Slow Creep of Megamorphism<\/h2>\n<p>Many operations in the TypeScript compiler are megamorphic by nature. We have hundreds of different syntax tree nodes\nthat represent the various syntactic productions in the TypeScript and JavaScript languages, and often need to branch\nbased on node kind. In general, we might expect that once we&#8217;re in a branch for a specific kind of node, the ICs that\nthe JavaScript VM creates should be monomorphic. However, that is not always the case.<\/p>\n<p>Unfortunately, JavaScript polymorphism can be insidious. Two objects produced by the same constructor can still be\nconsidered different &#8220;types&#8221; if those properties were initialized in a different order, or if some properties are only\ninitialized conditionally. Unfortunately, this was the case with many data structures in the TypeScript compiler. We\noften had conditional assignments, such as assigning the <code>symbol<\/code> of a node only during binding, and assignments\noccurring in varying orders based on which functions might be called first for a given node. This ends up leading to a\nlot of unintentional polymorphism.<\/p>\n<h2>Example: Property Order Polymorphism<\/h2>\n<p>In the following example, the order in which properties are initially assigned in the object returned by <code>f()<\/code>\nis different based on which branch of the <code>if<\/code> is evaluated. In <code>g()<\/code>, the <code>p.x<\/code> property access will become\npolymorphic because it observes two different shapes: <code>{ x, y }<\/code> and <code>{ y, x }<\/code>:<\/p>\n<pre class=\"lang:default decode:true\" style=\"background-color: #f0f0f0; padding: 10px; border-radius: 10px;\"><code>function f(x, y) {\r\n  if (x &lt;= y) {\r\n    return { x, y };\r\n  }\r\n  else {\r\n    return { y, x };\r\n  }\r\n}\r\n\r\nfunction g(p) {\r\n  const x = p.x; \/\/ polymorphic\r\n}\r\n\r\ng(f(0, 1));\r\ng(f(1, 0));\r\n<\/code><\/pre>\n<h2>Example: Conditional Property Polymorphism<\/h2>\n<p>In this example, the property <code>p.y<\/code> is only defined conditionally in <code>f()<\/code>. As a result, the <code>p.x<\/code> property access in\n<code>g()<\/code> will become polymorphic because it observes two different shapes: <code>{ x }<\/code> and <code>{ x, y }<\/code>.<\/p>\n<pre class=\"lang:default decode:true\" style=\"background-color: #f0f0f0; padding: 10px; border-radius: 10px;\"><code>function f(x, y) {\r\n  const p = {};\r\n  p.x = x;\r\n  if (y !== undefined) {\r\n    p.y = y;\r\n  }\r\n  return p;\r\n}\r\n\r\nfunction g(p) {\r\n  const x = p.x; \/\/ polymorphic\r\n}\r\n\r\ng(f(1));\r\ng(f(1, 0));\r\n<\/code><\/pre>\n<h2>Recognizing Megamorphism<\/h2>\n<p>It can be fairly difficult to recognize megamorphism in a large JavaScript code base, and even more difficult to\ndetermine whether that megamorphism is negatively impacting performance. Overoptimizing infrequently used code paths\nwastes time and resources, so we needed tooling to help us analyze poorly performing code to find actual, tangible\nimprovements that we could make. We built benchmarking tools to monitor compiler performance over time. We used CPU\nprofiling and heap snapshots to investigate performance regressions. But these tools often didn&#8217;t give us the details\nwe needed for fine tuning. So, for the past few years we&#8217;ve been working on a tool called <em>Deopt Explorer<\/em> that we&#8217;ve\nused internally to help us explore the various deoptimizations, ICs, and object types that V8 produces when the compiler\nis executing.<\/p>\n<h2>Introducing Deopt Explorer<\/h2>\n<p><img decoding=\"async\" title=\"Overview\" src=\"https:\/\/devblogs.microsoft.com\/typescript\/wp-content\/uploads\/sites\/11\/2023\/05\/deopt-explorer-overview.png\" alt=\"VS Code open with the Deopt Explorer extension visible in the activity bar\" \/><\/p>\n<p><a href=\"https:\/\/github.com\/microsoft\/deoptexplorer-vscode\">Deopt Explorer<\/a> is a VS Code extension that can analyze trace logs\nproduced by V8. It was heavily influenced by tools like Vyacheslav Egorov&#8217;s <a href=\"https:\/\/mrale.ph\/irhydra\/2\/\">IR Hydra<\/a>, and\nThorsten Lorenz&#8217;s <a href=\"https:\/\/github.com\/thlorenz\/deoptigate\">Deoptigate<\/a>, and provides a detailed look at deoptimizations\nand ICs right from within the editor.<\/p>\n<p>To explain how Deopt Explorer works, I will walk through how we <a href=\"https:\/\/github.com\/microsoft\/TypeScript\/pull\/51880\">used it recently<\/a>\nto improve compiler performance by making property accesses against TypeScript&#8217;s internal <code>Symbol<\/code> type monomorpic.<\/p>\n<h2>Generating a Log<\/h2>\n<p>To get started, we need to produce a V8 trace log that we can analyze. There are a number of V8-specific options that\ncontrol trace log output that are exposed by NodeJS. These options are known to change from release to release, so we\npublished a commandline utility called <a href=\"https:\/\/npmjs.com\/package\/dexnode\"><code>dexnode<\/code><\/a> to make it easier to provide the\ncorrect logging options based on the version of V8 embedded in the running version of NodeJS. <code>dexnode<\/code> can be invoked\nfrom the commandline in place of the normal <code>node<\/code> executable, and we can use that to invoke the TypeScript compiler\nagainst one of our test cases:<\/p>\n<pre class=\"lang:default decode:true\" style=\"background-color: #f0f0f0; padding: 10px; border-radius: 10px;\"><code>npx dexnode --out v8.log .\\built\\local\\tsc.js -p .\\path\\to\\project\r\n<\/code><\/pre>\n<p>Which is the equivalent of the following:<\/p>\n<pre class=\"lang:default decode:true\" style=\"background-color: #f0f0f0; padding: 10px; border-radius: 10px;\"><code>node --log-deopt --redirect-code-traces --redirect-code-traces-to=\\\\.\\NUL\r\n  --log-ic --log-maps --log-maps-details --log-code --log-source-code --prof\r\n  --log-internal-timer-events --detailed-line-info --logfile=v8.log\r\n  --no-logfile-per-isolate .\\built\\local\\tsc.js -p .\\path\\to\\project\r\n<\/code><\/pre>\n<p>This generates a file called <code>v8.log<\/code> that we can feed into Deopt Explorer.<\/p>\n<h2>Investigating ICs<\/h2>\n<p>After the log has been processed, we can expand the <code>ICS<\/code> tree view to get an idea of how polymorphic the code is in\n<em>binder.ts<\/em>:<\/p>\n<p><img decoding=\"async\" title=\"Megamorphic ICs in binder.ts\" src=\"https:\/\/devblogs.microsoft.com\/typescript\/wp-content\/uploads\/sites\/11\/2023\/05\/deopt-explorer-megamorphic-ics-in-binder.png\" alt=\"Close up of the ICs tree view. The &quot;Megamorphic&quot; node is expanded, showing a list of files. In that list, the &quot;binder.ts&quot; node is expanded, showing a list of functions, which in turn contain a list of individual ICs\" \/><\/p>\n<p>Given that there are quite a few megamorphic ICs, we&#8217;ll start by clicking on <code>addDeclarationToSymbol<\/code> to jump to that\nfunction. This function is called by TypeScript&#8217;s binder for every variable, function, class, method, parameter,\nproperty, etc., so it is invoked quite frequently. With the file open in the editor, Deopt Explorer will highlight ICs\nand other deoptimizations using editor decorations, allowing us to easily pick out those that are megamorphic:<\/p>\n<p><img decoding=\"async\" title=\"'addDeclarationToSymbol' decorations\" src=\"https:\/\/devblogs.microsoft.com\/typescript\/wp-content\/uploads\/sites\/11\/2023\/05\/deopt-explorer-addDeclarationToSymbol-decorations.png\" alt=\"Close up of an editor pane open to the &quot;addDeclarationToSymbol&quot; function. Several sections of code have additional highlights\" \/><\/p>\n<p>Here, megamorphic ICs are highlighted in red, while polymorphic ICs are highlighted in yellow. Immediately we can see\nthere are megamorphic ICs for <code>symbol.flags<\/code>, <code>node.symbol<\/code>, <code>symbol.declarations<\/code>, and <code>symbol.constEnumOnlyModule<\/code>,\nmeaning that each IC has observed multiple different maps for our <code>Symbol<\/code> and <code>Node<\/code> objects. Hovering over\n<code>symbol.flags<\/code> gives us more context:<\/p>\n<p><img decoding=\"async\" title=\"Megamorphic read and write to 'symbol.flags'\" src=\"https:\/\/devblogs.microsoft.com\/typescript\/wp-content\/uploads\/sites\/11\/2023\/05\/deopt-explorer-symbol.flags-megamorphic-read-and-write.png\" alt=\"Close up of a Hover tooltip with the message &quot;Megamorphic read from property 'flags', followed by a table containing the old and new IC state, address of each map, and the names of the functions that produced each map\" \/><\/p>\n<p>We can see that there were two different ICs associated with this statement, given that it is a compound assignment.\nFor a given IC, each line in the hover represents an IC event, and includes the current state of the IC (i.e., monomorphic,\npolymorphic, megamorphic), the &#8220;map&#8221; associated with the event, and the source location where that &#8220;map&#8221; was defined. In\nV8, a &#8220;map&#8221; (not to be confused with the JavaScript built-in <code>Map<\/code>) represents the type of an object, including its\nproperties, prototype, the constructor that produced it, and other related metadata.<\/p>\n<p>TypeScript only has one kind of <code>Symbol<\/code>, so lets look at the V8 maps associated with the <code>Symbol<\/code> constructor to find\nout where things went wrong.<\/p>\n<h2>Exploring V8 Maps<\/h2>\n<p>Expanding the <code>MAPS<\/code> tree view in Deopt Explorer shows the maps produced by V8, grouped by the constructor that produced\nthem:<\/p>\n<p><img decoding=\"async\" title=\"V8 maps for 'Symbol'\" src=\"https:\/\/devblogs.microsoft.com\/typescript\/wp-content\/uploads\/sites\/11\/2023\/05\/deopt-explorer-symbol-maps.png\" alt=\"Close up of the 'Maps' tree view, consisting of a list of constructor names, with the &quot;Symbol&quot; constructor expanded to show a long list of map addresses\" \/><\/p>\n<p>Expanding the constructor shows a list of each related map&#8217;s addresses, as well as a hint to the name of the function\nthat introduced the property that produced the map.<\/p>\n<p>V8 produces more than 30 different maps for <code>Symbol<\/code>, although Deopt Explorer will filter out a number of\ninconsequential maps by default. The ones we see here are directly referenced by ICs, and, as we can see from the list,\ncome from far more places than the <code>Symbol<\/code> constructor itself. Clicking on the third map down (<code>0x03ef521c8c49_1<\/code>),\nopens an editor showing the structure of the map:<\/p>\n<p><img decoding=\"async\" title=\"V8 maps for 'Symbol'\" src=\"https:\/\/devblogs.microsoft.com\/typescript\/wp-content\/uploads\/sites\/11\/2023\/05\/deopt-explorer-symbol-map-1.png\" alt=\"Close up of an editor pane showing a conceptual syntax for a map\" \/><\/p>\n<p>This view shows a number of useful pieces of information:<\/p>\n<ul>\n<li>The address of the map (<code>0x03ef521c8c49<\/code>).<\/li>\n<li>A counter (<code>_1<\/code>) that is used to differentiate between two or more maps that existed at that address at\ndifferent points in time, such as when a map is garbage collected and that memory is reused for a different map\nat a later time.<\/li>\n<li>The constructor that produced the map (<code>Symbol<\/code>).<\/li>\n<li>An optional base map, from which this map was produced when a new property was added (or some other change occurred).<\/li>\n<li>A list of properties and their associated runtime types, such as <code>smi<\/code> which is a V8 &#8220;small integer&#8221;, or <code>heap<\/code> which\nindicates a heap reference. This may also point to another V8 map.<\/li>\n<\/ul>\n<p>The data structure is followed by a commented section containing a timeline showing how the map has evolved, as well as\na section containing extra metadata provided by V8.<\/p>\n<p>From within this view, you can <kbd>Ctrl<\/kbd>&#8211; or <kbd>Cmd<\/kbd>-click on various links to jump to related source code locations, use &#8220;Go to\nDefinition&#8221; to jump to another map, or &#8220;Find all references&#8221; on map identifiers to see their associated ICs.<\/p>\n<p>We can also see that <em>checker.ts<\/em> added a new property called <code>checkFlags<\/code> that wasn&#8217;t initialized in the constructor.\nThis means that symbols produced by the checker, which we call <em>transient symbols<\/em>, will have a different V8 map than\nthose produced by the binder. But that isn&#8217;t the only case.<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/devblogs.microsoft.com\/typescript\/wp-content\/uploads\/sites\/11\/2023\/05\/deopt-explorer-symbol-map-2.png\" alt=\"V8 map for a produced by #1\" \/><\/p>\n<p><img decoding=\"async\" src=\"https:\/\/devblogs.microsoft.com\/typescript\/wp-content\/uploads\/sites\/11\/2023\/05\/deopt-explorer-symbol-map-3.png\" alt=\"V8 map for a produced by #2\" \/><\/p>\n<p>Clicking on the first two <code>addDeclarationToSymbol<\/code> maps in the tree view shows us two different maps produced by the\nsame function: one that adds an <code>exports<\/code> property and one that adds a <code>members<\/code> property. This indicates that there\nmultiple conditional property assignments, which in turn leads to more maps.<\/p>\n<h2>Reducing Megamorphism<\/h2>\n<p>To make property accesses on <code>Symbol<\/code> monomorphic, we need to avoid these conditional assignments. This means ensuring\nthat the V8 map for an object is stable, and all properties are initialized to <em>something<\/em>. For properties we intend to\nfill in later, this meant using <em>undefined<\/em>.<\/p>\n<pre class=\"lang:default decode:true\" style=\"background-color: #f0f0f0; padding: 10px; border-radius: 10px;\"><code>function Symbol(\/*...*\/) {\r\n    \/\/ ...\r\n    \/\/ Unconditionally assign to 'exports' and 'members':\r\n    this.exports = undefined;\r\n    this.members = undefined;\r\n}\r\n<\/code><\/pre>\n<p>However, there is a trade off when you do this. The more properties you\nassign to an object, the more space those objects take up in memory.<\/p>\n<p>For <code>Symbol<\/code>, reducing megamorphism wasn&#8217;t as simple as pre-initializing these optional properties because we create so\nmany symbols during compilation. In addition, symbols produced by our checker not only included all of the properties of <code>Symbol<\/code>, but all\nof the properties of <code>SymbolLinks<\/code>, an internal interface we use to cache checker-specific information for symbols. We\ndid this initially for performance reasons. Symbols from the binder are reused during incremental parsing, so\nchecker-specific information is stored in a lookaside table. Since symbols produced by the checker aren&#8217;t reused, we\nopted to store checker-specific information on the symbol itself to avoid the cost of an additional indirection. We\nobviously don&#8217;t want to pre-initialize all of the <code>SymbolLinks<\/code> properties on <code>Symbol<\/code>, since that would cause our\nmemory consumption to skyrocket. Instead, we chose to add a single <code>links<\/code> property to <code>Symbol<\/code> in which we would\nstore the <code>SymbolLinks<\/code> object for transient symbols. This still requires indirection, but is far cheaper than reading\nfrom a lookaside table because we can leverage a monomorphic IC when accessing the property.<\/p>\n<h2>Outcomes<\/h2>\n<p>After making these changes in <a href=\"https:\/\/github.com\/microsoft\/TypeScript\/pull\/51880\">microsoft\/Typescript#51880<\/a>, we\ndramatically reduced the number of maps V8 produced for <code>Symbol<\/code> from thirty down to two:<\/p>\n<p><img decoding=\"async\" title=\"V8 map reduction for 'Symbol'\" src=\"https:\/\/devblogs.microsoft.com\/typescript\/wp-content\/uploads\/sites\/11\/2023\/05\/deopt-explorer-symbol-maps-after.png\" alt=\"Close up of the &quot;Maps&quot; tree view showing a list of constructor names. The &quot;Symbol&quot; constructor has been expanded, showing only two entries.\" \/><\/p>\n<p>Even though this view shows two maps, only the second one matters as the first map is the empty object produced before\nany properties are assigned. All property access against <code>Symbol<\/code> instances in the compiler are now monomorphic, and\nbetween <a href=\"https:\/\/github.com\/microsoft\/TypeScript\/pull\/51880\">this change<\/a> (3-5%) and improvements to monomorphism for\n<a href=\"https:\/\/github.com\/microsoft\/TypeScript\/pull\/51682\">some of our <code>Node<\/code> subtypes<\/a> (4-5%), we&#8217;ve reduced the average\ncompile time in our benchmarks by between 8-10%! And we&#8217;re not done yet as there are still many more opportunities to\nreduce megamorphism that we&#8217;re still working on.<\/p>\n<h2>Getting Deopt Explorer<\/h2>\n<p><a href=\"https:\/\/marketplace.visualstudio.com\/items?itemName=rbuckton.deoptexplorer-vscode\">Deopt Explorer is available now<\/a> in\nthe VS Code extension marketplace. Deopt Explorer is also <a href=\"https:\/\/github.com\/microsoft\/deoptexplorer-vscode\">open source on GitHub<\/a>,\nwhich is the best place to provide feedback and file issues, and PRs are welcome!<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Over the past few months, during the lead-up to the TypeScript 5.0 beta, our team spent a good portion of our time looking for ways to improve the performance of our compiler so that your projects build faster. One of the ways we improved was by looking into an oft overlooked aspect of many JavaScript [&hellip;]<\/p>\n","protected":false},"author":118742,"featured_media":1797,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_acf_changed":false,"footnotes":""},"categories":[1],"tags":[],"class_list":["post-3906","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-typescript"],"acf":[],"blog_post_summary":"<p>Over the past few months, during the lead-up to the TypeScript 5.0 beta, our team spent a good portion of our time looking for ways to improve the performance of our compiler so that your projects build faster. One of the ways we improved was by looking into an oft overlooked aspect of many JavaScript [&hellip;]<\/p>\n","_links":{"self":[{"href":"https:\/\/devblogs.microsoft.com\/typescript\/wp-json\/wp\/v2\/posts\/3906","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/devblogs.microsoft.com\/typescript\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/devblogs.microsoft.com\/typescript\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/typescript\/wp-json\/wp\/v2\/users\/118742"}],"replies":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/typescript\/wp-json\/wp\/v2\/comments?post=3906"}],"version-history":[{"count":0,"href":"https:\/\/devblogs.microsoft.com\/typescript\/wp-json\/wp\/v2\/posts\/3906\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/typescript\/wp-json\/wp\/v2\/media\/1797"}],"wp:attachment":[{"href":"https:\/\/devblogs.microsoft.com\/typescript\/wp-json\/wp\/v2\/media?parent=3906"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/typescript\/wp-json\/wp\/v2\/categories?post=3906"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/typescript\/wp-json\/wp\/v2\/tags?post=3906"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}