Messages in this thread |  | | Date | Fri, 24 Jan 1997 22:53:38 +0100 (MET) | From | Finn Arne Gangstad <> | Subject | Faster timers for Linux 2.1.22 (patch included) |
| |
(apologies to those that get this twice or more)
Several people have complained about Linux timers. I've spent a few days looking at the code, and came out with what I think is a good solution to timers.
First, a few words about the old code:
- add_timer() inserts a timer into a sorted doubly linked list, by starting at the top and figuring out where the timer fits in. This is a O(N) operation, where N is the number of currently active timers. This function is the performance problem with the old code. - del_timer() removes the element from the list, and is a O(1) operation. - run_timer_list() removes the first elements from the list, and is a O(1) operation per timer that has timed out.
Someone suggested keeping the timers in a heap, this would lead to add_timer, del_timer and run_timer_list being O(log N) operations, where N is the number of active timers.
The code presented here makes all these operations O(1) operations, which means timers are incredibly cheap, and there is no extra cost for other parts of the system by adding timers. It uses about 2kb for 5 timer-arrays (4kb on 64 bit pointer architectures).
A user-level test-program with all sti() and cli()s removed could insert and dispatch 800000 timers with empty functions per second on a ppro 200, with 2 million active timers at all times.
begin 644 patch-2.1.22-timers.gz M'XL(`*0AZ3("`YU8^U/;UA+^6?XK-G3*E9%E6\8!`H$;,J$,+=",,<V=IAV- ML([P*;+DT<.0ING?WMWST,.6P;U,`M;1V=VSKV^_8Y\'`=AY`B&/\B=['GH\ MZO%H$N8^ZXFU7L9G+.E.Y8[F=RW;ME_68'QB/IS.$X!=Z!\<#OJ'P]?@O'FS MU[(LZSGUQ@\)AQ^]"`9#(*DWA_T#$MQOO7L']OZ;CN.`A7]V#^#=NQ;`#F0Q M^#S->'2?\W0*=RQ[9"R";,IP/0A8PJ(,>+2()U[&XRCMDE2O!6F6Y),,A%TW M1`WPM64;JZL[$7O*CEK6VE?0VX%9CH]W#`*>X`>TF'P11IJ$Y@E;'.&K/$KY M?81Q"N/H'MC3G"<L77WA>YE'JXN8^V#N!'DT(3_:9FU;&T_X#?^WK-Y.R\*P MC'^Y=M]?C&_`9Q/NLU0$).5_,H@#B.+(#ID7V%'L,WDX>\$F69RD2GBT7I@^ M-PN3;(_.\)W/`AZQ\A![U36E^Z"^[^;BUS,P'7C[MA!KUZ5J.T:K.Z[=J].; MG\`LM-G@+*G0&T;5#2VKEB7T!4MA*=^T6%1"/4&S/%Q=S/[`VN.43\O@6(#I ME`>9?N"1SY[6E!0:^JP=^+U(ZO)9W"2.LQ=.N9FED;8$:`E:6(<92R(0U>;Y MOBLDS`9Q^8!UYS?AR@,J86$OG4R9WYVHCJ\OKB!)_745"9Q=Q(_#H2.1H(20 M]1(#YW!X<.CLE]BQU]D#:Z^SKW%#P)'=']H#Q[B*T0F.N;O[`K=APB=3^(2A M"PE<9MX#@^OQ1WB,DX>*I#.P![L`5=$/WH+!>1)3AZ!DP)_@+K]/,0N0LIDW MG\;8X>!%OE13_1%6*IMNKCY"Z@5,M*-PPNX[-CI6,_@#CR(XQ1C`N1?=IYGG M%R<6V4DAG7@A(U#$K&KD:R%BR9`,!YW]/D9EN-MQ7@]$9`S734/&YFX<F?/. M&/O%O;V^N!Z?C4:W'\<7[R_/VE0KJ,5&+3:!!7H[96@ZB!,!#A(21)5,/?07 MMA2X;6%(6.@3B%R=_L^]1;4=H0)#(B$F3@C((8GSC%IV$N=1ED),<,[3;I<V M]UHV.IKQ20."RX_B,,?P%;;+YT[]X>]^!_#?]>WE)=6]U:21FBE;O(;CEO55 M[.R`P!ZS0#`+IUN)M&VA<LU+?*<[>9VEH;2TC38;+`V>LS3X=Y9V"TO#!DO. M<Y:<?V=I4%C:59:TKIKBES1)N,L6CDKK8H`24!-9@E\AJ3`8A?JT%?0DN+G\ M^9/[_G;L?CA[?WM^?G%][HXOKLY&-]"GNMX8^PKC/`I)KQ#D4<J2;+VL^-Q! M2,:?AM<$RQT0V.T_M5N"E-1]"T+O'N=*(U>9"^`/P#1E$Y[0,$#_">M1W^_M M-AG63_8)<1%\+3:3J'Y375.:U-8FE]K;6HX&5B4IU;A00-,P?FR*C)A;V4)% M!6!=V/#T7U=&+=JE<ZEC*JC!T9XM[!,]AMMP<B(6RCF,02+)D^.2??SU%RQI M>5NOI+88N4*6E%%PU9*QY)Y^W2G&)&[Z!BQ,F1(@GD;.RF)"P`../"N.50'' M1"<3=H_.(X5%R/J#*":&\Z$0TU!+FWF6LC#H@GK9$W_K-5#/8Y%>PY@G6&X/ MYD]GHVOWT^D(T?X<MDYQ8LPR)@8*^H8H+FT]\FP*6]*,_-'HCDJ_#W.5"!VQ M8UQJ_Q9M=:H2]2!WEF(L0X6_JN&J=95L(9%/T2TBVH+J($)1V\!V00>%NF]4 MEAB;ESO[_RBSE<.+S&*"2&*"=.2.3>(9`]L!+)PO<;X:SR6EQ\>@]$E%8QQ^ M0M/4F\_Q;K-.C0=_LB36]21E1=EX`181)'GD5GREV8Q+7;&O5VD)0GD\0E]@ MA72;\--``,4M:\$3N8-HC$K1E0U%54>M`D6Y;95Y:*-S88B!%E[0Y43X(4X9 M)/$,OI^+$K*QA%SW+N<AL@,W85F>1"ZJP9BE9K\M*T?5V//[\!ARF3YB:7S' M(F15:&".SE:80C6=@F7F(</CIHS-4M6C"X9WO2".!*W1#<OU#$J%3U*![G., M[>WESQ@W)$%80(_3+_\%^!!'_\$K)'''I*:&9YU*)@D`FCH?J1->UL(BH$16 MD7JI`L+"P@L:<N1:KE>KKCB60K6-`$2U:0U0Y:U":5F"1CF^2UA\N<V=KFYS MI[O2YJ.E-E^9/C1+?99YD^EF;4_[L3ATU:^Y]G?T1=XRZN'1UZ]JF&30]-BI MC`WZ6$14[S&D=4>Y)&1T_UB&4%SD1%NC?;*BZ>QZ#+<LZ7RX`96IN+YZG56< M`XP4KSBN>#+%;]%+DY";;6(D?BSXBNBBN0Z%C1E^G'*\ABQ7W`EM4@]"OEYO M\\J2#I&.)';J<B76]M:+]DA&!Q]KA5#6X'.%WB<7\8097LR67*_'7-Z*-H]X M`TF:>'AA\YD43IND=_R"(`HNT\R9%*%2_+%6T?8R2K=ESM:0S*;Z!YW8IG+` MU:(>)!5=[8\VO#H65RIEVS!KC5"=&4N5;K]`:TBIW%4TD4ULPC;6IK"WH\,. M.(5*<$WE[,D6%&Q$5Q'37C,B%%56I8:PO0VO"FJBNG<IPP6'*<BI_"BBI!M; M=8],&KDLA3X7NI'7:_S,-%'9@!`+>W)J8A`2-HL7>K`(UW&TR"%,]W,)S;B& MUW'Z`G#!0LCGBFJN::M&/%<%C/@MAZ]=!RZC)'/'=6;G5'F=WJD=`DO&17P; M)SH1&OJK3H%,6E,]LK91L8"J$+>2BX(K=(O*KA`(JH'E.T7![E3UZV]V5[[3 M+:M;?^M[M-JI]/UPN5%^6VS7FJ2IKZI[5O&RA.[-FBW-=,,'D4E'J.%`6<#" M*U-G;)D[$W7HJT)^KL=$D[TJR("^@:UTEJ(-_8[XQJ"\5S3TD]CZN5!9]-/: MPMX@+I91!*8BH#-I5A*F=A3ADJ>TK%IXCL3=KJ1`QW4^Y%39D&*UVCRVPS^= ''W4?_1D````` ` end
- Finn Arne Gangstad
|  |