  
Welcome to Ventspace! Most posts here are delayed copies of posts from the real Ventspace.
| Thursday, August 16, 2007 |
  XNA's Future Looks Bright | 
Posted - 8/16/2007 4:46:32 PM | Screw schedules. From now on I'm just writing entries whenever I get around to it. If you really want to follow things, use the RSS feed to the journal. (No, I have no idea where it is.) Coming entries are the last part of Static Checking, and another entry on linked lists.
XNA's Future Looks Bright
Recently, I've felt that I have been much too unbalanced in my talk about XNA. XNA has plenty of problems, but I expected most of these problems (certainly the major ones with XNA's goals) to be fixed within the next year. While claiming that something is "the future" is idiotic, I do believe that XNA is a very viable and promising future. And what's more, I think it's absolutely critical that XNA succeeds, because it may be the only hope for our industry to move forward on a technical level. I think Microsoft is going to see this one through, too. MDX was a short term research project; XNA is a long term platform strategy like the Xbox itself.
The reason I'm writing this entry now is that a number of things have been announced fairly recently with XNA, all of which paint a much brighter future than the relatively bleak present I've discussed here and in other places. Incidentally, I'd like to encourage anybody interested in this stuff to hang out in #xna on the EFNet IRC network. Lots of cool people there, and many of them not nearly as technically obsessed as I am.
First, XNA 2.0 is coming. This is something the XNA community has been aware of for some time, but the details were only revealed recently. There's a number of major changes here, and I suggest you read the blog posting. XNA Game Studio Express is effectively the same thing as the pre-release SlimDX that I had posted back at the end of June; a first draft intended to explore basic principles and to get a more precise gauge of customer and developer interest. It's clear at this point that developer interest is massive, even amongst the typically slow to move pro game studios. MDX always had a dedicated hobbyist and indie following, but nothing more than that. (Plus it wasn't exactly strategically useful.) XNA has a real future here.
Second, the XNA team has been very aware of criticisms and problems, much more so than would normally be expected from a corporate group. This is something that's been pushed fairly heavily across Microsoft in recent years, but the XNA guys are in a particularly good position to make use of it. They have done so quite well, running a team blog as well as keeping other people interested and writing about XNA. They also have their own, reasonably active forums where a number of the XNA guys hang out and post. (In particular, information like this.) That kind of thing really helps to boost developer confidence, even when the actual content of the message is not what people want to hear.
Third, I don't really consider SlimDX and XNA to be competitors. The people who would use SlimDX would not be happy on XNA, and I get the feeling that many of these people would simply switch back to unmanaged DX or or soldier on with MDX even as the coffin is lowered. My basic take on XNA hasn't changed -- it's an Xbox API that happens to run on Windows. I just think there's a very real market and range of opportunity for a library like that. SlimDX, on the other hand, seeks to tackle a pure PC market by providing more traditional or Windows-specific APIs related to making games focused around Windows. Like MDX before us, SlimDX is not a platform strategy so much as it is just a convenience. At some basic level, our development model simply makes more sense for what we are. Similarly, XNA is a platform, providing access to something we would never have had in any capacity without it -- the ability to make Xbox games. SlimDX and XNA are brothers, even if there's some sibling rivalry involved.
Lastly -- and this is by far the most important point -- XNA makes managed games acceptable. Right now, games are written in C++, end of story. People know this. It serves to distort people's perception of what languages are suitable for writing games and why. I'm not interested in the actual reasons now, since it's not relevant to this post. The real key is that XNA based games are coming, and people are noticing. We can thank the Dream-Build-Play contest for that, because it served as a fairly violent catalyst in the matter. As XNA games start to appear, people (indies, pros, everyone) will begin to understand that managed code is great for games. Even if we accept the claim that managed code is not fast enough for cutting edge high end games, most games are not cutting edge high end graphical monsters of eye scorching brilliance. Consider that the top 5 PC games today are The Sims and World of Warcraft, both of which are fairly average looking games. It's not like managed code will "take over" or become "the future" or anything like that. Saying those things simply corrupts the discussion with rhetoric. What XNA does for us is to make people understand that managed code is not inherently slow or inherently bad for games (and we can probably blame Java for creating or at least providing evidence for that horrible misconception in the first place).
I'm not fond of XNA in its current form. I'm not interested in using XNA in its current form. But at the end of it all, XNA can succeed and it needs to succeed. I would hope that the people working on XNA share at least the last sentiment. I think in a year's time, a lot of very skilled developers will be doing absolutely amazing work with XNA, and they'll be doing it at speeds which the guys working with C++ and DirectX will never be able to match. Some of you have probably seen the strategy I've developed for completely shutting down language threads on the spot, without taking any moderator action. When XNA's time comes, I hope to be able to force managed code doubters into silence with nothing more than a list of links: a list of incredible XNA (and SlimDX I hope) games being built that look incredible and blow away the indie work we've seen to date*. 
* No offense guys, I think indies are doing great stuff already. I just feel that the work done on XNA when that environment has fully matured will allow people to step up into another league.
| |
| Wednesday, August 15, 2007 |
| Linked Lists Are Tricky | |
Posted - 8/15/2007 7:22:42 PM | Life is too damn busy. Still, I think I prefer work life over school life even if the net amount of free time, or at least time spent at home, is less. Some cool things happening with XNA recently; I will write about it soon but need to collect my thoughts a bit first.
Unfortunately, I suspect that what I'm writing today will be very, very old news to the sorts of people who read this journal.
Linked Lists Are Tricky
Everybody knows linked lists, especially if you learned C or C++ at some point. They're a relatively simple data structure that provides constant time insertion and removal, and linear time random access by index. They're popular when people are writing hobby games, because of how quick and easy it is to add things, remove things, and move things around. Since these games usually run a traversal of the list from beginning to end, the linear time random access isn't a concern. For getting things done, it's hard to beat linked lists. And the performance characteristics seem ideal. They don't suffer from the nasty linear time removals and insertions, and their drawbacks don't apply to a typical update pattern in a game.
As usual, things aren't quite so simple. On a purely theoretical level, looking at asymptotic performance bounds and such, linked lists are great for this sort of thing. Once you add real computer architecture into the mix and see what's going on though, linked lists turn out to have some rather inconvenient hidden drawbacks. Now these aren't necessary fatal problems, and they're largely performance oriented. However, it is important to be aware of such things, and it complicates the landscape quite a bit.
The problem, you see, is locality. Computers love locality. Linked lists, howver, tend to exhibit terrible locality. (And in the case of native code, practically no locality at all, particularly spatial locality.) An application that relies heavily on linked lists will cache miss at a high frequency, costing it dozens of cycles doing nothing but waiting every time it looks at an object. Throw in a few thousand objects and it really starts to add up; before long you're seeing full percentage points of CPU time lost to nothing but cache misses.
In order to understand why linked lists are so bad with locality, we first need to look at how a processor cache works. The cache exists to avoid going all the way out to main memory for recently used memory. There's also management structures involved in order to keep track of what memory is currently available in the cache, what memory needs to be updated from cached values, etc. It would be prohibitively expensive to maintain this information for every single byte, as well as extremely redundant in many cases. So instead, things are managed in what are called cache lines. The actual size of the cache lines can vary between architecture, sub architecture, and even between the L1/L2/L3 caches. 64 and 128 bytes are common sizes, though.
So we can think of all memory as being sliced into cache line sized chunks. When some memory is looked up, the entire chunk which it belongs to is loaded into cache at once. So even if you access a lone int, you'll get 64 or 128 bytes of nearby data loaded as well. So, consider how the cache behaves in a contiguous list. Let's assume we have a 32 byte cache composed of two 16 byte cache lines, and a list of 8 items, each of which is 4 bytes. Some simple math will show that we have just enough cache space for all of our items. Let's take a look at what happens as we iterate over the list a couple times. When we hit the first item, we'll get a cache miss and load some of the list into cache:
1 2 3 4 5 6 7 8
The bold items are in cache, the non-bold ones aren't. The next three items will be pulled from cache. When we hit 5, there will be another cache miss and we'll load the other half of the list:
1 2 3 4 5 6 7 8
Once again, we'll continue through the next couple items without any misses. And on the next pass through, the entire thing is already in cache, and so there are no more future cache misses. This is an exaggerated scenario, of course, but you get the basic idea.
Now, what happens with a linked list? Because a linked list allocates a new node for each item, it exists on its own, usually surrounded either by garbage memory or by memory that is simply not relevant to it. This layout will tend to become exacerbated over time if you're just using a normal heap. All of the nodes will eventually end up scattered far and wide. So when we go to traverse it, we get something like this:
1 -> {+} 2 -> {+} 3 -> {+} 4 -> {+} 5 -> {+} 6 -> {+} 7 -> {+} 8
I've used the {+} symbol to represent the junk data following each node. So far we've managed to load one item, its next pointer, and a bunch of junk data. We've already used an entire cache line up right now. Here's what happens as we continue to traverse:
1 -> {+} 2 -> {+} 3 -> {+} 4 -> {+} 5 -> {+} 6 -> {+} 7 -> {+} 8
1 -> {+} 2 -> {+} 3 -> {+} 4 -> {+} 5 -> {+} 6 -> {+} 7 -> {+} 8
1 -> {+} 2 -> {+} 3 -> {+} 4 -> {+} 5 -> {+} 6 -> {+} 7 -> {+} 8
1 -> {+} 2 -> {+} 3 -> {+} 4 -> {+} 5 -> {+} 6 -> {+} 7 -> {+} 8
You get the idea. The lack of locality has caused a drastic increase in the cache miss rate, because each cache read only pulls in one item. Worse still, the actual cache space used has gotten a lot larger, especially if that junk data really is junk that we're not interested in. We now need eight cache lines to store what previously fit in only two. And since the beginning of the list falls out of cache, we will start the whole pattern of misses over again on future passes.
Of course, this effect decreases quite a bit as the size of each individual node increases. At the point where your node size (including prev/next/etc pointers) is a multiple of the cache size, you're not doing nearly as badly as in this example. It's still not as good as the contiguous storage (and this is connected to much weaker, difficult to pin down factors like virtual address lookup, CPU prediction, etc), but it helps a lot. A structure like std::deque, which is a linked list of large (page size or bigger) blocks will do just as well as the contiguous block. The point is not to avoid linked lists, but to be careful about the exact behavior and structure of the list. A linked list of integers has the potential to really ruin your day; a linked list of 512 byte objects won't really hurt you.
It's worth pointing out that this advice applies to any linked structure, especially trees. A big reason that octrees are preferable to binary partitions is that you can allocate all of the child nodes in a contiguous block, which can really help your cache hit rate as you do a traversal. It doesn't help much if you just have an array of pointers to your children, though. You need to allocate the actual children in a continuous block to really see a benefit. Again, the exact structure and node size is key, and can make or break the caching behavior. Accessing scattered small objects is something you want to try to avoid at a design level. Don't create data structures that force you to do it, because if these things show up on profiles, you'll find yourself trying to micro-optimize code inside traversals and completely missing the actual source of the problem. Preserve locality as much as you can from the beginning, and it will save you headaches later on.
| |
| Car Watching | |
Posted - 8/7/2007 6:43:32 PM | Whoo, SlimDX is starting to grow up a little bit. I'm pushing it a little while limiting the publicity right now; the real marketing push will come around November when the next DX SDK drops. Lots to do until then. I'm exhausted today and can't concentrate, so I'm just going to throw up this fairly random entry. I'll go back to technical stuff...later...
Car Watching
I enjoy watching what cars are on the road. Naturally, seeing all the various sports cars is cool, and there are plenty out here in Silicon Valley. There's plenty of cars to be noticed just because they're out of the ordinary. And it's interesting to see how common various cars and brands are.
When it comes to the nice and expensive cars, these are what I've seen so far in this area:
* Acura NSX -- This is a bit of an odd one, and I didn't expect to see one, let alone two. Still, it's a supercar in its own right.
* Chevy Corvettes -- Lots and lots and lots of Corvettes. C5s and C6s are all over the place, and I've seen a couple C4s, C3s, and even a Stingray. I never expected to see a Stingray in person, just out on the road.
* Shelby Cobra -- At least it looked like a Shelby Cobra. I have a hard time believing that somebody is driving around a Cobra on the weekends, even out here. Anybody know any cars that look like Cobras but aren't?
* Mercedes-Benz -- So many Mercedes of so many models. I don't even like these cars, but they are expensive luxury cars after all.
* Ferrari F430 -- I've seen at least one of these, possibly more. Since they're all red, I don't know if I see the same one every time. Absolutely beautiful car though.
* Maserati -- I don't know Maserati models, sorry. I'm don't really even know anything about these, but I never really expected to see one.
* Bentley Continental GT -- Another high end luxury car I never expected to see. Again, I don't know much about them.
* Lamborghini Gallardo -- I love these cars, and I would love to drive one.
* Lotus Elise/Exige -- I've seen one of each, and only one of each. I know they're not the most roomy or comfortable cars around, but I thought they'd be more popular. There were a number around Redmond last summer, so I don't know what's with the lack of love for them here.
* Aston Martin DB9 -- I've seen two of these so far. Another car I absolutely love, and one of these was parked, so I got to take a fairly close look. I actually wish they'd given that poor DBS more driving time in the last Bond movie.
* Nissan 350Z -- Another favorite of mine. Plenty of these around, too.
* Infiniti G35 Coupe -- Slightly uglier, slightly slower versions of the 350Z. Not really worth noticing, but there's a fair few out there.
* Honda S2000 -- Same thing, although I'm not sure how loud the engine is in one of these. They are fairly high revving.
* BMW Z3/Z4 -- These bore me.
* Lexus -- Again, all boring.
* Subaru Impreza WRX -- There's a lot of these on the road. A LOT. They're powerful, snappy, hideous cars, but I'm amazed that there are so many. They're not at Mustang levels of saturation, but damn.
* Porsches -- Lots and lots of Porsches. Finally saw a few Caymans in person, along with the usual crop of Boxsters, Carreras, 911 Turbos, and Cayennes. I like them (except the Cayenne), but you can only see so many before you stop caring.
Notable omissions from the list:
* Dodge Viper -- Especially the 600 HP version, I'd love to see that tearing down the road.
* Ford GT -- Sure they're hideous, but apparently they drive nice.
* Audi R8 -- Ok, I don't even know if these are out yet. But god damn, I want to see one.
* Rolls Royce Phantom -- I think they're ugly, but I was hoping to see one anyway.
* Mercedes Benz SLR McLaren -- Same as the Phantom.
The strangest thing, though, is how many vintage cars I've seen. I don't know vintage cars at all, but I can recognize one when I see it. I don't really even understand why people drive these things. Remembering their own childhood or something maybe?
I used to be one of those people that didn't really care about cars. I kinda wish I still was, since I have a tendency to be obsessive in my interests. Still, it's fun to see what's out on the road and it gives me something to do when I'm out walking or on the bus.
| |
|
| S | M | T | W | T | F | S | | | | 1 | 2 | 3 | 4 | 5 | 6 | | 8 | 9 | 10 | 11 | 12 | 13 | 14 | | | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | | |
OPTIONS
Track this Journal
ARCHIVES
October, 2009
September, 2009
August, 2009
July, 2009
June, 2009
October, 2008
June, 2008
May, 2008
April, 2008
March, 2008
February, 2008
January, 2008
December, 2007
November, 2007
October, 2007
September, 2007
August, 2007
July, 2007
June, 2007
May, 2007
February, 2007
|
