ホームページ >システムチュートリアル >Linux >ゲームビジネスにおけるタイマーコンポーネントの重要性とその実装方法
タイマーは比較的一般的なコンポーネントです。サーバーに関する限り、フレームワーク レベルではタイマーを使用してセッションをタイムアウトする必要があり、アプリケーション レベルではタイマーを使用して時間関連のビジネス ロジックを処理する必要があります。多数のタイマーを必要とするゲームなどのビジネスには、シンプルで効率的なタイマー コンポーネントが不可欠です。
タイマー コンポーネントの実装は 2 つの部分に分けることができます:
最初の部分は比較的単純で、さまざまな実装方法がありますが、基本的には言語に関連するものであるため、この記事の焦点ではありません。いわゆる具体的な概念とは、ユーザーがどのように使用するかを指すようです。
【記事の特典】編集者がより良いと思う学習本やビデオ教材をグループファイルにアップロードしましたので、必要な場合はグループ[977878001]に参加して入手してください。 ! ! 699 相当の追加カーネル情報パッケージ (ビデオ チュートリアル、電子書籍、実用的なプロジェクトとコードを含む) が付属しています
カーネル情報ダイレクトトレイン: Linuxカーネルソースコード技術学習ルート+ビデオチュートリアルコード情報
特急列車の学習(Tencent Classroomへの無料登録):Linuxカーネルソースコード/ビデオメモリチューニング/ファイルシステム/プロセス管理/デバイスドライバー/ネットワークコントラクトスタック
2 番目の部分では、実際には最初の部分よりも多くのコードが必要になり、実装方法は非常に限られています。
これらのモデルの目的は、データ構造を研究した卒業生を見つけて書き留めてもらうことで、バグが発生しにくくなるということです。 add の時間計算量は n(lgn) であり、timeout の時間計算量も n(lgn) です。
ただし、私たちのビジネス システムが、短期間にタイムアウトになる多数のタイマーを登録するというような要求に直面しているとします。実際、最小ヒープの実装は少し恥ずかしいものです。
以下の本文に入り、Xiaoxiao はアプリケーション層に Linux カーネル スタイルのタイマーを実装する方法を紹介します。言語は例として C# です。
パフォーマンスを比較するには、まず最小ヒープに基づいてタイマー マネージャーを実装する必要があります。最小ヒープのインターフェイスは次のとおりです。Linux アプリケーション タイマー は最も基本的なものですが、具体的な実装はありません。データ構造。
リーリー
リーリー
リーリー
その後は、Linux カーネル スタイルのタイマーのマネージャー実装です。まず設計の前提があります:
システム全体の時間精度の下限を定義するには、ティックを使用する必要があります。たとえば、ゲームの場合、10 ミリ秒未満の精度は気にする必要がないため、ティック幅を 10 ミリ秒に設定できます。つまり、最初にハングアップした WaitFor(8ms) と、後でハングアップした WaitFor(5ms) が先にタイムアウトになる可能性があります。 1 ティックは 10 ミリ秒であり、このような 32 ビット ティックが表現できる時間粒度は、組み込み Linux トレーニングのほぼ 500 日分に相当します。これは、再起動を行わないサーバー グループの時間よりもはるかに長くなります。
虽然这些定时器实现,就是由于这个抉择,在面对之前提到的问题时,方才具有了更佳的性能表现。每次按照tick领到timeout数组,直接dispatch,领到这个数组的时间是一个常数,而最小堆方式领到这个数组须要的时间是m*lgn。
因为空间有限,我们不可能做到每位即将timeout的tick都有对应的数组。考虑到虽然80%以上的timer的时间都不会超过2.55s,我们只针对前256个tick做这些优化举措即可。
那怎么处理注册的256tick以后的timer?我们可以把时间还比较长的timer置于更粗细度的数组中,等到还剩下的tick数大于256以后再把她们取下来重新整理一下数组能够搞定。
假如我们保证每一次tick都严格的做到:
保证这两点,就须要每位tick都对所有数组做一次整理。这样就得不偿失了,所以这儿有个trade-off,就是我通过一个表针(index),来标记我当前处理的position,每过256tick是一个cycle,才进行一次整理。而整理的成本就通过分摊在256tick中,增加了实际上的单位时间成本。
概念比较具象,接出来贴一部份代码。
常量定义:
public const int TimeNearShift = 8; public const int TimeNearNum = 1 << TimeNearShift;// 256 public const int TimeNearMask = TimeNearNum - 1;// 0x000000ff public const int TimeLevelShift = 6; public const int TimeLevelNum = 1 << TimeLevelShift;// 64 public const int TimeLevelMask = TimeLevelNum - 1;// 00 00 00 (0011 1111)
基础数据结构:
using TimerNodes = LinkedList; private readonly TimerNodes[TimeNearNum] nearTimerNodes; private readonly TimerNodes[4][TimeLevelNum] levelTimerNodes;
相当于是256+4*64个timer数组。
tick有32位,每一个tick只会timeout掉expire与index相同的timer。
循环不变式保证near表具有这样几个性质:
level表有4个,分别对应9到14bit,15到20bit,21到26bit,27到32bit。
因为原理都类似,我这儿拿9到14bit的表来说下循环不变式:
有了数据结构和循环不变式,前面的代码也就容易理解了。主要列一下AddTimer的逻辑和Shift逻辑。
private void AddTimerNode(TimerNode node) { var expire = node.ExpireTick; if (expire < index) { throw new Exception(); } // expire 与 index 的高24bit相同 if ((expire | TimeNearMask) == (index | TimeNearMask)) { nearTimerNodes[expire & TimeNearMask].AddLast(node); } else { var shift = TimeNearShift; for (int i = 0; i < 4; i++) { // expire 与 index 的高bit相同 var lowerMask = (1 <> shift)&TimeLevelMask].AddLast(node); break; } shift += TimeLevelShift; } } }
private void TimerShift() { // TODO index回绕到0的情况暂时不考虑 index++; var ct = index;// mask0 : 8bit // mask1 : 14bit // mask2 : 20bit // mask3 : 26bit // mask4 : 32bit var partialIndex = ct & TimeNearMask; if (partialIndex != 0) { return; } ct >>= TimeNearShift; for (int i = 0; i >= TimeLevelShift; continue; } ReAddAll(levelTimerNodes[i], partialIndex); break; } }
以上代码用c/c++重画后尝尝鲜味更佳。
实现大约就是这种了,接出来我们测一下究竟linux内核风格定时器比最小堆实现的定时器快了多少。
建立的测试用例和测试方式:
static IEnumerable BuildTestCases(uint first, uint second) { var rand = new Random(); for (int i = 0; i < first; i++) { yield return new TestCase() { Tick = (uint)rand.Next(256), }; } for (int i = 0; i < 4; i++) { var begin = 1U << (8 + 6*i); var end = 1U << (14 + 6*i); for (int j = 0; j < rand.Next((int)second * (4 - i)); j++) { yield return new TestCase() { Tick = (uint)rand.Next((int)(begin+end)/2), }; } } }
{ var maxTick = cases.Max(c => c.Tick); var results = new HashSet(); foreach (var c in cases) { TestCase c1 = c; mgr.AddTimer(c.Tick, (timer, data) => { if (mgr.FixedTicks == c1.Tick) results.Add((uint) data[0]); }, c.Id); } var begin = DateTime.Now; for (int i = 0; i < maxTick+1; i++) { mgr.FixedTick(); } var end = DateTime.Now; }
建立测试用例时的参数first指大于等于256tick的timer数目,second是指小于256tick的timer数目。
first固定为一千万的测试结果:
加速比的波動不是非常顯著,而且假如second繼續降低,linux內核定時器的加速比實際上還是會因為shift頻度的提高而逐漸增加。
second固定為1000的情況:
跟第一次測試的推論差不多,256tick以內的timer佔比越高,相比最小堆定時器的優勢越大。
最終結論,linux內核定時器比起最小堆定時器的優勢還是很顯著的,大部份情況下都有2倍以上的性能表現,強烈建議採用。
這次的程式碼放到github上linux 應用計時器,並且因為訂閱號文章裡沒辦法放連結linux軟體,只要後台給小說君發訊息「計時器」就會手動回覆github連結。這個專案裡不僅有一個工業級的linux風格定時器實現代碼,還有小說君實現的一套基於這個定時器的Unity3D風格的Coroutine。
--核心技術英文網-建立全省最權威的核心技術交流分享高峰會
原文位址:了解Linux核心風格的定時器實作-作業系統-核心技術英文網-建立全省最權威的核心技術交流分享高峰會(版權歸原作者所有,侵刪)
以上がゲームビジネスにおけるタイマーコンポーネントの重要性とその実装方法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。