[MUSIC PLAYING]
SPEAKER: The next two are by Evan Patton,
who is the head of the engineering
team at App Inventor.
And his first talk is on handling very large workspaces.
EVAN PATTON: Yeah.
So Eric emailed me to ask me if I
would be willing to give some talks here at the summit.
And I said, OK.
Yeah, I could do one on really big workspaces,
because we have some projects that are, like, 10,000 blocks,
and we've had to do a lot of optimizations
to make that work reasonably well.
And then I went, and I actually looked,
and I did not have a 10,000-block project.
So if you saw, in the schedule, the title was 10,000 Blocks.
But if you saw, at the top of the agenda,
it was not, because I realized [INAUDIBLE]..
So I'm just going to call my talk Exploring Blocky
Performance and Case Studies in MIT App Inventor.
So some of these may or may not apply to your own projects.
A lot of examples tend to be smaller workspaces.
And so most of the optimizations that we've done
may not really be useful for you.
But if you are looking to build a system that
is being used by people who are building
really complicated pieces of software with Blockly,
then, potentially, some of this will be useful for you.
OK.
So I just wanted to give a little bit of App Inventor
history.
So who here is aware of App Inventor?
A number of you are.
Oh, pretty much everybody.
OK, excellent.
So I guess I'll do the history real quickly.
So App Inventor started at Google in 2009
as part of Google Labs.
And then a number-- actually, Neil--
Mark is here.
Maybe a couple others were part of that team.
It was moved out to MIT in 2011 when
Google shut down Google Labs.
But it was also the inspiration for Blockly,
because, if you've ever seen the original App Inventor blocks
editor, it is a little bit more complicated than what
you can do today.
It required a separate Java process
to run on your computer to both interact with Android phone
and to render the blocks.
Now it's all done in JavaScript.
So in a way, we sort of catalyzed the need for Blockly.
Our mission is primarily education.
People use App Inventor to build real apps
that they publish in the Google Play Store,
but that is not really our primary objective.
Our primary objective is to help people learn about computer
science through app building.
And over the weekend, we just had our 10 millionth user sign
up.
So we're really excited about that.
And overall, we've--
[APPLAUSE]
Thank you.
We've had 42 million projects created with App Inventor.
And as of earlier this week, we had 623,000 active users.
That typically peaks around April and May.
When competitions like Technovation are happening,
we usually hit a little over a million users a month.
So we have a lot of people using App Inventor,
and we're interested in performance.
And why can I not go to the next slide?
So people build big apps with App Inventor.
So the largest are on the order of 1k blocks.
I'm going to show data a little bit later
in this presentation where we'll actually
see some of those numbers.
But these are not necessarily simple applications.
They're actually quite complicated.
And when you get to that size, there
are some interesting challenges.
So the first is that dragging tends to be kind of slow,
either when you're dragging the workspace
or when you're dragging individual blocks.
Sometimes collapse and expand is kind of slow.
We do have features for expanding all and collapsing
all the blocks.
In fact, we find that there's some performance benefits
to keeping blocks collapsed, which a lot of our users
tend to end up doing.
And then, of course, arranging blocks is slow.
So if you want to reorganize your code, for some reason--
often, people do this to do a printout or something,
because things like clean up blocks
will put everything in a nice, vertical, linear fashion
for printing.
And so sometimes that can also be slow.
And so we have a random sample of projects that I pulled out.
And so this is kind of the breakdown.
If you aggregate project count by number of blocks
on the bottom, you have number of blocks going up
towards a little over 1,300.
And then on the y-axis, you've got
number of projects in the data set with that many blocks.
And so you get this sort of typical power law curve.
But if you actually try to then represent that as a--
OK.
So on my screen, there is-- oh, there it goes.
There is this.
And you'll see, as a power law, if you
do the log on both of those axes, what normally you
would expect is kind of a straight line.
But it starts to really dip off around 300 or so blocks, right?
So for some reason, there is a lot
of significant resistance to people building projects
with more than 300 blocks.
And performance is one of those reasons.
There are others, which involve how App Inventor is
designed that I won't go into.
So a couple of caveats.
First, we have an older version of Blockly.
So some of these performance numbers
may not reflect changes to Blockly as of late.
And two things that we're really interested in
and how it's going to affect the numbers
are the new rendering pipeline, and how is that
going to change performance of our rendering system?
And also, how the connection database is being changed.
I saw Becca put in a couple of things about that.
So take some of the numbers I'm saying with a grain of salt,
because in a couple of weeks, they might all be different.
OK.
So we have two different methods that we use internally
for measuring these things.
So one of these is we have a package
we call Blockly Instrumentation, which
was written by Professor Lyn Turbak at Wellesley College.
And it allows us to basically measure
a whole suite of different features of App Inventor using
various debugging flags.
So we can collect performance measurements and all sorts
of stuff using this.
And it has flags for turning on certain optimizations
that we use.
I've covered all that.
Good.
The second that we use is the Browser Devtools.
So if you open your Browser Devtools in Chrome,
you can hit the Record button from the performance panel.
And then when you do, and you collect your data,
Chrome will give you this matrix looking thing.
And so what you have is basically
a breakdown of all of the different function calls
and everything that's happening when your block workspace is
being rendered.
And so this is actually--
I can't quite read it.
But it's over the course of about three seconds all
of this data gets generated.
So there's quite a lot of information here.
Of course, measuring the performance
does affect how fast it actually runs.
So things are always a little bit slower.
But it's a pretty good metric for how
things are changing as you make changes
to how Blockly's working.
So the first optimization that I want to talk about
is what we call Render Here, Render Down, which
is our replacement for the normal rendering mechanism
that Blockly does.
And so one observation that we've noticed
is a lot of people collapse their blocks.
And one of the benefits of collapsing blocks
is there's a whole lot less you have to draw.
So if we know that we can do an optimization here,
where, if we're collapsed, we don't have to do
any further calculations--
again, I don't know how this is going
to be affected by the stuff that Rachel presented this morning.
But, potentially, we can save a lot of computation time.
We're not touching the DOM as much,
which means that there's fewer slow operations that
are occurring.
And then, basically, the two operations are,
we render here, which is, draw the current block,
or we render down, which is, draw my descendent blocks.
And we can skip that last step in the case
of collapsed blocks.
So here's kind of what you can get.
So I loaded up four different projects.
The first two actually have the same number of total blocks,
except one--
the blue one-- is only 100 top-level blocks.
And the orange one--
I basically took the blue one and disassembled
the entire thing, and it has 1,200 top-level blocks.
And then the other two are 1,300 and 900 blocks, respectively.
And so on the left, you have the Blockly render performance.
And then on the right, you have the render down performance.
And so what we can see is that, whether you're
expanded or collapsed, we can actually still get
about four times the performance gains using
the render down mechanism.
And the important thing here, for us,
is that we want to try to get it at least under a millisecond
per block, which is this graph, where, if you've got 1,000
blocks, and you're spending a millisecond per block,
that's a whole second the user has to wait for a draw
operation to happen.
And if we want to get to 10,000 blocks some day,
that means we have to get it down to 0.1 milliseconds,
right?
So we still have a ways to go.
So we're not quite at the stage yet
where we think we'll have performant workspaces
with 10,000 blocks, but we are slowly
moving in that direction.
The next change that we did was around event optimization.
So there was this comment--
and this was talked about, actually,
at last year's Blockly summit.
Merge duplicates.
O of n squared, but n should be very small.
And what would happen is people would
organize their workspaces.
And if you've got a hundred blocks or 1,000 blocks,
that means that you don't quite have such a small n anymore.
And so even with just 100 top-level blocks,
you're still talking two orders of magnitude
more work than if you could do it in linear time.
So we actually rewrote that algorithm to be linear.
And that actually is already in Blockly core.
So if you're using a new version of Blockly,
you've got that already.
So the second we saw is in the connection database, where we
had a lot of issues with this.
So the invariant that the connection database
tries to manage is that all of the connections
are sorted by y position and then the x position
so that, when you're dragging, Blockly can quickly look up,
are there nearby connections to connect to?
And the way this is normally achieved, to keep this sorted,
is, Blockly removes and then re-adds the connections.
I don't know if that's true as of your recent changes, Becca,
but it might still be.
Of course, the problem is, is, if we
start moving a whole stack, or if we, again,
try to reorganize the entire workspace
as a single operation, then you're
moving all of the connections at once,
which, for those of you who are computer scientists
and remember back to your probably freshman or sophomore
computer science courses, this is basically insertion
sort, which is O of n squared.
So we introduced a new mechanism in App Inventor
for these types of operations where we can set a flag saying,
we're about to do a bulk update of the workspace.
Do not change the database at all.
And then at the end, we used the JavaScript array sort
function, which is running a native code
and will run an O n log n.
And so we can reduce the running time of this operation
from minutes down to seconds for really large workspaces.
And then the last piece is the mutator.
So for those of you who don't use mutators,
this will not affect you.
But one of the App Inventor users
had a create a list block with over 50 connections in it.
And whenever he opened the mutator,
it would actually take, like, a minute to draw,
for some reason.
And we're not sure why this originally was.
We had to do a lot of digging into it.
But there was this subtle O of n squared performance thing
that we managed to find.
I don't know if it's still in Blockly,
but it was definitely a problem for when
you had lots of mutations.
And so we, again, rewrote this to use a linear approach,
using our render here mechanism.
So we were able to drastically reduce
the amount of time it took to render the mutator workspace.
So just a couple of takeaways--
see what your users actually do, because it might surprise you.
One thing I didn't mention earlier
with the workspace rendering was that one person put, like,
thousands and thousands of blocks inside
of a backpack, which is kind of like the trash can feature
that was demoed earlier, where you can store
your blocks for later use.
And every time they opened the backpack,
it would take seconds to render, because it was doing this.
And they just stored thousands and thousands of blocks
in there.
I don't know why they decided to do it that way, but they did.
You don't know what you don't measure.
So using the Devtools, or using some sort of instrumentation
mechanism, can really give you a lot of insight
into how your application is working
and where the bottlenecks are.
And we're not quite at 10,000 blocks yet, but I expect,
as we continue to make improvements to App Inventor,
and as people want to build more sophisticated applications,
we'll be getting there, probably,
in the next couple of years.
So that's the end of the first talk.
Are there any questions?
Yes, Neil?
AUDIENCE: [INAUDIBLE]
EVAN PATTON: Some of them, yes, we have.
A lot of times--
so actually Lyn has a great paper
on this that one of his students and he worked on,
which is trying to detect patterns of block reuse
to basically infer when you could, say, use
a loop or a procedure to simplify
the structure of the program.
And, in fact, there are quite a number of cases,
both in novice users and in power users
of App Inventor, where they don't necessarily
take an optimal path.
They build something that copies a lot of code and things
like that.
And we think the reason for that is, basically,
because it's so easy to hit Command-C, Command-V
to copy a bunch of blocks versus actually
having to think through and restructure your code.
So one of the features we recently added to App Inventor
is generic event handlers, because it
used to be the case you'd have to have the same event
handler for every--
so one example was a Breakout game.
So somebody made the game Breakout.
You've got a bunch of bricks, and you've got a ball,
and it's got a bounce.
And they had a collision handler for when the ball hit
every single block.
But that was a design decision in App Inventor
that it was done that way.
So we implemented generic event handlers.
So now, that 30 plus set of blocks
can be reduced down to a single block,
because you have this way of saying, for any block
that I hit, run this code.
So there are definitely reasons for having such large projects.
Like I said, they're often, also,
because of design decisions in App Inventor
that we're working to improve.
But yeah.
Yeah, people do do that.
Yes?
AUDIENCE: [INAUDIBLE]
EVAN PATTON: Most likely, yes.
And we've come up--
AUDIENCE: [INAUDIBLE]
EVAN PATTON: Ah, perfect segue, because Rachel asked me
to demo something for you.
So let me do that.
We added a feature recently, as well, to App Inventor.
But I'm bringing up a test server,
just because it has something else that's really nice for me
to demo with.
So we added this feature recently
to allow for people to export blocks as PNG files.
For about five years now, I think-- four or five years--
we've had the ability to export the workspace
as a set of blocks.
But now, you can also do it for individual blocks, where
you can right-click, and there's this Download Blocks
as PNG feature, which allows you to just click on it,
and you get an image.
And then the other thing-- which,
I don't know if it works on a Chromebook, but I'll try it--
is that you can drag these into App Inventor,
and it will put them back into your workspace.
And so we've been working on things like, how can we
make the documentation better?
So for those of you building tools with Blockly,
this is kind of a cool thing where you can say, oh,
there's this feature, Make Generic, which
was about the generic event handlers I just talked about,
where you get some documentation,
and then I can say, oh, there's some information here.
And oh, these blocks are interesting.
I can actually just drag these into App Inventor
and instantiate them into my program.
And so it's a great way for you to build documentation
and things like that that can be pulled right
into your application.
And this, again, is one of these things where
we're making it really easy for people
to be able to copy and paste stuff,
because now it's just a picture you can put on a website
and drag into your app.
But at the same time, we are also thinking about,
can we make more sophisticated tools
to inform people when they're doing this,
and say, like, oh, that's kind of an anti-pattern.
You should consider doing something else instead--
to make them also think more abstractly about how
to apply what they're learning to their programs?
But that is kind of future work that we're
in the process of setting up now.
[MUSIC PLAYING]