{"id":298,"date":"2023-08-19T07:46:33","date_gmt":"2023-08-18T23:46:33","guid":{"rendered":"https:\/\/neolefty.org\/wordpress\/?p=298"},"modified":"2023-08-26T04:57:40","modified_gmt":"2023-08-25T20:57:40","slug":"benchmarking-javascript-collections","status":"publish","type":"post","link":"https:\/\/neolefty.org\/wordpress\/2023\/08\/19\/benchmarking-javascript-collections\/","title":{"rendered":"Benchmarking JavaScript Collections"},"content":{"rendered":"\n<p>Code for this post: <a href=\"https:\/\/github.com\/neolefty\/js-collection-benchmarks\">github.com\/neolefty\/js-collection-benchmarks<\/a><\/p>\n\n\n\n<p><a href=\"http:\/\/hexpansion.io\"><em>Hexerals<\/em><\/a> uses <a href=\"https:\/\/immutable-js.com\/\">immutable.js<\/a> for its <a href=\"https:\/\/github.com\/neolefty\/hexerals\/blob\/master\/v1\/src\/game\/model\/board\/Board.ts\">game state<\/a> \u2014\u00a0could it switch to JavaScripts native collections? That would make the code more readable, but how would effect performance?<\/p>\n\n\n\n<p><strong>Summary:<\/strong> In <em>Chrome<\/em>, <strong>object<\/strong> operations are much faster than <strong>immutable Map<\/strong> \u2014\u00a0just don&#8217;t  <code>freeze()<\/code> them. But in <em>Firefox<\/em> and <em>Safari, <\/em><strong>immutable Map<\/strong> still wins. Chrome&#8217;s advantage might come from <a href=\"https:\/\/v8.dev\/docs\/hidden-classes\">Hidden Classes<\/a>.<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-full\"><a href=\"https:\/\/github.com\/neolefty\/hexerals\/blob\/bfa8d0e3b2fd633c68ddedb4d1a1598d692cdcc0\/v1\/src\/game\/model\/board\/Board.ts#L1\"><img loading=\"lazy\" decoding=\"async\" width=\"407\" height=\"22\" src=\"https:\/\/neolefty.org\/wordpress\/wp-content\/uploads\/2023\/08\/Screenshot-2023-08-17-at-7.41.30-PM.png\" alt=\"\" class=\"wp-image-299\"\/><\/a><\/figure><\/div>\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-full\"><a href=\"https:\/\/github.com\/neolefty\/hexerals\/blob\/bfa8d0e3b2fd633c68ddedb4d1a1598d692cdcc0\/v1\/src\/game\/model\/board\/Board.ts#L112\"><img loading=\"lazy\" decoding=\"async\" width=\"483\" height=\"126\" src=\"https:\/\/neolefty.org\/wordpress\/wp-content\/uploads\/2023\/08\/Screenshot-2023-08-17-at-7.41.15-PM.png\" alt=\"\" class=\"wp-image-300\"\/><\/a><\/figure><\/div>\n\n\n<p>The strengths of <strong>immutable.js<\/strong> are:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Memory \u2014&nbsp;immutable.js only duplicates sections that are changed, which saves memory. It makes keeping a full history of a game especially efficient.<\/li>\n\n\n\n<li>Speed \u2014&nbsp;it&#8217;s fast! For example, <em>Hexerals<\/em> robots use the game state to make decisions, and if it slows down, it limits their intelligence.<\/li>\n<\/ul>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"alignright size-full is-resized\"><a href=\"https:\/\/neolefty.org\/wordpress\/wp-content\/uploads\/2023\/08\/Screenshot-2023-08-17-at-7.26.46-PM.png\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/neolefty.org\/wordpress\/wp-content\/uploads\/2023\/08\/Screenshot-2023-08-17-at-7.26.46-PM.png\" alt=\"\" class=\"wp-image-292\" style=\"width:331px;height:229px\" width=\"331\" height=\"229\"\/><\/a><\/figure><\/div>\n\n\n<p><em>Hexerals<\/em> uses a lot of <a href=\"https:\/\/immutable-js.com\/docs\/v3.8.2\/Map\/\">Maps<\/a> and <a href=\"https:\/\/immutable-js.com\/docs\/v3.8.2\/List\/\">Lists<\/a>.<\/p>\n\n\n\n<p>For example, its board is represented using a Map, matching each location (a <strong>Hex<\/strong>) to contents (a <strong>Tile<\/strong>) \u2014 the hexagon in upper left might be Hex (0, 6), with a Tile whose owner is Red, population 8, and no special terrain.<\/p>\n\n\n\n<p>So how expensive would it be to switch from those Maps and Lists to JavaScript&#8217;s built-in <a href=\"https:\/\/developer.mozilla.org\/en-US\/docs\/Web\/JavaScript\/Reference\/Global_Objects\/Object\">Objects<\/a> and <a href=\"https:\/\/developer.mozilla.org\/en-US\/docs\/Web\/JavaScript\/Reference\/Global_Objects\/Array\">Arrays<\/a>?<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">To the Benchmarks!<\/h2>\n\n\n\n<p>These are run in your local browser (click the gear to change settings &amp; run again):<\/p>\n\n\n\n<iframe loading=\"lazy\" id=\"benchmarks\" title=\"JS Collection Benchmarks\" width=\"100%\" height=\"750px\" src=\"https:\/\/neolefty.org\/js-benchmarks\/unframed\/\"><\/iframe>\n\n\n\n<p>What are these benchmarks doing? Something that resembles the internal state transitions in a single turn of <em>Hexerals<\/em>. See <a href=\"https:\/\/github.com\/neolefty\/js-collection-benchmarks\/blob\/18b8e4de10f1c071245d905ba39e3e1a51824c87\/app\/bench\/BenchWorkers.ts#L74\">BenchWorkers.ts<\/a> for actual code.<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li><em>Collection Size:<\/em> Create a collection with that many simple items in it.<\/li>\n\n\n\n<li><em>Iterations:<\/em> Copy it this many times.<\/li>\n\n\n\n<li><em>Mutation Fraction:<\/em> Each time it&#8217;s copied, also randomly replace a fraction of its contents. For example, if Collection Size is 1000 and Mutation Fraction is 0.1, then 100 entries will be modified at random during each Iteration.<\/li>\n<\/ul>\n\n\n\n<figure class=\"wp-block-table\"><table><tbody><tr><td><\/td><td>1. <strong>Copy<\/strong><\/td><td>2. <strong>Modify<\/strong><\/td><\/tr><tr><td>JS <strong>object<\/strong><\/td><td><code>copy = {...original}<\/code><\/td><td>copy[x] = y<\/td><\/tr><tr><td>immutable <strong>Map<\/strong><\/td><td><code>copy = Map(original.entries())<\/code><\/td><td><code>copy = copy.withMutations(mutable =&gt; mutable.set(x, y)<\/code><\/td><\/tr><\/tbody><\/table><figcaption class=\"wp-element-caption\">You can see why developers might prefer the <strong>object<\/strong> \u2014\u00a0its syntax is simpler.<\/figcaption><\/figure>\n\n\n\n<h2 class=\"wp-block-heading\">Surprises<\/h2>\n\n\n\n<ul class=\"wp-block-list\">\n<li><a href=\"https:\/\/developer.mozilla.org\/en-US\/docs\/Web\/JavaScript\/Reference\/Global_Objects\/Object\/freeze\">Object.freeze()<\/a> is <em>slow<\/em> for objects but practically free for arrays!<\/li>\n\n\n\n<li><a href=\"https:\/\/immerjs.github.io\/immer\/\">Immer<\/a> (which uses Object.freeze) is slow if you use it inner loops. But it&#8217;s very safe! And almost nobody needs it to be inside inner loops anyway.<\/li>\n\n\n\n<li><a href=\"https:\/\/giusepperaso.github.io\/structura.js\/\">Structura<\/a> is an interesting alternative to Immer. It &#8220;freezes at compile time&#8221; which &#8230; is not quite freezing, but relying on <a href=\"https:\/\/www.reddit.com\/r\/rust\/comments\/10mvx9m\/any_idea_about_what_figma_is_using_to_run_rustc\/\">TypeScript&#8217;s Readonly&lt;T&gt;<\/a>. Anyway it looks like that&#8217;s the key to performance in JS \u2014 and it&#8217;s what the winning benchmark is doing with <em>object<\/em>.<\/li>\n\n\n\n<li>JavaScript&#8217;s built-in <a href=\"https:\/\/developer.mozilla.org\/en-US\/docs\/Web\/JavaScript\/Reference\/Global_Objects\/Map\">Map<\/a> is slow for this kind of operation, compared to plain old objects \u2014&nbsp;which is too bad because Map is more flexible than objects. It turns out that copying a map is slow. There is another slightly faster way (using an iterator to insert one by one) but it&#8217;s not enough faster to close the gap. Probably worth revising the benchmark to include it tbh.<\/li>\n<\/ul>\n\n\n\n<p>The fastest would be to skip all this and go straight to <a href=\"https:\/\/webassembly.org\/\">WebAssembly<\/a>. That&#8217;s what <a href=\"https:\/\/www.figma.com\/blog\/webassembly-cut-figmas-load-time-by-3x\/\">Figma does<\/a>, but it would mean <a href=\"https:\/\/www.reddit.com\/r\/rust\/comments\/10mvx9m\/any_idea_about_what_figma_is_using_to_run_rustc\/\">switching from TypeScript to Rust\/C++<\/a>. Hmm &#8230;<\/p>\n\n\n\n<hr class=\"wp-block-separator has-css-opacity is-style-wide\"\/>\n\n\n\n<h2 class=\"wp-block-heading\">Comparing Firefox, Safari, and Chrome<\/h2>\n\n\n\n<p>In short, Safari and Firefox both really like <em>Immutable.js Map<\/em>, and Chrome likes <em>object<\/em>.<\/p>\n\n\n\n<p>For 1000 x 1000 x 0.1, on an M1 laptop, in milliseconds:<\/p>\n\n\n\n<figure class=\"wp-block-table\"><table><tbody><tr><td><\/td><td><em>object<\/em><\/td><td><em>Map<\/em><\/td><td><em>immutable Map<\/em><\/td><\/tr><tr><td><em>Chrome<\/em><\/td><td>4.1<\/td><td>44<\/td><td>19<\/td><\/tr><tr><td><em>Firefox<\/em><\/td><td>55<\/td><td>57<\/td><td><strong>20<\/strong><\/td><\/tr><tr><td><em>Safari<\/em><\/td><td>114<\/td><td>82<\/td><td>18<\/td><\/tr><\/tbody><\/table><figcaption class=\"wp-element-caption\"><strong>Immutable.js Map<\/strong> has the best-worst-case on my desktop, with 20ms on Firefox.<\/figcaption><\/figure>\n\n\n\n<p>Chrome loves object, but everybody does well with immutable.js.<\/p>\n\n\n\n<p>How about some older mobile devices?<\/p>\n\n\n\n<figure class=\"wp-block-table\"><table><tbody><tr><td><\/td><td><em>object<\/em><\/td><td><em>Map<\/em><\/td><td><em>immutable Map<\/em><\/td><\/tr><tr><td><em>Pixel 4a 5G (2020<br>Chrome<\/em><\/td><td>21<\/td><td>105<\/td><td>64<\/td><\/tr><tr><td><em>Samsung A50<\/em> (2019)<br><em>Chrome<\/em><\/td><td>33<\/td><td>170<\/td><td><strong>79<\/strong><\/td><\/tr><tr><td><em>iPad (2018)<\/em><br><em>Safari<\/em><\/td><td>178<\/td><td>101<\/td><td>42<\/td><\/tr><\/tbody><\/table><figcaption class=\"wp-element-caption\"><strong>Immutable.js Map<\/strong> wins here too, with 79ms on an old Samsung phone.<\/figcaption><\/figure>\n\n\n\n<p>So, what&#8217;s the best choice? The widest bottleneck is clearly <strong>Immutable.js&#8217;s Map<\/strong>. The object spread operator (and <code>object.assign<\/code>) is too dang slow on Safari, and so is Map on Chrome.<\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity is-style-wide\"\/>\n\n\n\n<p>Tools learned: <a href=\"https:\/\/nextjs.org\/\">Next.js<\/a> (with static deployment), <a href=\"https:\/\/tailwindcss.com\/\">Tailwind CSS<\/a>, <a href=\"https:\/\/daisyui.com\/\">DaisyUI<\/a>.<\/p>\n\n\n\n<p>Caveats: The benchmarks run synchronously. Still working on getting web-workers right.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Code for this post: github.com\/neolefty\/js-collection-benchmarks Hexerals uses immutable.js for its game state \u2014\u00a0could it switch to JavaScripts native collections? That would make the code more readable, but how would effect performance? Summary: In Chrome, object operations are much faster than &hellip; <a href=\"https:\/\/neolefty.org\/wordpress\/2023\/08\/19\/benchmarking-javascript-collections\/\">Continue reading <span class=\"meta-nav\">&rarr;<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[24],"tags":[],"class_list":["post-298","post","type-post","status-publish","format-standard","hentry","category-hexerals"],"_links":{"self":[{"href":"https:\/\/neolefty.org\/wordpress\/wp-json\/wp\/v2\/posts\/298","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/neolefty.org\/wordpress\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/neolefty.org\/wordpress\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/neolefty.org\/wordpress\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/neolefty.org\/wordpress\/wp-json\/wp\/v2\/comments?post=298"}],"version-history":[{"count":30,"href":"https:\/\/neolefty.org\/wordpress\/wp-json\/wp\/v2\/posts\/298\/revisions"}],"predecessor-version":[{"id":344,"href":"https:\/\/neolefty.org\/wordpress\/wp-json\/wp\/v2\/posts\/298\/revisions\/344"}],"wp:attachment":[{"href":"https:\/\/neolefty.org\/wordpress\/wp-json\/wp\/v2\/media?parent=298"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/neolefty.org\/wordpress\/wp-json\/wp\/v2\/categories?post=298"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/neolefty.org\/wordpress\/wp-json\/wp\/v2\/tags?post=298"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}