Full transcript
0:04thanks so uh title slide all right yeah
0:07I'm Andrew Kelly I am the uh president
0:11and Lead software developer of the zig
0:13software foundation and uh thanks for
0:15coming to my talk so uh first
0:18thing
0:21um where am I pointing
0:27here pressing the Go Button
0:31not working
0:32no we're experiencing technical
0:36difficulties oh okay I'll press it hard
0:38and long there we go all right uh yeah
0:41just want to tell you a little B about
0:42my backstory uh I'm sure it's pretty
0:44familiar to a lot of you uh I became
0:46interested in games at a very young age
0:51and uh but my parents gave me a rule
0:54that I could only be on the
0:57computer or TV
1:00or video games for 1 hour a day it
1:03didn't matter what it was just 1 hour a
1:05day and then I was kicked off so
1:07needless to say I became very
1:10sneaky uh my first game was uh Sonic the
1:14Hedgehog 2 for Sega Genesis so this
1:16always has a nostalgic place in my heart
1:19um but my favorite games were the ones
1:21where you can make your own
1:23stuff does anyone remember Tony Hawk Pro
1:25skat or 2 they had that that level
1:27editor right that was the
1:30like this thing was so cool you can make
1:32your own levels you can put like the
1:33start points in there um you can even
1:36like make your own gaps name them give
1:38them points and then you could like play
1:40local multiplayer with your friends and
1:43uh and like play horse and tag and stuff
1:45it was super cool so when I discovered
1:49uh programming it's like the ultimate
1:51game right it's like make your own game
1:53that's ultimate power so yeah then I got
1:56into Visual Basic 6 I still love this so
1:59much right you open up the program and
2:02then just like any other contemporary
2:03program it gives you a new document form
2:06one just like how it would look like
2:09it's just begging you to just drag a
2:10button on there and make it do something
2:13right um so you know as I as I
2:16progressed I would you know I learned
2:18other languages learned Pearl python C++
2:21C and yeah I learned them in the wrong
2:23order uh just like everybody does and
2:26then um every time I looked at my own
2:29code
2:30even from just like a week ago I would
2:33always think it looked like garbage I'd
2:35be like yeah that code I wrote a week
2:37ago it's trash I've learned so much in
2:39one week right that was my experience
2:41for like 10 years you know every time I
2:44looked at my old code I was like I know
2:46how I can do it better but then it
2:48stopped right after you know about 10
2:51years of of
2:53experience I'd start to write code and
2:55then I go back and look at my old code
2:56and I think yeah you know fair enough
2:58like if I did it now just do it pretty
3:00much the same way like I don't really
3:02see any improvements I can make so um
3:06and you know part part of that whole
3:07process was you know learning like oh
3:09object-oriented programming that they
3:11teach us not quite right like you know
3:12you learn your own way to go you know
3:14but I still plateaued right at some
3:16point I hit this plateau and um but
3:19then something happened where it it
3:22started happening again and I'm in this
3:25phase right now where I'm looking at
3:26code I wrote four months ago and I'm
3:29seeing s again I got past the plateau
3:32and for me that was learning about data
3:34oriented programming so to get here um
3:37you know I watched a bunch of Talks on
3:39YouTube uh that's a pretty famous One in
3:43fact let me just take a little moment
3:45here I think I I'm going to do a talk on
3:48data oriented design I think I better uh
3:55[Applause]
4:03yeah that feels right that feels right
4:04okay anyway so yeah in order to get here
4:07I I I watched some talks you know um I I
4:09attended handmade Seattle three times
4:11you know talked to a bunch of people uh
4:14and then I read this uh data oriented
4:15design book by Richard Fabian um but it
4:19still took me a long time to get it like
4:22it just didn't click for a long time for
4:25me so my goal of this talk is that if
4:27you're here if you're where I was for
4:30this 10-year period of my life I want to
4:32help you like get over it with me uh
4:34like if if you have the same like
4:35learning model as me maybe I can like
4:37help you just like Fast Forward
4:39right okay so let's so let's do this
4:43what's a computer right the big picture
4:45if I run uh LS CPU on this laptop that
4:49I'm presenting with oh wait a minute
4:51we're doing it totally different than I
4:52thought just kidding if we run LS CPU on
4:55my main laptop um it tells us a little
4:57bit about it so uh 8 with hyper
5:00threading I got this amount of L1 cache
5:02L2 cache L3 cache what what does that
5:04mean um so here here it is in kind of
5:06like graph form so this is this is high
5:10level what the hell is a computer from
5:12the perspective of memory right and if
5:16you if you notice L1 has a very small
5:19amount of memory L2 has a little bit
5:21more L3 has a little bit more then main
5:23memory is huge right so there's
5:26trade-offs here l1's real fast l2's a
5:30little slower L3 is a little slower and
5:31Main memory is a lot
5:34slower so um just try to keep that
5:37little that picture in your head when I
5:38go on to this next slide here so we have
5:41um yeah thanks to it.com for this this
5:43chart and um if you're uh if you later
5:47just go look up this chart because it's
5:48super interesting and I'm only going to
5:49highlight a couple points here but what
5:52I want to point out is where where those
5:54L1 L2 and L3 are on this chart right and
5:57if you if you look over
6:00uh sorry wrong button this one so if you
6:04look over here every time we go down
6:05it's an order of magnitude right
6:07L1 really fast okay L2 order of
6:10magnitude L3 order of magnitude main Ram
6:12order of magnitude
6:14right and the other interesting point is
6:18that all this stuff there's there's so
6:21many things that a CPU can do that's way
6:24faster than reading from Main memory
6:26right so like in particular notice that
6:29the fastest thing you can do is math
6:31like math is faster than reading from
6:33memory so you can draw a pretty
6:36interesting conclusion from this which
6:38is like should you memoize results of
6:42doing
6:43math maybe not you might actually just
6:45be slowing yourself down by not
6:47repeating the math right and that
6:50includes multiplication right
6:52multiplication uh right there faster
6:55than faster than L1 read even right
7:00um and then furthermore if since you
7:03know we're focusing on memory here I
7:05want to highlight one more thing so
7:08kernel call is one of the slowest
7:10possible things on here and that's
7:12something that might happen if you call
7:13Malik right if you if you Heap alocate
7:16and uh to highlight um the talk on the
7:20the the Json parser that's that that cor
7:23that correlates right because they found
7:25out all all their in the first round it
7:27was Malik doing kernel calls
7:30that was taking the the performance down
7:31to this order of magnitude
7:35right okay so what's the takeaway here
7:38right the CPU is fast but main memory is
7:42slow so okay now we understand but how
7:46do we apply that like what do we
7:48actually need to
7:49do so we need to do more stuff on the
7:52CPU we need to do less stuff with memory
7:56we'll we'll drill down into that more
7:58but let me just one more big picture
8:00mental model help you out with this so
8:03try to think of it like whenever you
8:05need to do any memory access you're
8:07always going to go through a cach line
8:10always so the question is are we going
8:12to have to evict a cach line in order to
8:15do the job so let's say that I'm um
8:18storing something to
8:19memory each cach line is typically about
8:2264 bytes could be 32 could be 128 it's
8:25usually
8:2664 and that's that's the granularity
8:28that you have
8:30so if you're going to access something
8:32from you know this part of a 64 by
8:35chunk and then you want to access
8:37something from the same 64 by chunk
8:39that's good you're not going to evict a
8:41cash line but if
8:44you if you access something really far
8:47away you might require another Cash Line
8:49to get involved you're going to increase
8:51the chances that you evict one right and
8:54so the whole point here is just don't
8:57have cash misses that's the whole point
8:59point
9:02right so now I'm going to make this so
9:05you know my talk title is applying data
9:08oriented design in in practice right I
9:11want to help you do it like you know we
9:13all we all know we want stuff to go
9:15faster we want high quality code what do
9:18we actually do so here's one strategy
9:20you can use among many that you can that
9:23you can use to apply data oriented
9:25design okay think of your pet project
9:28think of the thing you're working on
9:29think about where you have a lot of
9:31objects in memory of the same kind like
9:34like a struct think about a struct that
9:36you have the most of in memory and think
9:38about how you can make it smaller that's
9:40the whole trick that's all we're going
9:42to talk about
9:44today so part two I'm going to do like a
9:48short lecture on uh how structs are laid
9:51out in memory and this part's
9:52interactive so I want people to like
9:53shout out don't feel um like you can be
9:56a smarty pants know at all don't worry
9:57just just go for it so every type in in
10:00programming like C Zig Nim whatever uh
10:03it has a natural alignment and a size
10:07and let's just go with some examples we
10:09do example based learning here so u32
10:12right 32 by integer uh what is the
10:15natural
10:17alignment four good and the size four
10:21okay good everyone's on on the same page
10:24um so let's go a little different all
10:26right aou natural alignment is
10:31and size
10:32is all right I had some different
10:34answers so alignment's actually one you
10:37can just load a a buol um with even if
10:41it's not aligned you can just load a one
10:42bite no problem one one alignment one
10:45size one all right next challenge a
10:48union with a u32 and a bu natural
10:52alignment is four I'm hearing fours and
10:55size
10:56is all right I'm hearing all correct
10:58answers
11:00yeah okay now instead of a union let's
11:02go
11:04struct natural lemon
11:08is oh I'm hearing some different answers
11:10size
11:11is I'm hearing
11:14eight so the alignment is the alignment
11:17of the biggest one which is the u32 and
11:20the size is here's how it works you
11:23start with each field and uh you add the
11:27size so we go from zero to four okay and
11:29we put the buol right there so now we're
11:31at five but now we're at the end so we
11:34have to go to the stru alignments we
11:35have to add three more bytes boom boom
11:37boom to get back to four so the answer
11:40ends up being
11:41eight okay all right let's keep going
11:44now we have a struct we have u32 u64 u32
11:49what's the
11:50alignment eight right and the
11:55size yeah you had to do math on that one
11:57yeah 24 right because the ALG lthm is
11:59start at zero we go four but then we
12:02have to go aligned so we have to go up
12:03to eight and then we put the 8 one in
12:06there we get 16 and then we put the four
12:08one in there we get to 20 but now we're
12:10not aligned yet we have to go four more
12:11to get back to eight alignment so now
12:12we're at 24 so just by moving these two
12:17fields around right we put the two ins
12:19in a row now what are we looking at
12:21what's the
12:23alignment same same alignment and the
12:26size yeah we went back down to 16
12:29now maybe your language is going to do
12:31this for you you know some languages do
12:33but that's not my point my point is on
12:35the computer there you know this is how
12:38it's going to work like if the language
12:39does it for you great but this is what
12:40the language is doing for you
12:44right okay I have one more let's put
12:46another Bo on there now where we at
12:50alignment's the same right eight how
12:52about the
12:54size oh I heard different numbers okay
12:56we're back up to 24
13:00yeah so this is wild right because abou
13:04is one like in information Theory Abu is
13:07one bit of information but we went from
13:1016 to 24 right we paid the cost of 64
13:13bits just to add one to the struct and I
13:17remember from Mike Acton's talk on data
13:20oriented design he was so mad about this
13:22Boolean that was an A struct in like uh
13:25like ogre 3D or something right I
13:26remember watching this and thinking yeah
13:29he was so mad and he did this like
13:30script that like printed out how many
13:31bits are being wasted or something and I
13:33was like okay okay I get it but like the
13:35hell am I supposed to put that state
13:37because I need to know if it's true or
13:39false like what am I supposed to do
13:41right uh so I'm going to try to answer
13:44that question um and so here we go into
13:47the next uh to the next section here so
13:51here are some strategies that you can
13:53use in practice to take a struct and
13:56represent the same information according
13:59to information Theory um you know you're
14:01not you're not losing any bits but
14:04you're reducing the footprint in memory
14:06of your struct
14:08right um so let's look at we'll get back
14:11to the bu one in a minute but here's
14:12another
14:13example here's a struct with some
14:15pointers okay so if we're running on a
14:1764-bit CPU uh we're looking at uh 32
14:20bytes right if we're running on a 32bit
14:22CPU we're actually only looking at 16
14:25bytes so you know interesting
14:27observation even those 64 that computers
14:30can uh you know have more
14:33RAM it by default they actually also use
14:36more RAM right because each pointer is
14:38double the size but there's something
14:41you can do just use integers so if we uh
14:46if we don't Heap allocate these objects
14:48if we have them in an array list for
14:50example and we use indexes instead of
14:52pointers to refer to them we've halfed
14:55the size of of the struct on you know on
14:5864-bit CPUs use so uh use indexes
15:03instead of pointers that's a trick you
15:05can use to have a smaller uh memory
15:08footprint now I have to say um oh sorry
15:12I want to make one more Point too we
15:13also reduced the alignment right we went
15:15the alignment went from eight to four in
15:17this case so if you wanted to add just a
15:1932-bit integer in a fifth field you're
15:21not wasting anything right because if we
15:23tried to add a u32 onto the other struct
15:26we'd be paying for four bites of padding
15:28here it's 4 by alignment we're not going
15:29to pay for that four byes of padding so
15:31that's another benefit okay but I have a
15:33warning which is watch out for type
15:36safety because in the pointer example
15:39you're going to get compile errors if
15:40you use the wrong type of stuff right
15:42you pass to a and you should have passed
15:44to B compile error if they're all
15:46integers with no types this is uh you
15:49know you've you've made debugging harder
15:52and you've made some possibly
15:53interesting uh bugs possible right so
15:57you have to watch out for that you know
15:58maybe your language has a distinct
16:00integers that will probably help um Zig
16:03doesn't have them maybe we should add
16:04them I think I think Odin has them there
16:07you go use Odin for this use case um I
16:10also would say uh if you um write this
16:14down go search the internet for handles
16:16are the better pointers there's this
16:18blog post by um flow of wo Andre Weiss
16:21flog um it's really good and so I'm I'm
16:24not I'm just telling you like here's
16:25something you can do I'm not telling you
16:27the details of like here's how you use
16:29integers instead of pointers this blog
16:31post will tell you here's how you use
16:33integers instead of pointers right it's
16:34the how instead of the like what right
16:37okay so there's that one we took a um
16:41what was our original size 20 32 bytes
16:43we got down to 16 with this example okay
16:47what
16:48else okay here's an example we're going
16:50back to that Boolean right um so we have
16:53a pointer we have two 32bit in we have
16:55that
16:56Bool uh so if we look at the size of
17:00this we're looking at 24 bytes right
17:02this is the same example 24 bytes on
17:0464-bit CPUs 16 bytes on 32bit CPUs lots
17:07of wasted bits um I did a little bit of
17:10you know math here so you can kind of
17:11get a feel for it if you had a 100 of
17:13these that'd be 2.4
17:15kilobytes so what this is where I was
17:18thinking like what can we do I need to
17:20know if the monster's alive like I can't
17:23just delete that field because I have to
17:24know what the answer is right so the
17:27trick is you can store that information
17:29somewhere else so by having two arrays
17:33instead of one uh you have all the alive
17:36monsters in one array all the dead
17:38monsters in another array now that that
17:40Boolean that that according to
17:42information Theory it's still there it's
17:44which array is it in right but according
17:46to your memory footprint it's gone so we
17:49went from uh we went from was 24 on
17:5364-bit CPUs to 16 right and if we do the
17:58other trick trick that I just mentioned
17:59and go to indexes we're down to 12 so
18:02this so here we go this is another trick
18:04we went half right we were at we were at
18:0724 now we're down to 12 instead of
18:09taking up 2.4 kilobytes for 100 monsters
18:11we're taking up 1.2 for 100
18:14monsters there's another benefit to this
18:16too which is that if you had a loop
18:19where you know the first thing you're
18:20doing in the loop is saying like if the
18:22monster is dead skip them right which
18:25you can imagine you would do in your
18:26game now you're just looping over only
18:29the alive monsters and before in memory
18:32you were touching that flag right you
18:34were looking you were doing a memory
18:35load of alive to see if they were alive
18:39right that could evict a cash line but
18:41if we only look at the alive monsters
18:44we're not we're not paying for that
18:46check there's no Branch there's no load
18:50and that's going to that's going to
18:52result in less cash
18:55misses so store booleans out of band
18:58that's that's the answer to the the
19:00question the part that I did not
19:02understand when I first watched Mike D's
19:04talk um okay here's another one I'll
19:07give you a second to kind of study the
19:09uh the struct layout here we're going to
19:10go with like the monster but I'm just
19:12going to keep swapping out the fields to
19:14just different ideas so again we have a
19:16pointer um now we have an enum that
19:18tells what kind of monster it is we got
19:20five monsters here or five animals here
19:23um and yes humans are
19:26monsters uh so in this example I did
19:2910,000 monsters and I did little
19:32calculation 160 kiloby for all this
19:35stuff
19:36right so let's look at how this is laid
19:38out in
19:39memory in memory we're going to have uh
19:44this is called array of structs right so
19:46at element zero we have all the fields
19:48of the struct and then before we get to
19:51element one we need element one to be
19:54aligned so we had to insert seven bytes
19:56of padding to get back to 8 by alignment
19:59so so that the struct so that element
20:01one could be properly aligned and then
20:03same thing for element two at the end we
20:05had to have more padding so that element
20:06two can be properly aligned so every
20:09single element is paying seven bytes of
20:11padding but there's a really simple
20:14trick you can do instead of having one
20:16array where you have the struct as the
20:18element you just have multiple arrays uh
20:21which each with each field as the
20:23element so this is called um struct of
20:25arrays so you know if your programming
20:27language lets you use a multi-array list
20:30for example that's a five character fix
20:34same same API and now the elements are
20:37right after each other right we have the
20:38pointer pointer pointer pointer those
20:40are all eight byes aligned no padding
20:42needed then we have enum enum enum enum
20:45those are all one bite remember one bite
20:48things don't need any alignment so we
20:50just eliminated the padding by putting
20:52them in different
20:54arrays so if we go back to our example
20:57this is the oneline fix we just use a
20:58different data structure and now we went
21:01from 160 kiloby for 10,000 monsters to
21:0491 kiloby right that's no joke that's a
21:07big savings just by eliminating the
21:11padding so eliminate padding with
21:13structive arrays that's a trick what
21:16else can we
21:17do all right here's another
21:19one so in this case we got a monster we
21:22got some HP some XY coordinates we have
21:24an array of them okay now we have this
21:26thing where each monster can have like
21:27four things that their hold you know
21:29maybe we use zero for empty or something
21:31like that um so I ran the script I ran
21:34the calculation so if if there was
21:3610,000 monsters this would be 366
21:38kilobytes including the array capacity
21:41overhead right the part where you over
21:42alocate all that stuff um and Al that'll
21:45become clear why we're now including
21:46that calculation in a
21:48moment let's say that we make a
21:51hypothetical observation so let's say
21:54that we for our use case we just happen
21:56to notice that 90% of monsters are not
22:00holding anything all all of their items
22:02held are
22:04empty so if we make this observation we
22:06can exploit
22:08it so now we take out we take out that
22:12field and we just store that out of band
22:14kind of the same thing we did with the
22:15Boolean right but now we're using a
22:17table so as long as we can use a index
22:21for the monster and that's the key of
22:22the hashmap we can just put that data as
22:26the value and now it's sparse and if we
22:29do the math and um I I did a whole bunch
22:32of scripts to calculate these numbers
22:33there'll be links there'll be like a
22:34gist link the slides at the ends you can
22:36check my work if you want um just just
22:38go download it later you can play with
22:40it but anyway so I I did the math with
22:4210,000 monsters we went from 366 to 198
22:45kilobytes including the overhead from
22:48these data structures right the savings
22:50are are there and and that's with with
22:52uh only uh 10% of monsters holding
22:55something and I also want to point out
22:58like we could have done different things
23:01you know maybe it's that most monsters
23:04are only holding one thing so then you
23:06would put that in the struct and then
23:07you'd have it the special cases for when
23:09they're holding like four you know you
23:11you can really uh choose to store the
23:15data according to what makes sense
23:17tically for your observed
23:22experience okay so store sparse data in
23:25hashmaps that's that one I got one more
23:27for you
23:29and this is kind of the the cool thing
23:30I'm bringing to the table here so um
23:33please take the time to to understand
23:35this a little bit because I think it'll
23:37be this is kind of like one of the cool
23:38things that I've I've done so I want to
23:40uh I won't make you like do too much
23:42hard stuff but let like this this one's
23:43interesting right so um I'm I'm going to
23:47give you 15 seconds to shout out how
23:51many bytes is the struct
23:592 what you got 28 any other guesses I'll
24:03tell you that's not
24:04it uh you might be forgetting that the
24:07union is
24:10tagged I heard of 32 okay that's that's
24:13that's right so the human struct is 20
24:16the B struct is one um there's a a
24:19tagged Union there so there's a tag
24:20right that's just an enum and then
24:22there's the the payload so 32 bytes now
24:25this is using a strategy where we use
24:27the same
24:29size for every monster right if we could
24:31put these all in Array and they all each
24:33element would take up 32 bytes exactly
24:35that has convenient properties um but we
24:39are paying you know if if we have a lot
24:41of bees we're paying for all those
24:43humans even for the humans that are not
24:45bees it's a funny sentence it's true uh
24:50okay so let's let's TR let's take a
24:51different strategy let's try organizing
24:53our data a different
24:55way so here I've actually take an
24:58object-oriented approach or I I guess
25:00you could just call it polymorphism to
25:02me those two things mean kind of the
25:04same thing but we've reorganize the data
25:07so that there's a base struct okay
25:09that's tag X and Y and then each uh you
25:12know specialization of it um just adds
25:15stuff so the B adds color and the humans
25:18add hat shoes shirt pants and heads
25:20braces right this is actually an
25:22improvement uh so if we do this we're
25:25looking at 24 down from 32
25:29right this is an improvement we we have
25:31used less mem in terms of how much
25:33memory is used for a a a a set of
25:36objects we have reduced the memory
25:38footprint through an object-oriented
25:40approach right but can we do
25:44better so take special note right now of
25:48all the state that we need to represent
25:50because on the next slide it's less
25:52obvious how all the state is represented
25:55but that is the point right so maybe I
25:57focus on um like has braces for example
25:59will be interesting and maybe like the
26:01color of the be right yellow black red
26:04so here we
26:06go so this is what I call the encoding
26:10approach and in this example there is a
26:13tag and there is some common data but we
26:17get back to the the um property that
26:21they all uh there's a there's a common
26:23amount of data that takes the same size
26:25and then there's uh sparse data stored
26:27externally we're kind of putting all of
26:30the the
26:32um uh lessons together for this one so
26:36you can see that bees there's no longer
26:37an enum for bees the the the color for
26:41bees is now extracted into the encoding
26:44tags likewise we have four encodings for
26:47humans so we've chosen to represent
26:49naked humans differently than clothed
26:51humans and we've chosen to represent
26:54humans with braces differently than
26:55humans without braces so that that has
26:58braces has disappeared into the encoding
27:00tag the B color has disappeared in the
27:02encoding tag you can see how we're we're
27:04kind of the out of Band theme is coming
27:07back right and so how this works for
27:10humans let's look at um human clothed
27:14like how do we know all the information
27:15for human clothed so in this case uh you
27:19know the the the the the monster is an a
27:22struct of arrays multi-array list right
27:24so we're not paying for padding between
27:26the tag and the common struct for a
27:28clothed human we're going to repurpose
27:30the oh I don't need a point I did it in
27:32the thing there we go so the the extra
27:34index can be repurposed depending on the
27:37tag so if the tag is human braces
27:41clothed or human clothed we know we have
27:44to look at the extra index field and
27:46then go look up the this struct inside
27:49this extra uh this extra thing so that's
27:51how this
27:53works um and then let's figure out the
27:55size
27:58so if you want to encode a b a b is 13
28:02bytes because you need the tag the
28:05common struct but that's it the color we
28:08could have put the color here but we
28:09didn't even use this we just put the
28:11color here so we even have you know
28:12extra data about the B we could store
28:14you know this is not a fully loaded
28:17fully efficient data structure I this is
28:19this is not optimized for memory
28:21footprint this is optimized for fitting
28:22on the slide like let's be honest
28:25right um so here's what this comes out
28:29to now in order to give you a number I I
28:32have to add more assumptions right
28:34because we we made the how much size
28:37stuff takes depend on you know the the
28:41actual thing that you have in practice
28:44so we have to make some assumptions in
28:45order to report how did we do right
28:47which is good because what we're
28:48learning is that by by taking in
28:52theistic information about your actual
28:54data you can create encodings that work
28:56better for you so here we have to assume
29:00equal distribution of humans and bees
29:03and we have to assume you know some kind
29:04of distribution of naked and clothed
29:06humans and I feel like a realistic
29:09distribution of naked and clothed humans
29:11is like half and half you know feel like
29:13that matches the world so uh let's do
29:15that that comes out to 17 bytes per
29:17monster so we went down from 32 to 17
29:21almost broke that in half Again by
29:23switching to an encoding approach and
29:26yeah I mean I think I made this point
29:27already
29:28but choosing codings according to your
29:30actual distributions right if if you
29:32know if half and half naked in clothes
29:34is not what you have pick something else
29:36like maybe most humans are just walking
29:38around with a hat and nothing else in
29:41which case you would want a human with
29:42hat encoded you know and then you could
29:44just put the Hat as the extra index and
29:47then you got 13 bytes for humans with
29:48Hats done
29:52right okay so that's the encoding
29:54approach and uh that's we're going to
29:56come back to that in in the next
29:57sections of this of the of the talk so
30:01um that's the five like lessons you know
30:05this that's the five strategies that I
30:07want to share with you and that that's
30:09it that's the take-home knowledge but I
30:11do have a case study so you know I did I
30:14did these things uh in the zig compiler
30:17and uh I just want to report my findings
30:19so that you know you know this is not
30:21just me you know at home just like oh
30:23maybe I can move the data around I tried
30:25it for real in a real project and I I
30:27will share with you the results um but I
30:29will say uh you know this guy is pretty
30:31cute but if since we're talking about
30:33performance uh we got to go
30:36fast so this is the um the pipeline of
30:39the zig compiler uh if it's it's pretty
30:44standard um on the very left hand side
30:47we have source code which is what you
30:48type into the editor right hand side we
30:51have machine code which is what the CPU
30:53understands um this stuff is logic so
30:57this is like implementations of doing
30:59stuff um this stuff is data right source
31:03code is data machine code is data um but
31:06we can't control what the source code
31:08format is or what the machine code
31:09format is machine code is specified by
31:12the hardware the source code is
31:13specified by the language specification
31:15but everything else that's compiler
31:18details we can just pick whatever data
31:20we want whatever data layout we want for
31:23this so all those principles that I just
31:25talked about we can apply them here
31:27that's a that's the core pipeline of the
31:30compiler so if this stuff actually works
31:32we would expect to see good results
31:35right uh I also just want to take
31:38advantage of the fact that I'm bothering
31:39to document this stuff just to explain
31:41that um everything to the left of this
31:43line is done on a per file basis doesn't
31:46matter what flags you pass doesn't
31:48matter anything like what the same
31:49source code results in the same Z data
31:53and on the right hand side of that we
31:55start to have to get more you know
31:56involved in the in the compiler stuff
31:58it's per function and when we start to
32:00get into code generation now we have to
32:01do something different for arm the x86
32:04you get the
32:05idea um I also want to foreshadow that
32:09uh this part here is embarrassingly
32:11parallel um so we'll we'll come back to
32:14that
32:15point and uh let's let's hone in on the
32:18tokens so let's go look at how we can
32:21apply these memory footprint reduction
32:23strategies to a real world project where
32:25our goal is to tokenize source code and
32:28output a list of tokens that can then be
32:31um used to parse for a
32:36compiler so I'm going to throw I'm going
32:38to throw a struct at you here um I'll go
32:43now we're not doing exercises so you
32:44know don't feel bad if you didn't like
32:46get it exactly I'm not going to ask you
32:47to try and calculate these this is uh
32:49more high level at this point but I'm
32:51just kind of reporting like so this is
32:53how it used to be right it used to be
32:55that you might recognize this right this
32:57is the tagged Union approach where
32:59everything's the same size um you can
33:02see that I uh got an enum there some
33:05there's some padding right this is me
33:07right now looking at my old code and
33:09being like oh now I see the mistakes
33:10again right so like there's the enum uh
33:13is there a Boolean here probably like
33:15why are we using 64-bit sizes why are we
33:17storing the line and column we can just
33:19calculate those you know like just I I
33:23I'm almost delighted with how bad my old
33:25code looks to me again finally right
33:29um so yeah to say it more sustin we can
33:32compute line and column lazily get them
33:33out of there uh another Point um let's
33:37make a reasonable limitation we only
33:39want to be able to compile 4 gigabyte
33:40source files or smaller if we make this
33:43limitation We Can Make a Better Faster
33:45compiler so let's use smaller amounts of
33:48memory to store
33:49those okay other point do we need to
33:52store the end position of a token in a
33:54compiler I mean we can just roken it
33:56again right we can just do a little a
33:57little bit of math again and avoid
34:01storing some
34:03memory um also like in the compilers
34:06tokens are just like asterisk slash or
34:09like the and keyword we don't even need
34:12to roken IE those we just know how we
34:13just know the end position based on the
34:15fact that it's the and keyword it's
34:16obviously three
34:19right um finally uh why are we parsing
34:24integer literals why are we parsing
34:25string literals during the tokenizing we
34:27we can just do that later it'll be the
34:29same cost but now we can make our tokens
34:31way smaller by not storing all this
34:33extra
34:35data
34:37um and then yeah so so here's the
34:40results right I I went through all all
34:43my own strategies you know it took my
34:45own lessons and we went down from 64
34:48bytes per token to five it's just it's
34:52just where is it in the file and what is
34:54it that's right there in the file that
34:56is what a zig token is now so yeah
34:59that's uh it's much
35:02smaller and we have a lot of tokens
35:04right you can imagine you know every
35:06identifier in your source code every
35:08asterisk every slash that's a token so
35:10every single one of those is taking up
35:12five uh five bytes instead of 64 when
35:15the compiler is doing its work so that's
35:18that
35:20one we're going to look at as next and
35:22then I'll show you a benchmark and then
35:24we'll go to the next one so okay as
35:27we're I'm going to show you another
35:28struct again so this is how it used to
35:30be um actually this is how it still is
35:33in the compiler that we ship today so
35:36this has not been uh fixed yet so to
35:41speak so this is again the tagged union
35:44strategy for the as nodes uh you can see
35:46I got a Boolean in there you can see I
35:49got an enum in there what are the lining
35:51column doing they just keep coming back
35:53like I just was so paranoid I was going
35:55to forget what the lining column of
35:56stuff was but you can just calculated
35:58lazily uh so yeah once again stop stop
36:03stop memoizing stuff I can calculate
36:06that uh right also uh I was also storing
36:11uh like like links to like where which
36:14tokens this this as node point2 and all
36:16these things you actually it's a tree
36:18structure so you only need to store one
36:21um that's less of a data oriented design
36:23thing and more of just I realized that I
36:25could calculate something again
36:28calculate something rather than
36:29memorizing it right this that's what
36:31this bullet point is
36:33again um and then okay the encoding
36:35strategy is going to come back now right
36:37so here we go I'll put up I'll put up
36:39the new one uh the new one is uh I I I
36:45did a I I wrote a little hacky script
36:48that ran the whole standard Library
36:49tests for both cases and just kind of
36:51counted up how many of them there were
36:53divided by the total so these numbers
36:55are pretty accurate actually um
36:58so this went from 120 bytes to
37:0015.6 average and you know it's average
37:03because the nodes now take up a
37:05different amount of size for each one so
37:08again um this is not what it is exactly
37:11this is optimized to fit on a slide um
37:13but it is the encoding strategy so you
37:16can see that there's uh a main token um
37:20all of these are stored with structive
37:22arrays so we're not we're not paying for
37:24padding or anything like that um
37:28there's a left- hand side and a right
37:29hand side that are repurposed depending
37:31on the tag and the point is that we have
37:33multiple encodings so a variable
37:35declaration is encoded in three
37:37different ways an if is encoded in two
37:39different ways a while is encoded in two
37:40different ways and there's just you know
37:43an arbitrary number of these encodings
37:45depending on what tically we found there
37:47were we needed to be represented in a
37:49efficient
37:53way okay so I showed you these two um
37:57and I actually did collect some per
37:59performance stats for this so did it
38:01help yes after I did just these two
38:05changes it didn't change anything else
38:07yet and I just measured the difference
38:08in uh just just parsing a whole bunch of
38:11files this is the stats that I took and
38:15uh wall clock time is the big one right
38:17and if if you do 22% faster wall clock
38:21time something that I'm quite happy with
38:23so that's that's good but we're not done
38:26yet there's still three more stages in
38:29the compiler pipeline so I will talk
38:32about this one um I'm I'm low on time so
38:36I won't talk about this one I won't talk
38:37about this one suffice to say the same
38:39strategies work but let's go look at the
38:41the Z one next phase of the pipeline so
38:45this one's going to take in uh a syntax
38:48tree and it's going to Output um um an
38:53IR that has no type analysis done yet so
38:56here's what we had before
38:58before uh before we had it's basically
39:02polymorphism you know object-oriented
39:04programming that that that whole thing
39:06so each each node will have a different
39:08amount of size depending on which one it
39:09is um pointers to talk about each
39:12other you know one canonical the T in
39:15this case the tag it's not the encoding
39:17strategy right there's one canonical way
39:19to represent everything which is you
39:21know nice in a maintainability
39:23perspective but um not as ideal for
39:26memory footprint right so here's some
39:29observations uh not every instruction
39:31needs a source location some can be
39:33inferred from a some other
39:37context uh Source locations can be u32
39:40indexes into the tokens array or ASC
39:42node so uh that's going to drop the size
39:45of that one in a
39:47half um let's see also sorry also this
39:51one before it was like some canonical
39:53Source location thing now since we're
39:56doing in in now we're doing encodings
39:59the encoding tells you the meaning of
40:01the source location so that the encoding
40:03can say in this case the source location
40:05a token index or in this case the source
40:07location is a node
40:09index uh and then finally this is the
40:12pointer to index thing right so now
40:13references to other instructions are in
40:15are half as big right so there's that
40:18one uh and then finally uh references
40:21can encode simple values so if you're
40:23just talking about you know a true like
40:25literally the value true or false
40:27uh we don't need to create you know a
40:29whole instruction to represent that um
40:31the the the reference to true or the
40:33reference to false itself in the the IR
40:35format can just have an enum tag
40:38dedicated to that um uh I'm going to
40:41just gloss over that because I don't
40:43want to run out of time but anyway
40:44suffice to say before it was uh an
40:47average of
40:4954.0 bytes
40:51each um oh and sorry we're going to do
40:54one more observation here we're going to
40:57use the encoding strategy obviously
40:58that's what I've been keeping saying so
41:00we're going to go from the PO
41:01polymorphism strategy to represent
41:03memory to the encoding strategy so we go
41:06from 54 on average to 20.3 again on
41:10average and um you know download the the
41:13code if you want at the end and and
41:15check my work I did some scripts that
41:16just ran against the whole standard
41:18library to figure out these uh these
41:20averages so this is the encoding
41:22strategy um I had to simplify it a lot
41:25to just fit it on the slide but but um
41:28it's the same deal right it's the
41:30encoding so you you encode multiple
41:32different ways to express everything
41:34here we can see strong and weak that's a
41:36that's a Boolean flag that's been you
41:37know put into the encoding tag
41:41um what else can I point out here I
41:45think I don't I don't think I need to
41:46point anything else out it's the
41:47encoding strategy it's the same thing I
41:48gave you three other examples of we went
41:50from 54.0 to
41:5320.3 um so what I do want to point out
41:56though is that each of these
41:57improvements we we cut the amount the
42:00size of each object in half or smaller
42:03through these techniques like the amount
42:05of memory that this thing is using
42:08drastically
42:09reduced uh so and did it work like you
42:13know does using less memory result in
42:15less cache misses well empirically yeah
42:20um and this one it gave me a 39%
42:21reduction of wall clock time which is
42:24ridiculous and and that's on top of the
42:26other one that I just reported for just
42:28doing it for the other two um I guess I
42:30had more of these objects in memory than
42:32the other
42:33one um
42:36so that works like in a real world
42:38project it works if you do the tricks
42:41you will get faster code uh and now I
42:44know I foreshadowed this embarrassingly
42:46parallel thing here so I had one more
42:48thing to report which is that when I
42:50went ahead and um I implemented a a
42:53thread pool or sorry King implemented a
42:55thread pool which I just copied from him
42:57thank you for that uh and then I I I
43:01made it distribute the work of doing
43:03this embarrassingly parallel part uh you
43:05know on the threadpool and this is on my
43:07like Dell Inspiron it's it's a pretty
43:09beefy laptop right it's a good laptop um
43:12when I did this just for this part of
43:14the pipeline it came out to 8.9 millions
43:16of lines of code per
43:18second so that's pretty
43:24fast and as a bonus uh uh the the zir
43:29right the the the output of this part of
43:31the pipeline it's now only four arrays
43:35it's a tag it's a common data um and
43:38then it's like an extra array and then
43:39there's a string table it's arrays
43:42that's it it's it's stupid stupidly easy
43:46to save and load that from disk there's
43:49a Cy call on posix called uh write V or
43:51or read V where you actually just give
43:54arrays to the OS and it just does the
43:57whole thing at once like it's one CIS
44:00call to save these to the cash or to
44:02load these from the cash so like this
44:04this number here this includes like
44:06saving the data into the cache right
44:09like this we're interacting with the
44:10file system here to like avoid this work
44:14next time okay caveat though right I'm
44:17only talking about this orange part and
44:20this parts of the compiler pipeline are
44:21no joke I know like is that Walter I see
44:24there yeah I know you're thinking that
44:26right now um
44:27so I do want to um highlight these areas
44:30over here because that number I gave you
44:32that's going to go down a lot right um
44:34if I can keep it above a million I would
44:36love that but obviously if these parts
44:39of the pipeline are harder that number
44:41is going to go down that number is just
44:43for the orange part I just want to be
44:44perfectly clear um but let me just let
44:46me just zoom in and and tell you like
44:49okay where are we at like what's going
44:50on here so I made this slide so that you
44:52can kind of see the idea um the the part
44:56that I gave you that stat add on that
44:57part is done okay but we're still
44:59working on the back end so um we're at
45:02about 35% of the behavior tests are
45:05passing for the self-hosted compiler so
45:08every time I've been reporting on these
45:09improvements I'm talking about
45:11improvements that have been made in the
45:12selfhosted compiler which is not what
45:14you get if you download Zig today if you
45:16download Zig today you get the slow one
45:19so if you are interested in this and you
45:21haven't tried it yet actually kind of do
45:23recommend waiting like maybe wait till
45:24these numbers go up to like I don't know
45:2790 or so 90 or so um you know wait till
45:30we have a release where we ship this new
45:33code as the default and then take it
45:36away so I just wanted to be very Frank
45:39with the uh the progress report here and
45:42um I think uh yeah I think let's move on
45:45from here
45:46so let's
45:48summarize this is what a computer looks
45:50like from a memory
45:52perspective add CPU cache to your mental
45:54model of computers see CPU is fast
45:57memory is
45:59slow uh identify where you have a lot of
46:01the same thing in memory and make that
46:03size of each thing smaller there's a
46:06bunch of Handy tricks you can you you
46:07can use to reduce the size of things so
46:09indexes instead of pointers watchever
46:12type safety store bullion out of band
46:15eliminate padding with structive arrays
46:17store sparse data in hashmaps use
46:20encodings instead of uh
46:24polymorphism uh and you know as you can
46:26see with the Z compiler it's worth it
46:29like these tricks uh H have actual real
46:32benefits um so that's it that's my talk
46:35thanks for listening