NetBSD-Bugs archive

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index][Old Index]

misc/55595: tests/usr.bin/make/t_make is quadratically slow

>Number:         55595
>Category:       misc
>Synopsis:       tests/usr.bin/make/t_make is quadratically slow
>Confidential:   no
>Severity:       serious
>Priority:       medium
>Responsible:    misc-bug-people
>State:          open
>Class:          sw-bug
>Submitter-Id:   net
>Arrival-Date:   Fri Aug 21 11:10:00 +0000 2020
>Originator:     Andreas Gustafsson
>Release:        NetBSD-current
System: NetBSD
Architecture: aarch64
Machine: evbarm

Since a recent increase in the number of test cases, the
tests/usr.bin/make/t_make test has become quite slow.  This is
especially noticeable when running it under qemu on an architecture
with a slow emulation, such as evbarm-aarch64 or sparc, and has been
causing some test runs to time out.

One reason for this appears to be that ATF exhibits O(N^2) time
complexity with respect to the number of test cases in a single test
program.  ATF invokes t_make (at least) once per test case, and each
invocation defines all the test cases in a loop.  With some 200 test
cases, this means the action of defining a test case is performed some
200^2 = 40,000 times.  Defining a test case involves forking a tr(1)
process to replace dashes in the test name by underscores, and each
tr(1) invocation takes on the order of 0.1 seconds on evbarm-aarch64
under qemu on, so just running the tr processes alone
takes more than an hour and accounts for much of the total run time.



I'm not sure what's the best way to fix this.  In the meantime, I will
increase timeouts in anita as a work-around.

Home | Main Index | Thread Index | Old Index