Numerical ID manager

how many objects are you going to be using? 1k, 1M, 1B? if its under 1M then just use a stl map 1M*4 is only 4MB of memory, which at first seems wasteful, but your time would be much better spent on other areas. i would just use an ever incrementing dword, if that isn't good enough use an __int64, both are much faster, cleaner, and easier than any kind of a list.

Work out how quickly the objects in question are created, and then how long your game would have to run before you ran out of IDs. If it's believable that your game would be left running for that long, use a 'long long' instead.

Remember, K.I.S.S. (Keep It Simple, Stupid)

Ya the only reason I haven't been inclined to use a map is b/c there are several of these ID managers, each one with a 4MB foot print doesn't sound nice to me.

I have done some preliminary analysis and truthfully I won't run out of IDs. But... just seems like something that should be accounted for. Rather then leaving, basically, a known bug.

OpenGL for instance, when you free a texture the ID goes back into the pool. Wounder what they use...

What's wrong with something like this?

class IdPool{public:    IdPool() : next(0)    {// empty    }    uint32_t getId()    {        uint32_t id(0);        // re-use a recently released id if one is available        if(!spares.empty())        {    id = spares.back();             spares.pop_back();        }        // else generate and return a new id        else        {    id = ++next;        }        return id;    }    void releaseId(uint32_t id)    {   spares.push_back(id); // retain this id for later re-use    }private:    uint32_t next;    std::vector<uint32_t> spares; // list of spare ids};

[Edit] IdPool::spares is going to get big as you release ids, particularly if you've used a lot of them. Having an object that grows in size as your app shuts down probably isn't something you want.

A possible solution to this might be to change spares to a sorted container, and have releaseId check to see if the highest spare id is next-1; if so, then pop the spare and decrement next, and repeat the test (this effectively absorbs spare ids back into next). Note that this only avoids the growth of spares when id usage is roughly stack based (i.e. FILO) - queue based id usage (i.e. FIFO) will not benefit from this 'improvement' unless you do a check on the lowest spare too...

However, this solution is quickly getting complicated... you might be better off using a KISS solution as joanusdmentia suggested. [smile]

[Edited by - ajones on April 4, 2007 2:42:49 AM]

If you're really concerned about running out of IDs I would actually calculate how long an average case of execution would take before you would overflow. It it is longer than your lifetime then don't waste effort.

If 4294967295 unique IDs aren't enough for you, then I would work out the max number of IDs you need at any one time and just use bits as IDs as you were thinking (I work on platforms where 6KB is often a big deal let alone 4 Megs so my solutions usually are less memory intensive regardless of whether or not they're super optimal). You could always just track the smallest free ID and if a smaller ID becomes available just set it to that. You will of course need to calculate the next free ID when the current one is used up which is slightly annoying.

If you don't have a crazy number of max IDs at any one time you could always just use a stack such that when you need an ID you pop the stack and when you're done with an ID you push it back on. If you end up running out of IDs (whether it's due to not initially having enough or change in design) then it will be easy to track down and correct. There's a million stack implementations out there if you didn't want to write your own. Not sure how the STL one is implemented since I don't use it at work but I'm sure it's fine (and won't need to allocate/deallocate on the fly if you don't exceed its capacity).


Another options is to just have two linked lists where one list represents free IDs and one represents used IDs although that seems overkill to me.

In other words, if it was me, I'd take the lazy approach and do nothing about this. I know lots of retail games that have knowingly shipped with identical things. Although to be fair most games ship with crash bugs that will trigger before the IDs could ever even near beginning to run out so....yeah....

Or you could use the address of the address of the item instance as its ID. That way you get as many as you can allocate and they are automatically reused when freed by the memory manager functions.

Simple solution: use a std::set to track the IDs that have been allocated. When allocating a new ID, first do a monotonic increase (i.e. just return ++id) until you hit a certain threshold, say std::numeric_limits::max() - 1000). Once you pass that threshold, instead of just returning an ID, do a binary search on the ID-space until you find one that isn't already in use (i.e. is not in the std::set of allocated IDs).

If there is no ID found free, go ahead and return to the simple monotonic behaviour. When you hit a second threshold (perhaps std::numeric_limits::max() - 10)), throw an exception to indicate you have no more IDs to allocate.

This is my stock solution for ID pools; it's not the most lightweight thing in the world, but if you're allocating four billion resource instances that are all alive at the same time, you don't need to give a shit about how much the ID tracker uses [wink] In general, follow the most important rule of optimization: write the clean, easy solution first. Profile. If and only if you have a severe problem (say, too much memory use), then opt for a more complex or hand-tuned solution.

Quote:

Original post by FluffysWhole Or you could use the address of the address of the item instance as its ID. That way you get as many as you can allocate and they are automatically reused when freed by the memory manager functions.

Be careful with pointer/integer casts - there's a lot of portability gotchas there. It's best to avoid this when possible IMHO because accidentally truncating an address on a 64-bit platform is a very bad thing. There's also the fact that it may give bogus behaviour on certain platforms (segmented memory models come to mind).

Quote:

Original post by ApochPiQ Be careful with pointer/integer casts - there's a lot of portability gotchas there. It's best to avoid this when possible IMHO because accidentally truncating an address on a 64-bit platform is a very bad thing. There's also the fact that it may give bogus behaviour on certain platforms (segmented memory models come to mind).

No need to do any casting at all. Pointer values provide all the operations you could conceivably need to use them as internal IDs.

Quote:

Original post by Sneftel Quote: Original post by ApochPiQ Be careful with pointer/integer casts - there's a lot of portability gotchas there. It's best to avoid this when possible IMHO because accidentally truncating an address on a 64-bit platform is a very bad thing. There's also the fact that it may give bogus behaviour on certain platforms (segmented memory models come to mind). No need to do any casting at all. Pointer values provide all the operations you could conceivably need to use them as internal IDs.

You can't persist them.

Sure you can. Just deswizzle them right at the point of serialization, and swizzle them when you read them back in.

Awesome, thanks for all the feed back. I'm probably gonna stick w\ my solution for the moment but may look into doing an ID pool a bit later when other more pressing tasks are completed.

Why not just keep a list of all the Ids freed and the maximum Id used?

If the free list is empty, use the maximum Id+1, if not, use the top of the list.
The solution has the benefit that it only uses memory as elements are freed whereas the std::map solution uses a constant 4mb to handle a situation that will never occur.


Personally, I'm happy with a 32-bit unsigned int and throwing an exception if I get to the maximum.

In fact, I find reusing Ids a bit nasty - what happens if (say in an rts) a unit diedhalf an hour ago, but a script kept around a reference to it? Do you want to be able to tell the script that the unit in question no longer exists? Or would you prefer to hand it a reference to a totally different unit?

Quote:

Original post by Nitage In fact, I find reusing Ids a bit nasty - what happens if (say in an rts) a unit diedhalf an hour ago, but a script kept around a reference to it? Do you want to be able to tell the script that the unit in question no longer exists? Or would you prefer to hand it a reference to a totally different unit?

If this scenario ever occurs, you have serious design issues anyways, and likely some major bugs lurking under the surface. When the unit dies and becomes non-existent, every reference to it should be released.

Your systems should be built in a way that makes it trivial to track all known references to a given resource or entity; as a logical consequence, it should be trivial to remove those references if an entity stops existing. If this is not a very simple process, chances are the design has some major weaknesses - most likely excessive coupling, probably some temporal coupling, and certainly a lot of unwritten and unverifiable assumptions.

I did this sort of thing for a project once - in some cases our ids were only 16-bit and did recycle so the "just add one and forget about it" strategy didn't work. My approach was to keep a collection of (start,end) pairs of allocated ids. e.g. if you allocated ids 1-10 then freed #5 you'd have (1-4),(6,10) in the collection. This was based on the expectation that ids wouldn't hang around for to long and that they would be freed in roughly the same order they were allocated in (i.e. there wouldn't be a ton of ranges).

With any sort of complex id tracking algorithm one of the big problems that you may need to worry about is whether or not freeing an id can fail (because of out of memory say).

I agree that you should not reuse IDs if possible. There is a reason Relational DB's generally don't reuse key fields or even remove them when a row containing it is "nulled". They generally just set the ID negative because you will inevitably need to go back and get that data at some point, no matter how many people tell you that you won't. I also don't agree that you should not worry about this possibility because the rest of your game should be error free enough to make up for it.

Quote:

Original post by rockdeity I agree that you should not reuse IDs if possible. There is a reason Relational DB's generally don't reuse key fields or even remove them when a row containing it is "nulled". They generally just set the ID negative because you will inevitably need to go back and get that data at some point, no matter how many people tell you that you won't. I also don't agree that you should not worry about this possibility because the rest of your game should be error free enough to make up for it.

Uh... a relational database addresses a completely different problem than a dynamic ID pool. The dangers and risks of one domain are not necessarily transferrable to all other domains.

By your logic, I should have anti-lock brakes and airbags on my office chair, because both my chair and my car have wheels.


(My point here, of course, is that cars don't have ABS and airbags because of their wheels; those safety features are because of the mass and speed involved in driving a car in typical usage. RDBMs usage of IDs is related to maintaining referential integrity, good data recovery principles, and occasionally legal requirements [c.f. Sarbanes-Oxley]. The fact that ID reuse is avoided in large-scale databases is not because of the fact that there are IDs involved. Correlation is not causation, etc. etc.)

Man idk, lets say for the sake of argument I do want an ID pool of some sort.

My algorithm works a bit like an insertion sort. You would maintain a bit mask for testing the bit vector. And you would also maintain the lowest free ID, so if the ID ur freeing was higher then the current lowest free ID you wouldn't change anything except twiddle the bit in the bit vector for the one you are freeing which would be a constant time function.

So when requesting a new ID u already know the lowest free ID which is what will be assigned. Then the only n dependent factor is, once u assign that lowest free id, traversing the bit vector to find the next lowest free ID, I may just do some algorithm analysis on this to see what big O is roughly but it sounds pretty good and a lot more light weight that many of the other solutions.

Think about it, for 1 million IDs you only need ~1Mb of space!

Now please show me the obvious holes in my theory I couldn't see.

Here's the hole. Suppose that instead of doing all that ginormous bitfield crap, you simply use sequentially assigned 64-bit integers, never reusing them. Assuming you continuously created ten billion new IDs every second, you'd run out of IDs in about 58 years. That's eight bytes per ID, and eight bytes of overhead, you don't need to worry about scalability because I just showed you the math, and you don't have to worry about bit twiddling, and allocating n IDs doesn't take O(n²) time like in your approach. Beat that.

I know its not something I have to worry about. I plan on leaving it how it is for the moment infact.

But i started my last reply by saying "lets say for the sake of argument" b/c i thought it was atleast an interesting thing to think about a best way to do.