这个时间戳方法怎么会返回重复的值呢?

Question

我有一个方法，它应该在Base36中生成一个唯一的10个字符的时间戳，具有微秒分辨率。但是，它没有通过唯一性测试。这怎么可能呢?

    private static string _lastValue = string.Empty;
    private static readonly DateTime _epoch = DateTime.SpecifyKind(new DateTime(1970,1,1), DateTimeKind.Utc);
    private static readonly DateTime _lastInitialized = DateTime.Now; 
    private static readonly Stopwatch _sw = Stopwatch.StartNew();
    public static TimeSpan EpochToStopwatchStart()
    {
        return _lastInitialized.Subtract(_epoch);
    }
    public static string GetBase36Timestamp()
    {
        string result;
        do
        {
            // _sw is a running Stopwatch; Microseconds = ticks / 10
            long microseconds = EpochToStopwatchStart().Add(_sw.Elapsed).Ticks / 10L;
            result = MicrosecondsToBase36(microseconds);
        }
        // MicrosecondsToBase36 encodes the Int64 value; the while() loop compares to a
        // tracking field to ensure the encoded value changes from the previous one:
        while (result == _lastValue);
        _lastValue = result;
        return result;
    }

我知道我丢弃了一些分辨率，但这在Base36中需要10个字符，并且该方法无论如何都会检查编码值。在一次运行中会发生意想不到的欺骗。为了简化问题，我使用单线程运行测试。我想要么答案会很有趣，要么我会因为问题中的一些愚蠢的疏忽而感到非常尴尬。

Answer 1

如果在do/while循环中添加Thread.Sleep(1);会发生什么?每次迭代生成的时间很可能超过一微秒。

Answer 2

分析

创建一个多线程性能测试显示，尽管存在while循环，该函数仍然能够以大于每微秒一次的速率退出:

    static void Main(string[] args)
    {
        List<string> timeStamps = null; ;
        int calls = 1000000;
        int maxThreads = 5;
        for (int threadCount = 1; threadCount <= maxThreads; threadCount++)
        {
            timeStamps = new List<string>(calls * maxThreads);
            var userThread = new ThreadStart(() =>
                {
                    for (int n = 0; n < calls; n++)
                    {
                        timeStamps.Add(TimeStampClass.GetBase36Timestamp());
                    }
                });
            Thread[] threads = new Thread[threadCount];
            var stopwatch = Stopwatch.StartNew();
            for (int j = 0; j < threadCount; j++)
            {
                threads[j] = new Thread(userThread);
                threads[j].Start();
            }
            for (int j = 0; j < threadCount; j++)
            {
                threads[j].Join();
            }
            stopwatch.Stop();
            Console.WriteLine("threadCount = {0}n ------------------", threadCount);
            Console.WriteLine("{0} calls in {1} milliseconds", timeStamps.Count, stopwatch.ElapsedMilliseconds);
            Console.WriteLine("{0} ticks per call", (double)stopwatch.Elapsed.Ticks / (double)timeStamps.Count);
            Console.WriteLine();
        }

结果输出为:

threadCount = 1
 ------------------
1000000 calls in 1080 milliseconds
10.802299 ticks per call
threadCount = 2
 ------------------
1985807 calls in 1379 milliseconds
6.94705779564681 ticks per call
threadCount = 3
 ------------------
2893411 calls in 1731 milliseconds
5.98568471606695 ticks per call
threadCount = 4
 ------------------
3715722 calls in 2096 milliseconds
5.64319478152564 ticks per call
threadCount = 5
 ------------------
4611970 calls in 2395 milliseconds
5.19515413153164 ticks per call

多线程环境解决方案:

将while环锁定在_lastValue上:

        public static string GetBase36Timestamp()
        {
            string result;
            lock (_lastValue)
            {
                do
                {
                    // _sw is a running Stopwatch; Microseconds = ticks / 10
                    long microseconds = EpochToStopwatchStart().Add(_sw.Elapsed).Ticks / 10L;
                    result = MicrosecondsToBase36(microseconds);
                } while (result == _lastValue);
            }
            return result;
        }

Answer 3

我认为你需要使用System.Threading.Interlocked.CompareExchange()来做一个线程安全的比较和交换作为一个原子操作。详情请参见联锁操作。简而言之，你…

• 获取要更改的状态的副本作为本地变量。
• 执行计算以获得新状态
• 执行Interlocked.CompareExchange()，返回当前旧值
• 如果old-value的本地副本与返回值不同，则交换失败:重复上述操作。

这里有一个简化的例子，快速地回顾你的工作:

class TimeStamp
{
  static readonly DateTime  unixEpoch        = new DateTime(1970,1,1,0,0,0,DateTimeKind.Utc) ;
  static readonly long      BaseMicroseconds = (DateTime.UtcNow-unixEpoch).Ticks / 10L ;
  static readonly Stopwatch Stopwatch        = Stopwatch.StartNew() ;
  static          long      State            = TimeSpan.MinValue.Ticks ;
  private long OffsetInMicroseconds ;
  private TimeStamp()
  {
    long oldState ;
    long newState ;
    do
    {
      oldState = State ;
      newState = Stopwatch.Elapsed.Ticks / 10L ;
    } while (    oldState == newState
              || oldState != Interlocked.CompareExchange( ref State , newState , oldState )
            ) ;
    this.OffsetInMicroseconds = newState ;
    return ;
  }
  public static TimeStamp GetNext()
  {
    return new TimeStamp() ;
  }
  public override string ToString()
  {
    long   v = BaseMicroseconds + this.OffsetInMicroseconds ;
    string s = v.ToString() ; // conversion to Base 36 not implemented ;
    return s ;
  }
}