Unique ID generation without using GUID

Question

I was trying to think of a way to get unique IDs without using GUID and thought of this. Just wondering what you all think, if it's safe or not, etc.

 // IDGEN: an auto incrementing ID for our nodes public int IDGen; public List<int> IDs; // NEWID: will generate a unique ID for a node. Whenever a node is destroyed // its ID will be put back in the IDs list and reused to ensure we never go over limit public int NewID() { if (IDs.Count > 0) { int i = IDs[0]; IDs.RemoveAt(0); return i; } else { return _.game.IDGen += 1; } }

Why bother with the list - are you expecting more than 2 billion uses in a session? GUIDs are mostly used when the values need to survive the session or will be shared among processes - your proposed solution suggests that's not the case here. — 500 - Internal Server Error
– 500 - Internal Server Error, Commented Sep 29, 2024 at 19:06
Linked lists are expensive. They can be good on a benchmark but in real-wold application, node are likely spread in memory and the addresses are located everywhere in memory so they are unpredictable for the CPU. This is a problem since it is likely to cause cache misses. The resulting latency is likely the one of a DRAM access (dozens of ns and hundreds of cycles). I am pretty confident there is a faster way to generate GUID than that. A growing-array (with a power-of-two growth policy) should be better, or even a List of buckets. — Jérôme Richard
– Jérôme Richard, Commented Sep 29, 2024 at 19:32
A better data structure could be to pack bits in 64-bit integers in a hierarchical data structure. When an integer has all its bit set then you compress its representation by setting a bit in another 64-bit integer (enabling 4096 items to be packed in a 64 bit integer). In the worst case bits are randomly set and you need 1 bit per GUID as opposed to something like 100x more currently. This strongly reduce the memory required in pathological cases while avoiding cache misses. Bit-packing can be done in less than 10 ns on most platforms (possibly significantly less, like on x86 CPUs). — Jérôme Richard
– Jérôme Richard, Commented Sep 29, 2024 at 19:41
TL;DR: on modern CPUs, computation is cheap while (unpredictable) memory accesses are expensive. — Jérôme Richard
– Jérôme Richard, Commented Sep 29, 2024 at 19:43
@500-InternalServerError - ya I am saving the IDs. There will be between 5 - 10 million different IDs required but overtime I want a way to reuse them. So if a node gets deleted then I add its ID to the list and it will be reused instead of incrementing the IDGen. — user2980746
– user2980746, Commented Sep 29, 2024 at 21:35

Collectives™ on Stack Overflow

Unique ID generation without using GUID

0

Linked

Hot Network Questions

Collectives™ on Stack Overflow

0

Know someone who can answer? Share a link to this question via email, Twitter, or Facebook.

Linked