How are you handling Serialization with Unity3D?

[RogueDeus]

Fair enough.

I am getting the impression that I am beginning to annoy you.

I understand that you are busy and I really do appreciate the attention you are giving me. I hope I an not squandering it with pointless questions, only to lose it when I have good ones.

[x4000]

You're not particularly annoying me.  But, the questions lately have boiled down to two categories: 1) things that really are a matter of opinion and that everybody does differently and that I don't have any reason to try to convince you to do my way -- it would be a disservice to you and a waste of my time; and 2) things that are fairly basic programming questions that most professional programmers should be able to answer.

I'm happy to answer questions when I can, but I don't have any desire to convert you or anyone else to my exact methodology of doing things, or to teach C# 201, or to get into lengthy debates of any kind.  I spend most of my time trying to avoid getting into such discussions at this point, as they rarely serve any purpose as nobody comes away convinced of anything most of the time.

[RogueDeus]

You're not particularly annoying me.  But, the questions lately have boiled down to two categories: 1) things that really are a matter of opinion and that everybody does differently and that I don't have any reason to try to convince you to do my way -- it would be a disservice to you and a waste of my time; and 2) things that are fairly basic programming questions that most professional programmers should be able to answer.

I'm happy to answer questions when I can, but I don't have any desire to convert you or anyone else to my exact methodology of doing things, or to teach C# 201, or to get into lengthy debates of any kind.  I spend most of my time trying to avoid getting into such discussions at this point, as they rarely serve any purpose as nobody comes away convinced of anything most of the time.

Point(s) taken.

It did not occur to me that someone who has been programming for a living wouldn't exactly be as excited as I am about the possibilities of code use... 

Makes me want to laugh at myself for my naivete.

I shall endeavor to be less obtuse with my future inquiries! 

[x4000]

No worries, I'm glad you're excited about the code -- that's the right way to be.

[RogueDeus]

I hope this is not an unusual question...

I have decided I will use C# standard DataContractSerializer for my needs until my needs change. Now I am thinking how I will pick and save the data.

I am thinking an easy way to contextualize serialized files is by game level (map, region, what have you). Thus when entering a map, the collection of serialized objects for that map gets checked and instantiated as necessary. But this also means that each object will either need to be individually serialized, or added to a collection for group serialization.

How do you handle this?

[x4000]

I've never used DataContractSerializer, so I can't really comment on any of that.  However, I will say that Microsoft has a tendency of breaking its own serialization.  It's very brittle, because sometimes when they update to a new version of .NET, it loses the ability to read back some older serialized data.  This is fine if it's used for passing messages, but not for persisting data if you ever plan to upgrade .NET.

[keith.lamothe]

My general advice with regard to the class library or any 3rd party code: use it to save time doing things yourself, but be prepared to have to go back and re-implement at least part of the functionality yourself.  It doesn't happen in every case but between:

1) Libraries that don't do what they say they do (actually pretty rare in my experience with .NET).
2) Hidden gotchas like:
- transient heap allocation that leads to lots of garbage collection (foreach creating enumerators, string + operator).
- not deterministic across different machines and runtimes (float, double).
3) Simply needing to make it more efficient.

I've wound up re-implementing or at least wrapping a lot of the library stuff I once used.

[Nalgas]

Also, indexing by strings is incredibly slower than by enums.  String comparisons are wicked slower than enum comparisons, and the comparison time varies by the length of the string.

That is generally a good rule of thumb, but strings do come in handy for that sometimes, and there are some pretty nifty ways of dealing with them, like tries.  You can actually have your dictionary use strings for keys and be faster than a hash table in some situations, when used appropriately.

[x4000]

Pretty cool on the tries!

[keith.lamothe]

Yea, I love the idea of bitwise tries particularly, but all the cases I've thought to use them on (like the lookup for ForegroundObject's in AIW, since they're always uniquely identifiable by a 32-bit int primary key) don't seem like good use cases because as the number space approaches full the memory size of the trie structure would approach 2^32*sizeof(node) bytes.  That's more than a theoretical concern because the IDs cannot be reused; obviously the game would go bonkers once it ran out of IDs anyway but the memory consumption of the trie would become highly non-trivial fairly early on.  Of course, a smart trie implementation could "hollow out" the actual in-memory bits that corresponded to leaves and sub-trees of dead-and-gone units.  But it would depend on the distribution of deaths for actually being able to dump large swaths, etc.  As long as every 64th unit (in creation order) was still alive, for example, you'd still be approaching 2^26 nodes.

Or am I missing something about those wonderful little binary-math-exploiting structures?

[Hearteater]

Well, a bitwise Trie's memory footprint for 32-bit IDs would not be anywhere near 2^32 until your active IDs got that high at which point I'm sure other memory issues would be the problem.  Tries aren't complete binary trees stored in a solid block of memory so they only use up memory for actual IDs not potential IDs.  If I recall correctly it would have n-1 interior nodes and n leafs where n is the number of IDs currently in use.

For example, assume you had 0x8000 and 0x0001 as the only IDs.  You would have a root node with two children.  Those children would point directly to the two objects: Left -> ID 0x0001 and Right -> ID 0x8000.  If you added ID 0x8001 the right child would point to a new node with two children: Left -> 0x8000 and Right -> 0x8001.  Every 64th unit being alive or the first 2^26 units being alive would occupy exactly the same amout of space for the Trie.

Not to imply you didn't know any of that.  I just happen to like data structures.  In my free time I read about them.  Yeah, it's a little weird.  I especially love priority queues.

Anyway, I think I have a bitwise Trie implementation around in C or C++ if you want me to dig it up.

[keith.lamothe]

Well, a bitwise Trie's memory footprint for 32-bit IDs would not be anywhere near 2^32 until your active IDs got that high at which point I'm sure other memory issues would be the problem.

Right, my concern is that the memory complexity of the trie would be such that n is the number of ForegroundObject's that have ever existed in that savegame, rather than proportional to the number of ForegroundObject's that currently exist.  Not that the no-longer-existing ones would require storage, but that a single existing unit could require 32 nodes all by itself if the trie is totally uncompressed (and I'm really not clear on the insert time for compressed tries, we have frequent inserts); some those nodes would be "reused" by anything within the appropriate "subtries" but those early ones are going to get sparser and sparser as the game goes on and old units die off but the game would be unable to reclaim some (most?) of the memory due to the remaining "skeleton" being necessary to keep linking those ships from those ID intervals that were still alive.

So in a practical case we might only be talking 20MB extra late in a large game, but that could be enough to push it over the limit and we're back to OutOfMemory errors.  Those errors really annoy us

[Hearteater]

Yeah, it actually isn't that bad.  When inserting, you don't create extra nodes unless you hit an existing leaf and need to split it.  So at most each insert adds one node.  You actually wouldn't want a compressed Trie since you will be modifying the Trie.  But you can prune off the skeleton nodes in the delete method.  It actually isn't all that unreasonable to do so.  A recursive delete can remove nodes as it backs out when you've deleted the only leaf on a node.  Optionally adding a parent pointer to each node makes an iterative delete extremely fast at the cost of more total memory usage for the whole Trie.  I tend to favor the recursive solution, but in a Trie that can cause an issue when you use a lookup table to jump into the middle of the tree.  The best way around that is to not allow the nodes referenced in the lookup table to be deleted.  In effect that splits the Trie up into 32 smaller Tries.

[keith.lamothe]

But you can prune off the skeleton nodes in the delete method.

Unless, of course, you still need them because there's still a single unit left alive in that interval

[Hearteater]

It actually works pretty well.  Every internal node has either a) at least one leaf node, b) two internal nodes.  Deletes leave no real skeleton regardless of sparsity.  I'll dig up the code for it.  I think it may take up less memory than you are expecting.  Whether it meets any of your other needs is another question .

NOTE: In a way this is actually a compressed Trie implementation, but without the compact data representation that tends to make them read-only.  Because of that it adds very little to the delete operation and inserts are actually slightly faster since you don't create extra internal nodes.