Last visit was: It is currently Fri Mar 29, 2024 5:03 am


All times are UTC-05:00




Post new topic Reply to topic  [60 posts ] 
Author Message
 Post subject:Re: Loading/saving duration
PostPosted:Fri Mar 19, 2010 4:03 pm 
Literally Nine
User avatar
 

Joined:Sat Apr 02, 2005 3:31 pm
Posts:1171
Location:The vicinity of an area adjacent to a location.
It sounds like people want to know my idea.

Well, before I get into solutions, I want to summarize the problem as it stands. I should also say that this idea is only in the planning stage, and I haven't actually made a working example yet. But the idea is fairly straightforward.

What's the current process for saving?
  • Pause the game, to prevent the data structures from changing.
  • Serialize the data into XML.
  • Write to disk.
What's the current problem with the savegame timing?
  • The game engine currently MUST pause until the data is serialized.
  • The serialization can take a long time and a LOT of RAM.
  • The RAM usage ends up causing a huge cascade of page faults.
What happened to Onlink? Why did this start happening?
Unfortunately, the XML save games that we introduced are the main problem. Our main goal in using XML was that we wouldn't have to make very many compatibility breaks (making users recreate profiles) every time we distributed a new build of the game. While our main goal has been achieved, we neglected to consider some of the obvious hardware limitations.

Why do the save files grow so much over time?
The game world constantly changes, and things get added to it all the time. When you start the game, most of the in-game servers don't have any logs at all. As each minute passes, your fellow Uplink agents initiate connections, bouncing through servers, hacking things, etc. So the connection logs and bank transaction logs keep increasing in size.

XML did magnify a problem here, in that we didn't know that the logs were kept indefinitely (meaning your savegame would continue to bloat forever). We fixed this by culling anything > 3 in-game months old (or some such age). But you should know that until you reach that point (3 in-game months after the game starts), your save game will increase in size. After that point, your save game size should not vary much.

What's the solution? (or: Get to the point!)
There are a multitude of things that can be done to rectify the situation:
  • Stream the save to disk instead of buffering it into RAM and then writing all at once.
  • Eliminate the need to pause the game for saving to disk.
  • Eliminate redundancy in the dataset.
The first item above is theoretically not very painful to implement, but it does require some big code changes.

The second item above is already implemented on Linux and Mac builds, and my idea for the Windows build should create the same effect.

And the third item is one reason why we're developing Cerberus. We see Onlink's need for redundant data as a critical design flaw which we can't fix in Onlink without doing a rewrite.

My idea to accomplish the second item in the list above is to create copy-on-write data structures, allowing us to essentially "snapshot" the game state. See this article for an excellent explanation of what copy-on-write would entail.

On Linux and Mac, we use the fork() call to essentially create an identical copy of the Onlink process, allowing us to save the game state without ever pausing the game for more than a hundredth of a second, and this would be much the same thing. But considering how Onlink is currently coded, it's unlikely we'll ever get the copy-on-write data structures to work perfectly (which is why fork() is such a blessing). We can try it though, and see what happens. But I suspect our copy-on-write structures would best work with Cerberus, since we're designing it from the ground up.

_________________
- Tycho

Image


Top
Offline  
 Post subject:Re: Loading/saving duration
PostPosted:Fri Mar 19, 2010 4:15 pm 
 

Joined:Tue Mar 16, 2010 9:47 am
Posts:27
Quote:
It sounds like people want to know my idea.

Well, before I get into solutions, I want to summarize the problem as it stands. I should also say that this idea is only in the planning stage, and I haven't actually made a working example yet. But the idea is fairly straightforward.

What's the current process for saving?
  • Pause the game, to prevent the data structures from changing.
  • Serialize the data into XML.
  • Write to disk.
What's the current problem with the savegame timing?
  • The game engine currently MUST pause until the data is serialized.
  • The serialization can take a long time and a LOT of RAM.
  • The RAM usage ends up causing a huge cascade of page faults.
What happened to Onlink? Why did this start happening?
Unfortunately, the XML save games that we introduced are the main problem. Our main goal in using XML was that we wouldn't have to make very many compatibility breaks (making users recreate profiles) every time we distributed a new build of the game. While our main goal has been achieved, we neglected to consider some of the obvious hardware limitations.

Why do the save files grow so much over time?
The game world constantly changes, and things get added to it all the time. When you start the game, most of the in-game servers don't have any logs at all. As each minute passes, your fellow Uplink agents initiate connections, bouncing through servers, hacking things, etc. So the connection logs and bank transaction logs keep increasing in size.

XML did magnify a problem here, in that we didn't know that the logs were kept indefinitely (meaning your savegame would continue to bloat forever). We fixed this by culling anything > 3 in-game months old (or some such age). But you should know that until you reach that point (3 in-game months after the game starts), your save game will increase in size. After that point, your save game size should not vary much.

What's the solution? (or: Get to the point!)
There are a multitude of things that can be done to rectify the situation:
  • Stream the save to disk instead of buffering it into RAM and then writing all at once.
  • Eliminate the need to pause the game for saving to disk.
  • Eliminate redundancy in the dataset.
The first item above is theoretically not very painful to implement, but it does require some big code changes.

The second item above is already implemented on Linux and Mac builds, and my idea for the Windows build should create the same effect.

And the third item is one reason why we're developing Cerberus. We see Onlink's need for redundant data as a critical design flaw which we can't fix in Onlink without doing a rewrite.

My idea to accomplish the second item in the list above is to create copy-on-write data structures, allowing us to essentially "snapshot" the game state. See this article for an excellent explanation of what copy-on-write would entail.

On Linux and Mac, we use the fork() call to essentially create an identical copy of the Onlink process, allowing us to save the game state without ever pausing the game for more than a hundredth of a second, and this would be much the same thing. But considering how Onlink is currently coded, it's unlikely we'll ever get the copy-on-write data structures to work perfectly (which is why fork() is such a blessing). We can try it though, and see what happens. But I suspect our copy-on-write structures would best work with Cerberus, since we're designing it from the ground up.
I saw a suggestion from someone for using a SQLlite database or some other database. Seeing there is allot of data, and databases are well.. designed for lots of data :-)

I can only assume you have some XML Schema somewhere, wouldn't it be a rather "small" step of converting this schema into a dbase of some sorts?

If I recall correctly, SQLlite uses files as a dbase, doesn't need no service running. I used it on a VERY small task for school a (few?) years back, but that was the only time I encountered SQLlite.

edit: so correct me if I'm wrong about SQLlite only needing files, no perticular service :-)

edit 2: Maybe I can answer my own question: if the gameworld changes constantly and you need to recreate the XML-file from scratch everytime, that would mean emptying and refilling the dbase at every save action, which doesn't sound like very efficient. I don't have allot of practical experience with efficiency so I wouldn't know, but maybe it would still be better than hogging the RAM everytime? Feedback please! This is interesting! :-)


Top
Offline  
 Post subject:Re: Loading/saving duration
PostPosted:Fri Mar 19, 2010 4:23 pm 
Literally Nine
User avatar
 

Joined:Sat Apr 02, 2005 3:31 pm
Posts:1171
Location:The vicinity of an area adjacent to a location.
Yes, SQLite would be the ideal option, really. It's something we have on the list of ideas for Cerberus. It's not going to happen for Onlink, though, because we'd have to rewrite everything.

_________________
- Tycho

Image


Top
Offline  
 Post subject:Re: Loading/saving duration
PostPosted:Fri Mar 19, 2010 4:31 pm 
 

Joined:Tue Mar 16, 2010 9:47 am
Posts:27
Quote:
Yes, SQLite would be the ideal option, really. It's something we have on the list of ideas for Cerberus. It's not going to happen for Onlink, though, because we'd have to rewrite everything.
I see :-) The question remains is then - IS Cerberus comming? I don't recall who exactly, I think either you or Miah(?) said that due to the GUI being such a pain in the ***, a new Onlink version would be more prone to come than Cerberus.

Out of curiosity, can you describe the magnitude of Onlink? You know, nr of classes, nr of code lines .. :-p I think you can say that without compromising too much inside information :-)

And rewriting everything, don't you just gotta rewrite the save() & load() methods? I mean, as long as they get & receive the correct parameters, the rest of the program isn't affected right? Unless there are XML reference scattered throughout the program :-) (Not judging by any means, absolutly not, just curious about the inside of a game program :-))

edit: bad technical jargon used :-p


Top
Offline  
 Post subject:Re: Loading/saving duration
PostPosted:Fri Mar 19, 2010 4:59 pm 
Literally Nine
User avatar
 

Joined:Sat Apr 02, 2005 3:31 pm
Posts:1171
Location:The vicinity of an area adjacent to a location.
Quote:
I see :-) The question remains is then - IS Cerberus comming? I don't recall who exactly, I think either you or Miah(?) said that due to the GUI being such a pain in the ***, a new Onlink version would be more prone to come than Cerberus.
We _want_ Cerberus, but we also hate doing the GUI for it. It's not that it's difficult, it's just incredibly tedious. We'll do it eventually, once the Onlink code tortures us enough.

Quote:
Out of curiosity, can you describe the magnitude of Onlink? You know, nr of classes, nr of code lines .. :-p I think you can say that without compromising too much inside information :-)
The Onlink Credits Machine (in-game) tells the code statistics from the time when it was released. But I can do a quick statistics check:
Code:
tycho@winslow ~/Development/onlink $ tools/stats.sh Total files: 547 Total lines: 134779
And a _very_ rough estimate on the number of classes:
Code:
tycho@winslow ~/Development/onlink/uplink/src $ find . -type f -name '*.h' -print0 | xargs -0 grep 'class' | grep -v ';$' | wc -l 405
Quote:
And rewriting everything, don't you just gotta rewrite the save() & load() methods? I mean, as long as they get & receive the correct parameters, the rest of the program isn't affected right? Unless there are XML reference scattered throughout the program :-) (Not judging by any means, absolutly not, just curious about the inside of a game program :-))
Not really. I mean, it's certainly possible to just do that, but it's not the best way. Modifying save/load only means that we'd be recreating an SQLite database on every save/load, and that'd end up being no different than using XML, performance-wise. The best way to do it would be to always store all the in-game elements in an SQLite database. So a "save" would never really need to happen, because it would in effect _always_ be saved to disk.

But maybe we should just start writing an SQLite backend. That'd actually make the Onlink codebase much more maintainable. If only I could get ahold of Miah, I could discuss this with him.

_________________
- Tycho

Image


Top
Offline  
 Post subject:Re: Loading/saving duration
PostPosted:Fri Mar 19, 2010 5:14 pm 
 

Joined:Thu Apr 28, 2005 3:57 pm
Posts:175
AOL:DKWiz214
Ahh, that makes a lot of sense now. Out of curiosity, how did Uplink avoid having so much RAM usage when it wrote the save files? I suppose since they only saved the game on close, there was no need to worry about pausing it, they just took the state of the game as it was closed and wrote while the menu ran, but I don't remember any sluggishness or severe hard drive thrashing indicative of page faults.

I'm not sure, but it seems after reading the article that a copy-on-write might not be the best idea, since it would require a large amount of work to adjust to, and it would end up taking up a lot of memory if old copies of things are floating around in the game world. However, if there was a way to "lock" the objects when saving begins, so that old copies persist, but changes create new versions that are unlocked (so as not to create extra copies), and then after saving is complete all locked objects are unlocked or destroyed depending on if they were changed, that might be a good method.

I may not be the best programmer out there, but I'm currently a junior studying game design and comp sci at RPI, and I would be more than happy to help you guys out if you want help. I'm in sore need of something challenging to keep my programming skills up. Of course, I don't want to impose or intrude, but if you are looking for help, keep me in mind. I've been watching the slow progress for 5 years and have loved everything so far.

_________________
The light shall be your demise.


Top
Offline  
 Post subject:Re: Loading/saving duration
PostPosted:Fri Mar 19, 2010 5:16 pm 
 

Joined:Tue Mar 16, 2010 9:47 am
Posts:27
Quote:
The Onlink Credits Machine (in-game) tells the code statistics from the time when it was released. But I can do a quick statistics check:
Code:
tycho@winslow ~/Development/onlink $ tools/stats.sh Total files: 547 Total lines: 134779
And a _very_ rough estimate on the number of classes:
Code:
tycho@winslow ~/Development/onlink/uplink/src $ find . -type f -name '*.h' -print0 | xargs -0 grep 'class' | grep -v ';$' | wc -l 405
Holy shit that's allot of code :-D makes my software design project give the complexity of a pen.. :-p
Quote:
Not really. I mean, it's certainly possible to just do that, but it's not the best way. Modifying save/load only means that we'd be recreating an SQLite database on every save/load, and that'd end up being no different than using XML, performance-wise. The best way to do it would be to always store all the in-game elements in an SQLite database. So a "save" would never really need to happen, because it would in effect _always_ be saved to disk.
Yeah, thats what I figured as much, that that wouldn't give much of a performance gain if you would recreate the dbase everytime. But wouldn't it be a gain in decreased memory usage? Right now the data is serialised before it's written into the XML file, but say you open up a dbase connection and just fill it up one (long but not too long) query at a time. This way you wouldn't hog up the memory right? Mmm, my noobish gut tells me it would maybe cost some more time, but at least you wouldn't have the overflooding memory problem?

But if you're gonna redesign something, you might wanna just do the way it's an overall best increase instead of pasting some more. :-)
Quote:
But maybe we should just start writing an SQLite backend. That'd actually make the Onlink codebase much more maintainable. If only I could get ahold of Miah, I could discuss this with him.
Sounds like a plan! ;-)


Top
Offline  
 Post subject:Re: Loading/saving duration
PostPosted:Fri Mar 19, 2010 5:41 pm 
Literally Nine
User avatar
 

Joined:Sat Apr 02, 2005 3:31 pm
Posts:1171
Location:The vicinity of an area adjacent to a location.
Quote:
Ahh, that makes a lot of sense now. Out of curiosity, how did Uplink avoid having so much RAM usage when it wrote the save files? I suppose since they only saved the game on close, there was no need to worry about pausing it, they just took the state of the game as it was closed and wrote while the menu ran, but I don't remember any sluggishness or severe hard drive thrashing indicative of page faults.
Uplink used a binary save format, and they saved it to disk by streaming it directly to disk instead of buffering and then saving. The XML save format is our biggest embarrassment, really. :(
Quote:
I'm not sure, but it seems after reading the article that a copy-on-write might not be the best idea, since it would require a large amount of work to adjust to, and it would end up taking up a lot of memory if old copies of things are floating around in the game world. However, if there was a way to "lock" the objects when saving begins, so that old copies persist, but changes create new versions that are unlocked (so as not to create extra copies), and then after saving is complete all locked objects are unlocked or destroyed depending on if they were changed, that might be a good method.
I think you don't understand the concept of "copy-on-write", because it really does pretty much as you describe. It maintains revisions for as long as they're needed (reference counting), and any changes to the data essentially make it a new data structure. It's an efficient process, and it's pretty much exactly what fork() does underneath, transparent to users.
Quote:
I may not be the best programmer out there, but I'm currently a junior studying game design and comp sci at RPI, and I would be more than happy to help you guys out if you want help. I'm in sore need of something challenging to keep my programming skills up. Of course, I don't want to impose or intrude, but if you are looking for help, keep me in mind. I've been watching the slow progress for 5 years and have loved everything so far.
Absolutely, we always love having contributors. For legal reasons, though, we need you to get an Uplink Developer CD from Introversion. It's preposterously overpriced, considering how crappy their code is, but hey. Once you buy it, you can work on Onlink too.

(Also, if you're looking for programming challenges, check out Project Euler. I used it to learn Python.)

And I've thought further about using SQLite for Onlink, and I think that although the code changes would be numerous, it'd be worth it to try it. So I'm going to scrub the Onlink code base and get it nice and shiny, and then branch and start trying SQLite out.

_________________
- Tycho

Image


Top
Offline  
 Post subject:Re: Loading/saving duration
PostPosted:Fri Mar 19, 2010 6:00 pm 
 

Joined:Tue Mar 16, 2010 9:47 am
Posts:27
Quote:
And I've thought further about using SQLite for Onlink, and I think that although the code changes would be numerous, it'd be worth it to try it. So I'm going to scrub the Onlink code base and get it nice and shiny, and then branch and start trying SQLite out.
Be sure to keep us informed about your findings & progress then! :)


Top
Offline  
 Post subject:Re: Loading/saving duration
PostPosted:Fri Mar 19, 2010 6:08 pm 
 

Joined:Mon Apr 23, 2007 1:16 pm
Posts:190
Quote:
On Linux and Mac, we use the fork() call to essentially create an identical copy of the Onlink process, allowing us to save the game state without ever pausing the game for more than a hundredth of a second
according to this, there is a fork-equivalent in windows warning: the tip on gamedev is written in 2005 and refers to a post from 1999, aka about 10 years ago!!
also i have heard about a posix-threads-for-windows-lib "pthreads", maybe it got what you need

@SQLite from XML
couldn't be that hard.. the current savegame creates an XML file in ram, writing ips, logs, agents, passwords, etc in stages.. you should be able to create a store-to-sqlite function with nearly the same inputs, .. without so much code change that its not a option.. i guess.


Top
Offline  
 Post subject:Re: Loading/saving duration
PostPosted:Fri Mar 19, 2010 6:18 pm 
Literally Nine
User avatar
 

Joined:Sat Apr 02, 2005 3:31 pm
Posts:1171
Location:The vicinity of an area adjacent to a location.
Yes, I saw that post about ZwCreateProcess before. I'm pretty certain it's a privileged function (only accessible to drivers), but I could be wrong. Maybe you just need LoadLibrary() and GetProcAddress() to use it.

But using undocumented Windows API feels _wrong_ anyway.

_________________
- Tycho

Image


Top
Offline  
 Post subject:Re: Loading/saving duration
PostPosted:Fri Mar 19, 2010 10:21 pm 
 

Joined:Thu Apr 28, 2005 3:57 pm
Posts:175
AOL:DKWiz214
Ugh that is preposterously overpriced. Let me get back to you once I find out about the status of my summer job. If I get it I can spare a bit of cash. At this point, do you think you will be spending enough time on Onlink (not Cerberus) that it would be worth it?

_________________
The light shall be your demise.


Top
Offline  
 Post subject:Re: Loading/saving duration
PostPosted:Sat Mar 20, 2010 3:38 am 
 

Joined:Fri Mar 19, 2010 4:06 am
Posts:3
you mean every 3 months pass ,pause the game ,save once? :sleazy:
will that work? anyone talk about that


Top
Offline  
 Post subject:Re: Loading/saving duration
PostPosted:Sat Mar 20, 2010 4:31 am 
Literally Nine
User avatar
 

Joined:Sat Apr 02, 2005 3:31 pm
Posts:1171
Location:The vicinity of an area adjacent to a location.
Quote:
you mean every 3 months pass ,pause the game ,save once? :sleazy:
will that work? anyone talk about that
That's not what I mean. I mean that after three in-game months pass, your saves wouldn't be inflating anymore, but up to that point, you'd see them grow.

That doesn't mean that if you save a zillion times before three months pass your saves will bloat crazily. No, it just means that your save games haven't hit the maximum size at that point.

_________________
- Tycho

Image


Top
Offline  
 Post subject:Re: Loading/saving duration
PostPosted:Sat Mar 20, 2010 4:33 am 
Literally Nine
User avatar
 

Joined:Sat Apr 02, 2005 3:31 pm
Posts:1171
Location:The vicinity of an area adjacent to a location.
Quote:
Ugh that is preposterously overpriced. Let me get back to you once I find out about the status of my summer job. If I get it I can spare a bit of cash. At this point, do you think you will be spending enough time on Onlink (not Cerberus) that it would be worth it?
And yes. The more I think about SQLite for savegames in Onlink, the better I think Onlink's code will be.

Of course, if I hit major roadblocks and end up not completing the SQLite save system, then it wouldn't be "worth it". But at this moment, I don't see any obvious roadblocks. It'd just take some time to finish.

_________________
- Tycho

Image


Top
Offline  
Display posts from previous: Sort by 
Post new topic Reply to topic

All times are UTC-05:00


Who is online

Users browsing this forum: No registered users and 31 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
Theme created by Miah with assistance from hyprnova