From bdb9b86170175ac6c98b8c9b1034312a84487f41 Mon Sep 17 00:00:00 2001 From: Lupus Date: Thu, 24 Mar 2005 17:18:26 +0000 Subject: timers optimization / speed up / bug fix : no freezing mobs ported from Yor's git-svn-id: https://rathena.svn.sourceforge.net/svnroot/rathena/branches/stable@1284 54d463be-8e91-2dee-dedb-b68131a5f0ec --- Changelog-SVN.txt | 1 + src/common/timer.c | 366 ++++++++++++++++++----------------------------------- src/common/timer.h | 13 +- 3 files changed, 137 insertions(+), 243 deletions(-) diff --git a/Changelog-SVN.txt b/Changelog-SVN.txt index 7f699be37..441e08bd1 100644 --- a/Changelog-SVN.txt +++ b/Changelog-SVN.txt @@ -1,6 +1,7 @@ Date Added 03/24 + * Added timer.c optimization / timers sort fix. 'no freezing mobs anymore' Thanx 2 Yor/Freya [Lupus] * Added 'map_charid2id' [celest] * Changed monster damage logging to save char ID's for the most time -- also fixes an exp bug, thanks to Super Novice / Ezhik [celest] diff --git a/src/common/timer.c b/src/common/timer.c index 96631c078..90b4e901e 100644 --- a/src/common/timer.c +++ b/src/common/timer.c @@ -1,82 +1,75 @@ -// $Id: timer.c,v 1.1.1.1 2004/09/10 17:44:49 MagicalTux Exp $ +// $Id: timer.c,v 1.1.1.1 2004/09/10 17:44:49 Yor Exp $ // original : core.c 2003/02/26 18:03:12 Rev 1.7 +//#include + #include #include #include #include -#ifdef _WIN32 -#include +#ifdef __WIN32 +#define __USE_W32_SOCKETS +#include #else #include #include #endif #include "timer.h" -#include "utils.h" -#include "../common/malloc.h" +#include "malloc.h" #ifdef MEMWATCH #include "memwatch.h" #endif -// タイマー間隔の最小値。モンスターの大量召還時、多数のクライアント接続時に -// サーバーが反応しなくなる場合は、TIMER_MIN_INTERVEL を増やしてください。 - -// If the server shows no reaction when processing thousands of monsters -// or connected by many clients, please increase TIMER_MIN_INTERVEL. - -#define TIMER_MIN_INTERVEL 50 - static struct TimerData* timer_data; -static int timer_data_max,timer_data_num; +static int timer_data_max, timer_data_num; static int* free_timer_list; static int free_timer_list_max, free_timer_list_pos; -static int timer_heap_max=0; //fixed Shinomori from eA forums +static int timer_heap_num = 0, timer_heap_max = 0; static int* timer_heap = NULL; // for debug struct timer_func_list { int (*func)(int,unsigned int,int,int); struct timer_func_list* next; - char name[40]; + char* name; }; -static struct timer_func_list* tfl_root=NULL; +static struct timer_func_list* tfl_root; -#if defined(_WIN32) -void gettimeofday(struct timeval *t, struct timezone *dummy) -{ - DWORD millisec = GetTickCount(); +#ifdef __WIN32 +/* Modified struct timezone to void - we pass NULL anyway */ +void gettimeofday(struct timeval *t, void *dummy) { + DWORD millisec = GetTickCount(); - t->tv_sec = (int) (millisec / 1000); - t->tv_usec = (millisec % 1000) * 1000; + t->tv_sec = (int) (millisec / 1000); + t->tv_usec = (millisec % 1000) * 1000; } - #endif - // -int add_timer_func_list(int (*func)(int,unsigned int,int,int),char* name) -{ +int add_timer_func_list(int (*func)(int,unsigned int,int,int), char* name) { struct timer_func_list* tfl; - CREATE(tfl, struct timer_func_list, 1); - //CREATE(tfl->name, char, strlen(name) + 1); + //CALLOC(tfl, struct timer_func_list, 1); + tfl = aCalloc( sizeof(struct timer_func_list) , 1); + //MALLOC(tfl->name, char, strlen(name) + 1); + tfl->name = aMalloc( strlen(name) + 1 ); tfl->next = tfl_root; tfl->func = func; - strncpy(tfl->name, name, sizeof(tfl->name) - 1); + strcpy(tfl->name, name); tfl_root = tfl; return 0; } -char* search_timer_func_list(int (*func)(int,unsigned int,int,int)) -{ +char* search_timer_func_list(int (*func)(int,unsigned int,int,int)) { struct timer_func_list* tfl; - for(tfl = tfl_root;tfl;tfl = tfl->next) { + + for(tfl = tfl_root; tfl; tfl = tfl->next) { if (func == tfl->func) return tfl->name; } @@ -88,24 +81,21 @@ char* search_timer_func_list(int (*func)(int,unsigned int,int,int)) *----------------------------*/ static unsigned int gettick_cache; static int gettick_count; -unsigned int gettick_nocache(void) -{ -#ifdef _WIN32 - gettick_count = 256; // [Shinomori] - return gettick_cache = GetTickCount(); -#else + +unsigned int gettick_nocache(void) { struct timeval tval; - gettimeofday(&tval,NULL); + + gettimeofday(&tval, NULL); gettick_count = 256; - return gettick_cache = tval.tv_sec * 1000 + tval.tv_usec/1000; -#endif + + return gettick_cache = tval.tv_sec * 1000 + tval.tv_usec / 1000; } -unsigned int gettick(void) -{ +unsigned int gettick(void) { gettick_count--; - if (gettick_count<0) + if (gettick_count < 0) return gettick_nocache(); + return gettick_cache; } @@ -113,141 +103,66 @@ unsigned int gettick(void) * CORE : Timer Heap *-------------------------------------- */ - -// デバッグ用関数群 -/* -static void dump_timer_heap(void) { - int j; - for(j = 1 ; j <= timer_heap[0] ; j++) { - if(j != timer_heap[0] && DIFF_TICK( - timer_data[timer_heap[j]].tick, - timer_data[timer_heap[j + 1]].tick - ) < 0) { - printf("*"); +static void push_timer_heap(int index) { + int i, j; + int min, max, pivot; // for sorting + + // check number of element + if (timer_heap_num >= timer_heap_max) { + if (timer_heap_max == 0) { + timer_heap_max = 256; + //CALLOC(timer_heap, int, 256); + timer_heap = aCalloc( sizeof(int) , 256); } else { - printf(" "); + timer_heap_max += 256; + //REALLOC(timer_heap, int, timer_heap_max); + timer_heap = aRealloc( timer_heap, sizeof(int) * timer_heap_max); + memset(timer_heap + (timer_heap_max - 256), 0, sizeof(int) * 256); } - printf("%d : %d %d\n",j,timer_heap[j],timer_data[timer_heap[j]].tick); } -} -*/ - -static void push_timer_heap(int index) -{ - if (timer_heap == NULL || timer_heap[0] + 1 >= timer_heap_max) { - int first = timer_heap == NULL; - - timer_heap_max += 256; - timer_heap = (int*)aRealloc(timer_heap, sizeof(int) * timer_heap_max); - memset(timer_heap + (timer_heap_max - 256), 0, sizeof(int) * 256); - if (first) - timer_heap[0] = 0; - } - - // timer_heap[0] : タイマーヒープの数 - // timer_heap[1..] : タイマーヒープ（大　→　小） - if(timer_heap[0] == 0) { - // データが無い : 先頭に追加 - timer_heap[0]++; - timer_heap[1] = index; - } else if(DIFF_TICK(timer_data[timer_heap[timer_heap[0]]].tick,timer_data[index].tick) > 0) { - // 最後尾に追加 - timer_heap[++timer_heap[0]] = index; - } else if(DIFF_TICK(timer_data[timer_heap[1]].tick,timer_data[index].tick) < 0) { - // 先頭に追加 - memmove(&timer_heap[2],&timer_heap[1],timer_heap[0] * sizeof(int)); - timer_heap[0]++; - timer_heap[1] = index; - } else { - int min = 1; - int max = timer_heap[0] + 1; - while(max != min + 1) { - int mid = (min + max)/2; - if(DIFF_TICK(timer_data[index].tick,timer_data[timer_heap[mid]].tick) > 0) { - max = mid; - } else { - min = mid; - } - } - memmove(&timer_heap[min+2],&timer_heap[min+1],(timer_heap[0] - min) * sizeof(int)); - timer_heap[min+1] = index; - timer_heap[0]++; - } - // check_timer_heap(); -} -// 指定したindex を持つタイマーヒープを返す -static int search_timer_heap(int index) -{ - if (timer_heap == NULL || timer_heap[0] <= 0) { - return -1; + // do a sorting from higher to lower + j = timer_data[index].tick; // speed up + // with less than 4 values, it's speeder to use simple loop + if (timer_heap_num < 4) { + for(i = timer_heap_num; i > 0; i--) + if (j < timer_data[timer_heap[i - 1]].tick) + break; + else + timer_heap[i] = timer_heap[i - 1]; + timer_heap[i] = index; + // searching by dichotomie } else { - int min = 1; - int max = timer_heap[0] + 1; - while(max != min + 1) { - int mid = (min + max)/2; - if(DIFF_TICK(timer_data[index].tick,timer_data[timer_heap[mid]].tick) > 0) { - max = mid; - } else { - min = mid; - } - } - if(timer_heap[min] == index) { - return min; - } else { - int pos = min - 1; - while(pos > 0 && timer_data[index].tick == timer_data[timer_heap[pos]].tick) { - if(timer_heap[pos] == index) { - return pos; - } - pos--; - } - pos = min + 1; - while(pos <= timer_heap[0] && timer_data[index].tick == timer_data[timer_heap[pos]].tick) { - if(timer_heap[pos] == index) { - return pos; - } - pos++; + // if lower actual item is higher than new + if (j < timer_data[timer_heap[timer_heap_num - 1]].tick) + timer_heap[timer_heap_num] = index; + else { + // searching position + min = 0; + max = timer_heap_num - 1; + while (min < max) { + pivot = (min + max) / 2; + if (j < timer_data[timer_heap[pivot]].tick) + min = pivot + 1; + else + max = pivot; } - printf("search_timer_heap : can't find tid:%d\n",index); - return -1; + // move elements - do loop if there are a little number of elements to move + if (timer_heap_num - min < 5) { + for(i = timer_heap_num; i > min; i--) + timer_heap[i] = timer_heap[i - 1]; + // move elements - else use memmove (speeder for a lot of elements) + } else + memmove(&timer_heap[min + 1], &timer_heap[min], sizeof(int) * (timer_heap_num - min)); + // save new element + timer_heap[min] = index; } } -} -static void delete_timer_heap(int index) { - int pos = search_timer_heap(index); - if(pos != -1) { - memmove(&timer_heap[pos],&timer_heap[pos+1],(timer_heap[0] - pos) * sizeof(int)); - timer_heap[0]--; - } + timer_heap_num++; } -#ifdef _WIN32 -int top_timer_heap(void) -#else -static inline int top_timer_heap(void) -#endif -{ - if (timer_heap == NULL || timer_heap[0] <= 0) - return -1; - - return timer_heap[timer_heap[0]]; -} - -#ifdef _WIN32 -int pop_timer_heap(void) -#else -static inline int pop_timer_heap(void) -#endif -{ - if (timer_heap == NULL || timer_heap[0] <= 0) - return -1; - return timer_heap[timer_heap[0]--]; -} - -int add_timer(unsigned int tick,int (*func)(int,unsigned int,int,int),int id,int data) -{ +int add_timer(unsigned int tick,int (*func)(int,unsigned int,int,int),int id,int data) { struct TimerData* td; int i; @@ -258,25 +173,18 @@ int add_timer(unsigned int tick,int (*func)(int,unsigned int,int,int),int id,int } else i = timer_data_num; if (i >= timer_data_num) - for (i = timer_data_num;i= timer_data_num && i >= timer_data_max) { - int j; if (timer_data_max == 0) { timer_data_max = 256; - CREATE_A(timer_data, struct TimerData, timer_data_max); - //timer_data[0] = NULL; + //CALLOC(timer_data, struct TimerData, timer_data_max); + timer_data = aCalloc( sizeof(struct TimerData) , timer_data_max); } else { timer_data_max += 256; - RECREATE(timer_data, struct TimerData, timer_data_max); - if (timer_data == NULL) { - printf("out of memory : add_timer timer_data\n"); - exit(1); - } - memset(timer_data + (timer_data_max - 256), 0, - sizeof(struct TimerData) * 256); + //REALLOC(timer_data, struct TimerData, timer_data_max); + timer_data = aRealloc( timer_data, sizeof(struct TimerData) * timer_data_max); + memset(timer_data + (timer_data_max - 256), 0, sizeof(struct TimerData) * 256); } - for(j = timer_data_max-256;jtick = tick; @@ -288,94 +196,79 @@ int add_timer(unsigned int tick,int (*func)(int,unsigned int,int,int),int id,int push_timer_heap(i); if (i >= timer_data_num) timer_data_num = i + 1; + return i; } -int add_timer_interval(unsigned int tick,int (*func)(int,unsigned int,int,int),int id,int data,int interval) -{ +int add_timer_interval(unsigned int tick,int (*func)(int,unsigned int,int,int),int id,int data,int interval) { int tid; + tid = add_timer(tick,func,id,data); timer_data[tid].type = TIMER_INTERVAL; timer_data[tid].interval = interval; + return tid; } -int delete_timer(int id,int (*func)(int,unsigned int,int,int)) -{ +int delete_timer(int id,int (*func)(int,unsigned int,int,int)) { if (id <= 0 || id >= timer_data_num) { printf("delete_timer error : no such timer %d\n", id); return -1; } if (timer_data[id].func != func) { printf("delete_timer error : function dismatch %08x(%s) != %08x(%s)\n", - (int)timer_data[id].func, - search_timer_func_list(timer_data[id].func), - (int)func, - search_timer_func_list(func)); + (int)timer_data[id].func, search_timer_func_list(timer_data[id].func), + (int)func, search_timer_func_list(func)); return -2; } // そのうち消えるにまかせる timer_data[id].func = NULL; timer_data[id].type = TIMER_ONCE_AUTODEL; - // timer_data[id].tick -= 60 * 60 * 1000; +// timer_data[id].tick -= 60 * 60 * 1000; + return 0; } -int addtick_timer(int tid,unsigned int tick) -{ - delete_timer_heap(tid); - timer_data[tid].tick += tick; - push_timer_heap(tid); - return timer_data[tid].tick; +int addtick_timer(int tid,unsigned int tick) { + return timer_data[tid].tick += tick; } -struct TimerData* get_timer(int tid) -{ + +struct TimerData* get_timer(int tid) { return &timer_data[tid]; } +int do_timer(unsigned int tick) { + int i, nextmin = 1000; -int do_timer(unsigned int tick) -{ - int i,nextmin = 1000; - -#if 0 - static int disp_tick = 0; - if (DIFF_TICK(disp_tick,tick)<-5000 || DIFF_TICK(disp_tick,tick)>5000) { - printf("timer %d(%d + %d)\n",timer_data_num,timer_heap[0],free_timer_list_pos); - disp_tick = tick; - } -#endif - - while((i = top_timer_heap()) >= 0) { - if(i == 2) { - i = 2; - } - if (DIFF_TICK(timer_data[i].tick , tick)>0) { - nextmin = DIFF_TICK(timer_data[i].tick , tick); + while(timer_heap_num) { + i = timer_heap[timer_heap_num - 1]; // next shorter element + if (DIFF_TICK(timer_data[i].tick, tick) > 0) { + nextmin = DIFF_TICK(timer_data[i].tick, tick); break; } - pop_timer_heap(); + if (timer_heap_num > 0) // suppress the actual element from the table + timer_heap_num--; timer_data[i].type |= TIMER_REMOVE_HEAP; if (timer_data[i].func) { - if (DIFF_TICK(timer_data[i].tick , tick) < -1000) { + if (DIFF_TICK(timer_data[i].tick, tick) < -1000) { // 1秒以上の大幅な遅延が発生しているので、 // timer処理タイミングを現在値とする事で // 呼び出し時タイミング(引数のtick)相対で処理してる // timer関数の次回処理タイミングを遅らせる - timer_data[i].func(i,tick,timer_data[i].id,timer_data[i].data); + timer_data[i].func(i, tick, timer_data[i].id, timer_data[i].data); } else { - timer_data[i].func(i,timer_data[i].tick,timer_data[i].id,timer_data[i].data); + timer_data[i].func(i, timer_data[i].tick, timer_data[i].id, timer_data[i].data); } } - if (timer_data[i].type&TIMER_REMOVE_HEAP) { + if (timer_data[i].type & TIMER_REMOVE_HEAP) { switch(timer_data[i].type & ~TIMER_REMOVE_HEAP) { case TIMER_ONCE_AUTODEL: timer_data[i].type = 0; if (free_timer_list_pos >= free_timer_list_max) { free_timer_list_max += 256; - RECREATE(free_timer_list, int, free_timer_list_max); - memset(free_timer_list + (free_timer_list_max - 256), 0, - 256 * sizeof(free_timer_list[0])); + //REALLOC(free_timer_list, int, free_timer_list_max); + free_timer_list = aRealloc(free_timer_list, sizeof(int) * free_timer_list_max); + memset(free_timer_list + (free_timer_list_max - 256), 0, 256 * sizeof(int)); } free_timer_list[free_timer_list_pos++] = i; break; @@ -392,25 +285,14 @@ int do_timer(unsigned int tick) } } - if(nextmin < TIMER_MIN_INTERVEL) + if (nextmin < 10) + nextmin = 10; - nextmin = TIMER_MIN_INTERVEL; return nextmin; } -void timer_final(void) -{ - struct timer_func_list *tfl, *tfl_next; - for(tfl = tfl_root; tfl; tfl = tfl_next) - { - tfl_next = tfl->next; - aFree(tfl); - tfl = NULL; - } - if(timer_heap) - aFree(timer_heap); - if(free_timer_list) - aFree(free_timer_list); - if(timer_data) - aFree(timer_data); +void timer_final() { + //FREE(timer_data); + aFree(timer_data); } + diff --git a/src/common/timer.h b/src/common/timer.h index 57036ae01..81086cb70 100644 --- a/src/common/timer.h +++ b/src/common/timer.h @@ -3,6 +3,12 @@ #ifndef _TIMER_H_ #define _TIMER_H_ +#ifdef __WIN32 +/* We need winsock lib to have timeval struct - windows is weirdo */ +#define __USE_W32_SOCKETS +#include +#endif + #define BASE_TICK 5 #define TIMER_ONCE_AUTODEL 1 @@ -25,6 +31,10 @@ struct TimerData { // Function prototype declaration +#ifdef __WIN32 +void gettimeofday(struct timeval *t, void *dummy); +#endif + unsigned int gettick_nocache(void); unsigned int gettick(void); @@ -36,9 +46,10 @@ int addtick_timer(int tid,unsigned int tick); struct TimerData *get_timer(int tid); int do_timer(unsigned int tick); -void timer_final(); int add_timer_func_list(int (*)(int,unsigned int,int,int),char*); char* search_timer_func_list(int (*)(int,unsigned int,int,int)); +void timer_final(); + #endif // _TIMER_H_ -- cgit v1.2.3-60-g2f50