Generating Unique Numeric IDs using DateTime.Now.Ticks

Question

I need to generate a unique numeric ID to attach to an incoming request. This ID is used only temporarily to track the request and will be discarded once the request has completed processing. This ID will only be used in the context of this application but will need to be assigned in a high performance multi-threaded way.

I was thinking of using DateTime.Now.Ticks for this ID but would like to know if DateTime.Now.Ticks could still generate a colliding ID if simultaneous requests are being concurrently being processed?

If anyone could suggest a better way to generate these IDs (preferably one that is not Int64 like Tick is) in a multi-threaded environment, please let me know. Something as simple as an incrementing number would suffice even, if only I didn't have to lock the number before incrementing.

Thanks a lot for any help.

Solution 1

You just need to use a static variable that is incremented each time you want another unique value. You can make this thread safe and still very fast by using the Interlocked.Increment method...

// Declaration
private static int safeInstanceCount = 0;

// Usage
{
      ...
      Interlocked.Increment(ref safeInstanceCount);
      ...
}

Solution 2

DateTime.Now is absolutely terrible for this purpose. At best, you'll have a resolution of 1 millisecond; at worst, 17 ms on NT and 1 second (!) on CE/Compact Framework.

Consider using Interlocked.Increment method for a fast, thread-safe counter.

Solution 3

Start with a per-thread ID (if multiple threads are originating the requests), concatenated with a per-thread counter (if each thread is expected to originate more than one request).

Solution 4

Just get a strong random number or use a GUID

• http://www.codeproject.com/KB/security/CryptoPasswordGenerator.aspx

• http://msdn.microsoft.com/en-us/library/system.random.aspx

• http://msdn.microsoft.com/en-us/library/system.guid.newguid.aspx

If high performance is the MUST have feature, allocate sequential numbers in monotonous sequence. Prevent lock contention by 'reserving' a range of (say, 20-100) ID's per thread that handles messages. That way, you'll need to lock the sequence generator only once in 20-100 iterations.

View more solutions

Comments

[Nick Johnson]

What's wrong with using a GUID/UUID?

[Nick Johnson]

"Too much overhead"? A GUID only requires generating a few bytes of random data. It's not expensive. It sounds like you're engaging in premature optimisation.

[shyneman]

maybe it is insignificant in actual time but from some basic testing, it looks to be about 10x slower than interlocked.increment with 8 concurrent threads.

[shyneman]

i was already considering interlock.increment but i was hoping to avoid any type of lock. however, the performance impact is probably negligible as you mentioned so i will probably just go with that rather than spending too much thing over-optimizing. thanks.

[Phil Wright]

The performance impact is not worth thinking about unless you are planning on calling it millions of times per minute. Plus it is dead easy to use.

[sehe]

@PhilWright: On my linux box time csharp <<< "int x; while (System.Threading.Interlocked.Increment(ref x)<1000000000);" shows it does roughly 121,521,448 increments per second (2.6x slower than just x++. So (as ever) it would actually depend on what else needed to fit in that second whether you'd need to optimize anything.

[sehe]

However, performance degrades when threading: ThreadStart a = () => { int x=0; while(Interlocked.Increment(ref x) < 1000000000); }; in parallel x 4 takes 9s; sharing the int x (by taking it out of the lambda) it takes 32s (only ~31 miljon incr/s) -- whilst the number of overall calls to Interlocked.Increment is effectively 4x as small :)

[Phil Wright]

Interesting feedback. I suspect that the time taken to interlock.increment is small compared to the time of the actual operation being performed with it has been provided.

[Kirk Woll]

Using random seems like you might "randomly" have a collision.

[shyneman]

performance is a must, that's why i'm shying away from guids or having to compute the ID. the reservation of a range of IDs for each thread is a neat idea. i'll mull over that one a bit. thanks.

[sehe]

@KirkWoll: not if random is random enough. It is widely accepted that a GUID can be assumed not to clash for that reason.

[PeterX]

This article says: " There are 10,000 ticks in a millisecond."

[Jeffrey Hantin]

@PeterX The definition of 1 tick = 100ns in no way implies that the implementation of DateTime.Now is capable of such precision; I've encountered all the implementation limitations I mentioned in my post. If you really need microsecond-class precision, Stopwatch does it better.

[PeterX]

No worries - yeah, I've moved to Guid just to ensure my temp folders - which are cleaned-up anyway - are unique.

[MosheG]

I think you should change the example as the question asked for a way to generate ids and however implements it may make a mistake by writing his code this way: Interlocked.Increment(ref safeInstanceCount); Id = safeInstanceCount; writing: Id = Interlocked.Increment(ref safeInstanceCount); will explain the solution better. #IMHO

[Theodor Zoulias]

Using the Interlocked class inside a lock-protected region defeats the purpose of using the Interlocked in the first place (avoiding the lock-induced contention).