Bug#492086: partman: menus are very slow

[John Reiser]

Subject: partman: menus are very slow
Package: debian-installer
Severity: wishlist

*** Please type your report below this line ***
The menus used by the partition manager during an install in low-memory mode
are very slow.  Several seconds elapse between <Enter> and the next menu.  This
is too long.  The delay should be 1/2 second or less, similar to the reponse
for choosing timezone (continent, country, zone) at the beginning of install.

Examining /lib/partman/lib/base.sh, the culprit is the intensive use of
constructs such as  "$(cat $dir/default_response)".  This takes way too long.

First, avoid searching for "cat" every time.  The default search tries:
   /usr/local/sbin/cat
   /usr/local/bin/cat
   /usr/sbin/cat
   /usr/bin/cat
   /sbin/cat
before finding /bin/cat.  Instead: use 'which' or 'type' to do the search once,
assign the result to a local variable, and expand the variable instead of
searching:
   CAT=$(which cat)
   $($CAT $dir/default_response)
Or, in nearly all cases the result is known ahead of time:
   CAT=/bin/cat

Second, use a shell builtin if possible:
   $(< $dir/default_response)
which is documented and works in bash.  The current version 0.5.4-11
of 'ash' does not complain, but also does not give the correct result.

Third, use shell text strings where possible:
   PM':'$dir':'default_response=$( ... )   # capture value as text
   $PM':'$dir':'default_response   # expand text variable
This is a good candidate for the fastest possible method, although it looks
ugly.

-- System Information:
Debian Release: lenny/sid
  APT prefers unstable
  APT policy: (500, 'unstable'), (500, 'testing')
Architecture: armel (armv5tel)

Kernel: Linux 2.6.25-2-ixp4xx
Locale: LANG=C, LC_CTYPE=C (charmap=ANSI_X3.4-1968)
Shell: /bin/sh linked to /bin/bash

--



--
To UNSUBSCRIBE, email to debian-bugs-dist-REQUEST@...
with a subject of "unsubscribe". Trouble? Contact listmaster@...

[Jérémy Bobbio-2]

On Wed, Jul 23, 2008 at 10:31:12AM -0700, John Reiser wrote:
> The menus used by the partition manager during an install in low-memory mode
> are very slow.  Several seconds elapse between <Enter> and the next menu.  This
> is too long.  The delay should be 1/2 second or less, similar to the reponse
> for choosing timezone (continent, country, zone) at the beginning of install.

I agree with the fact that partman currently feels a little bit
sluggish, even on not that old hardware.

Various improvements could probably be done, but we need people willing
to work on that.  Those changes would need to wait until the release of
Lenny though.

Cheers,
--
Jérémy Bobbio                        .''`.
lunar@...                    : :Ⓐ  :  # apt-get install anarchism
                                    `. `'`
                                      `-  

[Frans Pop-3]

On Wednesday 23 July 2008, Jérémy Bobbio wrote:

> On Wed, Jul 23, 2008 at 10:31:12AM -0700, John Reiser wrote:
> > The menus used by the partition manager during an install in
> > low-memory mode are very slow.  Several seconds elapse between
> > <Enter> and the next menu.  This is too long.  The delay should be
> > 1/2 second or less, similar to the reponse for choosing timezone
> > (continent, country, zone) at the beginning of install.
>
> Various improvements could probably be done, but we need people willing
> to work on that.  Those changes would need to wait until the release of
> Lenny though.

Actually, I think that using an environment variable for 'cat' would be
quite low risk. After all, we _know_ that all partman scripts are
executed under the main partman script (called from the postinst).

So, adding the following in partman-base/partman should ensure it can be
safely used anywhere else in partman:
    cmdCAT=$(type -P cat 2>/dev/null) || \
        cmdCAT=$(which cat 2>/dev/null) || exit 1
    export cmdCAT

- 'which' is not available in busybox (main use case), but 'type -P'
  produces same result and works in busybox and bash (but not dash)
- fallback to 'which' should ensure compatibility in other environments
  (Ubuntu?), even if other shells are used
- immediately fails on error
- I've chosen cmdCAT instead of just CAT to make it extremely unlikely
  that we'd conflict with existing envvars in any scripts/programs that
  are called (even outside partman itself)

Attached an example patch for partman-base/lib/base.sh. Note that I did
not replace all uses of 'cat' but basically only where it is used to get
info from files in /var/lib/partman/devices. IMO it should be limited to
that usage (which needs to be documented).

Doing similar patches for other scripts that are known to be called often
(update.d, display.d, check.d, active-partition, some sourced lib
scripts) or take relatively long due to looping (commit.d, finish.d,
recipe calculation in partman-auto) should be trivial.

As long as partman-base is uploaded first there should be no problems with
transition.

Main question is how much we would gain in practice from making just this
change. It would really need to be significant to make it worth doing for
Lenny.

The other options John proposes IMO carry to much risk of
incompatibilities between environments or make the code to obscure.

Cheers,
FJP


[attachment removed]

[Joey Hess]

There is already discussion about how to speed up partman elsewhere in
the BTS.

Minor shell efficiency tricks are not going to help much. It forks
*thousands* of processes per menu.

--
see shy jo

[Joey Hess]

John Reiser wrote:

> First, avoid searching for "cat" every time.  The default search tries:
>    /usr/local/sbin/cat
>    /usr/local/bin/cat
>    /usr/sbin/cat
>    /usr/bin/cat
>    /sbin/cat
> before finding /bin/cat.  Instead: use 'which' or 'type' to do the search once,
> assign the result to a local variable, and expand the variable instead of
> searching:
>    CAT=$(which cat)
>    $($CAT $dir/default_response)
> Or, in nearly all cases the result is known ahead of time:
>    CAT=/bin/cat

So the question is, how much system time do the following failing system calls
actually take, when multiplied by the number of calls to "cat" made in
the lifetime of partman:

joey@kodama:~>PATH=/usr/local/sbin:/usr/local/bin:/usr/sbin:/usr/bin:/sbin:/bin strace -f busybox sh -c 'cat /dev/null' 2>&1 |grep execv
[pid 32292] execve("/usr/local/sbin/cat", ["cat", "/dev/null"], [/* 45 vars */]) = -1 ENOENT (No such file or directory)
[pid 32292] execve("/usr/local/bin/cat", ["cat", "/dev/null"], [/* 45 vars */]) = -1 ENOENT (No such file or directory)
[pid 32292] execve("/usr/sbin/cat", ["cat", "/dev/null"], [/* 45 vars */]) = -1 ENOENT (No such file or directory)
[pid 32292] execve("/usr/bin/cat", ["cat", "/dev/null"], [/* 45 vars */]) = -1 ENOENT (No such file or directory)
[pid 32292] execve("/sbin/cat", ["cat", "/dev/null"], [/* 45 vars */]) = -1 ENOENT (No such file or directory)
[pid 32292] execve("/bin/cat", ["cat", "/dev/null"], [/* 45 vars */]) = 0

We can use a small C program to time an arbitrary number of failing exec's:

joey@kodama:~>cat foo.c
main () {
        int i;
        for (i=0; i < 100000; i++)
                execve("/no/such/path/to/cat", 0);
}

joey@kodama:~>make foo
make: `foo' is up to date.
joey@kodama:~>time ./foo
Command exited with non-zero status 255
0.01user 0.23system 0:00.27elapsed 90%CPU (0avgtext+0avgdata 0maxresident)k

So, for 1 second of time to be used searching the PATH for it, d-i would
have to run cat 70000 times on modern hardware (the nslu2 is of course
~ 500 times slower). OTOH, actually running cat, as opposed to searching
for it, takes much much more time.. The same hardware can only run cat
1500 times per second.

Conclusion 1: System calls are much much faster than you'd think. Except that
successfully doing a fork+exec is slow.

Conclusion 2: Benchmark before optimising. In this case, trying to
optimise away the wrong system calls is a waste of time.

PS: Reordering PATH to put /usr/bin first and omit /usr/local/bin would
    be the easy way to optimise this, IF searching the path were actually
    a significant time sink. However, it does not appear to be.

PPS: Actually _eliminating_ calls to cat and other binaries in partman would
     of course help. A partman written in C should be 100 to 1000 times as
     fast as the current one.

--
see shy jo

[John Reiser]

Joey Hess wrote:

> Conclusion 2: Benchmark before optimising. In this case, trying to
> optimise away the wrong system calls is a waste of time.

The benchmark code and measurements [snipped] are not a good comparison
with the actual environment of low-memory mode.  In particular, the use of
swap space is likely in low memory mode, but almost certainly not present
in the measurements reported above.  Any actual use of swap space (or paging)
will tend to increase the delay, and increase the relative advantage
of avoiding fruitless searching.

> PS: Reordering PATH to put /usr/bin first and omit /usr/local/bin would
>     be the easy way to optimise this, IF searching the path were actually
>     a significant time sink. However, it does not appear to be.

It takes a minute or so to change partman by adding something such as
"export PATH=/bin".  If the searching in partman becomes faster by >= 0.2
second per run, and if partman is run some thousands of times in the future
life of the installer, then that is a net savings, and not a waste.  Perhaps
the intended claim was, "I'd rather spend my time doing something with a
larger payoff."  So would the humans who use partman.

Consider this shell code:
-----
PATH=/usr/local/sbin:/usr/local/bin:/usr/sbin:/usr/bin:/sbin:/binPATH=/bin \
busybox sh -c '
  for i in 0 1 2 3 4 5 6 7 8 9
  do
    for j in 0 1 2 3 4 5 6 7 8 9
    do
      for k in 0 1 2 3 4 5 6 7 8 9
      do
        cat /dev/null
      done
    done
  done
'
----
which runs in 22.2 seconds on my NSLU2 for 1000 executions of "cat /dev/null"
in an environment much more similar to real partman than previous benchmarks.
Changing to "PATH=/bin " runs in 21.5 seconds, which is 0.7 seconds faster.
Altering the search path does achieve measured savings.

> PPS: Actually _eliminating_ calls to cat and other binaries in partman would
>      of course help. A partman written in C should be 100 to 1000 times as
>      fast as the current one.

The original bug report contains two further paragraphs which give specific ways
to avoid fork+exec:
   Second, use a shell builtin if possible.  [ $(< file) ]
   Third, use shell text strings where possible.
      [ PM':'$dir':'default_response=$( ... ) ]
"$(< file)" turns out not to work on various shells other than bash.
The use of non-literal variables was panned by Frans Pop as being too obscure,
although there are projects which use them.  [Look at libtool to see some
mind-boggling obscurity in shell programming.]

However, there is another shell builtin which does input without fork+exec,
namely 'read'.  If the replies are restricted to be only one line, then:
   read  < $dir/default_response
   default_response="$REPLY"
achieves the same effect as
   default_response=$(cat $dir/default_response)
but without requiring fork+exec.  So 'read' looks like a promising replacement.

--



--
To UNSUBSCRIBE, email to debian-bugs-dist-REQUEST@...
with a subject of "unsubscribe". Trouble? Contact listmaster@...

[Joey Hess]

John Reiser wrote:
> The benchmark code and measurements [snipped] are not a good comparison
> with the actual environment of low-memory mode.  In particular, the use of
> swap space is likely in low memory mode, but almost certainly not present
> in the measurements reported above.  Any actual use of swap space (or paging)
> will tend to increase the delay, and increase the relative advantage
> of avoiding fruitless searching.

Partman runs before swap is available. Also, the kernel is unlikely to
ever swap out its filesystem cache and syscall handlers.

> It takes a minute or so to change partman by adding something such as
> "export PATH=/bin".  If the searching in partman becomes faster by >= 0.2
> second per run, and if partman is run some thousands of times in the future
> life of the installer, then that is a net savings, and not a waste.  Perhaps
> the intended claim was, "I'd rather spend my time doing something with a
> larger payoff."  So would the humans who use partman.

No, my point is that it's pointless to nibble away at optimising
something in 1% increments. Instead find the actual large timesinks, and
optimise those. Also, work with real-world numbers, not guesses.

(BTW, I forgot to CC you, but AFAICS your numbers in #492077 are off by
several orders of magnitude.)

> Consider this shell code:
> which runs in 22.2 seconds on my NSLU2 for 1000 executions of "cat /dev/null"
> in an environment much more similar to real partman than previous benchmarks.
> Changing to "PATH=/bin " runs in 21.5 seconds, which is 0.7 seconds faster.
> Altering the search path does achieve measured savings.

Actually, the result is similar to that of my C-based tests. I
measured an added 0.000014 seconds per cat invocation due to PATH;
on the same hardware with your test I get a value of 0.000020.

> The original bug report contains two further paragraphs which give specific ways
> to avoid fork+exec:
>    Second, use a shell builtin if possible.  [ $(< file) ]
>    Third, use shell text strings where possible.
>       [ PM':'$dir':'default_response=$( ... ) ]
> "$(< file)" turns out not to work on various shells other than bash.
> The use of non-literal variables was panned by Frans Pop as being too obscure,
> although there are projects which use them.  [Look at libtool to see some
> mind-boggling obscurity in shell programming.]
>
> However, there is another shell builtin which does input without fork+exec,
> namely 'read'.  If the replies are restricted to be only one line, then:
>    read  < $dir/default_response
>    default_response="$REPLY"
> achieves the same effect as
>    default_response=$(cat $dir/default_response)
> but without requiring fork+exec.  So 'read' looks like a promising replacement.

Or one could teach busybox shell to jump to the in-busybox
implementations of cat and all other busybox commands, thereby
eliminating every exec in partman except for those needed to run
subshells. (It'd still have to fork, but linux can fork very fast, and
most shell tricks above involve a fork due to the use of subshells.)

--
see shy jo

[John Reiser]

Joey Hess wrote:

>>Consider this shell code:
>>which runs in 22.2 seconds on my NSLU2 for 1000 executions of "cat /dev/null"
>>in an environment much more similar to real partman than previous benchmarks.
>>Changing to "PATH=/bin " runs in 21.5 seconds, which is 0.7 seconds faster.
>>Altering the search path does achieve measured savings.
>
>
> Actually, the result is similar to that of my C-based tests. I
> measured an added 0.000014 seconds per cat invocation due to PATH;
> on the same hardware with your test I get a value of 0.000020.

I'm glad that you agree, because my results show that changing $PATH is
a 3.2% improvement for an environment quite similar to partman:
     ((22.2 - 21.5) / 22.2) = 0.0315
This is not "orders of magnitude" away from reality.
An speed improvement of 3.2% for very low implementation cost
is a much better than no improvement at all.

> Or one could teach busybox shell to jump to the in-busybox
> implementations of cat and all other busybox commands, thereby
> eliminating every exec in partman except for those needed to run
> subshells. (It'd still have to fork, but linux can fork very fast, and
> most shell tricks above involve a fork due to the use of subshells.)

There was a "Hamilton C shell" for OS/2 that used builtin versions
of cat, cp, mv, ln, etc.  That shell ran rings around any other
with respect to execution speed of the typical shell script.


Partman runs very slowly.  It reflects poorly on debian-installer.
There are two implementable ideas that avoid fork+exec without requiring
a near-total re-implementation: non-literal variables, and 'read'.
"$(< file)" might be fixable in ash.  The bash shell directly supports
text menus with
     select name [ in word ] ; do list ; done
which apparently is not yet so portable to other shells.

Action, anybody?

--



--
To UNSUBSCRIBE, email to debian-bugs-dist-REQUEST@...
with a subject of "unsubscribe". Trouble? Contact listmaster@...

[Joey Hess]

John Reiser wrote:
> Partman runs very slowly.  It reflects poorly on debian-installer.

Humans percieve interactive things as "slow" if they take longer than
approximatly 0.1 seconds to respond. Increasing the speed of partman by
less than 50% is not going to yield a difference that is percievable to
humans. "slow" == "slow".

> There are two implementable ideas that avoid fork+exec without requiring
> a near-total re-implementation: non-literal variables, and 'read'.

I mentioned a third one, that's easier to implement and test than either
of those (only needs a small modification to busybox, which already has
an option that does something very similar). Once someone has actually
implemented and tested it, or any other optimisation idea against the
actual code, and has actual numbers, we could think about actually applying
that optimisation.

--
see shy jo

[Jérémy Bobbio-2]

On Thu, Jul 24, 2008 at 07:28:41PM -0400, Joey Hess wrote:
> Or one could teach busybox shell to jump to the in-busybox
> implementations of cat and all other busybox commands, thereby
> eliminating every exec in partman except for those needed to run
> subshells. (It'd still have to fork, but linux can fork very fast, and
> most shell tricks above involve a fork due to the use of subshells.)

Just for the record, it seems that busybox upstream is working on that:

config FEATURE_SH_NOFORK
        bool "Run 'nofork' applets directly"
        default n
        depends on (MSH || LASH || HUSH || ASH) && FEATURE_PREFER_APPLETS
        help
          This option causes busybox shells [currently only ash]
          to not execute typical fork/exec/wait sequence, but call <applet>_main
          directly, if possible. (Sometimes it is not possible: for example,
          this is not possible in pipes).

          This will be done only for some applets (those which are marked
          NOFORK in include/applets.h).

          This may significantly speed up some shell scripts.

          This feature is relatively new. Use with care.

It seems to have been added in busybox 1.11.

Cheers,
--
Jérémy Bobbio                        .''`.
lunar@...                    : :Ⓐ  :  # apt-get install anarchism
                                    `. `'`
                                      `-  

[John Reiser]

Here are the code and the measurements.

partman/lib/base.sh currently uses statements such as:
    template=$(cat $dir/question)
As reported before, with the long default
    PATH=/usr/local/sbin:/usr/local/bin:/usr/sbin:/usr/bin:/sbin:/bin
then current busybox sh using both fork() and execve() runs
    cat /dev/null
for 1000 iterations in 22.2 seconds on unmodified armel-eabi NSLU2
(133MHz armv5te.)

Changing to the the modified short PATH=/bin , then 1000 iterations
take 21.5 seconds.

Changing tryexec()/shell/ash.c to use only fork() and no execve()
[verified using strace]:
-----
        struct BB_applet const *app = (struct BB_applet const *)find_applet_by_name(cmd);
        int argc = 0;
        {
                char **p;
                for (p = argv; *p; ++p)
                        ++argc;
        }
        if (app) {
                __environ = envp;
                exit(app->main(argc, argv));
        }
-----
runs 1000 iterations of the builtin applet
    cat /dev/null
in 12.7 seconds.

The syntax for busybox sh to replace
    template=$(cat $dir/question)
is
    read template  < $dir/question
Then 1000 iterations of
    read line  < /dev/null
takes 0.66 seconds.  [Thus fork() is almost as slow as execve()
when measured in the busybox sh environment.]

So, avoiding both fork+execve is faster by an order of magnitude
than using fork and avoiding only execve.  Avoiding both fork+exec
also bounds the required testing, because only partman is affected,
and not everything else that uses busybox sh.

Some d-i developer probably could edit partman/lib/base.sh to use 'read'
instead of 'cat', test it, and report the results in less than a day.
I got lost in debian-installer-20080522/build/README.

--



--
To UNSUBSCRIBE, email to debian-bugs-dist-REQUEST@...
with a subject of "unsubscribe". Trouble? Contact listmaster@...