The Good Soldier LMeyerov

Visualize Parallel Work Stealing in the Browser

2013-05-05T16:24:00.003-07:00

I try to write at least one interesting program every week. This weekend, to spice up my dissertation talk, I built an animated visualization of how my parallel CSS engine partitions a webpage via work stealing.

Work stealing is a great parallel task scheduling algorithm that provides dynamic load balancing and spatial locality. The idea is that each thread has a local queue of ready-to-fire tasks that it loops through, and if it ever runs out of local tasks, it will steal tasks from another thread's queue. The visualization shows how this works for a parallel top-down tree traversal over a webpage's HTML tree. In this case, a task is a node, and executing a task is denoted by changing the background color of that node to match the thread's color. The node's children are then added to the local queue for firing, and the process repeats. Whenever one thread steals a task from another, the webpage node corresponding to the stolen task has its border highlighted by the color of the thieving thread.

To try it it out, open your favorite website, paste the following code into the JavaScript console, and hit the start button:

var s = document.createElement("script");
s.type = 'text/javascript';
s.src = 'https://raw.github.com/lmeyerov/devnull/master/one-offs/worksteal.js';
document.getElementsByTagName('head')[0].appendChild(s);

Alternatively, copy the following into your URL bar and hit start after it loads:

javascript:(function(){var s = document.createElement("script"); s.type = 'text/javascript'; s.src = 'https://raw.github.com/lmeyerov/devnull/master/one-offs/worksteal.js'; document.getElementsByTagName('head')[0].appendChild(s); }())

For this version, make sure you browser doesn't strip the "javascript:" at the front.

The animation shows several important things for parallelization. First, the same thread will run many tasks that are near each other, which indicates good spatial locality. The evidence of this occurring is that many regions of the webpage will share the same color. Second, steals are infrequent, which keeps overheads low and again highlights locality benefits. This shows up in the page as very few stolen nodes (colored borders). To measure it, the per-thread percentage counters at top show the ratio of stolen nodes to non-stolen ones, and on most webpages, I get a pleasingly low 5% miss rate. Finally, you can see a problem with the algorithm: the steal rate spikes at the beginning and end of a tree traversal. I made a simple optimization to the initial traversal -- I do a short sequential BFS traversal rather than immediately start with parallel DFS -- but did nothing here for the end.

My layout engine actually uses a novel semi-static work stealer rather Cilk-style dynamic work stealing. The reason is that Cilk does not account for temporal locality, which is important in situations such as multiple traversals over a tree because they revisit the same nodes over time. With Cilk-style scheduling, which thread a node lands on can easily change across different traversals, which is a huge hit. Instead, my approach is to use work stealing once to partition the tree, and then reuse the precomputed schedule across different traversals: load balancing suffers a bit, but temporal locality goes up.

Enjoy!

Monday, Monday, Monday! Dissertation Talk

2013-05-03T21:11:00.000-07:00

About time.

---

Your message for list eecs-announce has been forwarded to editor(s):

[Dissertation Talk] Parallelizing the Browser: Synthesis and Optimization of Parallel Tree Traversals

Speaker: Leo Meyerovich
Advisor: Rastislav Bodik
Date: Monday, May 13th, 2013
Time: 3:30pm
Room: 373 Soda Hall

ABSTRACT:
From low-power phones to speed-hungry data visualizations, web browsers need a performance boost. Parallelization is an attractive opportunity because commodity client devices already feature multicore, subword-SIMD, and GPU hardware. However, a typical webpage will not strongly benefit from modern hardware because browsers were only designed for sequential execution. We therefore need to redesign browsers to be parallel. This thesis focuses on a browser component that we found to be particularly challenging: the layout engine.

We address layout engine implementation by identifying its surprising connection with attribute grammars and then solving key ensuing challenges:

1. We show how layout engines, both for documents and data visualization, can often be functionally specified in our extended form of attribute grammars.

2. We introduce a synthesizer that automatically schedules an attribute grammar as a composition of parallel tree traversals. Notably, our synthesizer is fast, simple to extend, and finds schedules that assist aggressive code generation.

3. We make editing parallel code safe by introducing a simple programming construct for partial behavioral specification: schedule sketching.

4. We optimize tree traversals for SIMD, MIMD, and GPU architectures at tree load time through novel data representation and scheduling optimizations.

Put together, we generated a parallel CSS document layout engine that can mostly render complex sites such as Wikipedia. Furthermore, we ran data visualizations in the browser that support interacting with over 100,000 data points in real time.

Parallel Parsing isn't Hard (Or, Parallel JSON via Web Workers!)

2013-04-07T15:54:00.000-07:00

Generalized parallel parsing is hard. Many a Ph.D. has been burned by attempting parallel parsing. Guy Steele wrote papers about it, and you'll find custom ones for favorite modern technology X for X = JavaScript, HTML, XML, etc. However, in practice, practical parallel parsing does not have to be so hard because parallel parsing research generally focuses on extreme cases. For example, our group examined automatically generating parallel parsers and handling arbitrary HTML.

Actual parallel parsing is easy. Real applications provide significantly simplifying assumptions. Case in point: for our browser-based big data visualization framework, we needed to somehow load in big JSON arrays. Modern browsers provide a fast native function "JSON.parse :: String -> JSObj" that is fine for normal sized data sets, but parsing 9MB of sparse data takes over 1s, which requires a loading screen and eats your battery. The solution took ~2 days: on the server, split the data into multiple arrays, and on the client, use web workers to parse each array in parallel. Even though I'm controlling the parsing in JavaScript, the actual parsing is still being done natively by calling into JSON.parse for handling each fragment.

Anyways, the proof is in the pudding. The relevant benchmarks are impact on file size and load time.

Benchmark 1: file size

Splitting one of our sparse JSON data files into multiple chunks has no real hit to the file size, and due to some uninteresting phenomena, actually helps when gzip is used. I'm also showing the benefit of compressing repeating zeros ("sparse json") for our particular data set.

Benchmark 2: speedup

For the second benchmark, I'm testing loading the data set from a local hard drive when using different formats. The first two columns are sequential data formats, and with the second column primarily demonstrating the benefit of doing preprocessing for my particular application. The blue part of each column shows, in ms, how much time is spent reading the file from disk and parsing it.

The important part is comparing the blue of the third column against the blue part of the second: using workers to parse JSON chunks is 2x faster than parsing the file in one sequential go.

For further parallel speedups, it is important to realize that this application hit Amdahl's Law. In particular, the sequential stuff, like the black subcolumns, must be parallelized. The blue columns also have sequential code due to APIs I'm using. First, Safari does not have zero-copy message passing (transferable objects), so a sequential copy is made in communicating a parsed fragment back to the master. Second, I'm actually creating a big typed array, so even current web worker APIs do not help: I want to the Buffer into the worker, not get a new buffer out of one, which means I have to do a sequential copy even in Firefox and Chrome. Basically, we're seeing the web's poor support of message passing forcing a lot of slow, sequential copies.

Finally, I only benchmarked the case of local file loads. Our application, ultimately, will be used online with a server providing the data on-the-fly. The optimizations I showed should still help even if the application is network bound: they also enable pipeline parallelism. By splitting the JSON, parsing one chunk is now done in parallel with downloading the next. Modern webpages alternate between waiting on the network and the CPU, which this solution elegantly addresses.

Conclusion

So there you have it -- parallel parsing, in practice, should be easy. I did a constrained case of handling big JSON arrays. Even for more general JSON, it should only take a day more of work: partition the JSON via work stealing -- I successfully did a similar thing in my thesis for HTML in a few hundred lines of C++.

If you'd like the code, it'll be part of our Superconductor (automatically GPU-accelerated web programming framework for big data visualization) release next month. Ping me if you'd be interested in working on parallel parsing of arbitrary JSON -- it should be awesome!

UPDATE

I more carefully measured the overheads and also did a couple more optimizations. The chart below shows the new results. It also now includes the message passing overheads in gray, where ~90% of it would go away in Chrome with transferable objects and the other 10% might be eliminated with ownership transfer of buffer views (sub-buffers), not just buffers.

Two big things are going on:

The workers now perform decompression rather than the master. However, decompressing in the worker has a cost: each worker now returns an inflated result message. Safari does not have ownership transfer so almost 100ms is spent copying the message back to the main thread rather than passing a pointer.

The overhead is still worth it -- the blue region shrunk a lot, even if there is now a big gray region. (The gray region is in both because the sequential job runs in a worker in order to avoid pressuring the UI thread.) If/when Safari gets transferrable objects, 90% of the gray bars will disappear.
Faster reduction of worker results into the final GPU buffer. Typed arrays support method set that can also help such reductions. It acts like a memcpy, so result.set(chunk, len) copies array buffer "chunk" into array buffer "result" starting at byte offset "len" into "result." It only takes about 13ms. If the typed array spec was extended so that disjoint sub-buffers could be transferred across workers, the other 10% of the gray bars would disappear.

Adoption-Oriented Languages

2013-01-26T20:34:00.004-08:00

Language design decisions should not just increase adoption but also exploit adoption. For example, I just measured how popular languages can rely upon Stackoverflow as a code assistant. The chart below shows that increased language popularity on SourceForge (x axis) leads to faster answer times for questions asked on Stackoverflow (colored bins on the y axis):

Stackoverflow Time-to-Answer vs. Sourceforge.net Language Popularity. Raw data grabbed a stackoverflow query that modifies G. Winker's, and language rankings from our previous analysis.

Top 10 languages have questions answered within 5 hours over 80% of the time, but for languages worse than Top 50, that shrinks to only 50% of the time. In terms of a simple blocker at work, that's a big deal: you can reliably ask a question, go work on something else, and come back to the answer!

Of course, measuring response time vs. popularity is up to interpretation: it could be that as adoption increaess, people ask easier questions. However, I suspect the chart is actually undercounting the adoption benefit: the more questions are answered, the more people don't need to wait for answers because they can just search for old ones! As one measure, we see that a language's popularity relates to its answer corpus size:

Stackoverflow Answer Corpus Size vs. Sourceforge.net Language Popularity. Same dataset as above.

I had to switch to a log-scale axis for answers! For popular languages, search becomes a valuable tool because Stackoverflow alone provides a FAQ of 100,000 solutions. An enterprising individual might want to further examine the duplicate rate, which I suspect would provide an insightful indicator for the likelihood of a query already being answered by a previous response.

Open source library repos are another case of a feature that improves with adoption: the library of builtins is ever expanding. Likewise, one of my favorite research projects is cooperative bug isolation, which exploits the adoption of a program to help narrow down causes of bugs. (AFAICT, most software companies do some form of tracking error and performance dumps.) A/B testing for feature design is also increasingly common. As another example, in academia, code completion tools are also increasingly incorporating corpus-based solutions. A corpus can provide more value than type and namespace based solutions because, for example, synthesized code completions will resemble what people would actually write.

I started sketching out the notion of adoption-oriented language design in a position paper last week. I struggled to think of features that couldn't be designed to strengthen with adoption. For example, verification, testing, security, program synthesis, and optimization could all be designed to automatically exploit adoption of either the language, the library, or a program. What strikes me is how little adoption is exploited today. Outside of the cases, am I missing any that are commonly practiced, or should be?

Superconductor Language in Action: Easy Big Data Viz in Your Browser

2013-01-20T19:43:00.000-08:00

Exciting news: we'll be talking about Superconductor at the O'Reilly Fluent conference! This will be the first time we show it outside of small seminars, and will hopefully coincide with our open source release. This video proposing our session gives a feel for what Superconductor can do. The link skips right into the demo:

The basic idea is that you write a normalish webpage (HTML5, JS, JSON, CSS) for including and manipulating your big data viz, except:

Instead of relying up on the browser to run it (parse, layout, render, & animate), you load in our GPU-accelerated JavaScript libraries for the heavy lifting. Behind the scenes, we automatically exploit workers, WebCL, WebGL, etc.
Instead of using JavaScript for fancy layouts, you load in a widget made with our declarative layout DSL (or use it to define your own). Our parallel program synthesizer automatically finds the parallelism in the widget specs and our code generators output GPU code based on it.

We're finally ramping up on a paper with the end-to-end system details; this will be the first time we discuss running inside of a commercial browser and using GPUs. Papers have a ridiculous delay period, so of you'll be at SIGGRAPH (LA), PPOPP (Shenzen, China), or Intel's TechFest (Portland), you'll be able to catch a demo before then.

Reactive Objects and Arrays via Direct Proxies

2012-12-26T19:10:00.006-08:00

Arrays are a crucial building block for programming. Consequently, an essential question for functional reactive programming is how to react to imperative array updates. Designing a clean interface gets bogged down in issues like identity, API consistency, and efficient incrementalization. I used a recent extension to JavaScript, Direct Proxies (Firefox-only), to sketch a transparent dual-mode model (JSFiddle) for Flapjax. I made a reactive array interface that covers the entire Array interface and supports both instant and batched updates. A fun holiday break from Superconductor :)

Update: I generalized the code in two ways: it works with object instances and also allows choosing whether the prototype is Array or Behavior.

Transparency

The idea is to create a reactive array that is tied to an existing normal array:

var arr = ['init'],
var arrB = bindB(arr);

From then on, interactions with one array are automatically reflected from one to the other. (In particular, arrB uses arr as its backing store and proxies interactions to it):

// assert(arr[0] == arrB[0]);
arr.push('a'); // assert(arr.length == fxArr.length);
arrB.push('b'); // assert(arr.length == fxArr.length);

By defining traps for JavaScript's meta-object proxy protocol, I guarantee that all of JavaScript's array methods are supported by the reactive array arrB. All in all, for normal JavaScript, it should not matter if you pass around arr or arrB: they act on the same underlying data.

(Full transparency might be wrong. I'll raise a semantic issue at the end about what if you *do* want to distinguish reactive arrays vs. flat ones using operators such as instanceof.In my implementation, I let you pick as an optional parameter to bindB.)

Functional Reactivity and Instant Reactions

Now the cool thing is that array mutations can be automatically reacted to using normal functional reactive programming constructs.

For example, we can declare a live counter of the array size:

insertDomB(arrB.liftB(function (av) { return av.length; }));

The above snippet is the usual functional reactive code that is a joy to read. It displays the length of the array. Whenever arrB updates, the GUI will automatically update to show the correct length.

The new ability here is that wrapped array mutations automatically trigger reactions:

arrB[30] = 20; //updates length counter on screen

arrB.push('hello'); //updates length counter on screen

I'm calling these instant reactions because each mutation registers an update event. In the above statements, two update events will be fired, one for each statement.

The original array and reactive array refer to the same data, but differ on how they interact with the event system. Updates to the original array do not trigger reactions:

arr.push('world'); //no screen update

Maintaining non-triggering behavior of the original array is important so that non-reactive code not ready for the extended behavior does not trigger massive DOM updates. In places where it is safe to do the switch, arrB can be swapped in.

Batched Reactions

A nice pattern falls out of the wrapped and unwrapped view of the array. When many updates to an array should happen, we can batch them for a single subsequent response:

function addSome(n, arrB) {

//batched update

for (var i = 0; i < n; i++) {

arrB.last.push(i);

}

//notification

if (n < 0)
arrB[0] = arrB.last[0]; //updates length counter on screen

}

addSome(10, arrB);

The "arrB.last.push(i)" calls trigger no reactions, while the assignment to arrB[0] triggers an instant reaction. This pattern of silent array updates followed by an instant reaction on the reactive view is a batched reaction. It is largely an optimization, but if you create local invariants inside the body of addSome, you can also use the pattern for (non-nested) transactional reactions.

Object Instances and Meta Protocols

In response to Shriram's comment, the technique here is a late-bound dual to his work in making legacy classes reactive. For Racket's class system, he showed how to make a reactive subclass: the case of arrays would act like "var myArrB = new ArrayB(1, 2, 3); assert(myArrB instanceof Array)". The dual problem examined in my post is where an instance of a class must be made reactive ("var myArr = [1,2,3]; ...; var myArrB = bindB(myArr)"). It is an important practical distinction because the developer writing "var myArrB = bindB(myArr)" might not have control over "var myArr = [1,2,3]" nor "...".

His connection is important for two reasons: it provides a principle for how bound arrays should act (as subclass instances) and, more generally, shows that the same approach can be used for making object instances reactive.

1. Design principle of subclassing. Given an array, his connection tells us that reactive version should act as a subclass of Array. As seen above, this works for methods like push and [] (get). However, the desired object protocol behavior is not obvious. For example, should "assert(myArrB instanceof Array)" succeed? By the subclass reasoning, yes!

Unfortunately, setting myArrB to be an instance of Array breaks introspection within the Flapjax library. To add dependencies to an object, Flapjax checks whether it can register event listeners. For example, "liftB(function (v) { return v.length; }, myArrB)" triggers a check "arg2 instanceof Behavior": if myArrB is an Array and not a Behavior, Flapjax will not register listeners on it! Some examples still work, such as "myArrB.liftB(function (v) { return v.length; })", because the check is elided. For now, I support two constructor options:

var xB = bindB(arr);
assert(xB instanceof Array); //indistinguishable from Array
xB.liftB(function (v) { return v.length; }); //only supports chained reaction

var yB = bindB(arr, true);
assert(xB instanceof Behavior); //distinguishable from Array
yB.liftB(function (v) { return v.length; }); //chained reactions

liftB(function (v) { return v.length; }, yB); //and as arguments

The non-default constructor is more readily distinguished from an Array, and Flapjax uses this ability to out-of-the-box to to react to it. If code consuming "myArrB" does not need "myArrB instanceof Array", I suggest the second, non-default form.

2. Generalization to Objects. The motivation of this post was to handle array instances, but as Shriram implies, those are a special form of object instances. We get the simpler case of objects for free!

var o = {};
var p = bindB(o);

insertDomB(DIV("o has x: ", p.liftB(function (v) { return v.x ? true : false; })));
//display shows false

p.x = 1; // o.x == 1 and display updates to show true
delete p.x; //o.x == undefined and display updates to show false

The code snippet above shows creating a reactive view of an object. The original object is the backing store for the view, and edits to the reactive view automatically trigger DOM updates. As with arrays, when reactions occur can be controlled by choosing to edit the raw object or the view.

Conclusion

Via proxies, I was able to make imperative arrays play nicely along their entire API with our FRP library and support both instant and batched/transactional updates. You can play with this in Firefox via my JSFiddle. There is more to do (for example, the direct proxy API precludes behavioral indices like fxArr[secondsB]), but the flexibility of this approach is handy.

APPENDIX

var arr = ['init'];
var fxArr = bindB(arr);

Google Tech Talk Video on Socio-PLT: Quantitative and Social Theories of Programming Language Adoption

2012-11-29T12:40:00.002-08:00

My Google Tech Talk on the Socio-PLT work was recorded and posted. It starts with the quantitative stuff + questions on it, and then switches to the social theories: pick your poison. Enjoy!

Temp URLs for Flapjax documentation

2012-11-28T11:42:00.005-08:00

The Flapjax server is a bit wonky right now, so if you are looking for online documentation, check out the following:

Of course, you can always check the git repo for the latest.

Hope that helps!

What Women Want

2012-11-22T13:34:00.004-08:00

Trending on Quora is the question, "Which programming language is the most female friendly?"I do not know (I can provide primary sources who will verify this), but based on our survey of 802 men and 154 women, I can answer which languages females prefer over males. To learn how to think about these questions, see my recent Google Tech Talk or the links below.

Gayle presciently suggests that "Python is also a no-no because, I mean, you just named a language after a snake. Ick! And, I mean, do I need to call out the Freudian imagery there?" Go Gayle -- there is indeed a 3% drop! However, despite Gayle's insight that "All women love shiny objects," that does not help Ruby. Our numbers show a 7% drop for Ruby, so Ruby's bad press might be representative.

Overall, we saw little difference among the top 10 languages known by males and females. The ordering is fairly stable, and overall knowledge is similar (see the pink trendline). A few language jumps stand out: C, PHP, C#, and Ruby drop for female knowledge, while Excel rises.

If you're curious, check out our methodology, more of our statistics and raw data, and what a language designed for women might look like. Long story short, for the above statistics, we had good respondents: mostly educated, mostly employed, and biases because we polled students taking a free UC Berkeley online Ruby course on software as a service.

Asymptotic Productivity of a Language Feature

2012-11-03T21:00:00.000-07:00

Good news: our big data visualization DSL has a new name (Superconductor!), runs in a browser, and even more unusual, a per-feature asymptotic analysis.

We built a synthesizer for Superconductor that automatically maps widget code down into parallel algorithms, but synthesis isn't magic: the more you want it to do, the longer it has to run. Synthesis is essentially a search that automates manual thinking a programmer would have performed. This introduces a new way of thinking about the benefit of language features. Features have a cost, and instead of being in runtime complexity, it is now in compilation speed, which is arguably a formal proxy for developer time. The new language design question is how to tame these costs by isolating them, and when pricey features are still desirable, how to provide levers.

Consider two of the following features in our language:

Automatic full tree traversals. For a particular top-down parallel traversal over a document, what parts of the (declarative) computation can be safely mapped into it? Not forcing the programmer to figure this out ends up being O(A^2) in the number of static object fields being computed. It took a bit of work (iterative refinement and topological sorting), but well worth it!
Automatic subtree traversals. Sometimes, different parts of a tree have different types of data dependencies. For example, text in CSS is represented as a subtree of the document, and several computations over it are inherently sequential such as line wrapping. The tree traversal that encounters text does not need to be sequential, however: for each traversal, we can run different types of subtrees with different types of traversals, and thereby exploit parallelism within some subtrees and even by running disjoint subtrees concurrently. The feature to automatically infer subtree traversals blows up in the number of types of nodes (classes). Basically, each partitioning of the classes is a different way of statically characterizing a different subtree (and matched with a traversal type, a prospective parallelization scheme).

Synthesis is fast enough that automatic parallelization of full tree traversals are effectively free. However, specializing for per-subtree traversal schedules is only fast for programs with few types of nodes. Subtree traversals are useful in practice (such as if you enjoy stylized text on a webpage!), so we still need to support it. What is a language designer to do?

Deprioritization. Of parallelization can occur without using a slow feature, it will. In this case, the search will look for a full tree traversal before trying subtree ones. O(A^2) asymptotics are actually preserved, even if the full tree traversal is impossible: if there is no full tree traversal, we guarantee there is no subtree traversal, and therefore can stop compilation and terminate with an error. Enumerating all parallelizations will reveal a subtree traversal if it exists, this will not be exercised during most development.
Sketching. We use sketching for targeted opt-in prioritization of slow features. If you know the third tree traversal of the algorithm should use subtree traversals, say so, and even better, give a hint as to how to group the classes. If you do that, synthesis will still handle mapping individual computations into the traversals, including the subtree ones, and compilation is still O(A^2)!

Asymptotics of synthesis is an intriguing way to characterize language features, and perhaps a step towards representing developer effort. It defines how much is 'unsaid' in a precise way, how hard is the 'exercise for the reader'. There is still more to be desired -- the asymptotics is subject to the synthesis algorithm and translation of the features into it -- but I found it to be a neat, and an insightful indicator for productivity.

Quantifying Social Influences on Language Adoption

2012-08-31T09:17:00.005-07:00

Average influences for picking a language at work

As alluded to in the previous post, Ari and I have been hard at work at quantitatively analyzing how programming languages get adopted -- or fail to. For example, the above chart shows that for commercial projects, social factors (open source libraries, legacy code, and familiarity) matter much more than language support (correctness, simplicity, development speed, tools, language features, ...). This chart is also fascinating because we see that developers act differently depending on the company size.

Check out our draft "Social Influences on Language Adoption" for more fun charts where we performed and analyzed large surveys and also looked at 10 years of the SourceForge repository with over 200,000 projects. As another example, we validated some of our suspicions in the sociology survey that DSLs can be understood in terms of competing niches (e.g., popularity comes from spreading to other niches, not being the best in the niche). We'd love comments! More is in the pipeline -- we'll be releasing the raw data and also a small writeup about the methodological hazards we had to circumvent for this type of research.

Socio-PLT camera-ready and a glimpse at the next step

2012-07-27T16:22:00.002-07:00

Our Onward! 2012 draft about matching problems in programming languages to social theories about adoption made a stir -- and solicited some great comments. We're cleaning up the camera ready, so if there are any final comments, we'd love to incorporate them for the 'final' print version. It's a controversial topic!

As a follow-up, we've been doing some heavy quantitative analysis of extrinsic (social) and intrinsic factors in language adoption. These charts should give you a taste:

Fig 1: Factors in Picking a Language for A Recent Project

Fig 2: Language Popularity on SourceForge.

The first figure is cool in that it shows that social factors are more important than intrinsic features when picking a language. Language designers are community builders.

The second figure starts questioning the social structure. Popularity, city populations, etc. often follow power laws, and therefore growth gets modeled by some intuitive generative processes. However, SourceForge for ~200,000 projects followed an exponential curve. What type of processes can make more sense there?

Anyways, hope the camera ready looks good and the quantitatve analysis sparks thought :)

Synthesis over Parallel Patterns: A Leap Beyond Parallel Frameworks, Types, and Annotations

2012-07-06T11:54:00.002-07:00

We've been struggling with explaining the theoretical PL parts of our language research, but I think we're finally circling in. Basically, we found attribute grammars OK for defining the functional behavior of CSS and simple enough for running basic compiler analyses, but the formalism is poor for programming over the parallel patterns used for efficient runtime evaluation. That's where our language extensions for synthesizing over parallel patterns comes in.

Synthesizing over / into parallel patterns breaks down to three high-level issues:

The low-level language of patterns. The low-level language has to thoroughly express how our crazy-optimized tree traversals can be used. Think of it as the assembly language for parallel algorithms.
The usable high-level language. Writing in assembly sucks. Unlike traditional higher-level languages, which suffer from leaky abstractions, ours is a superset of the low-level one: you can always pick the right level. We do this by adding the simple notion of a hole. Assemble the patterns where and how you want, but whatever patterns are inferable or unimportant, just leave a hole and let the compiler figure it out.
The compilation technique for going from the high-level pattern language to the low-level one. I'll try to give a more detailed explanation in a future post. In a sense, our algorithm is a form of CEGIS (counter-example guided inductive synthesis) that searches over ways to complete a partial program. Every time there is a potential candidate, it checks if any input would trigger a bug in the candidate, and if so, prunes out this and any other completion with the same sort of breakage. Ours is a bit cooler than usual because we have a domain-specific constraint solver, use symbolic counter examples ones that give asymptotic progress on the search, and we get a queryable debugger for free. All for another day :)

First, however, a recap of our use of attribute grammars for the functional specification language, all of which sits besides the pattern specification language.

Background: Attribute Grammars

The functional behavior in our language is specified with attribute grammars. For example, to define CSS, you'll say the width of an HBox is the sum of its children. That says nothing about when it is evaluated. Later, via our pattern specification layer, you can control that as well. In theory, other logical specification languages other than attribute grammars can be used, all the way up to your traditional favorite imperative language (see Sketch). However, the road from attribute grammars is clear, with most other alternative surface layers adding a painful indirection.

A traditional attribute grammar would let you declaratively define the horizontal box layout widget as follows:

HBox -> Node Node { HBox.width := max(HBox0.minWidth, Node1.width + Node2.width); ... }

Under our extensions (object-orientation, loops, etc.), we would instead write:

class HBox (paintRect) : Node attributes: input minWidth var intrinsWidth children: childs : [ Node ] constraints width = max(minWidth, intrinsWidth) loop childs: intrinsWidth = fold 0 .. childs[i - 1].width

Hopefully the mapping is intuitive. Our extensions are nice, for example, because we support lists of children. Instead of making an awkward NodeList tree schema with a traditional grammar, you can just have a list of Nodes ("childs : [Node]") in our modernized form (think EBNF). In the end, after some compiler translation, it's the same thing. After reductions, traditional AG compiler checks ensure that every variable is assigned exactly once (well-defined and non-ambiguous spec) and can generate a schedule that orders the assignments. Code generation (e.g., of a layout engine) is a direct step after getting the schedule.

In the example, our compiler realizes the width of an HBox should be computed after the loop. More subtle, when and how to perform the loops is determined as well. For example, this grammar defines a tree where some nodes have interface Node, such as HBox ones. The width of these nodes will be computed in a bottom-up or inorder traversal over the entire tree: for an inorder traversal, the compiler would insert a "recur" right before the computation of "intrinsWidth." Writing loopy code in our language is cathartic for this reason. You just say a statement occurs in some loop, and the compiler will figure out in which loop and when, and reason about both local loops over the children of a node and global loops over the tree.

To learn more about attribute grammars and our use of them for layout language specifications, I previously wrote about our declarative looping construct and an early experience in mechanizing CSS's automatic table layout specification.

The Low-Level Pattern Language

Our conceptually deep extension really starts with being able to express this new fragment:

schedule: (bottomUp ((HBox (intrinsWidth width))) ) ; ??

I'll get into the "??" bit later, but some of the low-level language shows through here: a bottomUp (parallel postorder) tree traversal. Both bottom up and inorder tree traversals are valid passes for laying out any tree in this widget language, so our declarative pattern scheduling construct lets you pick which one. Most layout languages have many passes: if there was another class in this language, whatever pass comes after the semicolon would presumably handle whatever it needs to solve.

Our schedules are expressive and fine-grained. The one above says exactly what attributes will be solved in the first bottomUp pass. Furthermore, the compiler will check that these attributes really will be solved in such a traversal. This is great if someone changes code elsewhere that has a non-local impact on the dependency structure, which is quite common in practice. The patterns can be complicated as well, such as using a (sequential) inorder traversal for some subtrees while doing an overall parallel bottom up, so help with reasoning about dependency validity is huge.

The amazing expressive bit about parallel pattern languages comes next, however.

High-Level Pattern Language: Declarative Scheduling with Holes

Imagine our HBox widget is being added to a parallel library. There might be some other traversals that happen after, but we want to guarantee that it will solve in the first one. The sequencing operator ";" runs one pattern after another. Powerfully, instead of saying what pattern to use next, we leave a hole, "??". It might be instantiated as another pattern, say "topDown", or even another composition of patterns, say "topDown ; bottomUp". The synthesizer will figure out what is valid. These can quite non-obvious. For example, we repeatedly found inorder tree traversals that sequentialize a computation can often be eliminated. Instead, a global parallel (topdown or bottomup) traversal is run, and only certain subtrees will be run as sequential subtraversals.

Holes can be anywhere (see the last line of the grammar above). If we don't care at all, we might replace the entire schedule with "??". More commonly, we'll specify something like that a bottomUp should be first and then trust the synthesizer to compute the right attributes in it: "(bottomUp ??) ; ??".

Not shown in the grammar above, and generally only rarely exploited, arbitrary Prolog expressions can actually be used to constrain the holes. For example, the schedule may be one where the last traversal is an inorder one that makes sequential rendering calls. Writing "?? ; (Inorder ??)" is incorrect because it presupposes there is a preceding traversal. Prolog, for all its oddities, ended up being a great for such constraints.

Synthesizing over Parallel Patterns

The above declarative pattern language let's us automatically use efficient parallel patterns with details where you care and holes where you don't. Synthesis over parallel patterns is powerful and expressive leap over say "@parallel" loop annotations in C++, map/reduce/etc. skeletons in cloud computing, and type-directed data parallelism in Haskell:

Our synthesizer finds complicated parallel pattern usages. Not discussed, it doubles as a parallelism inspecter/debugger. (Topic for another day: the algorithms under the patterns, such as my cool semi-static extension to work stealing that gives temporal locality and drops overheads).
Our synthesizer automatically generates code to exploit the parallelism based on an orthogonal specification. No need to group code in the spec based on the parallelization scheme!
Our low-level pattern language lets programmers communicate to each other and the compiler the precise parallelization scheme.
Our high-level pattern language (holes via synthesis) lets programmers communicate at an arbitrarily high level. Combined with the above, we get some very different styles of parallel programming: sometimes we roll in the mud, sometimes we don't.
Our synthesizer checks and rejects invalid schedules. This is good both when designing the initial code and especially essential when maintaining it. Editing someone else's parallel code is normally terrible: now we can both precisely learn about and check against the previous versions!

It'll be fascinating to see if the community can get such declarative schedule synthesis for applying patterns beyond the tree traversal scenario. For example, I bet most graph computations (e.g., stencils) can have their level of abstraction similarly raised through our basic model.

Socio-PLT: Quantifying Language Perception

2012-06-06T15:36:00.005-07:00

We finally released our interactive visualizations for exploring programmer beliefs about programming languages. We've been scouring several large data sets -- 10 years of SourceForge repo data, mass surveys of thousands of programmers each, etc. -- so visualizations like these help us get a grip on what's going on. Beyond revealing many surprises, such as static typing anti-correlating with code reuse, they are fun to play with.

Check it out! (Animations are fastest in Chrome/Safari)

Socio-PLT: Principles for Programming Language Adoption

2012-04-08T18:47:00.007-07:00

Ari and I are getting ready to send out our first paper on socio-PLT, the sociology of programming languages. We've been performing qualitative and quantitative analysis of language adoption, and I've been thinking about how to apply sociological principles to the design of my own languages. This paper 1) overviews some of my favorite cases that I gleaned from reviewing relevant sociology research over the past few years and 2) connects it to programming language design, both in the scientific design of existing features and the principled and creative design of new ones. Basically, it shows how understanding results from sociology can influence your approach to language design :)

I just put up a draft and would love comments. I suspect the paper may be controversial, but I would like it to be so for the right reasons :) Did we misrepresent anyone or leave out any awesome case studies? Was anything belabored and boring, or terse and tantalizingly vague? This is still in the draft state, so we have a lot to do and would appreciate feedback :)

Socio-PLT: Principles for Programming Language Adoption

Why does one programming language fail and another succeed? What does this tell us about programming language design, implementation, and principles? To help answer these and other questions, we argue for examining the sociological basis of programming language theory: socio-PLT.

This paper presents a survey for programming language adoption principles drawn from various sociological fields. For example, many programming language features provide benefits that programmers cannot directly and immediately observe and therefore may not find compelling. From clean water to safe sex, the health community has long examined how to surmount similar observability barriers. We discuss how principles and techniques drawn from social sciences such as economics, public health, and historical linguistics relate to programming languages. Finally, we examine implications of our approach, such as for the design space of language features and even the expectations of scientific research into programming languages.

Looking forward to your thoughts! (draft pdf)

Languages for Bad Programmers

2012-03-10T00:18:00.007-08:00

Bad programmers are linguistic victims and good programmers are masochists.

Brett Victor is going viral with an inspiring video on language and tool design (and philosophy). The language community has actually already made some strong strides in the directions he wants. Some of my favorite research is in tangible programming, live coding, and omniscient debuggers.

Patrick Lam picked up on something else. As part of Brett Victor's philosophy that every code artifact should be directly (physically) manipulatable and understood, Brett believes requiring indirect manipulation and indirect understanding to be language design flaws. In particular, programming should not require mentally simulating an abstract Von Neumann machine that steps through your program. Not everyone agrees: Pat observed that, on the list of signs of being a bad programmer, the very first warning that you are a bad programmer if you cannot "run the program in your head".

Here's the thought. What would a language for bad programmers look like? Looking at the list of hacky "bad" programming practices, can you imagine a future where language and tool support will advance enough that they're the acceptable norm? The "bad" habits actually form an admirable set of goals for the language research community:

Warning sign: Cannot simulate the program in their head.
Goal: Get the computer to do the simulation.
Warning sign: Have a poor understanding of the language's programming model.
Goal: If I make basic grammatical mistakes when I speak, people correct me -- why doesn't the compiler?
Warning sign: Chronically poor knowledge of the platform's features. Symptoms: reinvent language and framework code, "Email me teh code, plz" messages on forums, etc.
Goal: Instead of viewing code copying as a bug, it's a design goal: I suspect *most* code today is duplicated, so I look forward to the future where the emphasis is on searching and synthesizing code rather than learning and writing it.
Warning sign: Struggle to comprehend pointers. Symptoms: failure to implement a linked list, allocates arbitrarily big arrays, inability to find pointer arithmetic bugs, etc.
Goal: raise the level of abstraction so programmers don't have to think about these issues.
Warning sign: Have difficulty seeing through recursion.
Goal: Thinking concretely should be fine, and the tools should walk you through the base cases and generalization.

You can apply similar reasoning to the category of "mediocre programmers" and, my favorite, "pinball programmers". Pinball programmers struggle with edge cases, or simply do not care. They can be a security disaster. Again, however.... so what? These types of problems are exactly what we built computers to solve: rote grunt work.

The shocking conclusion of the bad programmer essay is the signs that you shouldn't be a programmer. If you cannot determine the order of program execution, cannot think abstractly, poorly organize your code as an ever-expanding ball of mud, believe the code and runtime are unreliable, or simply don't care about much of the code quality, you shouldn't be a programmer. Hogwash! If these traits are required for programming, our ability to write code that keeps growing in ambition by magnitudes seems doomed. I can fairly neatly bucket these warning signs as inevitable programming realities (massive and concurrent code on unreliable hardware) and goals ("search, don't sort"; declare what instead of how).

Maybe the programmers aren't really all that bad. It sounds like today's languages are the stupid ones.

(Updated 1/26/2013 with minor editing.)

Loop synthesis: more declarative than functional programming?

2012-03-07T20:57:00.004-08:00

As part of the FTL language, I've been playing with the idea of declarative loops. For example, I'd like to write:

for i in range(0, n):
b[i + 1] = g(a[i]);
a[i - 1] = f(b[i - 4]);

First, the synthesizer should figure out that the problem is under-constrained. It should report that the following values are undefined:

a[0..2] = ??
b[0] = ??
a[n] = ??

If, as suggested by the synthesizer, I refined the program to be consistent:

a[0..2] = 0
b[0] = 0
a[n] = 0
for i in range(0, n):
b[i + 1] = g(a[i]);
a[i - 1] = f(b[i - 4]);

I'd like to get:

a[0] = 0
a[1] = 0
a[2] = 0
b[0] = 0
b[1] = g(a[0])
b[2] = g(a[1])
b[3] = g(a[2])
for (int i = 3; i < n - 1; i++) {
a[i] = f(b[i - 3]);
b[i + 1] = g(a[i])
a[n] = 0

Note that the synthesizer performed loop peeling -- it figured out to do loop peeling to emit assignments for b[1], b[2], and b[3]. Furthermore, it reordered the assignments in the loop and performed loop skewing -- it changed the indices of the assignments, such as from a[i - 1] to a[i], to ensure an array value is written before it is read.

Milind and I just worked out most of the theory for this today. You can think of it as a generalization of attribute grammar synthesis to loop code. Basically, if we assume the input code is singly assigned -- array values should have one unique value -- this is a matter of unrolling the intermediate steps of the loop, scheduling their dependency graph, and reconstructing the Von Neumann-friendly loop. The weekend may be busy :)

A fun question is whether a functional program could declaratively handle the above. For example, it could expand the for loop into a dependency graph and then use demand-driven evaluation. However, there are two problems. First, the interpretation of indices would have to change: my code correctly skewed the loop indices to make sure "a[i - 1]" and "b[i - 4]" are never negative. Second, the loop would be unsafe: in my approach, the synthesizer can statically check that the array is fully defined. Either way, traditional functional languages force programmers to explicitly handle these (arguably) low-level loop details. Go synthesis!

Modeling language experience report: synthesizing CSS's automatic table layout solver

2012-03-04T15:37:00.012-08:00

Table rendered using an automatically synthesized layout solver.

Model-driven languages handle complexity in implementing a language. For example, after designing a language feature, you want it to work with the optimizer, parser, IDE, etc. As the language gets more complicated, such as we've seen with the increasing scope of the CSS layout language, the implementation burden gets so high that many seemingly small language extensions and tool improvements require understanding a lot of the eco-system. With modeling languages, we can use synthesizers and code generators to correctly write features, avoid duplication of work, and basically handle more code than you could manually. For example, we don't want to manually teach the Firebug debugger about CSS semantics nor, when parallelizing for multicore or SIMD hardware, do we want to manually look at every edge case in the layout specification.

We picked attribute grammars as the basic specification language for our parallel browser layout language work. However, this begs the question: are attribute grammars expressive enough to actually handle layout languages?** Previously, we wrote (and automatically parallelized) various visualizations, so we know attribute grammar can be used for future languages. We're now going after the elephant in the room: CSS. As a fun start, Ras and I just put together an experience report about our successful experience with synthesizing an implementation of the 'automatic table layout' specification.

In short, it works. The table above was rendered using an automatically generated layout engine. Furthermore, our synthesizer found a multicore implementation for it. Neat :)

Stay tuned for more and we'll welcome any challenge problems :) Props to Ras, Matt, and Sam for help in revising that report!

**: More specifically, can we do this with statically scheduled attribute grammars? I'm distinguishing against 'demand-driven' and other approaches that essentially reduce to the Turing tar pit via general lazy functional programming.

Rich macros in ANTLR grammars

2012-02-06T22:44:00.000-08:00

For the lastest extension to FTL, my declarative user interface language, I wanted to add some code sharing abilities: traits and file includes. These are purely syntactic AST transformations but tricky for tools like ANTLR because the transformations are non-local.

For example, I wanted to be able to write the following code in FTL:

trait ChildCount {
attributes {
var numChildren : int;
}
constraints {
loop boxes {
numChildren := fold 0 .. $-.numChildren + 1;
}
}
}

class HBox(ChildCount) : Node {
children {
boxes : [ Node ];
}
attributes {
var render : Scene;
}
constraints {
render := text(10, 10, numChildren, #FF0);
}
}

Desugaring would eliminate the traits through a global transformation. In this case, it yields:

class HBox : Node {
children {
boxes : [ Node ];
}
attributes {
var render : Scene;
}
constraints {
render := text(10, 10, numChildren, #FF0);
}

attributes {
var numChildren : int;
}
constraints {
loop boxes {
numChildren := fold 0 .. $-.numChildren + 1;
}
}
}

(I'm glossing over hygiene etc. for the purposes of this post).

I got a fairly good start based on these posts.

Eventually, I realized I had two problems:

Given a usage of a trait (as a parse tree) and the trait's expansion (as a string), how do I make desugared parse tree? While it may be possible to do the expansion earlier (e.g., lexing), this is a cleaner step. For example, the error handling is better: we get clean parse errors for the unexpanded form (e.g., trait was not found or is in the wrong place) and for bad expansions (e.g., the trait references an identifier unavailable at its point of use).

How do I incorporate the new parse into the semantics actions associated with the parser? For example, if the parser counts the number of nodes, it should be of the final desugared parse tree. Counting the original nodes would be wrong, as would the sum of the original + new.

The final solution was pretty simple at heart:

First, I told ANTLR to store the traits:

Trait :
'trait' id '{' body[false,null] '}'
{ traits.put($id.text, $body.text); }
;

Second, I used a tree rewrite rule that replaces uses of traits with subtrees that are programmatically constructed in a semantic action through invocations of sub-rule parser methods:

classTrait :
'class' c=id '(' tId=id ')' ':' typeId=id
{
FtlClass cls = new FtlClass($cName.text);
String traitBodyStr = traits.get($tId.text);
}
'{' body[true, cls] '}'
{
CharStream inputstream = null;
inputstream = new ANTLRStringStream(traitBodyStr);
ALEParser innerparser = new ALEParser(new CommonTokenStream(new ALELexer(inputstream)));
CommonTree traitBody = (CommonTree)(innerparser.body(true, cls).getTree());
transferStatePost(innerparser);
}
-> ^('class' $c ':' $typeId '{' body {traitBody} '}')
;

The idea is that for a class using a trait, we lookup the trait (traitBodyStr), create a new parse subtree from it (traitBody), and replace it with a new subtree (righthand side of ->) that incorporates a programmatically generated subtree (traitBody).

A subtle but important practical point is that, for the programmatic call to a sub-rule parser -- body(true,cls) -- innerparser is a new parser with its own state. We can pass parameters to it such as (true, cls) or initialize the parser state to mimic the current one (e.g., duplicate the symbol table), and get them back out. In this case, I needed some post-parsing parser state, so I added my custom method transferStatePost to handle it.

Bonus for any compiler DSL writers: could you synthesize the tree rewrite rule from my example? :)

The fallacy of race to halt: power measurements from vectorizing webpage layout and binary search

2012-01-31T01:12:00.001-08:00

An important rule of optimization is that you don't know if it worked until you've measured it. Parallel algorithms research, until recently, has violated this rule. Researchers typically report speedup (old time / new time) or scaling (sequential time / parallel time), but that is wrong. The main reason we even care about parallel algorithms is that parallel hardware might provide more performance per Watt (PPW) if we use it properly. Otherwise, we should just turn up the clock rate and forget about it.

One of the most efficient forms of parallelism is SIMD, so I finally had a good opportunity to measure PPW vs. speedup for an algorithms paper we're finishing. For example, for our SIMD webpage layout algorithm performance (top picture), our 5x of speedup comes with an 8.5x PPW increase. Likewise, we sped up the binary search algorithm you learn in school by 15.8x and with a corresponding improvement on PPW of 13.1x. The biggest PPW wins were consistently from SIMD evaluation.

The surprise is that not all speedups improve PPW. We often assume work-efficient algorithms (parallel asymptotics do not dominate sequential ones) will, at worst, not impact PPW. Such "race to halt" reasoning is a good intuition, but even "intuitive" cases can break it. For example, take a closer look at our binary search results. Cache line blocking, a common high performance computing trick for better data prefetching, gives speedups for our binary search algorithm (both eager and optimistic speculative variants), but decreases PPW for the optimistic case. Measuring cache line blocking energy consumption clearly shows it hurts performance -- but based on speedup numbers and conventional wisdom, I wouldn't have bet that way.

Addendum: At a lab-wide meeting where I gave an impromptu talk about these results, a surprising discussion ensued. What performance numbers do we actually care about? For example, I originally reported the increase in performance per Watt achieved over 1 second (so improvement of # queries / joules in that time period). However, in many scenarios, if I changed 1 second to be the time for 20 queries or some other fixed amount, PPW could be very different. The machine might go into a power-wasting turbo mode for such a short time interval and PPW would plummet. Switching to performance per Joule (or total Joules for a task) has similar issues. So what are we optimizing for, really?

Note to self

2012-01-24T22:51:00.001-08:00

Note to self: remember to include the phrase "We are 4.9x faster than FAST, the recent binary search algorithm ..." into the paper rewrite.

Natbib for LNCS / splncs.bst

2011-12-30T13:44:00.000-08:00

It took me awhile to find this, but if you want to use \citeauthor, \citet macros from natbib, etc. for Springer / LNCS papers, use this package. If you aren't using these macros, you should: it will avoid heartache from misspelling author names. If you are not mentioning author names, this may also help put you into the habit.

\documentclass{llncs}
\usepackage[numbers]{natbib}
\bibliographystyle{splncsnat}

Springer, please fix this!

FTL: Fast Tree Language for synthesizing a parallel layout engine

2011-12-25T14:59:00.000-08:00

A radial layout widget declaratively specified in FTL being used to visualize file directory structure. Achieves 22fps through quadcore layout and GPU rendering. Check out the HTML5 version and source code.

We finally submitted a paper about FTL, our language for specifying layout languages and synthesizing a parallel evaluator. The paper is dense, so we'd appreciate feedback on what to cut and what to expand :)

Our systems goes all the way from a high-level language specification to an optimized browser layout engine. We had to solve two basic problems:

Strongly scaling the parallel tree traversals. Our specification analysis will take a language specification, such as for CSS, and find a sequence of parallel tree traversals that will lay out any document (the tree) in that language. However, we couldn't find any existing algorithms that would give you a 2x speedup on 2 cores, 4x speedup on 4 cores, etc. We ended up A) finding a mix of existing data layout optimizations (pointer compression, blocking, etc.) and B) inventing our own runtime task scheduler (semi-static scheduling that simulates work stealing to precompute a partitioning). Scaling plummets if you drop either. More fun, due to the locality benefits of data layout optimizations, we achieve superlinear speedups -- 9.2.x on 8 cores!
Generating the right sequence of tree traversals. While our system will automatically find parallelism in a declarative specification, it won't find all. For example, specifying how a box lays out its children by using absolute coordinates creates a global dependency, but specifying them as coordinates relative to the box and then stitching them together to get the absolute ones will break the dependency enough for our analysis. Programmers can write queries about the set of schedules inferable from a specification to help debug this sort of problem.

We found reasoning about schedules to be such a helpful programming tool that we incorporated it into our specification language. For example, it's very convenient to make rendering calls within a specification, e.g., "box(self.x,self.y,self.w,self.h,self.color)". The specification must take care to say what order to render boxes, such as the foreground text being above the background. Z indices are ambiguous due to overlap and monadically passing around the dependency is really painful. We can take a lesson from the current informal CSS standard, which specifies the document traversal order and then locally defines order within each node. Our solution is to allow functional specifications (the grammar) to be refined with traversal order constraints ("do rendering in an inorder traversal"). We can also catch specification changes that violate such a constraint!

Synthesizing schedules yields extra benefits. When synthesizing an implementation that talks to legacy code, this has the added benefit of making it easy to avoid parallel calls into non-reentrant libraries. Furthermore, many different traversals will implement the same specification: our synthesizer can generate them and autotune over them.

I'm working with some great undergrads to move forward on several fronts. At MSR, I wrote a proof-of-concept manual implementation that uses SIMD instructions for further speedups within a core: we're now automating it as a new FTL backend. Next, Thibaud Hottelier is writing a visualization language based on bidirectional constraints that compiles to FTL, which our undergrads are using to write some stunning demos. I already wrote one to animate inspecting file sizes on your hard drive (see picture above): we get 22fps for animating 20,000 files, and we should handle bigger data sets once I fix some segfaults. [For reference -- the HTML5 version is 8fps and, on my phone, 1fps]. Finally, we're pushing FTL's expressive limits by formalizing the CSS standard in it. Fun times ahead!

What to Implement

2011-09-12T12:40:00.000-07:00

A big chunk of the coding side of my thesis is writing a declarative spec of CSS and then automatically generating a fast/correct/instrumentable/etc. implementation from it. However, how much do I really need to implement? More generally, if you're making a tool to compute over webpage style, how much do you really care about? E.g., if you make a proxy-based layout optimizer, which features are important? Full compliance, ACID tests, etc. are often an overkill.

To help pick a subset to focus on, I ran a bunch of popular pages through my parallel browser skeleton and counted dynamic occurrences of CSS attributes. For example, if a browser or user defined style property is that images inside paragraphs get a blue border ("p img { border: blue; }"), and a gallery has 2 such pictures, that counts as 2 hits on feature "border".

For many features, the options -- e.g., blue vs. red, 10" vs. 20% -- are easy to handle. For others, the cases are a big deal: e.g., a table ("display: table") vs. word-wrapping box ("display: block"). So, for some of the more common features, I also broke down the cases.

The diagrams below show first the features and then, for a couple, the cases. It might be interesting to also do a log plot (power law, anyone?). Basically, you can get legible (but wonky) looking sites without much. To get pixel perfect... not so much.

**Note: this isn't terribly scientific. The sample size is small and on popular, professionally engineered sites. Likewise, many of the features are 'default' features set by the browser, and may even correspond to doing nothing. For a bigger scale, also check out Opera's MAMA analysis.

Advanced, Submitted... Time for new things!

2011-07-25T01:25:00.000-07:00

I passed my quals, and Todd Mytkowicz and I just submitted a fun paper on using SIMD instructions where you shouldn't. Maybe now I can start doing research again..

Particularly fun in our submission is a 4x speedup on a canonically sequential algorithm as well as some more browser hardware acceleration tricks. Weirdest yet, in our approach, the clustering ratio of how well you can relate objects in a data parallel computation is inversely proportional to our expected vector etc. speedup! Somehow, it all makes sense.

Sadly, we couldn't do our 2 coolest algorithms: one for legal reasons, the other because the vector hardware I have is missing a permute instruction. So goes.