{"id":15904,"date":"2012-05-15T05:37:16","date_gmt":"2012-05-15T10:37:16","guid":{"rendered":"http:\/\/www.shamusyoung.com\/twentysidedtale\/?p=15904"},"modified":"2012-05-15T06:15:21","modified_gmt":"2012-05-15T11:15:21","slug":"project-octant-part-8-the-time-hole","status":"publish","type":"post","link":"https:\/\/www.shamusyoung.com\/twentysidedtale\/?p=15904","title":{"rendered":"Project Octant Part 8: The Time-Hole"},"content":{"rendered":"

So let’s talk about data structures. I’ve mentioned way back at the start of the project that there are certain costs to using an octree. An octree will make interfacing with ALL blocks a hundred times faster but make dealing with a specific block several times slower. I’m curious how…<\/p>\n

Hang on. My program has been behaving oddly recently. It’s like it will suddenly stop building new blocks and I’ll end up stuck on this island floating in empty space. I’ve got the program set to aim for 60fps, and if one thing starts eating too much CPU then the block-building gets choked off. Let’s see where these CPU cycles are going.<\/p>\n

I add a little benchmarking loop. Right now there are just five systems running:<\/p>\n

<\/p>\n

    \n
  1. Avatar: This moves the camera around and does a little super-cheap collision detection.\n<\/li>\n
  2. World: During block generation, world allocates these tables of handy values to speed up building. This part just looks for out-of-use tables and unloads them.\n<\/li>\n
  3. Scene: This is the heavy hitter. It does those crazy heavy-duty noise calculations<\/a>, places the blocks, maintains the octree, and turns the blocks into textured polygons.\n<\/li>\n
  4. Window: This bit really does almost nothing. It checks for keypresses.\n<\/li>\n
  5. Qt: Ah. This is where Qt gets a chance to process stuff. Qt is the platform I’m using to write this. Go back to part 3<\/a> if you need a refresher.\n<\/li>\n<\/ol>\n

    Let’s see where the time is going:<\/p>\n

    octant8_1.jpg<\/td><\/tr><\/table><\/p>\n

    I don’t have access to a microsecond timer here, so we have to make due with milliseconds. This is like wanting to measure how long a man’s stride is when he walks, but your ruler is only marked off in terms of kilometers. You have to measure a lot of individual steps to figure it out. These measurements were taken over the course of a second. There’s a thousand milliseconds in a second, so we’re looking to account for those thousand milliseconds. Note that there’s a tiny bit of overhead to taking these measurements and we’re likely to miss a tick-tock here or there on really short tasks, but this is good enough to give us a broad understanding of where the time is going.<\/p>\n

    Note that the item “Qt & Rendering” is there because I do my rendering during<\/em> the bit where Qt gets a timeslice. The two items in parenthesis break that number down. (Rendering) is how much time I spend shoving polygons at the graphics card, and (Qt) is how much time Qt eats doing… whatever it is that Qt does.<\/p>\n

    Hm.<\/p>\n

    This is not good. In fact, this is exactly what I was afraid of back when I started using Qt<\/a>. Over half of my CPU cycles are being eaten by Qt, doing… what? I have no idea. Qt is in charge of I\/O, so it’s doing some keyboard and mouse processing. But that stuff is so fast that I shouldn’t be able to measure it with this clock. It’s also in charge of drawing that black box with the checkboxes and text in it. <\/p>\n

    Could that be it? Is Qt burning six tenths of a second on a rectangle of text with a couple of checkboxes? Hm. If I get rid of the box then I won’t be able to see these results. Let’s get rid of the checkboxes and see if that changes anything.<\/p>\n

    octant8_2.jpg<\/td><\/tr><\/table><\/p>\n

    That made a big difference. Qt is now “only” using half of the CPU to draw this stupid black rectangle and text. For contrast, during the other<\/em> half of the second I’m rendering millions and millions of polygons. Picture two guys in a library. In the same hour, one of them reads the complete three-volume set of The Baroque Cycle<\/a> and the other guy reads a single Family Circus<\/a> strip. <\/p>\n

    Let’s do another test. Let’s give Qt a bunch more controls and see how it reacts. <\/p>\n

    octant8_3.jpg<\/td><\/tr><\/table><\/p>\n

    I’ve added a little text label, another text box, and a couple of progress bars. (I dunno. They look kind of like health bars or something. Seems like a reasonable thing to expect if this was a game environment.) And now Qt is eating 71% of our CPU. This would be funny if it wasn’t so sad. This makes it pretty clear why nobody’s ever tried to use this thing for a game. A real game interface would be even more complex than this.<\/p>\n

    Keep in mind that these controls aren’t changing. I’m not altering the position of the faux-health bars or anything else that would create a need for them to be re-drawn every frame. The text boxes only update once a second. <\/p>\n

    With performance like this, I might as well go use Visual Basic. (No, not really.) Note that this doesn’t mean that Qt is bad<\/strong>. It’s just built with different goals. Getting a cross-platform windowing system to play nice with 3D rendering like this requires a lot<\/em> of levels of abstraction. A normal Qt application is just some kind of interface with buttons and sliders and whatnot, without any 3D rendering going on. In those circumstances, the user isn’t going to notice a few missing milliseconds. My program is sensitive to single-digit millisecond usage, but a human being generally isn’t going to notice until it’s in the hundreds, and they probably won’t care until it’s near a thousand. The performance needs of Qt are at least two orders of magnitude from the performance needs of a 3D game. <\/p>\n

    I find this page<\/a>, which seems to be from one of the developers behind Qt. It confirms my worst fears: This CPU cost is an inescapable reality of using Qt. Even if all of those optimization techniques worked for me, and even if they applied to every little interface item, and even if I made maximum gains from all of them, it still<\/em> wouldn’t do more than cut the CPU usage in half, which would still be ten times more than it should be. <\/p>\n

    If I disable the Qt drawing entirely (and have it print out the timing info to the console window instead) then we get:<\/p>\n

    FPS: 179<\/p>\n

    Avatar: 0
    \nWorld: 1
    \nScene: 25
    \nWindow: 0
    \nQt&Render: 962
    \n(Qt): 251
    \n(Render): 711
    \nQt ms per Frame: 1<\/code><\/p>\n

    So the real overhead of using Qt is only ~1ms per frame. That’s reasonable. It’s just that the Qt drawing tools are too slow to be useful. A shame, really. “A platform-independent interface” was the main selling point of Qt for me. I’ve found a lot of other things to like about it since then, but losing the GUI is pretty much a deal-breaker. <\/p>\n

    When my processing began choking off I wanted to come in here and look for ways to optimize the octree or something. But it looks like the first order of business is “stop using qt” if I care about speed. I had a bunch of ideas for how I might tackle the crazy challenges that Goodfellow faced in part 32 of his series<\/a>. Seems sort of pointless now. There’s no reason to agonize over the aerodynamics of your car while you’ve got a half-ton of cinderblocks in the back seat. <\/p>\n

    Oh sure, I could<\/em> work on my optimizations like this, but the CPU drain of Qt is noisy, so measuring performance would be like trying to play Jenga on horseback. Also, experience has taught me that trying to monitor performance by reading a continuous spew of text in a console window is really aggravating. <\/p>\n

    I suppose I could take my code and go back to Visual Studio and SDL<\/a>, which is what Project Frontier used. But that means shopping for a suite of image loading, interface-drawing, font-reading tools. Yuck. I don’t want to unravel some idiotic chain of dependencies. I don’t want to download a dozen different SDK<\/acronym>‘s, spew their files all over my hard drive and then try to get them to compile and link with my project. I don’t want to have to choose between the package that only solves half the problem, the package that sucks to use, or the package that ties me to Windows. I don’t want to have to learn a new programming language. <\/p>\n

    I just – this external packages stuff is such a dang killjoy for me. I really, really, really hate it. It takes all the fun out of programming. When I was younger I tolerated it, but now I seem to have lost my patience. I know why this problem exists and I understand why there aren’t easy solutions. I just don’t have the desire to put up with it these days.<\/p>\n

    Maybe I’ll work a bit more on this project before I shelve it. Maybe I’ll migrate back over to Visual Studio and just muddle along with no interface. Maybe I’ll just stop here. I don’t know. I’m going to walk away from it for a bit and see how I feel about it then.<\/p>\n

    Onward?<\/p>\n

    EDIT: I’ve been meaning to ask: For those of you who played around with Project Frontier, what was the biggest hassle in porting it? I know the capitalized filenames were a problem. “Main.cpp” instead of “main.cpp”. I was obliged to use the former professionally for years, and eventually it became a habit that I didn’t question. I’ve since been making sure everything is lowercase, but what other headaches did you encounter? (Aside from, you know, bugs and stuff.)<\/p>\n","protected":false},"excerpt":{"rendered":"

    So let’s talk about data structures. I’ve mentioned way back at the start of the project that there are certain costs to using an octree. An octree will make interfacing with ALL blocks a hundred times faster but make dealing with a specific block several times slower. I’m curious how… Hang on. My program has […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[66],"tags":[233],"class_list":["post-15904","post","type-post","status-publish","format-standard","hentry","category-programming","tag-octant"],"_links":{"self":[{"href":"https:\/\/www.shamusyoung.com\/twentysidedtale\/index.php?rest_route=\/wp\/v2\/posts\/15904","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=15904"}],"version-history":[{"count":0,"href":"https:\/\/www.shamusyoung.com\/twentysidedtale\/index.php?rest_route=\/wp\/v2\/posts\/15904\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.shamusyoung.com\/twentysidedtale\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=15904"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shamusyoung.com\/twentysidedtale\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=15904"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shamusyoung.com\/twentysidedtale\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=15904"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}