Blog.csdn.net/soft2967/ar…
High performance timer How many timer structures such as linked list, minimum heap, time wheel in different application scenarios which need to consider efficiency and complexity this time I will first talk about the time wheel timer, in the Linux kernel this structure timer is widely used. 1. What are the advantages of the time wheel timer, or what problems can be solved by the timer of this structure? In the ascending list timer above, you can see that when adding a timer, the complexity is O(n) because of order, so the traversal list inserts into the appropriate position. Assuming the system has a large number of timers (10W) using the ascending chain phenotype will have performance problems. This is where a time wheel timer would be more appropriate. Commonly used timer implementation algorithm complexity StartTimerStopTimerPerTickBookkeeping based on chain table O (1) O (n) O (n) based on the ranking list O (n) O (1) O (1) based on the minimum pile of O (LGN) O (1) O (1) Based on the time round O(1) O(1) O(1) \
As shown in figure:
Suppose there are N slots, and the time wheel rotates clockwise at a constant speed. Each step of rotation points to the next slot, and the time interval for each rotation is called a ticking interval Si. In this way, the time for one rotation is T = Si *N, and each slot is a linked list. In this way, when inserting the timer, you can directly calculate which slot to put it in. \
If insertslot = (curslot + (T/si)) % N, then we can do it in O(1).
// Here is the simple time wheel timer code
class tw_timer; struct client_data { unsigned int uUin; // Role ID unsigned int utype; // Building type tw_timer* timer; }; \
\
typedef void (*pFUNC)(client_data*); Class tw_timer {public: // Ts slot index tw_timer(int rot, int ts,pFUNC TimeOutCall) : next( NULL ), prev( NULL ), rotation( rot ), time_slot( ts ) { TimeOutfunc = TimeOutCall; } public: // The timer expires int rotation; // Index of slot int time_slot; //void (*cb_func)(client_data*); pFUNC TimeOutfunc; // custom function client_data* user_data; // list pointer tw_timer* next; tw_timer* prev; }; Class time_wheel {public: time_wheel() : cur_slot(0)) {// Get the server time LastTickTime = GetCurTime(); for( int i = 0; i < N; ++i ) { slots[i] = NULL; } } ~time_wheel() { for( int i = 0; i < N; ++i ) { tw_timer* tmp = slots[i]; while( tmp ) { slots[i] = tmp->next; delete tmp; tmp = slots[i]; } } } tw_timer* add_timer( int timeout, pFUNC TimeOutCall) { if( timeout < 0 ) { return NULL; } int ticks = 0; // At least one tick interval if(timeout < TI) {ticks = 1; } else { ticks = timeout / TI; Rotation = ticks/N; Int ts = (cur_slot + (ticks % N)) % N; tw_timer* timer = new tw_timer( rotation, ts ,TimeOutCall); // If there is no timer on the current slot, put it in the head position, otherwise put it in the head position if(! slots[ts] ) { printf( “add timer, rotation is %d, ts is %d, cur_slot is %d\n”, rotation, ts, cur_slot ); slots[ts] = timer; } else { timer->next = slots[ts]; slots[ts]->prev = timer; slots[ts] = timer; } return timer; } void del_timer(tw_timer* timer) {if(! timer ) { return; } int ts = timer->time_slot; if( timer == slots[ts] ) { slots[ts] = slots[ts]->next; if( slots[ts] ) { slots[ts]->prev = NULL; } delete timer; } else { timer->prev->next = timer->next; if( timer->next ) { timer->next->prev = timer->prev; } delete timer; Void tick(unsigned int time) {// Count the number of ticks in the update interval unsigned int Ticount = (time – LastTickTime)/TI; tw_timer* tmp = slots[cur_slot]; printf( “current slot is %d\n”, cur_slot ); for(int i = 0; i < Ticount; ++i) { while( tmp ) { printf( “tick the timer once\n” ); if( tmp->rotation > 0 ) { tmp->rotation–; tmp = tmp->next; } else { tmp->TimeOutfunc( tmp->user_data ); if( tmp == slots[cur_slot] ) { printf( “delete header in cur_slot\n” ); slots[cur_slot] = tmp->next; delete tmp; if( slots[cur_slot] ) { slots[cur_slot]->prev = NULL; } tmp = slots[cur_slot]; } else { tmp->prev->next = tmp->next; if( tmp->next ) { tmp->next->prev = tmp->prev; } tw_timer* tmp2 = tmp->next; delete tmp; tmp = tmp2; %N cur_slot = ++cur_slot %N; } LastTickTime = time; } private: // Static const int N = 60; Static const int TI = 1; // Static const int TI = 1; // Time slots tw_timer* slots[N]; // Current slot index int cur_slot; // Last update unsigned int LastTickTime; }; \
\
// How is it used in the background
There’s a main loop in the background that looks something like this
bool update() { while(! Stopserver) {// Read network IO // read DB packets // handle events // handle timer timeWhel.tick (); // Process logic}}\
// Drive our timer in the living loop and call the tick function
For example, we now have a requirement that players can build all kinds of buildings, such as houses, barracks, fields, etc., which will be completed after a certain period of time and notified to the front desk, so we need a timer
.
Void BuilderHouse(client_data* clietData) {// pseudocode logic /* if (NULL == clietData) {LOG(“XXX”); return; } CRole* pRole = FindRole(clietdata->uUin); if (NULL == pRole) { LOG(“XXX”); return; } pRole->BuilderHouse();
// Notify the front desk
Send(msg); // void BuilderCamp(client_data* clietData) {// void BuilderField(client_data* clietdata) {// void BuilderField(client_data* clietdata) {//
\
static time_wheel timewhel; \
// Suppose the player creates a house in the game scene and executes the downlink code \
Int CmdBuild() {BuilderHouse: timewhel.add_timer(180,BuilderHouse); BuilderHouse: timewhel.add_timer(180,BuilderHouse); \
}
\