Thank you very much.
Hi, everyone.
Thanks for coming.
My name is Philip.
I currently work at Apple on the XNU kernel.
I work out of an office that we have in London.
But in years past, I spent quite a lot of my adolescents
and adult life working on this hubby OS called Axel.
So I'll give you a quick demo now.
So you can kind of get a sense for what the system is like.
So this is a UEFI Rust bootloader that I made.
And then we boot into the system.
And we get the desktop environment.
So we can click around a bit.
Obviously it's running in QMU.
It's got a doom floor.
So you can play doom.
Cheers.
Cool.
We could look at some other system utilities like a numerate the PCI bus.
As you can see, there's like gooey toolkits.
Here's a file browser.
We can look at the kind of visualized virtual address spaces
of different processes.
Let's see what else can we look at.
So it's a micro kernel.
So everything's in user space including device drivers,
like the mouse driver and keyboard driver.
And these all communicate via message passing.
So as an example, we could look at like,
we could open a text viewer for this cogent interface.
That the keyboard driver is using to send events
to the wind manager.
Good look at some other stuff as well.
Here's a gameboy emulator that I also wrote in Rust.
All the text that you see on the screen is rendered using a true
type font renderer that I wrote in Rust.
And this is all running within this wind manager.
This desktop environment called Axel Wind Manager.
Now, in this kind of long list of stuff that I've put up on the screen
and pointed out, you'll notice that nowhere in this have I pointed out a GPU driver.
And there's a few reasons for that.
One of them is that it's kind of difficult to take a kind of,
you know, abstract system software component like a GPU driver
and then point to it in an official demo.
And then the other reason is that I actually don't have a GPU driver
in this operating system.
This is all rendered on the CPU.
And you might ask yourself, okay, so what?
You know, all the other stuff that I showed is all in software
when it comes to CPU, why is the wind manager,
why does that have any special considerations?
Well, it turns out that if you want to have this kind of environment
of, you know, kind of an interactive system with animations
and it's all quite interactive.
It can be pretty difficult to render all of this entirely on the CPU
while having a frame rate of decent and fast.
So this talk, as you might have seen, is kind of some of the things
that we have to do along the way to save work
and make this fast enough to be interactive.
All right.
So switching over to this kind of web-based slide deck here.
Yeah, so just to give you a kind of fuel-for-the-system,
axolose as a whole, meaning like the kernel
and then all of the user space stuff that I've written for it
is roughly on the order of like 100,000 lines of code.
And then this wind manager itself is like, say, 5,000, 6,000 lines
of rust, give or take.
This is a clipping of the source tree.
Again, just to get a sense.
So it handles a few things like the various state machines for
window management and communicating with applications
and kind of the window life cycles, kind of event loop stuff
or interacting with the operating system.
And then the core compositor itself, which is actually responsible
for pushing all the pixels and figuring out what to draw
and doing animations and that kind of thing.
Cool.
So conceptually, if you wanted to make this sort of project,
if you wanted to make a compositing desktop environment,
it's pretty straightforward conceptually.
We have this like classic metaphor of documents laid out
on the top of a desk, a desktop.
And we have these kind of this idea of like the spatial indexes,
like these documents are laid out in a stack
and they all have a z index and you can drag them around on the desk
and you can rearrange them.
By the way, all of the demos in this talk,
these are like live 3D renders.
I don't know what that B was, I don't think was me.
Cool.
And then the way that this works is the compositor itself,
Axel Windermanager has like a giant frame buffer,
that you know gets eventually rendered to the display
output device.
And that's like a big grid of pixels.
And then so it'll draw like the desktop background to that.
And then all the applications that have windows that are managed by the Windermanager
have their own frame buffers, which is like a shared memory channel
between the Windermanager and the application that owns the window.
And then when the application says, hey, Windermanager,
you know, I want to redraw my window.
I've got some updated content.
The Windermanager will draw like the window decorations
to the final screen frame buffer.
And then it'll take the frame buffer from that shared memory channel
and copy it in to wherever it should be on the desktop.
So this is really just like a specialized man copy with lots of like rectangle
mouth happening.
But there's a term of jarge, a term of art for this.
It's called blitting.
So the Windermanager does a lot of blitting of windows.
Cool.
So if you wanted to do this and kind of do it in the most simple way
just to start out with, we could have a pretty simple set up
where initially the compositor would draw the background to the screen
and then every frame it would like loop through all the windows
draw each of those and then finally draw the cursor.
And we can see kind of how this would work in practice.
So this now is the actual acts of Windermanager
kind of extricated from the rest of the OS compiled web assembly
and running in the browser.
So this is again like the real thing.
And if we start to play with it a little bit,
immediately we can see why this strategy kind of falls apart.
We're not doing anything to like clear up the contents of previous frames.
So over time we just get a corrupted frame buffer with a bunch of old work leftover.
And we can throw in some windows to kind of highlight this problem a little bit more.
So it looks all right, but clearly we've got some work to do.
And you can drag some windows around, resize them.
This is my jog, by the way, isn't it?
Just taper.
All right.
So one really easy way to fix this is just every time we draw a frame
just totally clear the canvas and start over.
And that works pretty well.
That solves the problem that we just had.
And we can throw in some more windows.
So really, this works, this works pretty well.
We could just stop here.
This is is perfectly good enough.
However, I've got about 15 minutes or so left in this lot.
So we're definitely going to have to figure something else out.
And really there is a problem with this approach.
This approach is actually probably the best you could do in terms of the ratio between
like effort to bugs.
It was really easy to do and it has basically no bugs.
But unfortunately, there's like a secret kind of third constraint that we're also going to worry about.
And that is this approach is extremely slow.
And this isn't really the way we like to do things and kind of the, you know,
hobby, operating systems world.
We like things to be really fast.
Take a lot of effort and inevitably have tons of bugs.
Because that's where all the fun is.
And we can kind of visualize the problem a little bit more here if I add in this frames counter
and then do some movie magic to make it reflect like this actual frame rate.
It works, but it's not super pretty.
We can definitely do better than this.
And there's a few reasons for why this is one which is kind of pretty easy to spot
is we might have done all the work to like render a window.
But then it ends up just completely occluded by another window in front of it.
And this problem of overdraw causes a lot of wasted work.
And we can quantify this overdraw.
So about this counter and the upper right here.
And you can see that like as I make these windows larger,
this overdraw counter goes up.
And that's because, you know, we're doing all the work to like render the background.
And then we just draw over it again with the window.
And if I drag a window on top of another one, the problem gets even worse.
Because we're going the background and then the southern window and then it all gets
occluded again.
And of course as I like close windows, if you look at our frames counter, it'll go up.
Because we're doing less work.
Okay, so how do we solve this?
This problem of drawing these occluded regions?
What we can do the math and figure out all right.
We've got all these windows, but what kind of portions of each of them are actually going to
wind up visible on the final desktop?
So if we think of a window, obviously it starts out.
The full thing is visible.
But then as we start adding more windows on top of it, we can kind of do this operation
where we like, you know, squeeze up all the rectangles and figure out exactly what portions
are still uncluded.
And we can recursively do this operation as we consider everything in the Z stack and keep on
shrinking these rectangles until we find out, you know, the final list of what's
going to be visible on the desktop.
And one optimization that we'll go ahead and do here now is if you do this sort of algorithm
naively, it's really easy to wind up with these rectangles which are like, you know, they
could clearly be merged into a larger rectangle.
And it pays off to do this because this operation of drawing these rectangles is like
our main bottleneck.
So we want to reduce the wasted work as much as we can up front.
All right.
So this operation sounds simple.
And to be honest it is, there's just a lot of kind of hairy edge cases to think about
and kind of deal with.
So here's just a gallery of some of the cases you might be in.
So like over here you've got, you know, you've got one visible frame that gets
occluded and split into four or can be split into three or it can be split into two or
isontally or two vertically.
That's not right.
So just a lot of kind of edge cases to think about.
And to deal with this, I kind of ended up writing a bunch of unit tests in this in this
repository.
So I tried to make it easy for myself to be like, okay, given this layout of windows on the
desktop, here's exactly the configuration of visible regions that we expect to end up with.
Which helped a lot while locking down the the business logic here.
All right, one last kind of optimization will make to this set up before moving on.
So the naive way to do this is we compute all the visible regions and then we've got a big list,
a big list of all the things that are visible on the desktop.
But one of the main operations that we find ourselves doing in the compositor is like,
okay, given this rectangle, say it's a mouse cursor or whatever, what does it intersect with?
And we do this so often that scanning through this list of rectangles becomes a really heavy operation.
And so we can pick a better data structure to kind of deal with this.
So there are these really neat data structures called like hard trees or spatial indexing,
which gives much better algorithmic complexity on answering this question of given a rectangle,
you know, what are the rectangles that intersect with it?
We go from like a logarithmic complexity to cubic in the naive setup.
And we know from like classical computational complexity that as we have more stuff on the desktop,
the difference between these two setups becomes more and more pronounced.
So you know, really pays off.
Cool. So now we're moving to a world in which we're doing this.
We're figuring out, all right, given all the windows,
but are there visible regions and then only drawing those.
So we'll go ahead and kind of move some stuff around,
so you can kind of get a feel for how this works and what it looks like.
We can do the same thing with just some slower animations.
Again, just to get a sense.
You can add some more windows.
And now if we, all right, so same thing again,
but I've thrown in some more desktop elements just to make this a bit.
Look a bit more realistic.
So as I say, this is not the full operating system.
This is just kind of everything is sort of simulated.
So this menu bar and the dock normally these are like their own applications,
running a new space, but here I've just sort of hacked them in.
But anyway, you get the idea.
And you can see that as elements,
like these shortcuts become occluded,
we see that, you know, we don't have to do anything to draw those,
and we don't kind of render these regions here.
We don't do the splitting rather.
That's the Z index changes, this all updates.
Now if we check our overdraw again,
first of all our frames per second has rocketed up
to a cool 11 frames per second, which is,
it's all right, but we've still definitely got some improvements we can make from here.
But this problem of overdraw has basically completely gone away.
So you can see that we've got 196 pixels being overdrawn.
And that's actually just the mouse cursor.
It's 14 by 14.
So we could do like the visible region splitting for the cursor,
but it's not really worth it.
We just accept a bit of overdraw for that.
But everything else as I stack windows and add more stuff in,
we don't get any more overdraw, which is great.
Okay, so moving on, thinking about kind of the life cycle of an application,
obviously windows are going to be rendering stuff over time.
They're going to have a frame, they're going to do some work,
they're going to have another frame,
and they're going to tell the window manager,
hey, please, please redraw me.
So we can think about what the compositor would do in this case.
So these are both kind of the final frame that's rendered by the compositor.
So here's the previous frame,
and then it re-renders everything with the new application frame,
and draws that to the frame buffer.
But if we look at this frame that we just drew,
the only thing that changed was this,
this we know in the middle,
all the other drawing that we did was just waste work.
Oops, and this is kind of going to be our next step
in terms of making an efficient compositor.
So previously what we were doing was this strategy up top,
where every frame would clear the screen,
figure out all the drawable regions, draw all of those.
But then in the new world,
we're just going to be everything,
we're just going to be iterating whatever rectangles
have been dirtied since the previous frame.
So this involves quite a lot of like different cues
and state management that we didn't really have to think about before.
I'm not going to walk through this all,
but just to give you a sense for kind of what this involves.
We've got, as I say, these per frame cues,
we've got these trees of like visible regions,
and then as I do these different scenarios,
you know, moving the mouse or a window
says it needs to be redrawn,
you change the Z index or whatever different cues
kind of get implicated,
and we'll need to deal with them in the render loop.
Okay, so let's start to try and build up a strategy using these
cues that will track our dirty regions.
So just as a reminder, this is the sort of a scene
we're going to try to be rendering.
It's not going to look like this at first,
but we'll build back up to it.
So we've got these cues,
but you can see them kind of down here.
But we need to figure out,
okay, when do we need to add something to one of these cues?
Well, one example that's pretty easy to start with
is whenever the mouse moves,
we know we're going to need to redraw the background
wherever the mouse previously was.
So we can do that here by adding this line,
you know, cue a redraw,
where the mouse previously was,
and that looks like this.
You can see down here,
and the list of background draws,
we're cueing background draws,
whenever I move the mouse around.
And we can check,
we can add back in our frames per second counter.
And yeah, so this,
we're getting like infinity frames per second.
So this is definitely going to work well for us.
Obviously we're not really drawing anything yet,
so it's going to go down,
but as a strategy, this is going to work great.
Now it turns out that rather than just drawing the previous mouse frame,
it is useful to union where the mouse previously was,
and where it is now,
so we can just go ahead and make that change,
and that looks like this.
Okay, now as we kind of looked at,
there's some windows on the screen,
but you can't really see that at all,
like they're here,
but obviously they're invisible.
The other reason for that,
is we're never telling,
we're never doing this operation,
of like recombuting where its drawable regions are.
So we can now that in next,
we can say,
these windows are animating in,
so we can say,
whenever we do an animation step,
recompute the drawable regions of,
you know,
everything that's been dirtied by the animation.
So that helps a bit,
they've got these drawable rectangles now,
but we still can't see them,
because we also need to tell the compositor that,
when we kind of,
when we dirty a region,
we need to redraw the stuff that's within it.
So that works okay,
but of course,
we also need to clear up the background in that space,
so we can do that now.
So we'll keep track of,
whenever a region has been dirty,
we'll keep track of,
okay,
what portion of the background is now unaccluded,
we're at this previously included,
and we can hue background draws for those.
And this is,
this is starting to look pretty good.
I mean things fall apart a little bit
when we like drag a window around,
but we're definitely getting there,
so we can keep going.
All right,
so now we can make it,
so whenever we drag a window,
we hue and update for the entire affected region of the drag.
All right,
we're getting somewhere.
I noticed now that if I click on a window
to change this the order,
nothing really updates until I drag the window around,
which isn't right.
I'm clicking this,
which maybe you can't really see,
but it's not popping to the front until I move it.
So we'll also need to make it
so when you modify the Z index,
that triggers an update.
And that's working pretty well now.
So one thing here is,
when you hover over the title bars,
we're supposed to draw these like icons,
which is kind of happening as I jiggle the mouse cursor over it,
and triggers some dirty regions,
but not as it should.
So we'll make it so when you move the mouse over a title bar,
we'll do a redraw there.
And now that's working well.
Cool.
So keep it going a little bit.
Let's add in some desktop shortcuts and see how that goes.
So you can kind of see a few of them here,
but the rest seem to be invisible,
and actually they will show up if I like it dirty them,
by kind of hitting them with another shortcut,
or something like that.
That's kind of silly.
Also they're meant to highlight,
as I drag the cursor over them,
and that's not happening.
So we can make it so,
in this kind of state machine of dealing with mouse input,
as I drag over the shortcuts,
they handle that, they get a refresh.
Of course, they still weren't popping up
like when the page is loaded, which isn't right.
So we can make it so when the shortcuts are created,
we'll also call them to get a redraw.
And now our shortcuts are looking good.
Okay, that's it.
So this is what we got to.
Actually, maybe I'll show that with the,
so you can see all these kind of dirty regions,
see what happens, click around a bit more.
So I change the Z index,
you can see things get updated.
Stuff can animate in and out,
and you can see the these kind of ghost rectangles,
everything that's happening.
So that's it. I've turned off that visualization of the,
the dirty regions now.
This is the kind of final state that we're going to get to in this,
in this talk.
We have animations.
And everything is kind of you can see it in these bottom cues here.
Everything is getting dirty,
as it should without needing to do any unnecessary rewards.
Cool.
So one thing I thought I would mention is,
over the course of writing this system,
it can be kind of annoying,
because you have to like boot up the operating system,
and anyway,
I made this mode in the compositor,
where any time I would do anything like spawn a window,
or like, you know,
drag anything around,
or move the mouse,
it would dump all the actions to a file,
which looks like this,
it's text file.
And then I made another mode in the compositor,
which could kind of take that file as input,
and simulate all the actions happening.
And then it would generate frames,
like every frame would be outputted to a file,
and then strung together into an animation.
And then that allowed me to kind of test that,
as I was making changes to the compositor,
I wasn't introducing any visual regressions
and what got rendered.
Because it turns out that,
when you're writing a compositor like this,
it can be really easy to like accidentally make the literature.
So actually, over the course of making this presentation,
I saved a few snapshots of kind of where things went wrong a bit.
So here's one example,
like,
this is where it's that.
It's these like rectangles showing the region that was dirty,
but I wasn't properly excluding them from getting marked as dirty.
So anyway,
just nonsense.
Oh yeah, so you get all kinds of situations like this,
where you kind of forget to redraw something quite right,
and often like the mouse cursor will kind of unstick it,
because that's a pretty reliable redraw this.
It can be kind of fun.
I don't really know, oh yeah,
so just another,
when no drags are broken.
There's a few of these.
Yeah.
All right.
So that's it.
Thanks for watching.
This presentation is up at AxelOS.com slash compositor.
If you want to try out any of these visualizations for yourself,
and then I've left a couple links to the AxelOS GitHub project there.
So yeah, thanks for your attention.
Thank you.
Hey.
Good talk.
I like all the optimizations.
You did to avoid redrawing unnecessary regions.
I was wondering,
I guess everything is running on a single CPU,
but now that systems are more multi core,
but it makes sense to come up this screen
and to multiple separations and have,
for example,
force it used for a corner each.
Or would they just complicated synchronization?
Or would they not try to insert just what?
Would it actually be beneficial?
Yeah.
I think that would be quite neat.
I mean,
the slow part is definitely still writing to the video memory.
One note about AxelOS in general.
It is like SMP capable,
so it can do multi core,
but it's single threaded in the context of a process,
which is just because I never got around
and do multi threading,
so maybe you have to deal with that somehow.
But yeah, you could do it in multiple processes if you wanted to.
As you mean, you had to come on there,
is perfectly multi-strading capable.
Based on your experiences writing composites put there,
a book performance quite a bit.
I mean, if you say the bottlenecks writing to the framework,
or if you instead of having one core writing to the framework,
or you have four core spreading to different regions of the framework,
is the memory subsystem going to be the bottleneck or the CPUs?
Yeah, I don't know.
I mean, you definitely get into the problem of like tearing,
because if you're having multiple processes running to it,
you still need some kind of synchronizations
to make sure you don't see like a midframe artifact.
I would say that if we were trying to make this faster,
the thing to do would definitely be to write a GPU driver,
and do this with GPU acceleration instead,
for the question of like making this faster,
maybe do it on the GPU.
I know this isn't what you asked,
but I'll just kind of word vomit it anyway.
I think that for writing a GPU driver in a hobby OS,
like this, you basically have three options.
You have target, like a really old GPU,
that is kind of well known in the hobby OS space,
and well documented, et cetera.
Target a modern GPU, or do like a paravirtualized GPU driver,
where like, I'm running this often in QMU.
And you have some kind of paravirtualized system
with QMU work, QMU helps,
and offloads the GPU on your behalf.
So I looked into the first option,
writing a GPU driver for like an old,
you know, well known graphics card.
And what I found was that all of these cards
aren't really interesting for my purposes,
because I want a high resolution desktop,
and all of these cards,
like I forgot what it's called,
like the Voodoo 3DFX something,
caps out at say 800p or whatever.
So I didn't want to do that.
I also didn't want to write a paravirtualized driver,
because that kind of gives up the illusion
that this is intended for real hardware,
like I often run it in QMU,
but in my mind, that's just for convenience,
and I don't really want to commit to having
a very different rendering path
in the emulated environment versus on real hardware.
So that leaves writing like a GPU driver,
you know, a modern GPU driver,
which I think would be a totally reasonable thing
for me to do when they do,
but they're just quite complicated,
and I never kind of got around to it.
Thank you for the question.
Thanks for the talk.
It was amazing.
Thank you.
So 25 years ago,
when we started,
I mean, before we started doing this,
composing approach,
we have been doing diagram,
but we do have a lot of different rendering
and good things, right?
Of course, if you have a powerful GPU,
there's no reason to go back to it.
But if you are going somewhere under it,
and what's wondering,
would it be possible to somehow combine these two approaches
so do the composing approach
in complicated situations,
and maybe switch to drivers,
put thinking some, you know,
one window is just changing something
But in this kind of solo homegrown project,
the biggest liability is me making mistakes
and me having tripling on some memory
or like the message subsystem isn't setting up
the shared buffers properly,
or I haven't clip the rectangles properly
and then I get memory corruption in some random who knows.
And so I definitely try to not bifurcate stuff like that,
but I think it would be a valid thing to try.
I guess hopefully you would get to a place
where the compils of an overhead is, yeah.
But if it's a partial rectangle for a framework
or you'll be staying through multiple areas,
like multiple, absolutely, yeah.
So it's more like one mem copy per row, right?
Yeah.
Thank you.
This resummed what I did for my talk, previous.
And the question is, is VBA dead by now?
You couldn't use VESAC acceleration infrastructure
Yeah, so I'm getting the frame buffer from VESAC,
but I'm not kind of using anything else.
Because it should provide you at least beater
which would speed up you.
And you can avoid breaking drivers.
Yeah, I haven't looked at that,
but definitely worth a look.
Thanks for the heads up.
I think I've got a, I've got a note that I'm out of time,
but thank you everyone.
Thank you for joining this video,
thank you.
Thank you.