up to 25% reduction in runtime of `dpkg -S'
I've been studying the implementation of `dpkg -S'. I used gprof to
gather some hard information and discovered that a large proportion of
the runtime is spent in parsedb(), which is called twice, once to read
the status file and once to read the available file.
(There would appear to be situations in which it can be called more
often than that, which I don't fully understand yet, but I don't think
they're immediately relevant.)
I have a modified dpkg in which `dpkg -S' does not parse the available
file. I get a speed improvement of 25% when searching for a single
file and almost 20% when searching for all files. Here are my
figures:
lyonesse$ for i in a b c d; do time dpkg -S /bin/ls; done >/dev/null
real 0m2.396s
user 0m1.740s
sys 0m0.650s
real 0m2.394s
user 0m1.730s
sys 0m0.670s
real 0m2.401s
user 0m1.760s
sys 0m0.640s
real 0m2.392s
user 0m1.780s
sys 0m0.610s
lyonesse$ for i in a b c d; do time main/dpkg -S /bin/ls; done >/dev/null
real 0m1.772s
user 0m1.130s
sys 0m0.640s
real 0m1.778s
user 0m1.210s
sys 0m0.570s
real 0m1.775s
user 0m1.220s
sys 0m0.560s
real 0m1.865s
user 0m1.130s
sys 0m0.660s
lyonesse$
lyonesse$ for i in a b c d; do time dpkg -S \*; done >/dev/null
real 0m3.235suser 0m2.280s
sys 0m0.950s
real 0m3.320s
user 0m2.320s
sys 0m0.970s
real 0m3.233s
user 0m2.220s
sys 0m1.020s
real 0m3.253s
user 0m2.360s
sys 0m0.890s
lyonesse$ for i in a b c d; do time main/dpkg -S \*; done >/dev/null
real 0m2.603s
user 0m1.930s
sys 0m0.670s
real 0m2.653s
user 0m1.800s
sys 0m0.810s
real 0m2.608s
user 0m1.770s
sys 0m0.840s
real 0m2.613s
user 0m1.700s
sys 0m0.920s
Below is the diff. It's uuencoded to keep tabs safe. It works by
adding an msdbrw_noavail flag which searchfiles() passes to
modstatdb_init() to request that the available file not be read.
If I have missed some crucial fact about the implementation that means
that the `available' file must be parsed, then I offer my apologies in
advance, and would point out that I haven't had any breakfast yet.
ttfn/rjk
begin 644 dpkg.diff
M/R!D<&MG+F=M;VXN;W5T+FQS"C\@9'!K9RYG;6]N+F]U="YB:6XN;',*/R!P
M<F]F:6QE+C$*/R!A;F%L>7-Y<RYT97AT"C\@<')O9FEL92XR"C\@9VUO;BYO
M=70*26YD97@Z(&EN8VQU9&4O9'!K9RUD8BYH"CT]/3T]/3T]/3T]/3T]/3T]
M/3T]/3T]/3T]/3T]/3T]/3T]/3T]/3T]/3T]/3T]/3T]/3T]/3T]/3T]/3T]
M/3T]/3T*4D-3(&9I;&4Z("]U<W(O<W)C+T-64R]D<&MG+VEN8VQU9&4O9'!K
M9RUD8BYH+'8*<F5T<FEE=FEN9R!R979I<VEO;B`Q+C(*9&EF9B`M=2`M<C$N
M,B!D<&MG+61B+F@*+2TM(&EN8VQU9&4O9'!K9RUD8BYH"3$Y.3DO,#,O,#(@
M,#,Z,3$Z,3D),2XR"BLK*R!I;F-L=61E+V1P:V<M9&(N:`DQ.3DY+S`W+S(T
M(#$P.C`Y.C4U"D!`("TQ-#@L-R`K,30X+#@@0$`*("`@;7-D8G)W7W=R:71E
M+RIS*B\L(&US9&)R=U]N965D<W5P97)U<V5R+`H@("`O*B!.;W<@<V]M92!O
M<'1I;VYA;"!F;&%G<SH@*B\*("`@;7-D8G)W7V9L86=S;6%S:ST@?C`W-RP*
M+2`@+RH@+BXN(&]F('=H:6-H('1H97)E(&%R92!C=7)R96YT;'D@;F]N92P@
M8G5T('1H97DG9"!S=&%R="!A="`P,3`P("HO"BL@("\J(&9L86=S('-T87)T
M(&%T(#`Q,#`@*B\**R`@;7-D8G)W7VYO879A:6P@/2`P,3`P+`H@?3L*(`H@
M96YU;2!M;V1S=&%T9&)?<G<@;6]D<W1A=&1B7VEN:70H8V]N<W0@8VAA<B`J
M861M:6YD:7(L(&5N=6T@;6]D<W1A=&1B7W)W(')E<7)W9FQA9W,I.PI);F1E
M>#H@;&EB+V1B;6]D:69Y+F,*/3T]/3T]/3T]/3T]/3T]/3T]/3T]/3T]/3T]
M/3T]/3T]/3T]/3T]/3T]/3T]/3T]/3T]/3T]/3T]/3T]/3T]/3T]/0I20U,@
M9FEL93H@+W5S<B]S<F,O0U93+V1P:V<O;&EB+V1B;6]D:69Y+F,L=@IR971R
M:65V:6YG(')E=FES:6]N(#$N,@ID:69F("UU("UR,2XR(&1B;6]D:69Y+F,*
M+2TM(&QI8B]D8FUO9&EF>2YC"3$Y.3DO,#,O,#(@,#,Z,3$Z,C$),2XR"BLK
M*R!L:6(O9&)M;V1I9GDN8PDQ.3DY+S`W+S(T(#$P.C`Y.C4U"D!`("TQ-S$L
M.2`K,3<Q+#$P($!`"B`*("`@:68@*&-S=&%T=7,@(3T@;7-D8G)W7VYE961S
M=7!E<G5S97)L;V-K;VYL>2D@>PH@("`@(&-L96%N=7!D871E<R@I.PHM("`@
M('!A<G-E9&(H879A:6QA8FQE9FEL92P*+2`@("`@("`@("`@('!D8E]R96-O
M<F1A=F%I;&%B;&5\<&1B7W)E:F5C='-T871U<RP*+2`@("`@("`@("`@(#`L
M,"PP*3L**R`@("`**R`@("!I9B@A*&-F;&%G<R`F(&US9&)R=U]N;V%V86EL
M*2D@<&%R<V5D8BAA=F%I;&%B;&5F:6QE+`HK"0D)"0D@("!P9&)?<F5C;W)D
M879A:6QA8FQE?'!D8E]R96IE8W1S=&%T=7,L"BL)"0D)"2`@(#`L,"PP*3L*
M("`@?0H@"B`@(&EF("AC<W1A='5S(#X](&US9&)R=U]W<FET92D@>PI);F1E
M>#H@;6%I;B]E;G%U:7)Y+F,*/3T]/3T]/3T]/3T]/3T]/3T]/3T]/3T]/3T]
M/3T]/3T]/3T]/3T]/3T]/3T]/3T]/3T]/3T]/3T]/3T]/3T]/3T]/0I20U,@
M9FEL93H@+W5S<B]S<F,O0U93+V1P:V<O;6%I;B]E;G%U:7)Y+F,L=@IR971R
M:65V:6YG(')E=FES:6]N(#$N,@ID:69F("UU("UR,2XR(&5N<75I<GDN8PHM
M+2T@;6%I;B]E;G%U:7)Y+F,),3DY.2\P-R\R,B`P,#HQ,CHQ,0DQ+C(**RLK
M(&UA:6XO96YQ=6ER>2YC"3$Y.3DO,#<O,C0@,3`Z,#DZ-38*0$`@+3,T-"PW
M("LS-#0L-R!`0`H@("!I9B`H(2IA<F=V*0H@("`@(&)A9'5S86=E*"(M+7-E
M87)C:"!N965D<R!A="!L96%S="!O;F4@9FEL92!N86UE('!A='1E<FX@87)G
M=6UE;G0B*3L*(`HM("!M;V1S=&%T9&)?:6YI="AA9&UI;F1I<BQM<V1B<G=?
M<F5A9&]N;'DI.PHK("!M;V1S=&%T9&)?:6YI="AA9&UI;F1I<BQM<V1B<G=?
M<F5A9&]N;'E\;7-D8G)W7VYO879A:6PI.PH@("!E;G-U<F5?86QL:6YS=&9I
M;&5S7V%V86EL86)L95]Q=6EE="@I.PH@("!E;G-U<F5?9&EV97)S:6]N<R@I
$.PH@"@``
`
end
Reply to: