I've thought about replacing UUID:s with a long/int in artemis-odb, but the problem arises when you need to deal with saving/loading state. I guess one could keep track of used unique ids by saving them in a bitset - should yield better performance, haven't played around with it though.

You ought to grab the unit tests from artemis-odb btw; they might help in uncovering more bugs - most were written after running into one.

To be honest, I haven't figured out serialization yet either.

I do know that 128 bit UUIDs aren't that popular to "uniquify" game world entities. For example, all Elder Scrolls games (at least for Morrowind, Oblivion and Skyrim) use integer IDs for their world entities (anything from the static rock in the wilderness to the rusty sword you just dropped), so I don't think 128 bit UUIDs are the solution.

I'm not exactly sure of what problem you're talking about, but I suppose that is the problem of what IDs to assign to new entities after you have loaded the game state. You must serialize the Entities with the ID they had, but when you load them, you cant start the ID counter from zero.

You could just start counting from whatever value the counter was left in the saved state (say, max Entity ID in the saved state is X number, so set the counter to start counting from X+1). Entity IDs will keep increasing forever, someday after two billion entities are created, wrap around and after another two billion entities are created, they'd start to overlap the oldest Entities "alive" (0 and above).

If that isn't enough (seriously, 4 billion IDs, it will be enough for 98% of the use cases out there), you could pseudo solve it with an "IDAllocator".

Have an object that stores the range of IDs that are free (clean state -> from Integer.MIN_VALUE to Integer.MAX_VALUE), then, for each new ID request, modify the free range or, if necessary, split it.

Say that we request our first ID, free range would be [Integer.MIN_VALUE,-1], [1,Integer.MAX_VALUE]. And so on. You don't keep track of what IDs are used, just keep track of the range of IDs that are free.

Say that we load a game state that has IDs from 20 to 80 used, and from 100 to 200 used. Your free ranges would be [Integer.MIN_VALUE, 19], [81,99] and [201,Integer.MAX_VALUE].

You'd keep a "free list" of IDs like if it were a memory allocator, with the ranges of free IDs available (stored in [start,end] int pairs). That way you'll never "lose" an ID, if in the current state it isn't being used, it will be in the "free" range of IDs (ie, a list of ID ranges that aren't used).

There is a risk of "ID fragmentation", ie, having tons of little free ranges in the free range list, which would be bad for memory usage. Just be sure to occupy the smallest free ranges first (ie, order the free range list by size) and you'll be fine, that way you can keep track of all the IDs that aren't used with just a couple of int[2] in a list.

Hell, the IdPool could be implemented like that without using the IntStack now that I think of it...

BTW, I have no idea how to use those unit tests :D

I'm not sure ID fragmentation is actually an issue is it? That would only be an issue if your architecture required continuous lists of IDs to represent, say, groups of objects which would be a weird way to design. If the only requirement is for a single ID at a time, fragmentation is not an issue at all in the way it is with memory.

Yeah, as I said, it can be easily fixed by sorting by size of free range and use whatever range is smallest each time you "reserve" an ID.

The issue was with the structure to record which ranges are free. I put as an example a List of int[2], in index 0 you'd have the range start, in index 1 the range end. You'd have in the List as many int[2] as free ranges you have.

Say that you don't sort the free range list, and split the free ranges a couple of thousand times, you might end up with tons of tiny int[2] allocations in a list and possibly lots of range merges when returning IDs to the pool, which is slow (ordered list remove(), shifts all elements in the list). Add to that JVM's overhead (12 bytes or so for arrays IIRC), and it might add up.