История изменений

Исправление SZT, 13.08.15 23:45 (текущая версия) :

Кстати, раз уж говорить об оптимизации кода, то там много мест, которые можно переделать. Вот взять например оттуда же

http://lxr.free-electrons.com/source/kernel/groups.c#L104

109         for (stride = 1; stride < gidsetsize; stride = 3 * stride + 1)
110                 ; /* nothing */
111         stride /= 3;

особенность таких циклов (внутри нифига толком не делается, только меняются переменные) в том, что их можно заоптимизировать через плавучку, воспользовавшись реккурентным соотношением:

stride(1) = 1;
stride(n) = 3 * stride(n-1) + 1

Решаем через maxima:

(%i1) display2d:false$

(%i2) load(solve_rec)$

(%i3) solve_rec(stride[n]=3*stride[n-1]+1, stride[n], stride[1]=1);

(%o3) stride[n] = 3^n/2-1/2

Теперь надо найти такой n для stride(n), чтобы stride(n) = gidsetsize;

(%i4) solve ([3^n/2-1/2=x], [n]);

(%o4) [n = log(2*x+1)/log(3)]

Записываем получившиеся формулы через double. Сначала находим n (оно скорее всего получится нецелым) Получаем целую часть часть через http://www.cplusplus.com/reference/cmath/modf/ и считаем ей по формуле 3^n/2-1/2. Думаю что точности double вполне должно хватить. На всякий случай можно сравнить выдаваемые через вычисления по формулам значения с вычислением через цикл на всем интервале допустимых значений.

Таким образом можно сократить много всяких примитивных циклов, но что-то я сомневаюсь что такой патч будет принят разрабами ядра

Исходная версия SZT, 13.08.15 23:43:

http://lxr.free-electrons.com/source/kernel/groups.c#L104

109         for (stride = 1; stride < gidsetsize; stride = 3 * stride + 1)
110                 ; /* nothing */
111         stride /= 3;

stride(1) = 1;
stride(n) = 3 * stride(n-1) + 1


Решаем через maxima:

(%i1) display2d:false$

(%i2) load(solve_rec)$

(%i3) solve_rec(stride[n]=3*stride[n-1]+1, stride[n], stride[1]=1);

(%o3) stride[n] = 3^n/2-1/2

Теперь надо найти такой n для stride(n), чтобы stride(n) = gidsetsize;

(%i4) solve ([3^n/2-1/2=x], [n]);

(%o4) [n = log(2*x+1)/log(3)]