skip

Parallelism Support

November 30, 2017

Mat Hostetter, Aaron Orenstein

TL;DR: Skip (a new reactive programming language formerly called "Reflex") now supports parallel processing!

What's new?

Over Thanksgiving weekend Aaron Orenstein and I engaged in an impromptu bicoastal hackathon to add parallelism to Skip.

The first question we had to answer was what primitive parallel operation to provide. We settled on tabulate:

fun tabulate<T>(count: Int, f: Int ~> T): mutable Vector<T> {

This generic function takes a count and a function f and produces the array:

[ f(0), f(1), f(2), ..., f(count - 1) ]

by invoking f in parallel.

If this API seems a bit odd, just consider it a building block to implement other parallel algorithms. For example, the Skip standard library now provides a traditional parallelMap method that applies a function g to an array, returning:

[ g(array[0]), g(array[1]), ..., g(array[array.size() - 1]) ]

The implementation simply calls tabulate with a wrapper lambda that captures g and array.

Where are the mutexes and atomics?

You don't need them!

To facilitate reactive memoization, Skip's type system tracks when an object must be transitively immutable (which we call "frozen"). By using the ~> (“tilde”) rather than -> (“dash”) lambda syntax in its type declaration, tabulate constrains f to be a frozen lambda, which means it can only capture frozen objects.

Because Skip programs have no mutable global state, and f is frozen, it's impossible for any two invocations of f to modify the same data. This not only makes race conditions impossible, it also makes tabulate's return value deterministic. The strong guarantees provided by the type system are what made it possible to implement a foolproof parallelism API in a weekend.

Of course, parallel algorithms that update shared mutable state are undeniably useful, but they open a giant can (a barrel?) of worms. Skip doesn't support them, but there's always next Thanksgiving!

How is parallelism implemented?

The Skip compiler uses LLVM to produce optimized machine code. (It also has Javascript and Hack back ends, but they don't support parallelism). The compiled Skip program is linked against a C++ runtime library that provides traditional features like garbage collection and Unicode support as well as reactive memoization. We extended the runtime library to add a new parallelTabulate entry point.

When a thread (which we'll call the "launching thread") invokes parallelTabulate, it posts tasks to a folly CPUThreadPoolExecutor to enlist worker threads to help out. Rather than posting one task per array entry, it posts min(array_size, num_threads) - 1 tasks that each may compute many array entries. Each task runs a loop that grabs the next unprocessed array index using an atomic increment, computes and records the value for that index, and repeats until the index hits the end.

After posting tasks, the launching thread also runs the task loop. This way, even if no worker threads are available (perhaps due to a nested tabulate) it will still finish the job itself, and in any case it might as well do something useful. Once its loop finishes, the launching thread synchronizes by waiting only for threads that started computing something, rather than waiting for all posted tasks to complete. If a worker thread later picks up a task for a completed parallelTabulate call, it discards it.

Does it work?

Yes! To test threading we parallelized one important loop in Skip's LLVM back end which applies various optimization passes to each function being compiled. This code can now optionally use parallelMap instead of map:

newFuns = if (parallel) {
  funs.parallelMap(optimizeFun)
} else {
  funs.map(optimizeFun)
};

That was easy. We benchmarked this change on my 24-core dev VM by compiling the compiler with itself using varying numbers of threads:

As you can see, the speedup starts out nearly linear but starts to tail off around 5 cores or so, and by the time it hits 24 cores we're at a 12x speedup. That's a pretty typical-looking scaling curve, especially for a memory-intensive program like a compiler. We don't know what the bottlenecks are — we haven't tuned this at all, this is just what happened when we tried parallelMap.

Conclusion

The strong immutability guarantees of Skip's type system made it surprisingly easy to add safe, easy-to-use parallelism. And unlike a functional language, you can still use mutable data structures when you need to.

Although this was a fun hack, the next big exciting change won't involve parallelism, and will take a lot longer than a weekend — it's making the compiler incremental, using Skip's own reactive memoizer to only recompile code affected by modified files. Stay tuned!

Faster CMake

November 21, 2017

Christopher Chedeau, Aaron Orenstein

When I joined the Skip team, my biggest annoyance was that CMake took forever to run (okay, 45s). I didn't expect it to be that slow since there was only a hundred source files. It turns out that we generate a target for every single test (we have a lot) and we duplicate all those test targets for each backend. At the end of the day, we had 5500 targets.

I commented out the line that generated targets for tests and CMake only took 1.5s! My instinct was to get rid of CMake altogether and with some healthy dose of hackery I was able to get Jest, our JavaScript testing framework, wired up for some of the tests. This triggered Aaron Orenstein to do something about it, he wasn't okay with the fact that a system built with C++ was slower than one in JavaScript ;)

Cmake Performance

Aaron started profiling CMake and found out that a ton of time was spent looking up target names in cmLocalGenerator. When looking at the source, he found that it was a classic O(n²) issue where targets were stored in a vector instead of a hash map. He sent a pull request that adds an index backed by a unordered map which brought down the time from 45s to 15s!

After this was merged, he ran perf again and found another place where Cmake was doing a linear lookup. But this time, it wasn't a straightforward lookup. It was doing a fuzzy search for a filename where, based on the platform, it is a case sensitive or insensitive search and doing some work to allow different file extensions in certain cases.

The solution that Aaron implemented for this is to have an index where keys are lowercase filenames without their extensions that point to an array of values. Then, do a linear lookup on this smaller array. In practice, all the arrays are 1 elements so it keeps the same performance characteristics. That second pull request brought down the time again from 15s to 7s!

Conclusion

The first improvement was shipped as part of CMake 3.10.0 this morning! If you are using a Mac you can run brew upgrade cmake to get the improvements. The second one is expected to ship as part of 3.11.0.

This is really exciting that as part of building Skip, we've been able to improve a tool used by the entire industry! #impact

Fixing the Syntax Barrier

November 20, 2017

Christopher Chedeau

One of my biggest frustration when I try to learn a new language (Rust, Elm) or work on a language that I haven't touched in a while (OCaml, C++, PHP) is around syntax. I know what I want to write and I have an approximate idea of how it should be written but don't exactly get it right.

Unfortunately, when you get it wrong, you always get an obscure parser error such as “Unexpected token x” and if you get lucky, you also get “expected ” as well. This is correct from a parser point of view but unhelpful for a person.

Elm developers spent a lot of energy on error messages but if you write “return” by mistake, they have a pretty error but the content is still the same.

Elm error message when you mistakenly write a return statement

The problem with error message around syntax is that it's near impossible to Google for the error you've made.

Other programming languages exist!

When looking at the errors I was making, the majority of them was me trying to use a syntax from a different programming language. All the programming languages only know about their own language idioms and make no attempt at trying to understand the rest of the world.

This makes total sense from a software engineering perspective: you want to carve off a world where everything is consistent and don't want to have to support everything people may write. However, this is not how people work, they go back and forth many languages on a regular basis and are mixing them up all the time.

Skip solution

The exciting part is that now that I'm working on a programming language, I actually have a shot at fixing this!

First of all, the solution is —not— to try and accept every programming language syntaxes people could throw at us and try to come up with a super language. This would be a terrible idea at so many levels.

What we want to do is —when there's an error—, try to figure out what the person meant to write and provide hints based on that. In the example above, the token just before the syntax error is return. This is trivial to detect!

If we encounter this specific instance, we can now provide helpful information such as: “our language doesn't support the return keyword and the last expression is returned, if you wanted to do an early return, here's a link to a document that explains how to translate those patterns.

Examples

Since my first time trying the language for the first time, I took note of every error I made. We've already added detection for 40 patterns such as:

  • a ? b : c instead of if (a) b else c
  • === instead of ==
  • => instead of -> or ~>
  • Missing fun before method declaration
  • boolean instead of Bool
  • $variable instead of variable
  • Extraneous var, const, let, val
  • etc...

And there's a long list of other patterns that we want to get to at some point. The good news is that it likely follows a 80-20 distribution where fixing a few common mistakes is going to cover a big amount of errors. Also it's pretty mechanical work and can be done at any time.

Conclusion

Syntax in my experience is a big barrier to entry for using a new language, even for experienced programmers. In many cases, when a syntax error is raised, there are heuristics that are easy to implement to figure out what the person meant to write and suggest the correct way to do it.

The ultimate goal is that you are able to paste code written in any of the top 20 most used programming languages and Skip is going to give you step by steps instructions on how to morph your code to make it valid Skip.

We've implemented many suggestions and results so far are very encouraging. As I'm writing code myself, I'm now seeing a lot of those (correct) suggestions when I make mistakes. Also, the first experience reports using Skip used to contain a lot of issues around syntax and the latest one didn't.

Simulating goto in JavaScript

November 15, 2017

Christopher Chedeau

Skip, a new programming language we’re working on, has pattern matching. In order to implement it efficiently, Tim Zakian implemented the technique described in the paper "Compiling Pattern Matching to Good Decision Trees". The idea is to turn the pattern matching rules into an acyclic graph that maximizes sharing of common sub-problems.

There’s a small example in the paper: given two lists built using Cons/Nil, if the first one contains exactly 1 element, then return 1. If the second one contains exactly 1 element, then return 2. Otherwise return -1. The Skip code looks like this:

(x, y) match {
  | (Cons(_, Nil()), _             ) -> 1
  | (_             , Cons(_, Nil())) -> 2
  | (_             , _             ) -> -1
}

If you implement the algorithm in the paper (which is easy to read if you are interested in the details), you’re going to end up with a graph that looks like this:

At the end of the day, the output is going to be some assembly doing jumps to labels but in this case we’re interested in targeting a high level language. For languages that support goto like C or PHP, the output code would look something like this:

A:  if (x instanceof Cons) {
      goto B;
    } else {
      goto C;
    }
B:  if (x.tail instanceof Nil) {
      return 1;
    } else {
      goto C;
    }
C:  if (y instanceof Cons) {
      goto D;
    } else {
      return -1;
    }
D:  if (y.tail instanceof Nil) {
      return 2;
    } else {
      return -1;
    }

Goto in JavaScript

Unfortunately, we don’t have the luxury of having goto in JavaScript. But, we can get creative. There is a little known feature of JavaScript that lets you break out of nested loops:

outer: while(true) {
         while(true) {
           break outer;
         }
       }

It turns out that you don’t even need the loop, you can put the label on a block and break out of it.

A: {
  B: {
    break A;
  }
}

This is going to jump to the end of the A block. Given this trick, we can rewrite our initial example by nesting labelled blocks.

D: {
  C: {
    B: {
      if (x instanceof Cons) {
        break B;
      } else {
        break C;
      }
    } // end of B
    if (x.tail instanceof Nil) {
      return 1;
    } else {
      break C;
    }
  } // end of C
  if (y instanceof Cons) {
    break D;
  } else {
    return -1;
  }
} // end of D
if (y.tail instanceof Nil) {
  return 2;
} else {
  return -1;
}

Voila! We managed to turn all our goto into something that JavaScript can run.

Backward goto

In our case, we only needed forward jumps. If we wanted backward jumps, the idea is to use continue instead of break. Unfortunately, JavaScript won’t let you do continue on just blocks, so we need to use while loop.

A: while(true) {
     if ( ... ) {
       continue A;
     }

     break;
   }

Further Optimizations

In the A case, we either jump to B or C. Since B is right after A, we don’t actually need the jump in that case. Same for the jump to D, so we can remove both. It’s also possible to reorder blocks to create more opportunities to remove blocks this way, even though in this case it doesn’t help. Here’s the output after this cleanup:

C: {
  if (!(x instanceof Cons)) {
    break C;
  }
  if (x.tail instanceof Nil) {
    return 1;
  }
} // end of C
if (!(y instanceof Cons)) {
  return -1;
}
if (y.tail instanceof Nil) {
  return 2;
} else {
  return -1;
}

This piece of code is going to do the smallest amount of operations to get the correct result but it looks weird. In this particular case, the version written by a human would be just as fast. My gut feeling is that it’s possible to transform the first one into the second one but it’s a wishlist for now :)

if (x instanceof Const && x.tail instanceof Nil) {
  return 1;
} else if (y instanceof Const && y.tail instanceof Nil) {
  return 2;
} else {
  return -1;
}

A Handy Tool is Born

August 13, 2017

Mat Hostetter

Recently Christopher Chedeau asked me if I could write a tool like Godbolt's Compiler Explorer that would allow developers to see what machine code the Skip compiler produces for their code.

That sounded like a good weekend hack, so I threw something together that shows the assembly code for any combination of functions or files, as either human-readable text or JSON.

A Small Example That Made Me Happy

Let's try using pattern matching to print "B" if passed an instance B and "C" if passed a C:

base class A
class B() extends A
class C() extends A

fun printTypeName(a: A): void {
  print_string(a match { B() -> "B" | C() -> "C" })
}

Here's the x86_64 code shown by the tool, which was optimized first by the Skip compiler and then by LLVM:

_rx.printTypeName:                      ## @rx.printTypeName
## BB#0:                                ## %b0.entry
 movq -8(%rdi), %rax
 movq (%rax), %rdi
 jmp _rx.print_string        ## TAILCALL

What happened here? The optimizer noticed that the match is simply mapping types to compile-time constants, so rather than generating a conditional branch it used a graph coloring algorithm to reserve a slot in each class's vtable and stored the constants there. Excellent!

A Smaller Example That Made Me Sad

Now let's change the code slightly, to simply return the String rather than print it:

fun printTypeName(a: A): String {
  a match { B() -> "B" | C() -> "C" }
}

You would expect an even shorter function, but instead we get:

_rx.printTypeName:                      ## @rx.printTypeName
## BB#0:                                ## %b0.entry
 movq -8(%rdi), %rcx
 movabsq $-4035225266123964350, %rdx ## imm = 0xC800000000000042
 leaq 1(%rdx), %rax
 testb $1, (%rcx)
 cmoveq %rdx, %rax
 retq

Why is it worse? It turns out that multiple return statements coming from the front end trick the match optimizer into thinking it needs to generate control flow. So it falls back to its second choice, storing a bit in each vtable and branching on that to do the type dispatch. Fortunately LLVM stepped in and optimized that branch into a conditional move, but it's still not as tight as it could have been.

I'll admit that when I started writing this post I wasn't expecting to see the code get worse in the second example, which shows how handy a tool like this can be.

Oh, and some of you may be wondering "what the heck is that huge integer?" That's the Skip String constant "B". Aaron Orenstein implemented a "short string optimization" where Strings smaller than a pointer (i.e. <= 7 UTF-8 bytes) are simply stored inline in the pointer itself. LLVM then cutely adds one to that to produce the String "C".

Next up, hopefully I can convince Christopher to use the JSON API to package this into something more user-friendly.

Reactivity Overview

January 4, 2017

Mat Hostetter

TL;DR: The runtime for the Skip programming language memoizes (caches) function return values. In addition to traditional memoization, it tracks dependencies on mutable state, such as database values, and automatically updates the memoization cache when values that affected a function's return value change. Multiversion concurrency control (MVCC) allows thousands of parallel tasks to use the cache without any global locks.

Overview

As an optimization, Skip caches certain function call results, a process called "memoization". Memoization sometimes allows function calls to be bypassed by looking up the arguments in a table and substituting the value found there rather than running the code.

Memoizing a function call's return value based on its arguments is straightforward, and many programming languages (such as PHP) provide some way to do this. Writing a memoization decorator is even a common Python interview question. Skip's memoizer goes much farther and not only memoizes a function's return value, but also makes the cached value "depend on" all mutable state that function examined when it ran. The literature variously calls this adaptive computation or incremental computation.

In addition to keeping its memoization cache up to date, Skip allows arbitrary callbacks to run whenever those cached values change. This would facilitate, for example, data to be "pushed" to a mobile device only when necessary.

Dependency Graphs

It's important to understand that the Skip runtime is much more than a simple database cache. For example, if a Skip program reads data from a reactive data source and analyzes it to compute some information (e.g. can the user see some content), Skip will memoize those computed results, not just the raw database result. So if the same information is computed again, it will be instantly satisfied from the memoization cache without re-running any code. The key to making this work correctly is automatically updating the cache when data changes.

Skip uses a dependency graph to identify when memoized values become invalid and to recompute them efficiently when they do. This graph is created by observing and recording at runtime which memoized functions are called by other memoized functions (and with what parameters, and in what order), as well as what pieces of mutable state those calls actually examined. The graph is related to ADAPTON's Demanded Computation Graph (DCG), but extended with multiversion concurrency control (MVCC) and incremental coarsening of dependency information to reclaim memory.

Memoization, dependency tracking, invalidation and recomputation are handled automatically by the Skip runtime, but they do constrain the user's programming model. In order for memoization to work, memoized functions need to be transitively side-effect-free, which the Skip compiler enforces statically. Skip is not a functional programming language, which would have been one way to achieve these guarantees; instead, objects marked mutable can be modified as in other languages, but the compiler does not allow such side effects to cross memoization points.

Side Effect Management

A Skip program is logically partitioned into two layers: a memoizing inner "Core", where "reader tasks" compute values in parallel, and an external, non-memoizing "Mutator" that is allowed to change specially designated mutable objects called Cells. A Cell might be a simple wrapper around a number or string, but could also be a more complex data structure like an array or hash table.

When a Core function reads a Cell in the course of computing a result, the runtime automatically creates an edge in the dependency graph between that Cell and the function's memoized result value. Similarly, when one memoized function calls another (directly or even indirectly through a chain of non-memoized functions), the runtime connects them in the dependency graph. This way, when the Mutator assigns a new value to a Cell, the runtime can find all of the memoized values that transitively depend on it.

The Mutator can be written in Skip, but can also be written in another language, like PHP, Javascript or C++. It might use the Core Skip program as a reactive caching library, or might itself be a library used by the Core, such as a reactive database access layer.

Scalability, Atomicity and MVCC

The memoization cache may have millions or billions of cached values in it, and many thousands of parallel readers both reading the cache and adding new memoized entries to it. And while readers are running, the Mutator may be making millions of Cell changes whose effects ripple through the dependency graph.

This high level of concurrency raises not only scalability concerns (we can't afford to "lock the world" to change a Cell), but semantic questions as well. What does it mean to memoize computed values when the Cells they are based on are constantly changing? Can the Mutator change multiple Cells atomically? Can multiple reader tasks be guaranteed to see exactly the same Cell values as each other (e.g. for computing different parts of the same UI in parallel)?

Skip uses multiversion concurrency control (MVCC), a popular database implementation technique, to answer all these questions.

Each Mutator change is performed as a transaction commit, an atomic change to any number of Cells. Each commit makes its changes, propagates invalidations through the dependency graph, then increments a global integer transaction ID to indicate that a new "version of the world" is available to reader tasks.

Each reader task (typically just making one function call) latches the global transaction ID when it starts and uses that throughout its entire run. It only "sees" Cell and memoized values "as of" that transaction ID, ignoring any subsequent changes. To make this work, each Cell and each memoization cache entry records not just a single value, but a linked list of "revisions", each consisting of a value annotated with a non-overlapping [begin, end) transaction ID "lifespan". Looking up a memoized value for a specific transaction ID requires scanning the revision list, but the most recent revision is at the head, so the search usually terminates immediately. As old tasks exit, revisions corresponding to transaction IDs that no tasks care about any more get garbage collected, keeping the lists very short in practice.

It's clear how MVCC provides atomicity -- latching a transaction ID "freezes" the version of the world that a reader task sees -- but it also provides scalability. The challenge when committing an atomic change that affects thousands of dependency graph nodes is making sure that readers always see a coherent snapshot of the cache. MVCC solves this in a scalable way without any global locks. The key insight is that, if the current global transaction ID is T, then no reader cares about the state of the cache at T+1, because when they scan revision lists they will only consider entries that match the transaction ID they latched, which must be less than T+1. So the Mutator can update thousands of revision lists to indicate information about T+1, but locking only one object at a time. This leaves the "snapshot" for T+1 temporarily but harmlessly incomplete while it is making all the updates. Only when the commit is fully finished does the Mutator assign T+1 to the global transaction ID, suddenly making that version visible to newly-spawned readers. Existing readers still running at T (or T-1, or T-100...) continue running unaffected, since those values continue to exist in the revision lists until the garbage collector is able to remove them.

Current Status

Version 1 of the Skip runtime is ready to be hooked up to a new, LLVM-based compiler back end currently being implemented. (Note that Skip's existing PHP back end supports the full Skip language but does not have memoization support).

Future Topics

There are quite a few Skip runtime topics that could be discussed, but this post is already long enough! Some ideas for future posts:

  • How revision lists get updated during a commit.
  • How Skip uses "traces" to avoid unnecessary recomputation caused by "false positives", where a function's return value does not change even though some dependency changed (in what turned out to be an irrelevant way).
  • How the dependency graph gets "incrementally coarsened" to recover memory, trading speed for space based on LRU heuristics.
← Prev