Faster timers for Linux 2.1.22 (patch included)

Finn Arne Gangstad (finnag@foa.unit.no)
Fri, 24 Jan 1997 22:53:38 +0100 (MET)


(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