{"id":48287,"date":"2019-10-10T06:00:17","date_gmt":"2019-10-10T10:00:17","guid":{"rendered":"https:\/\/www.shamusyoung.com\/twentysidedtale\/?p=48287"},"modified":"2019-10-15T12:16:20","modified_gmt":"2019-10-15T16:16:20","slug":"jai-part-7-where-does-the-time-go","status":"publish","type":"post","link":"https:\/\/www.shamusyoung.com\/twentysidedtale\/?p=48287","title":{"rendered":"Programming Vexations Part 7: Where Does the Time Go?"},"content":{"rendered":"<p>Last week I talked about the compiler and what it takes to turn source code into a program. At the end I talked about the apparent problem where the compiler seems to be slowing down in proportion to <a href=\"https:\/\/en.wikipedia.org\/wiki\/Moore%27s_law\">Moore&#8217;s Law<\/a>, creating a stalemate where faster processors don&#8217;t do much to reduce compile times. This naturally leads to the question:<\/p>\n<p><i>So what <\/i><b><i>is<\/i><\/b><i> the compiler doing with all those CPU cycles?<\/i><\/p>\n<p>There doesn&#8217;t seem to be an agreement on this. I can&#8217;t even find any proper <b>research<\/b> on the topic. All of the discussions take the form of repeated platitudes and received wisdom on Stack Overflow.\u00a0 As far as I can tell, nobody has done the homework to compare the performance of C compilers in the mid-90s with the compilers we&#8217;re using today<span class='snote' title='1'>If I&#8217;m wrong and there is indeed research on the topic, then please drop a link in the comments!<\/span>.<br \/>\n<!--more--><\/p>\n<h3>It&#8217;s Not That Simple<\/h3>\n<p><div class='imagefull'><img src='https:\/\/www.shamusyoung.com\/twentysidedtale\/images\/vex_complex.jpg' width=100% alt='Oh hey! I found Waldo!' title='Oh hey! I found Waldo!'\/><\/div><div class='mouseover-alt'>Oh hey! I found Waldo!<\/div><\/p>\n<p>Part of the problem is that you can&#8217;t just blame the compiler and be done with it. Obviously we&#8217;re writing more complex programs, but those programs are also built using more complex libraries. Even beyond that, not all code is created equal in terms of the time it takes for the compiler to digest it. It&#8217;s less about the performance of the compiler itself and more about what you&#8217;re asking it to do.<\/p>\n<p>As features are added to the language, people change their design to incorporate those new ideas. Perhaps these newer ideas take longer for the compiler to sort out, so it doesn&#8217;t really hurt compile times until you&#8217;re using a lot of them.<\/p>\n<p>I want to stress that I&#8217;m <b>not<\/b> suggesting that the folks who maintain the C++ compiler have been lax in their duties. I&#8217;m willing to bet that there is a good reason why things work the way they do. C++ is a big, complex language and its use-cases stretch across the entire spectrum of software projects, from operating systems to embedded systems to productivity software to hobbyist projects. The language is incredibly flexible and it ends up being used in a lot of different ways.<\/p>\n<p>I&#8217;m sure there <b>are<\/b> people out there who can account for the processor cycles C++ uses. The problem for us garden-variety programmers is that there&#8217;s no good way to sort their knowledge from the people reflexively chanting &#8220;You have too many templates&#8221;. Objective truth <i>exists<\/i>, but unless you want to become a compiler expert yourself there&#8217;s no good way to sort truth from platitudes. And even if you take the time to sort that out, it&#8217;s not always clear how to use that knowledge on your own project.<\/p>\n<p>There are lots of things that can slow down compile times, but the chief suspects are:<\/p>\n<ul>\n<li><b>Templates<\/b>: I&#8217;ll talk more about this below.<\/li>\n<li><b>Codebase size<\/b>: This is probably obvious, but our programs are larger and more complicated these days. Back in the 90s, I worked on a codebase that was a million lines of code. That was pretty big for the time period, but that&#8217;s pretty modest by today&#8217;s standards.<\/li>\n<li><b>Frameworks<\/b>. Not only are our programs getting larger, but the external packages we&#8217;re using are also growing. The Windows SDK &#8211; which you need to use if you&#8217;re developing anything for Windows &#8211; is pretty gargantuan by now. It only takes one line of code to include the windows.h header file<span class='snote' title='2'>I&#8217;ll talk about header files in later entry.<\/span> in your project, but that one line of code pulls in <a href=\"https:\/\/en.wikipedia.org\/wiki\/Windows.h\">a total of 40 different files<\/a>! The compiler needs to process those tens of thousands of lines of code. Even if you&#8217;re only using 1% of the features in Windows, the compiler still has to read the whole damn thing. This applies to all the libraries you might be using: Graphics, sound, networking, Steamworks, etc.<\/li>\n<li><b>Redundant compilation<\/b>: Because the C and C++ compiler only runs on one file at a time, it ends up doing a lot of redundant work. Sure, you can use muti-threading to compile multiple files at once, but those isolated instances of the compiler can&#8217;t cooperate. The same few lines of included code will get compiled again and again, and then the linker has to come through and throw away all of the needless extra versions.<\/li>\n<\/ul>\n<h3>Templates<\/h3>\n<p>Let&#8217;s say you want a function to add one to a number. So you write the following code:<\/p>\n<pre lang=\"cpp\">float AddOne (float num) {\r\n\r\n  float result;\r\n  \r\n  result = num + 1;\r\n  return result;\r\n\r\n}<\/pre>\n<p>That works for floating-point numbers<span class='snote' title='3'>Numbers that can have an arbitrary number of decimal places, like 10.78881 or 1284.4.<\/span> , but what about integer<span class='snote' title='4'>Variables that can only store whole numbers with no decimal places.<\/span> values? If you want to do the same thing to integers, then you need another function:<\/p>\n<pre lang=\"cpp\">int AddOne (int num) {\r\n\r\n  int result;\r\n\r\n  result = num + 1;\r\n  return result;\r\n}<\/pre>\n<p>It&#8217;s pretty easy to see that these two bits of code are <b>nearly<\/b> identical. In fact, all you need to do is replace all instances of the word &#8220;float&#8221; with &#8220;int&#8221;. Programmers do not like duplicating code like this. If the spec changes later and we realize we need to add 1 if the number is positive but <b>subtract<\/b> 1 if the input number is negative<span class='snote' title='5'>I&#8217;ve emailed the project lead and insisted that we should rename the function from AddOne to IncreaseMagnitudeByOne, but she hasn&#8217;t gotten back to me.<\/span>, then it&#8217;s very easy to forget \/ overlook the various versions of the AddOne function. You&#8217;ll change the floating-point version but leave the other version alone, and now the AddOne function will behave differently based on the type of input variable.<\/p>\n<p>What if we need yet <b>another<\/b> version for unsigned<span class='snote' title='6'>Variables that can only hold value that are positive or zero.<\/span> values!? What about doubles<span class='snote' title='7'>Floating-point values with twice the precision, so it can hold values like 221.453739006345.<\/span>?! Single-byte values? Are we going to need to write and maintain five different versions of this function??<\/p>\n<p>This is where template programming comes in. The idea is that you write a function like this:<\/p>\n<pre lang=\"cpp\">template \r\nT AddOne (T num) {\r\n\r\n  T result;\r\n\r\n  result = num + 1;\r\n  return result;\r\n}<\/pre>\n<p>Now you can use AddOne on any variable<span class='snote' title='8'>More precisely, any variable that can have 1 added to it.<\/span> and the compiler will automagically build a version of AddOne based on the variable you&#8217;re trying to use. You only need one version of the function, and the compiler uses it as a template to build the rest.<\/p>\n<p>That&#8217;s the ideal, anyway. In practice, people have <a href=\"https:\/\/yosefk.com\/c++fqa\/templates.html\">a lot of gripes<\/a> with templates. Additionally, they rapidly inflate compile times.<\/p>\n<p>At this point I&#8217;d give a quick overview of how I use templates and whine about any perceived shortcomings, but to be honest&#8230; I&#8217;ve barely used them. I&#8217;m sure they&#8217;re useful to people working in other domains (people must use these things for a reason) but they never seemed to help me out in my game-type work. In practice, I rarely have functions that need to apply to ALL types. Even when I do have a function that needs to work on more than one type, it always seems like the variants all need slightly different behavior<span class='snote' title='9'>Like maybe floating-point numbers need to be rounded off or unsigned values need to be clamped to 0 during subtraction rather than allowing them to wrap around to four billion.<\/span> so that using templates would actually be more work. Templates don&#8217;t solve the problems I typically run into.<\/p>\n<p>So don&#8217;t use templates, right? The problem is that C++ is really barebones in terms of game development. You might be one of those unicorn developers that writes everything from scratch, but the overwhelming majority of developers are going to be using external libraries like <a href=\"https:\/\/www.boost.org\/\">boost<\/a>, which makes <strong>heavy<\/strong> use of templates. The compile times of boost itself borders on surreal. I think a full compile of boost<span class='snote' title='10'>You only need to do this once, after downloading the source.<\/span> is something on the order of 10 minutes.<\/p>\n<p>TEN MINUTES!<\/p>\n<p>The point is that if you&#8217;re doing game development, then you&#8217;re probably going to be using external code that makes use of a lot of templates, and thus your project will compile very slowly. This is on top of all the other stuff that makes C++ so slow to compile.<\/p>\n<h3>Why Compile Times Matter<\/h3>\n<p><a href='https:\/\/www.xkcd.com\/303\/'><div class='imagefull'><img src='https:\/\/www.shamusyoung.com\/twentysidedtale\/images\/vex_distracted.jpg' width=100% alt='You thought I was going to put that one XKCD comic here, didn&apos;t you? But no! Instead here&apos;s a stock photo of an office worker THINKING about the XKCD comic. While playing air guitar.' title='You thought I was going to put that one XKCD comic here, didn&apos;t you? But no! Instead here&apos;s a stock photo of an office worker THINKING about the XKCD comic. While playing air guitar.'\/><\/div><\/a><div class='mouseover-alt'>You thought I was going to put that one XKCD comic here, didn&apos;t you? But no! Instead here&apos;s a stock photo of an office worker THINKING about the XKCD comic. While playing air guitar.<\/div><\/p>\n<p>I&#8217;m afraid it&#8217;s time for another Terrible Car Analogy\u2122. Let&#8217;s say you&#8217;re working on a car that won&#8217;t start. So you make an adjustment to the combobulator manifold or the humding injection filter. But you can&#8217;t test the car in this condition. You have to re-assemble the part you&#8217;re working on, put the cover back on, reconnect it to the combustion flange, and close the hood. The whole process takes a full three minutes.<\/p>\n<p>There are a dozen different things you can try in order to diagnose this problem, but every attempt costs you three minutes, even though the change itself takes two seconds. If you try them all, then you&#8217;re going to spend 36 minutes re-assembling everything again and again, and in all that time you&#8217;re only going to do 24 seconds of real work.<\/p>\n<p>In a tricky problem, you might need to make a lot of very small changes. Maybe those changes are only a single line of code. But if every test eats up a minute of compile time then you&#8217;re going to spend most of your time waiting for the compiler.<\/p>\n<p>Worse, this particular break in flow is incredibly disruptive to concentration. I&#8217;m mentioned before that programming involves having a lot of different ideas in your head at once. You need to keep thinking about the problem, yet there&#8217;s nothing to think about during the compile. You have to somehow maintain concentration while also being idle and bored. Have you ever seen a runner jog in place while waiting for the light to change? They&#8217;re trying to keep their heart rate up and their body moving because they don&#8217;t want to fall out of their groove. Imagine if they were locked in place and unable to move until the light changed. That&#8217;s what waiting for a compile feels like.<\/p>\n<p>Personally, I think around fifteen seconds is where the compile process becomes disruptive to the coding process. As soon as compile times get above that threshold, I find it really hard to keep my head fixed on the problem. In the old days you&#8217;d fire up Minesweeper or (my favorite) Freecell. These days I guess everyone just picks up their phone.<\/p>\n<p>As the compile drags on, I get bored and my mind starts to wander. If the compile is above half a minute, then I&#8217;ll jump over to another window to check social media \/ email \/ play a round of casual mobile game \/ check my website comments \/ etc. It&#8217;ll take me five minutes to get back from that voyage of distraction, and then it&#8217;ll take me half a minute to get back into the groove of the problem and remember where I left off.<\/p>\n<p>I realize it&#8217;s not fair to blame the language for human frailty. I&#8217;m not saying we should blame <a href=\"https:\/\/en.wikipedia.org\/wiki\/Bjarne_Stroustrup\">Bjarne Stroustrup<\/a> for my social-media distractions. But it&#8217;s also true that programmers are people and the problem of losing concentration during compiler downtime is not a rare one. If we can make a language that keeps compile time low, then we can stay &#8220;in the zone&#8221; for longer and thus enjoy higher productivity.<\/p>\n<h3>Jai Does it Differently<\/h3>\n<p>Jai is apparently ridiculously fast to compile. Jon Blow shows his game compiling in under a second on live streams. For reference, a second is about how long I usually have to wait before the compile process <b>begins<\/b> in Visual Studio. The difference in speed is almost comical. He\u2019ll occasionally compile the wrong program, or with the wrong settings, and it takes him longer to realize his mistake and say \u201coops\u201d than the entire compile process.<\/p>\n<p>To be fair, some of that improved compile time is because Jai has less to do. It isn&#8217;t chewing through decades of language features that aren&#8217;t strictly needed for your project. But I&#8217;m guessing the biggest speed boost is that the compiler is able to look at <b>all<\/b> the files in question, rather than looking at each file in isolation.<\/p>\n<p>I&#8217;m sure Jai compile times will go up as the language matures, but currently it&#8217;s compiling a nearly-complete game an order of magnitude faster than C++ would<span class='snote' title='11'>There&#8217;s no way you can fully compile a mid-tier 3D title in under 10 seconds.<\/span>. I&#8217;m not saying Jai is going to save us all, but I do think it&#8217;s reasonable to conclude that a language devised for games could really help us out when it comes to compile times.<\/p>\n<p>I&#8217;ve dabbled in other languages, but I&#8217;ve never done anything above trivial complexity outside of the C family and Java. I&#8217;d love to hear from Go, Rust, and Dlang developers: How are compile times in your neck of the woods?<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Last week I talked about the compiler and what it takes to turn source code into a program. At the end I talked about the apparent problem where the compiler seems to be slowing down in proportion to Moore&#8217;s Law, creating a stalemate where faster processors don&#8217;t do much to reduce compile times. This naturally [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[66],"tags":[],"class_list":["post-48287","post","type-post","status-publish","format-standard","hentry","category-programming"],"_links":{"self":[{"href":"https:\/\/www.shamusyoung.com\/twentysidedtale\/index.php?rest_route=\/wp\/v2\/posts\/48287","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.shamusyoung.com\/twentysidedtale\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.shamusyoung.com\/twentysidedtale\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.shamusyoung.com\/twentysidedtale\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.shamusyoung.com\/twentysidedtale\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=48287"}],"version-history":[{"count":18,"href":"https:\/\/www.shamusyoung.com\/twentysidedtale\/index.php?rest_route=\/wp\/v2\/posts\/48287\/revisions"}],"predecessor-version":[{"id":48370,"href":"https:\/\/www.shamusyoung.com\/twentysidedtale\/index.php?rest_route=\/wp\/v2\/posts\/48287\/revisions\/48370"}],"wp:attachment":[{"href":"https:\/\/www.shamusyoung.com\/twentysidedtale\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=48287"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shamusyoung.com\/twentysidedtale\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=48287"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shamusyoung.com\/twentysidedtale\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=48287"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}