diff options
| author | Marshall Lochbaum <mwlochbaum@gmail.com> | 2022-04-09 22:26:45 -0400 |
|---|---|---|
| committer | Marshall Lochbaum <mwlochbaum@gmail.com> | 2022-04-09 22:29:49 -0400 |
| commit | 8f43952c048f04f72e2e39f1611944ad8a274657 (patch) | |
| tree | 8c3c2cc25b1c4aea767f219f2c82be3daddaf704 /docs/implementation/compile | |
| parent | 9b3497c37db4177b43932f2b2459d11664a48931 (diff) | |
Array compilers in context but it's pretty much all interpreters so far, oops
Diffstat (limited to 'docs/implementation/compile')
| -rw-r--r-- | docs/implementation/compile/intro.html | 26 |
1 files changed, 26 insertions, 0 deletions
diff --git a/docs/implementation/compile/intro.html b/docs/implementation/compile/intro.html new file mode 100644 index 00000000..ea4eaed5 --- /dev/null +++ b/docs/implementation/compile/intro.html @@ -0,0 +1,26 @@ +<head> + <link href="../../favicon.ico" rel="shortcut icon" type="image/x-icon"/> + <link href="../../style.css" rel="stylesheet"/> + <title>BQN: Array language compilation in context</title> +</head> +<div class="nav">(<a href="https://github.com/mlochbaum/BQN">github</a>) / <a href="../../index.html">BQN</a> / <a href="../index.html">implementation</a> / <a href="index.html">compile</a></div> +<h1 id="array-language-compilation-in-context"><a class="header" href="#array-language-compilation-in-context">Array language compilation in context</a></h1> +<p>Chances are that if you're reading this, you know the difference between an interpreter and a compiler, and what separates C from interpreted Python. Good! You have a lot more to learn to understand what compilation means for the array language paradigm. The most important is that, for an array language, compiling isn't automatically better in the way that Python compilers tend to run a lot faster than interpreters. The two strategies have different advantages, and a hybrid approach could be much better than either alone. Here we'll discuss what makes BQN fast, what keeps it from always being fast, and how compiling might help.</p> +<h2 id="array-interpreters"><a class="header" href="#array-interpreters">Array interpreters</a></h2> +<p>Learn to run the code before you can tree-walk the source.</p> +<h3 id="fast-and-slow-evaluation"><a class="header" href="#fast-and-slow-evaluation">Fast and slow evaluation</a></h3> +<p>Let's start by looking closer at the example of C versus Python. Suppose you write a simple program, with a for loop, to sum the elements of a floating-point list in order. To evaluate this code, C compiles it to some machine code that quickly adds the elements. Python <em>does</em> compile the code as well, but only a little, leaving some object code that has any syntax complications stripped out but keeps the source code semantics entirely intact. Executing this code is relatively slow.</p> +<p>BQN executes like Python! If you write out a summation loop <code><span class='Brace'>{</span><span class='Value'>s</span><span class='Gets'>←</span><span class='Number'>0</span><span class='Separator'>⋄</span><span class='Brace'>{</span><span class='Value'>s</span><span class='Function'>+</span><span class='Gets'>↩</span><span class='Value'>𝕩</span><span class='Brace'>}</span><span class='Modifier'>¨</span><span class='Value'>𝕩</span><span class='Separator'>⋄</span><span class='Value'>s</span><span class='Brace'>}</span></code>, it's also slow. But you wouldn't do this in BQN: you'd write <code><span class='Function'>+</span><span class='Modifier'>´</span></code> to sum the list, and this runs at about the same speed as C for a long enough list. Well, the reason for that is just that CBQN has some pre-written C code to sum a list of floats, and it recognizes <code><span class='Function'>+</span><span class='Modifier'>´</span></code> and calls that.</p> +<p>You wouldn't write the loop in Python either—you'd write <code><span class='Value'>sum</span><span class='Paren'>(</span><span class='Value'>arr</span><span class='Paren'>)</span></code>. There are two differences, however. First, BQN's carefully chosen primitive set and cultural emphasis on array programming mean you're more likely to write a program where most computation is done with fast primitives. Second, uh, Python is slower. I measure about 2ms to sum <code><span class='Number'>1e6</span> <span class='Value'>•rand.</span><span class='Function'>Range</span> <span class='Number'>0</span></code> in BQN and 8ms to sum the equivalent in Python.</p> +<p>Python developers aren't stupid, just uninformed! Specifically, they are lacking information about types (and, as an aside, I like Python and am often found defending it against more hostile array programmers). Both C and BQN are faster because they're able to take advantage of knowing that all elements to be added are double-precision floats.</p> +<h3 id="ways-of-knowing-types"><a class="header" href="#ways-of-knowing-types">Ways of knowing types</a></h3> +<p>C and CBQN ultimately sum an array of floats with the same machine code, but they arrive at it in a different way.</p> +<p>C requires the programmer to specify the types used, and more generally a statically typed language is one where the type of a particular value is fixed based on the source code (or each copy of the value, with generics or other code generation mechanisms).</p> +<p>BQN uses dynamic types, but in each array it tries to determine a common element type: for example it might notice that every element can be represented as a signed two-byte integer. The type is stored only once in the array header, and all elements are packed into memory using the appropriate type. So the two-byte integer array would be stored using a fixed-size header (which mostly consists of the shape and other non-type things), then two bytes for each element.</p> +<p>I sometimes think of C's approach to types as <strong>temporally homogeneous</strong>, because once you write a function, a call one minute has the same types as a call the next, and BQN's as <strong>spatially homogeneous</strong>, because in an array each element has the same type as another one address over.</p> +<p>The temporal/spatial distinction isn't the same as static versus dynamic typing. Array elements in a statically-typed language are <em>both</em> temporally and spatially homogeneous, although in my opinion C compilers today only properly take advantage of the temporal part. And a dynamically-typed language can take advantage of temporal homogeneity with a combination of type checking and type inference, like a Javascript JIT compiler does.</p> +<h3 id="and-which-is-better"><a class="header" href="#and-which-is-better">And which is better</a></h3> +<p>Because static typing lets the programmer say exactly what type the data should have, it ought to be faster, right? Well that's a bold hypothesis, C Programming Language, given that you spent the entire 90s working to convince programmers that it's better to let the compiler choose which assembly instructions are run and in what order.</p> +<p>Array type detection can be both fast and accurate. First off, scanning a BQN array to get the appropriate type is very quick to do with vector instructions, particularly if it's an integer array. But also, this isn't usually necessary, because most primitives have an obvious result type. Structural manipulation leaves the type unchanged, and arithmetic can be done with built-in overflow checking, adding about 10% overhead to the operation in a typical case.</p> +<p>And on the other side, it's hard to pick a static type that always works. Most times your forum software is run, each user will have under <code><span class='Number'>2</span><span class='Function'>⋆</span><span class='Number'>15</span></code> posts. But not always, and using a short integer for the post count wouldn't be safe. With dynamically typed arrays, your program has the performance of a fast type when possible but scales to a larger one when necessary. So it can be both faster and more reliable.</p> +<p>However, with current array implementation technology, these advantages only apply to array-style code, when you're calling primitives that each do a lot of work. In order to get many small primitive calls working quickly, you need a compiler.</p> |