[devel] size_time_regression

[Alexey Tourbin]

Пока не забыл.  Есть ещё несколько идей.

Речь идет о возможности перманентной пересборки сизифа.  Разовая
пересборка с точки зрения имеющегося оборудования достаточно дорога;
и тем не менее оборудование большей частью простаивает.  Значит, каждый
день можно составлять определенный план инкрементной пересборки и
реализовывать его ночью, когда оборудование простаивает.

Disclaimer: это может быть не очень нужно с утилитарной точки зрения.
То есть разовые еженедельные пересборки "понятнее".  С другой стороны,
их приходится ждать.

Теперь ближе к задаче.  Большие по размеру пакеты собираются долго, а
маленькие -- быстро.  Нужно оценить зависимость времени сборки пакета от
размера пакета, это называется линейная регрессия.  (Регрессия может
быть и нелинейной, но в таком случае выбор класса функций становится
нетривиальной задачей; см. "регуляризация"; с другой стороны, нелинейную
регрессию можно свести к линейной при помощи преобразования координат;
это есть в учебниках по эконометрике.)

Если же есть регрессия с приличным коэффициентом детерминации, то можно
решить следующую задачу: какое количество пакетов, подлежащих
пересборке, удастся собрать за N часов?  По условию размеры пакетов
известны.  С вероятностью 95% апостериорное время сборки не должно быть
больше $N+1$ часов, но и не меньше $N-1$.

Короче, имея на руках логи сборки пакетов и сами эти пакеты, вот как
примерно можно оценить регрессию.

size_time_regression()
{
	find "$@" -type f -print0 |xargs -r0 gzip -cdfq |
		LC_ALL=C awk 'NF==2 && /^Installing .*[.]src[.]rpm$/ { pkg=$2 }
			NF>4 && $1~/user$/ && $2~/system$/ && 
				$3~/elapsed$/ && $4~/CPU$/ {
					if (match($3, /^([0-9]+):([0-9]+[.][0-9]+)/, a))
						print pkg "\t" int(a[1]*60+a[2]+0.5) }' |
				sort -n -k2,2 |sort -u -k1,1 >buildtime
	while IFS=$'\t' read -r pkg time; do
		f="${sisyphus:-/raid/ALT/Sisyphus}"/files/SRPMS/"$pkg"
		if [ -s "$f" ]; then
			size="$(du -bk "$f" |cut -f1)"
			printf "%s\t%s\t%s\n" "$pkg" "$size" "$time"
		fi
	done <buildtime >buildsizetime
	cut -f2,3 buildsizetime >buildsizetime.dat
	R -q --no-save --no-restore <<'__EOF__' |tee R.output
	dat=read.table("buildsizetime.dat", col.names=c("size", "time"))
	summary(dat)
	library(boot)
	corr(dat)
	x=c(as.matrix(dat["size"]))
	y=c(as.matrix(dat["time"]))
	linear=lm(y~x); linear
	cat("coeff_a0=", linear$coefficients[1], "\n", sep="")
	cat("coeff_a1=", linear$coefficients[2], "\n", sep="")
	qx=quantile(x, probs=c(0.95,0.99)); qx
	cat("q95_size=", round(qx[1]), "\n", sep="")
	qy=quantile(y, probs=c(0.95,0.99)); qy
	cat("q95_time=", round(qy[1]), "\n", sep="")
__EOF__
	eval "$(grep -E '^(q95_size|q95_time|coeff_a.)=' R.output)"
	gnuplot <<__EOF__
	set terminal png size 1024,768
	set output "buildsizetime.png"
	set xtics 0, 1024
	set ytics 0, 60
	set xlabel "source package size, KB"
	set ylabel "build time, sec"
	plot [1:$q95_size] [1:$q95_time] "buildsizetime.dat", $coeff_a0+$coeff_a1*x
__EOF__
	gnuplot <<__EOF__
	set terminal png size 1024,768
	set output "buildsizetime2.png"
	set logscale xy 2
	set xlabel "source package size, KB"
	set ylabel "build time, sec"
	plot "buildsizetime.dat", $coeff_a0+$coeff_a1*x
__EOF__
	gqview -t buildsizetime.png buildsizetime2.png
}

Вот выдержка из вывода:

>       summary(dat)
      size             time
 Min.   :     2   Min.   :   0.00
 1st Qu.:    26   1st Qu.:   5.00
 Median :   141   Median :  10.00
 Mean   :  1196   Mean   :  43.54
 3rd Qu.:   541   3rd Qu.:  30.00
 Max.   :174291   Max.   :3260.00
>       library(boot)
>       corr(dat)
[1] 0.1951247
>       x=c(as.matrix(dat["size"]))
>       y=c(as.matrix(dat["time"]))
>       linear=lm(y~x); linear

Call:
lm(formula = y ~ x)

Coefficients:
(Intercept)            x
   37.61992      0.00495

>       cat("coeff_a0=", linear$coefficients[1], "\n", sep="")
coeff_a0=37.61992
>       cat("coeff_a1=", linear$coefficients[2], "\n", sep="")
coeff_a1=0.004950177
>       qx=quantile(x, probs=c(0.95,0.99)); qx
     95%      99%
 3904.80 17872.64
>       cat("q95_size=", round(qx[1]), "\n", sep="")
q95_size=3905
>       qy=quantile(y, probs=c(0.95,0.99)); qy
   95%    99%
150.20 562.28
>       cat("q95_time=", round(qy[1]), "\n", sep="")
q95_time=150

Рисунок приложен.  Легко видеть, что линейная регрессия не удалась.
То есть видно, что маленькие пакеты собираются быстро, а большие пакеты
могут собираться как быстро, так и медленно.  То есть имеется
специфическая автокрреляция.  Условия Гаусса-Маркова не выполняются,
поэтому наибольшее правдоподобие (в частности, МНК-регрессию) вообще
применять нельзя.

На этом идея заканчивается. :)

Положительное содержание: пакет можно персобрать в среднем менее чем за минуту.
Желающие могут построить доверительный интервал.  Суммарная девиация (СКО)
выборки уменьшается в $\frac1{\sqrt N}$ раз.
----------- следующая часть -----------
Было удалено вложение не в текстовом формате...
Имя     : buildsizetime.png
Тип     : image/png
Размер  : 15269 байтов
Описание: =?iso-8859-1?q?=CF=D4=D3=D5=D4=D3=D4=D7=D5=C5=D4?=
Url     : <http://lists.altlinux.org/pipermail/devel/attachments/20060602/4d87ae18/attachment-0001.png>
----------- следующая часть -----------
Было удалено вложение не в текстовом формате...
Имя     : =?iso-8859-1?q?=CF=D4=D3=D5=D4=D3=D4=D7=D5=C5=D4?=
Тип     : application/pgp-signature
Размер  : 191 байтов
Описание: =?iso-8859-1?q?=CF=D4=D3=D5=D4=D3=D4=D7=D5=C5=D4?=
Url     : <http://lists.altlinux.org/pipermail/devel/attachments/20060602/4d87ae18/attachment-0001.bin>