博客

U3D客户端框架之小堆顶高性能定时器测试10W计时器耗时1.9ms

  • Post author:
  • Post category:其他


1 小顶堆计时器概要

小根堆定时器的优点如下：

a.添加时间复杂度为O(1);

b.删除时间复杂度为O(1);

c.执行一个定时器的时间复杂度为O(1);

2 代码设计

之前写的服务器定时器是全部轮询更新，这种计时器性能太差，每一帧都要全部迭代一次，客户端层应该把CPU性能压榨到极致，能少循环的尽量少循环尽可能的减少CPU循环次数，所以优化了算法，使用了小堆顶定时器。小顶堆是基于二叉树的排序算法，将剩余时间最小的节点交换到树的根节点。每次更新的时候只取树的根节点，判断是否超时，如果超时会对树重新进行排序，排序完成后继续轮询，查询到根节点无超时为止。

Timer.cs代码实现 

using UnityEngine;
using System;
using Object = UnityEngine.Object;

namespace UnityTimer
{
    public class Timer
    {
        public enum SCOPE
        {
            eLocal,
            eGlobal,
        }

        #region Public Properties/Fields

        /// <summary>
        /// 计时器回调时间持续时间
        /// </summary>
        public float duration { get; private set; }

        /// <summary>
        /// 执行完成后是否循环执行.
        /// </summary>
        public bool isLooped { get; set; }

        /// <summary>
        /// 本帧是否完成
        /// </summary>
        public bool isCompletedThisFrame { get; private set; }
        
        /// <summary>
        /// 是否完成
        /// </summary>
        public bool isCompleted { get; private set; }

        /// <summary>
        /// 计时器使用的是实时时间还是游戏时间
        /// </summary>
        public bool usesRealTime { get; private set; }

        /// <summary>
        /// 计时器是否暂停
        /// </summary>
        public bool isPaused
        {
            get { return this._timeElapsedBeforePause.HasValue; }
        }

        /// <summary>
        /// 是否取消了
        /// </summary>
        public bool isCancelled
        {
            get { return this._timeElapsedBeforeCancel.HasValue; }
        }

        /// <summary>
        /// 是否完成
        /// </summary>
        public bool isDone
        {
            get { return this.isCompleted || this.isCancelled || this.isOwnerDestroyed; }
        }

        #endregion

        #region Public Static Methods

        /// <summary>
        /// 注册一个新的计时器，在一定时间后触发一个事件
        /// 在切换场景的时候，注册的计时器会被销毁
        /// </summary>
        /// <param name="duration">在一定秒后执行事件</param>
        /// <param name="onComplete">计时器执行完回调事件.</param>
        /// <param name="onUpdate">每次执行计时器执行的回调</param>
        /// <param name="isLooped">计时器在执行后是否重复执行</param>
        /// <param name="useRealTime">是否使用实时时间</param>
        /// <param name="autoDestroyOwner">此计时器附加到的对象，物体被摧毁后,定时器将不执行</param>
        /// <returns>一个计时器对象</returns>
        public static Timer Regist(float duration, Action onComplete, Action<float> onUpdate = null,
            bool isLooped = false, bool useRealTime = false, MonoBehaviour autoDestroyOwner = null)
        {
            if (Timer._manager == null)
            {
                TimerManager managerInScene = Object.FindObjectOfType<TimerManager>();
                if (managerInScene != null)
                {
                    Timer._manager = managerInScene;
                }
                else
                {
                    GameObject managerObject = new GameObject { name = "TimerManager" };
                    Timer._manager = managerObject.AddComponent<TimerManager>();
                }
            }

            Timer timer = new Timer(duration, onComplete, onUpdate, isLooped, useRealTime, autoDestroyOwner);
            Timer._manager.RegisterTimer(timer);
            return timer;
        }

        /// <summary>
        /// 作用同上，不同的是此API创建的计时器在程序的生命周期内都有效，不会随着场景的销毁而销毁
        /// </summary>
        public static Timer RegistGlobal(float duration, Action onComplete, Action<float> onUpdate = null,
            bool isLooped = false, bool useRealTime = false, MonoBehaviour autoDestroyOwner = null)
        {
            if (Timer._globalManager == null)
            {
                GlobalTimerManager globalManager = Object.FindObjectOfType<GlobalTimerManager>();
                if (globalManager != null)
                {
                    Timer._globalManager = globalManager;
                }
                else
                {
                    GameObject globalManagerObject = new GameObject { name = "GlobalTimerManager" };
                    Timer._globalManager = globalManagerObject.AddComponent<GlobalTimerManager>();
                    GameObject.DontDestroyOnLoad(Timer._globalManager);
                }
            }

            Timer timer = new Timer(duration, onComplete, onUpdate, isLooped, useRealTime, autoDestroyOwner);
            Timer._globalManager.RegisterTimer(timer);
            return timer;
        }

        public static void Cancel(Timer timer)
        {
            if (timer != null)
            {
                timer.Cancel();
            }
        }

        public static void Pause(Timer timer)
        {
            if (timer != null)
            {
                timer.Pause();
            }
        }

        public static void Resume(Timer timer)
        {
            if (timer != null)
            {
                timer.Resume();
            }
        }

        public static void CancelAllRegisteredTimers(SCOPE eScope = SCOPE.eLocal)
        {
            //如果计时器不存在，不需要做任何事情
            if (eScope == SCOPE.eLocal)
            {
                if (Timer._manager != null)
                {
                    Timer._manager.CancelAllTimers();
                }
            }
            else if (eScope == SCOPE.eGlobal)
            {
                if (Timer._globalManager != null)
                {
                    Timer._globalManager.CancelAllTimers();
                }
            }
        }

        public static void PauseAllRegisteredTimers(SCOPE eScope = SCOPE.eLocal)
        {
            //如果计时器不存在，不需要做任何事情
            if (eScope == SCOPE.eLocal)
            {
                if (Timer._manager != null)
                {
                    Timer._manager.PauseAllTimers();
                }
            }
            else if (eScope == SCOPE.eGlobal)
            {
                if (Timer._globalManager != null)
                {
                    Timer._globalManager.PauseAllTimers();
                }
            }
        }

        public static void ResumeAllRegisteredTimers(SCOPE eScope = SCOPE.eLocal)
        {
            //如果计时器不存在，不需要做任何事情
            if (eScope == SCOPE.eLocal)
            {
                if (Timer._manager != null)
                {
                    Timer._manager.ResumeAllTimers();
                }
            }
            else if (eScope == SCOPE.eGlobal)
            {
                if (Timer._globalManager != null)
                {
                    Timer._globalManager.ResumeAllTimers();
                }
            }
        }

        #endregion

        #region Public Methods

        public void Cancel()
        {
            if (this.isDone)
            {
                return;
            }

            this._timeElapsedBeforeCancel = this.GetTimeElapsed();
            this._timeElapsedBeforePause = null;
        }

        public void Pause()
        {
            if (this.isPaused || this.isDone)
            {
                return;
            }

            this._timeElapsedBeforePause = this.GetTimeElapsed();
        }

        public void Resume()
        {
            if (!this.isPaused || this.isDone)
            {
                return;
            }

            this._timeElapsedBeforePause = null;
        }

        public float GetTimeElapsed()
        {
            if (this.isCompleted || this.GetWorldTime() >= this.GetFireTime())
            {
                return this.duration;
            }

            return this._timeElapsedBeforeCancel ??
                   this._timeElapsedBeforePause ??
                   this.GetWorldTime() - this._startTime;
        }

        public float GetTimeRemaining()
        {
            return this.duration - this.GetTimeElapsed();
        }

        public float GetRatioComplete()
        {
            return this.GetTimeElapsed() / this.duration;
        }

        public float GetRatioRemaining()
        {
            return this.GetTimeRemaining() / this.duration;
        }

        #endregion

        #region Private Static Properties/Fields

        private static TimerManager _manager;
        private static GlobalTimerManager _globalManager;

        #endregion


        #region Private Properties/Fields

        private bool isOwnerDestroyed
        {
            get { return this._hasAutoDestroyOwner && this._autoDestroyOwner == null; }
        }
        
        private readonly Action _onComplete;
        private readonly Action<float> _onUpdate;
        private float _startTime;
        private float _endTime;
        private float _lastUpdateTime;

        private float? _timeElapsedBeforeCancel;
        private float? _timeElapsedBeforePause;

        private readonly MonoBehaviour _autoDestroyOwner;
        private readonly bool _hasAutoDestroyOwner;

        #endregion

        #region 属性区
        public float EndTime { get { return _endTime; } }
        #endregion

        #region Private Constructor (use static Register method to create new timer)

        private Timer(float duration, Action onComplete, Action<float> onUpdate,
            bool isLooped, bool usesRealTime, MonoBehaviour autoDestroyOwner)
        {
            this.duration = duration;
            this._onComplete = onComplete;
            this._onUpdate = onUpdate;

            this.isLooped = isLooped;
            this.usesRealTime = usesRealTime;

            this._autoDestroyOwner = autoDestroyOwner;
            this._hasAutoDestroyOwner = autoDestroyOwner != null;

            this._startTime = this.GetWorldTime();
            this._lastUpdateTime = this._startTime;
            _endTime = _startTime + duration;
        }

        #endregion

        #region  Methods

        public float GetWorldTime()
        {
            return this.usesRealTime ? Time.realtimeSinceStartup : Time.time;
        }

        private float GetFireTime()
        {
            return this._startTime + this.duration;
        }

        private float GetTimeDelta()
        {
            return this.GetWorldTime() - this._lastUpdateTime;
        }
        
        public void Update()
        {
            isCompletedThisFrame = false;

            if (this.isDone)
            {
                return;
            }

            if (this.isPaused)
            {
                this._startTime += this.GetTimeDelta();
                this._lastUpdateTime = this.GetWorldTime();
                return;
            }

            this._lastUpdateTime = this.GetWorldTime();

            if (this._onUpdate != null)
            {
                this._onUpdate(this.GetTimeElapsed());
            }

            if (this.GetWorldTime() >= this.GetFireTime())
            {
                isCompletedThisFrame = true;
                
                if (this._onComplete != null)
                {
                    this._onComplete();
                }

                if (this.isLooped)
                {
                    this._startTime = this.GetWorldTime();
                    _endTime = _startTime + duration;
                }
                else
                {
                    this.isCompleted = true;
                }
            }
        }

        #endregion 

    }
}

TimerMgr.cs代码实现 

using System.Collections.Generic;
using UnityEngine;
using System;
using Object = UnityEngine.Object;

namespace UnityTimer
{
    public class TimerManager : MonoBehaviour
    {
        //protected List<Timer> _timers = new List<Timer>();

        //初始化默认new 1个空间出来
        protected Timer[] m_szTimers = new Timer[1];

        //已使用的空间
        protected uint m_iUsedSize = 0;

        //protected List<Timer> _timersToAdd = new List<Timer>();

        protected void Resize()
        {
            int iOldCapacity = m_szTimers.Length;
            int iNewCapacity = iOldCapacity * 2;

            Timer[] szTempTimer = new Timer[iNewCapacity];

            //尾部全部设置成null
            for (int i = iOldCapacity; i < iNewCapacity; ++i)
            {
                szTempTimer[i] = null;
            }

            //copy oldData -> newData
            Array.Copy(m_szTimers, szTempTimer, m_szTimers.Length);

            //指向新地址
            m_szTimers = szTempTimer;

            //解除引用
            szTempTimer = null;
        }

        /// <summary>
        /// 小顶堆排序   
        /// </summary>
        public void HeapAdjustSmall(int parent)
        {
            if (parent >= m_szTimers.Length)
            {
                return;
            }

            Timer tmp = m_szTimers[parent];
            
            //时间复杂度应该在O(LogN)附近
            for (int child = parent * 2 + 1; child < m_iUsedSize; child = child * 2 + 1)
            {
                if (child + 1 < m_iUsedSize && m_szTimers[child].EndTime > m_szTimers[child + 1].EndTime)
                {
                    child++;
                }
                if (tmp.EndTime > m_szTimers[child].EndTime)
                {
                    m_szTimers[parent] = m_szTimers[child];
                    parent = child;
                }
                else
                {
                    break;
                }
            }
            m_szTimers[parent] = tmp;
        }

        public void AddTimer(Timer timer)
        {
            if (null == timer)
            {
                return;
            }

            if (m_iUsedSize >= m_szTimers.Length)
            {
                Resize();
            }

            uint hole = m_iUsedSize;
            ++m_iUsedSize;

            // 由于新结点在最后，因此将其进行上滤，以符合最小堆
            for (uint parent = (hole - 1) / 2; hole > 0; parent = (hole - 1) / 2)
            {
                //把时间最短的计时器交换到树根节点
                if (m_szTimers[parent].EndTime > timer.EndTime)
                {
                    m_szTimers[hole] = m_szTimers[parent];
                    hole = parent;
                }
                else
                {
                    break;
                }
            }
            m_szTimers[hole] = timer;
        }

        public void PopTimer()
        {
            if (0 == m_iUsedSize)
            {
                return;
            }

            if (null != m_szTimers[0])
            {
                m_szTimers[0] = m_szTimers[--m_iUsedSize];
                HeapAdjustSmall(0);
            }
        }

        public void RegisterTimer(Timer timer)
        {
            AddTimer(timer);
        }

        public void CancelAllTimers()
        {
            Timer timer = null;
            for (int i = 0; i < m_szTimers.Length; ++i)
            {
                timer = m_szTimers[i];
                if (null != timer)
                {
                    timer.Cancel();
                    m_szTimers[i] = null;
                }
            }

            m_iUsedSize = 0;
        }

        public void PauseAllTimers()
        {
            Timer timer = null;
            for (int i = 0; i < m_szTimers.Length; ++i)
            {
                timer = m_szTimers[i];
                if (null != timer)
                    timer.Pause();
            }
        }

        public void ResumeAllTimers()
        {
            Timer timer = null;
            for (int i = 0; i < m_szTimers.Length; ++i)
            {
                timer = m_szTimers[i];
                if (null != timer)
                    timer.Resume();
            }
        }

        protected void Update()
        {
            UpdateAllTimers();
        }

        protected void UpdateAllTimers()
        {
            Timer tm = null;
            //for (int i = 0; i < m_szTimers.Length; ++i)
            //{
            //    tm = m_szTimers[i];
            //    if (null != tm)
            //        tm.Update();
            //}

            Timer tmp = null;

            tmp = m_szTimers[0];

            while (m_iUsedSize > 0)
            {
                if (null == tmp)
                    break;

                tmp.Update();

                //循环类型的计时器，如果到了时间，重新排序，而不清理
                if (tmp.isCompletedThisFrame && tmp.isLooped)
                {
                    HeapAdjustSmall(0);
                    tmp = m_szTimers[0];
                    continue;
                }

                if (!tmp.isDone)
                    break;

                PopTimer();
                tmp = m_szTimers[0];
            }
        }
    }

    public class GlobalTimerManager : TimerManager
    {
    }

}

3 测试数据对比

在更新所有timer的地方，开启10w定时器测试

使用小顶堆和不使用小顶堆做了对比：


计时器不使用小堆顶：

更新全部，cpu main 在 14.1左右浮动；


计时器使用小堆顶：

计时器timeout时间取的是1-10w,cpu mian 平均 在1.6左右浮动，在雪崩(全部更新的情况)情况下 cpuMian会突然上升到9.6左右；

通过数据比对，使用了小顶堆比不使用小顶堆，在综合情况下

效率要快将近8.8倍

引用


文章：基于STL的小根堆定时器实现（C++）_AlwaysSimple的博客-CSDN博客_小根堆定时器


版权声明：本文为qq_33531923原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。