Thread: [Algorithms] In-place loaded data structures.
Brought to you by:
vexxed72
From: <Bra...@pl...> - 2005-11-29 01:54:55
|
I remember some talk a while back about in-place loaded data structures. As in, all you have to do to "unpersist" the data is load it up into a contiguous block of memory and (possibly) fix up relative offsets into absolute pointers. IIRC, someone mentioned that they had written an in-place hash table and put it up on SourceForge? Can anyone point me to this discussion in the archives? Anyway, is there a magic Google phrase for this type of stuff? Does anyone know of any gentle introductions to in-place data structures, or is it just part of the collective black-art of console programming that no one talks about? :) Thanks, Brad... |
From: Jonathan B. <jo...@nu...> - 2005-11-29 02:17:25
|
If I were Sony I would have a library of such data structures pre-written as part of the Cell SDK. But I guess they don't. Bra...@pl... wrote: >I remember some talk a while back about in-place loaded data structures. >As in, all you have to do to "unpersist" the data is load it up into a >contiguous block of memory and (possibly) fix up relative offsets into >absolute pointers. IIRC, someone mentioned that they had written an >in-place hash table and put it up on SourceForge? Can anyone point me to >this discussion in the archives? > >Anyway, is there a magic Google phrase for this type of stuff? Does >anyone know of any gentle introductions to in-place data structures, or is >it just part of the collective black-art of console programming that no >one talks about? :) > >Thanks, > >Brad... > > > >------------------------------------------------------- >This SF.net email is sponsored by: Splunk Inc. Do you grep through log files >for problems? Stop! Download the new AJAX search engine that makes >searching your log files as easy as surfing the web. DOWNLOAD SPLUNK! >http://ads.osdn.com/?ad_id=7637&alloc_id=16865&op=click >_______________________________________________ >GDAlgorithms-list mailing list >GDA...@li... >https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list >Archives: >http://sourceforge.net/mailarchive/forum.php?forum_id=6188 > > > |
From: Mick W. <de...@mi...> - 2005-11-29 02:27:13
|
Try a search for "loading fast" in the archives: http://sourceforge.net/search/?type_of_search=mlists&forum_id=6188&group_id=7932&atid=0&words=loading+fast&Search=Search <http://sourceforge.net/search/?type_of_search=mlists&forum_id=6188&group_id=7932&atid=0&words=loading+fast&Search=Search> or http://tinyurl.com/b42z2 What were you going to "persist"? Mick* * Bra...@pl... wrote: >I remember some talk a while back about in-place loaded data structures. >As in, all you have to do to "unpersist" the data is load it up into a >contiguous block of memory and (possibly) fix up relative offsets into >absolute pointers. IIRC, someone mentioned that they had written an >in-place hash table and put it up on SourceForge? Can anyone point me to >this discussion in the archives? > >Anyway, is there a magic Google phrase for this type of stuff? Does >anyone know of any gentle introductions to in-place data structures, or is >it just part of the collective black-art of console programming that no >one talks about? :) > >Thanks, > >Brad... > > > >------------------------------------------------------- >This SF.net email is sponsored by: Splunk Inc. Do you grep through log files >for problems? Stop! Download the new AJAX search engine that makes >searching your log files as easy as surfing the web. DOWNLOAD SPLUNK! >http://ads.osdn.com/?ad_id=7637&alloc_id=16865&op=click >_______________________________________________ >GDAlgorithms-list mailing list >GDA...@li... >https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list >Archives: >http://sourceforge.net/mailarchive/forum.php?forum_id=6188 > > > > |
From: <Bra...@pl...> - 2005-11-29 02:59:21
|
> What were you going to "persist"? I didn't really have anything in particular in mind when I originally posted. I'm just curious if there are any general techniques for doing this kind of thing that apply across different data structures. Feel free to point out any obvious exceptions, but I would guess that just about any data structure could be made "in-place loadable" with sufficient amounts of elbow grease. I just wonder if there are any common themes or rules-of-thumb that people have gleaned about in-place loading that they would be willing to share, that's all. Thanks, Brad... |
From: <chr...@pl...> - 2005-11-29 03:25:40
|
Brad Byrd wrote: > I didn't really have anything in particular in mind when I originally > posted. I'm just curious if there are any general techniques for doing > this kind of thing that apply across different data structures. Feel free > to point out any obvious exceptions, but I would guess that just about any > data structure could be made "in-place loadable" with sufficient amounts > of elbow grease. "In-place loading" is an awkward and, I think, nonsensical term (for the reason that data loads are always in-place: the place the data is loaded to is the place the data is loaded to!). As someone else poined out, I think you're really asking about "relocatable data structures". A data structure can be trivially made relocatable by ensuring you instead of absolute pointers use relative offsets to link entries together. (Usually this makes your data structure smaller as well, with caching benefits as a result, in that offsets often can be smaller than a 4 or 8 byte pointer, sometimes much smaller.) You can also relocate pointer-based data structures by saving a patch table with the data structure. Said patch table contains the locations of pointers that must be updated when the data structure is moved. This is pretty ugly, IMO. Assuming you have a priori information about the data structure you don't necessarily have to store information about every pointer in this patch table, but that just makes it even uglier (now the patching is both code and data dependent). So, my recommendation is to use relative offsets and be done with it once and for all! Christer Ericson http://realtimecollisiondetection.net/ |
From: Tom P. <ga...@fa...> - 2005-11-29 05:41:22
|
> As someone else poined out, I think you're really asking about > "relocatable data structures". FWIW, on the Syphon Filter games on the first PlayStation, we actually stored the starting image of each level of our game data as a memory dump, and kept the loading code in the executable but disabled by a global boolean switch (so the code wouldn't change size and invalidate where we were loading the data). In short, we wrote out everything from the end of the executable to the end of the used heap to disk once the load was complete, and the "final" build just loaded stuff this whole file into the same place, bypassing all of the other loading and fixup code, loading the startup image into memory. We took this process to "the next level" by writing out the frontend state also and then linked that into the executable itself so that the initial frontend load happened as a part of the executable itself loading. After the initial load, all of our streamed data actually had inter-object references "baked" into the data, since we always knew where everything was loading as the levels (of 10-15M a piece) streamed into place. As one might imagine, this required a considerable push on the tools to create this data for us, but it also allowed us to guarantee that we'd never run out of memory because by definition we couldn't fragment. That discussion could go on forever, though. ;) Needless to say, I'm a big fan of deterministic data loading. Many if not most games could do something like this, but it isn't exactly glamorous work and most don't even think it's a problem that needs to be solved. For us, we did it just because we wanted to get load times down since we thought gamers would appreciate it. :) The grand irony of all of this is that while we had deterministic data loads, we had relocatable code modules. However, those too always loaded up in the same place every time you loaded a given level, they'd only move around level-to-level. (These modules were included in the "first load" dataset for a level.) -tom! |
From: Richard M. <mi...@tr...> - 2005-11-29 19:38:17
|
I'll see your heap and raise you one ;-) On Speed Kings, PS2, we had a similar system. Except our heap was actually relocatable too! The code that wrote out the heap dump did the following: 1. Allocate 16 bytes. 2. Load model data using standard method 3. Make a copy of the heap. 4. Unload model data. 5. Allocate 16 more bytes. 6. Load model data again using standard method. By then looking at the differences between the two heap dumps, it could then easily find the parts that needed relocating because they would differ by exactly 16 bytes each time. We then used that information to write out a relocation table along with the heap dump. I'm not sure I'd recommend using this system in future (it was a bit too crazy), but it worked quite well at the time :-) -- ()() Richard Mitton ( '.') (")_(") code jester .:. treyarch .:. mi...@tr... ----- Original Message ----- From: "Tom Plunket" <ga...@fa...> To: <gda...@li...> Sent: Monday, November 28, 2005 9:41 pm Subject: Re: [Algorithms] In-place loaded data structures. >> As someone else poined out, I think you're really asking about >> "relocatable data structures". > > FWIW, on the Syphon Filter games on the first PlayStation, we > actually stored the starting image of each level of our game > data as a memory dump, and kept the loading code in the > executable but disabled by a global boolean switch (so the code > wouldn't change size and invalidate where we were loading the > data). In short, we wrote out everything from the end of the > executable to the end of the used heap to disk once the load > was complete, and the "final" build just loaded stuff this > whole file into the same place, bypassing all of the other > loading and fixup code, loading the startup image into memory. > We took this process to "the next level" by writing out the > frontend state also and then linked that into the executable > itself so that the initial frontend load happened as a part of > the executable itself loading. > > After the initial load, all of our streamed data actually had > inter-object references "baked" into the data, since we always > knew where everything was loading as the levels (of 10-15M a > piece) streamed into place. As one might imagine, this > required a considerable push on the tools to create this data > for us, but it also allowed us to guarantee that we'd never run > out of memory because by definition we couldn't fragment. That > discussion could go on forever, though. ;) > > Needless to say, I'm a big fan of deterministic data loading. > Many if not most games could do something like this, but it > isn't exactly glamorous work and most don't even think it's a > problem that needs to be solved. For us, we did it just > because we wanted to get load times down since we thought > gamers would appreciate it. :) > > The grand irony of all of this is that while we had > deterministic data loads, we had relocatable code modules. > However, those too always loaded up in the same place every > time you loaded a given level, they'd only move around > level-to-level. (These modules were included in the "first > load" dataset for a level.) > > -tom! > > > > ------------------------------------------------------- > This SF.net email is sponsored by: Splunk Inc. Do you grep through log > files > for problems? Stop! Download the new AJAX search engine that makes > searching your log files as easy as surfing the web. DOWNLOAD SPLUNK! > http://ads.osdn.com/?ad_id=7637&alloc_id=16865&op=click > _______________________________________________ > GDAlgorithms-list mailing list > GDA...@li... > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_id=6188 |
From: Rok E. <ro...@si...> - 2005-11-30 10:53:35
|
>Needless to say, I'm a big fan of deterministic data loading. >Many if not most games could do something like this, but it >isn't exactly glamorous work and most don't even think it's a >problem that needs to be solved. > Well in my experience it generally isn't. In our PS2 games we are getting over 90% of theoretical raw-reading speed (as in, reading a rawblock of data from disc compared to reading the same amount of data with all the asociated object creation, decompression, and other setup that happens on level start). The point I'm getting at is that all the stuff I mentioned in the brackets is typically at least two orders of magnitude faster then any kind of optical disc read, and as such trivially hides behind the disc reading process, you just have to make sure the two are really interleaving eachother. Obviously the situation changes if you want to stream leveldata seamlessly during gameplay - as especially on PS2 CPU time is by far the most precious resource you have ;) but for regular "load level -> play level" type of game, deterministic data loads are really not needed IMO. |
From: Tom P. <ga...@fa...> - 2005-11-30 19:29:06
|
>>Needless to say, I'm a big fan of deterministic data loading. >>Many if not most games could do something like this, but it >>isn't exactly glamorous work and most don't even think it's a >>problem that needs to be solved. >> > Well in my experience it generally isn't. In our PS2 games we > are getting over 90% of theoretical raw-reading speed (as in, > reading a rawblock of data from disc compared to reading the > same amount of data with all the asociated object creation, > decompression, and other setup that happens on level start). Sure. For level loads you're correct as long as your files are ordered appropriately on the disc. As long as you're not seeking the head all over the place, so on and so forth. That requires a different tool to be authored though, or some manual effort laying out the disc, or an alternative file handler that redirects every file read out to a "stream" file or something to that effect. Start seeking the head, and you're finished. ;) > The point I'm getting at is that all the stuff I mentioned in > the brackets is typically at least two orders of magnitude > faster then any kind of optical disc read, and as such > trivially hides behind the disc reading process, you just have > to make sure the two are really interleaving eachother. Right; compressing your data and decompressing on the fly will likely result in faster data loads since less time is taken spinning data off the disc. This actually amazed me back in the days of Stacker which compressed your hard drive... Anyway, a tangent... > Obviously the situation changes if you want to stream > leveldata seamlessly during gameplay - as especially on PS2 > CPU time is by far the most precious resource you have ;) but > for regular "load level -> play level" type of game, > deterministic data loads are really not needed IMO. More and more, though, games /need/ to stream assets during gameplay. About the only games that don't need to stream anymore are arena fighting games, but even they would be able to stream cool things in during the battles, I would think. If you want to stream data, if you want to have memory changing while you play the game, you really should (IMO) investigate means to allow you to do this stuff non-deterministically. Fragmentation /will/ kill you if you allow it to occur. -tom! |
From: <Bra...@pl...> - 2005-11-30 19:38:03
|
Wow, looks like I started quite a thread. Thanks for all the extremely useful ideas and information. Lots to think about! Brad... gda...@li... wrote on 11/30/2005 11:29:02 AM: > >>Needless to say, I'm a big fan of deterministic data loading. > >>Many if not most games could do something like this, but it > >>isn't exactly glamorous work and most don't even think it's a > >>problem that needs to be solved. > >> > > Well in my experience it generally isn't. In our PS2 games we > > are getting over 90% of theoretical raw-reading speed (as in, > > reading a rawblock of data from disc compared to reading the > > same amount of data with all the asociated object creation, > > decompression, and other setup that happens on level start). > > Sure. For level loads you're correct as long as your files are > ordered appropriately on the disc. As long as you're not > seeking the head all over the place, so on and so forth. That > requires a different tool to be authored though, or some manual > effort laying out the disc, or an alternative file handler that > redirects every file read out to a "stream" file or something > to that effect. > > Start seeking the head, and you're finished. ;) > > > The point I'm getting at is that all the stuff I mentioned in > > the brackets is typically at least two orders of magnitude > > faster then any kind of optical disc read, and as such > > trivially hides behind the disc reading process, you just have > > to make sure the two are really interleaving eachother. > > Right; compressing your data and decompressing on the fly will > likely result in faster data loads since less time is taken > spinning data off the disc. This actually amazed me back in > the days of Stacker which compressed your hard drive... > Anyway, a tangent... > > > Obviously the situation changes if you want to stream > > leveldata seamlessly during gameplay - as especially on PS2 > > CPU time is by far the most precious resource you have ;) but > > for regular "load level -> play level" type of game, > > deterministic data loads are really not needed IMO. > > More and more, though, games /need/ to stream assets during > gameplay. About the only games that don't need to stream > anymore are arena fighting games, but even they would be able > to stream cool things in during the battles, I would think. If > you want to stream data, if you want to have memory changing > while you play the game, you really should (IMO) investigate > means to allow you to do this stuff non-deterministically. > Fragmentation /will/ kill you if you allow it to occur. > > -tom! > > > ------------------------------------------------------- > This SF.net email is sponsored by: Splunk Inc. Do you grep through log files > for problems? Stop! Download the new AJAX search engine that makes > searching your log files as easy as surfing the web. DOWNLOAD SPLUNK! > http://ads.osdn.com/?ad_id=7637&alloc_id=16865&op=click > _______________________________________________ > GDAlgorithms-list mailing list > GDA...@li... > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_id=6188 > > |
From: Alen L. <ale...@cr...> - 2005-11-30 22:22:29
|
> More and more, though, games /need/ to stream assets during > gameplay. About the only games that don't need to stream > anymore are arena fighting games, but even they would be able > to stream cool things in during the battles, I would think. If > you want to stream data, if you want to have memory changing > while you play the game, you really should (IMO) investigate > means to allow you to do this stuff non-deterministically. > Fragmentation /will/ kill you if you allow it to occur. This is also an interesting side-topic that loading goes hand-to-hand with. I have a feeling that Doug Lea's allocator is doing an excellent job in preventing any serious fragmentation problems (unless your usage patterns are absolutely insane). On a recent console project, it allowed us to be relatively care-free regarding fragmentation. (The only problem was in the physical memory allocations that had to go straight from the non-remappable pool, allocated by the system, and it is a bit difficult to get two allocators to cooperate. But that can be solved.) In general, I believe it would be much easier to do streaming if one would relax regarding fragmentation. Do you think it is not possible? Cheers, Alen |
From: <phi...@pl...> - 2005-12-01 03:06:21
|
tom!: > Start seeking the head, and you're finished. ;) Indeed, this is the major operation to optimise for a title that streams, or just cares about load times. Always always always pre-load the TOC, so you don't have to move the head to find out where a file that never changes lives. Write an analyser that flags when the head moves, when it stops, and when (and what) it's reading. Get clever and work out when the head actually moves or just tilts (which is way way faster). Or get stupid, and spend a long time with your ear stuck to the drive. Write a version that logs all of this, and get your testers to play through the game with the logging turned on. Write your own file system that allows you to place multiple copies of key files on the disc. Make your toolchain spit out hint files that tell you which levels load which auxilary files, and have your packer take note of them. Have it reference a hand-edited hint file, that you generate by analysing the logs. Analyse the logs using Excel. Think very seriously about automating that process too. Tell your test department that the 'Loading' message is a reportable bug. Locate the one area in the game that is impossible to remove the 'Loading' message from, without altering the speed of light. Miss the area where if you backtrack in a particular way, you get the 'Loading' message. Write your name in the gaps between files. Laugh when the hackers remove all the duplicated files from the warez version and then wonder why the game takes ages to load. Cheers, Phil |
From: Tom P. <ga...@fa...> - 2005-12-01 03:59:41
|
> Tell your test department that the 'Loading' message is a > reportable bug. Three Cheers! I never really thought about loading or load time optimization while we were working on <our PSX game>, but thought the system we had was a cool bit of engineering. Then that Crash Bandicoot game came out in the first batch of games for the then-new PS2, and what did it have, 60-second load times? Holy hell. I then realized why it was something that you'd actually want to care about. Subsequently, it made me amused to see "Loading" and get a hitch while playing Halo on the Xbox. Loading data off the hard drive and hitching? Wow, we (not me <g>) actually were pretty smart back in '97. ;) -tom! |
From: Rok E. <ro...@si...> - 2005-12-02 03:47:53
|
>requires a different tool to be authored though, or some manual >effort laying out the disc, or an alternative file handler that >redirects every file read out to a "stream" file or something >to that effect. Yea that's pretty much how we do things (single large file that is treated as a "stream" most of the time). >> Start seeking the head, and you're finished. ;) > > Which in particular goes for one recent handheld platform. I've actually been considering pregenerating "random" sets of enemy cars and store then on disc as continous batches since seek times are such a pain there... >If >you want to stream data, if you want to have memory changing >while you play the game, you really should (IMO) investigate >means to allow you to do this stuff non-deterministically. >Fragmentation /will/ kill you if you allow it to occur. > On that I completely agree, which is one reason I've found this thread particularly interesting read. It's also something that I've been investigating for the future projects. >Then that Crash Bandicoot game came out in the first batch of >games for the then-new PS2, and what did it have, 60-second >load times? Holy hell. > > Heh, I originally realized this one on our first CD test - when the level took 10 minutes to load ;) Which is one anecdote I keep telling people when trying to explain WHY physical drive transfer speeds have very little with loading issues in most games. In final we got the load time down to ~7seconds, and that loads roughly 2x the raw data that original 10minutes did ;) (and it's compressed with LZW, which original data also wasn't). |
From: Jamie F. <ja...@qu...> - 2005-12-01 04:02:11
|
phi...@pl... wrote: > tom!: > >>Start seeking the head, and you're finished. ;) > > > Indeed, this is the major operation to optimise for a title that streams, > or just cares about load times. > > Always always always pre-load the TOC, so you don't have to move the head > to find out where a file that never changes lives. The alternative, of course, is to have one file. > Write your own file system that allows you to place multiple copies of key > files on the disc. The equivalent if you have a single file is to have multiple copies of the data within the file. > Tell your test department that the 'Loading' message is a reportable bug. > > Locate the one area in the game that is impossible to remove the 'Loading' > message from, without altering the speed of light. > > Miss the area where if you backtrack in a particular way, you get the > 'Loading' message. It's quite possible to do a fair amount of work deterministically, and know it'll be safe; but when you try to push it that little bit further, there always comes a time when driving down a particular alleyway where 4 areas just happen to meet causes something to overstretch itself :) 7 years ago everything used to crash when this happened, so at least you could be sure of noticing :) Jamie |
From: <phi...@pl...> - 2005-12-01 04:37:42
|
> > Always always always pre-load the TOC, so you don't have to move the head > > to find out where a file that never changes lives. > > The alternative, of course, is to have one file. We actually had two, one for each layer. Well, three, as it was easier to keep the TOC file seperate (which is how the hackers stripped it so quickly, no such luck for you naughty boys next time :). We didn't bother compressing the data, although we had the CPU for it. IOP sits at 97% idle most of the time. Cheers, Phil |
From: Jamie F. <ja...@qu...> - 2005-12-01 10:20:57
|
phi...@pl... wrote: > > We didn't bother compressing the data, although we had the CPU for it. IOP > sits at 97% idle most of the time. > At least you get to keep the IOP memory :) Jamie |
From: <phi...@pl...> - 2005-12-01 23:06:23
|
Jamie: > phi...@pl... wrote: > > We didn't bother compressing the data, although we had the CPU for it. IOP sits at 97% idle most of the time. > At least you get to keep the IOP memory :) All went to file buffers, and sounds. I think there's maybe the 4k on VU0 that we didn't use. There's only a couple of K free on the DVD too. Cheers, Phil |
From: Jamie F. <ja...@qu...> - 2005-12-02 09:17:08
|
phi...@pl... wrote: > Jamie: > >>phi...@pl... wrote: >> >>>We didn't bother compressing the data, although we had the CPU for it. > > IOP sits at 97% idle most of the time. > >>At least you get to keep the IOP memory :) > > > All went to file buffers, and sounds. I think there's maybe the 4k on VU0 > that we didn't use. There's only a couple of K free on the DVD too. It's a small enough buffer even if you're not doing anything much on the IOP. I'm surprised you're not using the VU0 memory, though :) Jamie |
From: <phi...@pl...> - 2005-12-02 20:57:45
|
Jamie > phi...@pl... wrote: > > All went to file buffers, and sounds. I think there's maybe the 4k on VU0 > > that we didn't use. There's only a couple of K free on the DVD too. > > It's a small enough buffer even if you're not doing anything much on the > IOP. I'm surprised you're not using the VU0 memory, though :) Well it was more for lack of developer time, rather than lack of memory (I was busy learning important lessons about mutexes). Also, we made enough savings by minimising seeks, and the designers/artists made large enough load zones that we didn't need to compress. Which is great, because available memory just grew by a significantly larger factor than transfer rate, and I bet that head isn't moving much faster either. Cheers, Phil PS Actually we may have some sort of lookup table in VU0, I can't recall. We use it primarily in macro mode anyway. |
From: <Bra...@pl...> - 2005-11-30 19:24:28
|
> "In-place loading" is an awkward and, I think, nonsensical term > (for the reason that data loads are always in-place: the place > the data is loaded to is the place the data is loaded to!). > As someone else poined out, I think you're really asking about > "relocatable data structures". Yes, I agree. That was part of why I was having such a hard time searching the archives/Google for information about it. :) As other posters further down the thread pointed out, there's not much "standard" terminology in regard to this kind of stuff. Everyone seems to call it something a little bit different at each of their respective studios. Anyway, thanks for your input. Brad... |
From: James L. <ja...@in...> - 2005-11-29 02:58:22
|
I think the thread you're after was called "relocatable data structures": http://sourceforge.net/search/?type_of_search=mlists&forum_id=6188&group_id=7932&atid=0&words=relocatable+data+structures&Search=Search James Bra...@pl... wrote: > I remember some talk a while back about in-place loaded data structures. > As in, all you have to do to "unpersist" the data is load it up into a > contiguous block of memory and (possibly) fix up relative offsets into > absolute pointers. IIRC, someone mentioned that they had written an > in-place hash table and put it up on SourceForge? Can anyone point me to > this discussion in the archives? > > Anyway, is there a magic Google phrase for this type of stuff? Does > anyone know of any gentle introductions to in-place data structures, or is > it just part of the collective black-art of console programming that no > one talks about? :) > > Thanks, > > Brad... > > > > ------------------------------------------------------- > This SF.net email is sponsored by: Splunk Inc. Do you grep through log files > for problems? Stop! Download the new AJAX search engine that makes > searching your log files as easy as surfing the web. DOWNLOAD SPLUNK! > http://ads.osdn.com/?ad_id=7637&alloc_id=16865&op=click > _______________________________________________ > GDAlgorithms-list mailing list > GDA...@li... > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_id=6188 > > |
From: Charles N. <cha...@gm...> - 2005-11-29 04:37:23
|
[reply off-list] I've been working on a system like this for the past 2 months or so. My data structures are POD only (no vptr/vtable) with relative pointer addresses (for the reasons Christer suggests). The biggest problem I've ha= d was having both the tool and the game know the structure layout. The bungie guys (at least, as Butcher described at Game|Tech) do their in-place loading by using a macro-language to describe the metadata for their tools, a la struct Foo { int x; char y; } TAG_MACRO_BEGIN(Foo) TAG_FIELD(int, x) TAG_FIELD(char, y) TAG_MACRO_END() This file gets compiled into both the game and the tool, so that the tool can auto-generate GUI widgets and know how to spit them out in the platform-native structure. When it's time to load, their engine streams in a huge chunked file and after pointer fixup they're all ready to go. They actually did some vtable/vptr serialization for their havok stuff (all C++ objects) IIRC. I'm taking a more data-driven approach- I have XML files that describe eac= h structure, like <class name=3D"Foo"> <field type=3D"int" name=3D"x" min=3D"0" max=3D"30" /> <field type=3D"char" name=3D"y" /> </class> this schema is read by the editor which generates UI widgets. Actual level data gets spit out in schema-conformant XML, like <Layout> <Foo name=3D"Designer_placed_foo_1"> <x>15</x> <y>c</y> </Foo> </Layout> An offline tool turns the above xml into raw bit patterns that can simply b= e reinterpret_cast<>ed into their correct structures, which themselves are generated by another tool. That tool takes a schema as input and spits out .h files, like struct FooDataBlock { int x; char y; } It also emits pointer fixup code. It can handle strings, arrays, pointers (static & polymorphic), etc... The game only links with the generated code and none of the runtime stuff. This keeps it lean and avoids needing things like an XML parser on board, while the tools can use boost, MSXML, all the fun stuff. It's interesting to note that the process of baking all of this verbose XML into a binary file is akin to compiling and linking a static executable. Each independen= t XML file (one per model, layout, entity archetype, trigger set) is independently compiled into a binary with an unresolved external table, and the linker simply starts at the 'entry point' (top-level node in the data graph) and pulls in everything it needs, doing linking and relative address fixup along the way. The result is a perfect data graph of every asset you need for whatever chunk of play you're entering. It seems to be a complete solution for non-streaming games. I'm most excited about extending the compile/link metaphor to streaming games- DLLs and runtime link-up. There are a ton of directions it could be taken. Havok takes this approach to the extreme and doesn't even introduce the concept of the 'schema'- every serializable class has an associated meta-class that describes the memory/field layout for its target. Their serialized XML simply has these meta-classes at the top, like <class name=3D"Foo"> <field offset=3D"0" type=3D"int" name=3D"x" /> <field offset=3D"4" type=3D"char" name=3D"y" /> </class> <Foo> <x>3</x> <y>c</y> </Foo> They parse your C++ to generate the "FooClass" class that describes your Fo= o class, and at runtime you get a static global object called 'hkFooClass' which you can use as a token for searching packfiles, like hkPackfileReader reader(memoryBlob, memoryBlobSize); hkVariant* object =3D reader.FindFirstOf(hkFooClass); and an hkVariant looks like struct hkVariant { void* object; hkClass* classType; } Their packfiles do hold actual objects, though, rigid bodies that you can use _in-place_, which is pretty cool. It gets ugly when their vectors grow past their memory boundaries and are dynamically re-allocated (seems to def= y the point a bit), but all in all it's very useful for limited-memory consoles (psp i guess) where you don't want to keep around any prototype data (from which you instantiate the _actual_ game objects, as i'm doing). OTOH, the heavyweight prototype data is always in the form of textures, sounds and vertex buffers, i'm not sure that game object data really takes up that much memory but i guess it depends on the game you're making. If i were better at C# or could take the time, i think another fine way to take my approach would be to make an assembly that has the data schema, lik= e [MetaSerialize] class Foo { [min(0), max(30)] int x; char c; }; Then tools would load this assembly and use introspection/reflection to generate UIs and data. A C# tool could easily turn one of these metadata-annotated classes to generate the C++ runtime stuff. Anyway, sorry if i skimped on some details or if this was wildly off-topic (i had a few glasses of wine with dinner and just checked my mail to find this conversation). If you're interested in seeing a little sample app i whipped up, i could send it along. I'm always interested in talking about this stuff though. btw, are you at sony san diego by any chance? Do you know Max Elliot? Regards, charles nicholson. On 11/28/05, Bra...@pl... <Bra...@pl...= > wrote: > > I remember some talk a while back about in-place loaded data structures. > As in, all you have to do to "unpersist" the data is load it up into a > contiguous block of memory and (possibly) fix up relative offsets into > absolute pointers. IIRC, someone mentioned that they had written an > in-place hash table and put it up on SourceForge? Can anyone point me to > this discussion in the archives? > > Anyway, is there a magic Google phrase for this type of stuff? Does > anyone know of any gentle introductions to in-place data structures, or i= s > it just part of the collective black-art of console programming that no > one talks about? :) > > Thanks, > > Brad... > > > > ------------------------------------------------------- > This SF.net email is sponsored by: Splunk Inc. Do you grep through log > files > for problems? Stop! Download the new AJAX search engine that makes > searching your log files as easy as surfing the web. DOWNLOAD SPLUNK! > http://ads.osdn.com/?ad_id=3D7637&alloc_id=3D16865&op=3Dclick > _______________________________________________ > GDAlgorithms-list mailing list > GDA...@li... > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_id=3D6188 > |
From: Charles N. <cha...@gm...> - 2005-11-29 04:39:08
|
Damn. :) On 11/28/05, Charles Nicholson <cha...@gm...> wrote: > > [reply off-list] > > I've been working on a system like this for the past 2 months or so. My > data structures are POD only (no vptr/vtable) with relative pointer > addresses (for the reasons Christer suggests). The biggest problem I've = had > was having both the tool and the game know the structure layout. > > The bungie guys (at least, as Butcher described at Game|Tech) do their > in-place loading by using a macro-language to describe the metadata for > their tools, a la > > struct Foo > { > int x; > char y; > } > > TAG_MACRO_BEGIN(Foo) > TAG_FIELD(int, x) > TAG_FIELD(char, y) > TAG_MACRO_END() > > This file gets compiled into both the game and the tool, so that the tool > can auto-generate GUI widgets and know how to spit them out in the > platform-native structure. When it's time to load, their engine streams = in > a huge chunked file and after pointer fixup they're all ready to go. The= y > actually did some vtable/vptr serialization for their havok stuff (all C+= + > objects) IIRC. > > I'm taking a more data-driven approach- I have XML files that describe > each structure, like > > <class name=3D"Foo"> > <field type=3D"int" name=3D"x" min=3D"0" max=3D"30" /> > <field type=3D"char" name=3D"y" /> > </class> > > this schema is read by the editor which generates UI widgets. Actual > level data gets spit out in schema-conformant XML, like > > <Layout> > <Foo name=3D"Designer_placed_foo_1"> > <x>15</x> > <y>c</y> > </Foo> > </Layout> > > An offline tool turns the above xml into raw bit patterns that can simply > be reinterpret_cast<>ed into their correct structures, which themselves a= re > generated by another tool. That tool takes a schema as input and spits o= ut > .h files, like > > struct FooDataBlock > { > int x; > char y; > } > > It also emits pointer fixup code. It can handle strings, arrays, pointers > (static & polymorphic), etc... > > The game only links with the generated code and none of the runtime > stuff. This keeps it lean and avoids needing things like an XML parser o= n > board, while the tools can use boost, MSXML, all the fun stuff. It's > interesting to note that the process of baking all of this verbose XML in= to > a binary file is akin to compiling and linking a static executable. Each > independent XML file (one per model, layout, entity archetype, trigger se= t) > is independently compiled into a binary with an unresolved external table= , > and the linker simply starts at the 'entry point' (top-level node in the > data graph) and pulls in everything it needs, doing linking and relative > address fixup along the way. The result is a perfect data graph of every > asset you need for whatever chunk of play you're entering. It seems to b= e a > complete solution for non-streaming games. > > I'm most excited about extending the compile/link metaphor to streaming > games- DLLs and runtime link-up. There are a ton of directions it could = be > taken. > > > Havok takes this approach to the extreme and doesn't even introduce the > concept of the 'schema'- every serializable class has an associated > meta-class that describes the memory/field layout for its target. Their > serialized XML simply has these meta-classes at the top, like > > <class name=3D"Foo"> > <field offset=3D"0" type=3D"int" name=3D"x" /> > <field offset=3D"4" type=3D"char" name=3D"y" /> > </class> > <Foo> > <x>3</x> > <y>c</y> > </Foo> > > They parse your C++ to generate the "FooClass" class that describes your > Foo class, and at runtime you get a static global object called 'hkFooCla= ss' > which you can use as a token for searching packfiles, like > > hkPackfileReader reader(memoryBlob, memoryBlobSize); > hkVariant* object =3D reader.FindFirstOf(hkFooClass); > > and an hkVariant looks like > > struct hkVariant > { > void* object; > hkClass* classType; > } > > Their packfiles do hold actual objects, though, rigid bodies that you can > use _in-place_, which is pretty cool. It gets ugly when their vectors gr= ow > past their memory boundaries and are dynamically re-allocated (seems to d= efy > the point a bit), but all in all it's very useful for limited-memory > consoles (psp i guess) where you don't want to keep around any prototype > data (from which you instantiate the _actual_ game objects, as i'm doing)= . > OTOH, the heavyweight prototype data is always in the form of textures, > sounds and vertex buffers, i'm not sure that game object data really take= s > up that much memory but i guess it depends on the game you're making. > > If i were better at C# or could take the time, i think another fine way t= o > take my approach would be to make an assembly that has the data schema, l= ike > > [MetaSerialize] > class Foo > { > [min(0), max(30)] > int x; > > char c; > }; > > Then tools would load this assembly and use introspection/reflection to > generate UIs and data. A C# tool could easily turn one of these > metadata-annotated classes to generate the C++ runtime stuff. > > Anyway, sorry if i skimped on some details or if this was wildly off-topi= c > (i had a few glasses of wine with dinner and just checked my mail to find > this conversation). If you're interested in seeing a little sample app i > whipped up, i could send it along. I'm always interested in talking abou= t > this stuff though. > > btw, are you at sony san diego by any chance? Do you know Max Elliot? > > Regards, > charles nicholson. > > On 11/28/05, Bra...@pl... < > Bra...@pl...> wrote: > > > > I remember some talk a while back about in-place loaded data structures= . > > As in, all you have to do to "unpersist" the data is load it up into a > > contiguous block of memory and (possibly) fix up relative offsets into > > absolute pointers. IIRC, someone mentioned that they had written an > > in-place hash table and put it up on SourceForge? Can anyone point me > > to > > this discussion in the archives? > > > > Anyway, is there a magic Google phrase for this type of stuff? Does > > anyone know of any gentle introductions to in-place data structures, or > > is > > it just part of the collective black-art of console programming that no > > one talks about? :) > > > > Thanks, > > > > Brad... > > > > > > > > ------------------------------------------------------- > > This SF.net email is sponsored by: Splunk Inc. Do you grep through log > > files > > for problems? Stop! Download the new AJAX search engine that makes > > searching your log files as easy as surfing the web. DOWNLOAD SPLUNK! > > http://ads.osdn.com/?ad_id=3D7637&alloc_id=3D16865&op=3Dclick > > _______________________________________________ > > GDAlgorithms-list mailing list > > GDA...@li... > > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > > Archives: > > http://sourceforge.net/mailarchive/forum.php?forum_id=3D6188 > > > > |
From: Ben G. <be...@ga...> - 2005-11-29 05:04:40
|
Charles Nicholson wrote: > Damn. :) I found it interesting... Thanks for sharing, even if inadvertantly. :) On a more general note, is this sort of technique something that a lot of people are using in their engines? What are the downsides to this sort of data storage method? Does endian-ness mess it up horribly? It seems like with the addition of a little versioning info, you'd have a really sweet general purpose data format... Ben |