www

Unnamed repository; edit this file 'description' to name the repository.
Log | Files | Refs

index.html (5187B)


      1 <!DOCTYPE html>
      2 <html>
      3 	<head>
      4 		<title>banna - ramblings</title>
      5 		<meta name="viewport" content="width=device-width, initial-scale=1">
      6 		<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
      7 		<link rel="stylesheet" href="/styles/style.css" />
      8 		<link rel="stylesheet" href="/styles/look.css" />
      9 		<link rel="stylesheet" href="/styles/codetheme.css" />
     10 		<script src="/scripts/highlight.js"></script>
     11 		<script>hljs.initHighlightingOnLoad();</script>
     12 	</head>
     13 
     14 	<body>
     15 		<div id="sidebar">
     16 			<div id="logo">
     17 				<a href="/">
     18 					<img src="/banna.png" alt="banna.tech" height="45" width="201" />
     19 				</a>
     20 			</div>
     21 			<div id="nav">
     22 				<a class="current" href="/post">blog</a>
     23 				<a class="" href="/things">things</a>
     24 				<a class="" href="/about">about</a>
     25 			</div>
     26 		</div>
     27 
     28 		<div id="wrapper">
     29 			<div id="content">
     30 <div class="post">
     31     <a href="/post/efficiency_of_2d_typed_arrays_vs_normal_arrays" class="link"><h1 class="header">Efficiency of 2D Typed Arrays vs Normal Arrays</h1></a>
     32     <span class="date">Posted on February, 22 2014</span>
     33     <div class="content">
     34 <p>The efficiency of some aspects of JavaScript surprise me, in good ways and bad ways.</p>
     35 
     36 <p>When working on my latest <a href="//banna.tech/projects/?title=Game_of_Life">project</a>, It was originally using the normal <a href="https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array">Array</a> that JavaScript provides, since it was the most straight-forward option. The project required to use a 2D array to store points on a grid.</p>
     37 
     38 <p>The method used to create a 2D array was by nesting Arrays with two coordinates in one big array:</p>
     39 
     40 <pre><code>var array = [[x0,y0],[x1,x2]];
     41 array[i][0] = x;
     42 array[i][1] = y;</code></pre>
     43 
     44 <p>Originally I thought this method was fine and dandy until I realized that the algorithm is extremely slow... Looking over it I saw nothing that I could improve so I just set it back into the corner for a bit.</p>
     45 
     46 <p>Flash-forward a week, and I find the existence of <a href="https://developer.mozilla.org/en-US/docs/Web/JavaScript/Typed_arrays">Typed Arrays</a>. </p>
     47 
     48 <p><strong>What's so special about Typed Arrays?</strong> Well, there's a myriad of differences between Typed arrays and normal arrays. First off, with normal JavaScript Arrays, they're not actually arrays. What I mean by this is that JavaScript arrays are actually just key-value objects, and the indexes are not integers, they're strings- generally. JavaScript engines do different things with Arrays, and that's where JavaScript gets its unreliable <a href="https://github.com/sq/JSIL/wiki/JavaScript-Performance-For-Madmen">performance</a> from. Typed Arrays on the other hand uses a set chunk of memory to construct a C-style array with a variety of different data Types (and yes, this does mean that all numbers in JavaScript that aren't doubles).</p>
     49 
     50 <p>Using 2D Typed Arrays is a bit more complex initially. First, nesting Typed Arrays is pointless, since you're still using the wonky normal arrays. Therefore, we must create a flat array that's x*y big. For a Boolean Typed Array we will use an Unsigned 8 bit Array:</p>
     51 
     52 <pre><code>var array = new Uint8Array(Array(x*y))</code></pre>
     53 
     54 <p>To read/write to this array, we must assume how the data is stored. In languages like C, this is generally implemented in a colexicographic order (also known as <a href="http://en.wikipedia.org/wiki/Row-major_order">Row-major order</a>), likewise in other languages like Fortran use a lexicographic ordering (also known as Column-major order). Assuming a colexicographic order, we can calculate an offset based on X Y coordinates, like so:</p>
     55 
     56 <pre><code>index = (columns * x) + y</code></pre>
     57 
     58 <p>With this offset calculated, all we have to do is throw it as an index in our typed array in one neat little statement:</p>
     59 
     60 <pre><code>//maxy is the maximum Y value
     61 array[maxy*x+y] = 1;</code></pre>
     62 
     63 <p>Originally I was a tad naive on the speed, so I ran some <a href="http://jsperf.com/performance-of-2d-typed-arrays-vs-normal-arrays">tests</a>. The results I got were shocking, since I knew the normal arrays in JavaScript were bad but... that bad?</p>
     64 
     65 <p><img alt="Graph" src="//i.banna.tech/40blog.png" /></p>
     66 
     67 <p>This test did 1 basic operation: go through a 1,000^2 2D array and set all the values to one.</p>
     68 
     69 <h2>Setup:</h2>
     70 
     71 <pre><code>var normal = [];
     72 var typed = new Uint8Array(new Array(1000*1000));</code></pre>
     73 
     74 <h2>Normal Array:</h2>
     75 
     76 <pre><code>for (var x = 0; x < 1000; x++) {
     77     for (var y = 0; y < 1000; y++) {
     78         normal.push([x,y]);
     79     }
     80 }</code></pre>
     81 
     82 <h2>Typed Array:</h2>
     83 
     84 <pre><code>for (var x = 0; x < 1000; x++) {
     85     for (var y = 0; y < 1000; y++) {
     86         typed[1000*x+y] = 1;
     87     }
     88 }</code></pre>
     89 
     90 <p>The normal array was 95% slower than the typed array on average. To put that in perspective, the normal array did 32 operations per second on average. The typed array on the other hand did 575 operations/second on average, leaving it 18x faster than the normal array.</p>
     91 
     92 <p>In hindsight, I feel pretty dumb to even use my original method.</p>
     93     </div>
     94 </div>
     95 
     96 
     97 			</div>
     98 		</div>
     99 	</body>
    100 </html>