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

[gson%gson.org@localhost (Andreas Gustafsson)]

>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
>Organization:
>Environment:
System: NetBSD
Architecture: aarch64
Machine: evbarm
>Description:

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 lyta.netbsd.org, so just running the tr processes alone
takes more than an hour and accounts for much of the total run time.

>How-To-Repeat:

>Fix:

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.