NetBSD Problem Report #55595

From gson@gson.org  Fri Aug 21 11:07:11 2020
Return-Path: <gson@gson.org>
Received: from mail.netbsd.org (mail.netbsd.org [199.233.217.200])
	(using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits))
	(Client CN "mail.NetBSD.org", Issuer "mail.NetBSD.org CA" (not verified))
	by mollari.NetBSD.org (Postfix) with ESMTPS id ADEE71A923D
	for <gnats-bugs@gnats.NetBSD.org>; Fri, 21 Aug 2020 11:07:11 +0000 (UTC)
Message-Id: <20200821110706.DDA4C253EDF@guava.gson.org>
Date: Fri, 21 Aug 2020 14:07:06 +0300 (EEST)
From: gson@gson.org (Andreas Gustafsson)
Reply-To: gson@gson.org (Andreas Gustafsson)
To: gnats-bugs@NetBSD.org
Subject: tests/usr.bin/make/t_make is quadratically slow
X-Send-Pr-Version: 3.95

>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:          closed
>Class:          sw-bug
>Submitter-Id:   net
>Arrival-Date:   Fri Aug 21 11:10:00 +0000 2020
>Closed-Date:    Sun Oct 04 11:25:00 +0000 2020
>Last-Modified:  Sun Oct 04 11:25: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.

>Release-Note:

>Audit-Trail:
From: "Robert Elz" <kre@netbsd.org>
To: gnats-bugs@gnats.NetBSD.org
Cc: 
Subject: PR/55595 CVS commit: src/tests/usr.bin/make
Date: Thu, 10 Sep 2020 17:33:17 +0000

 Module Name:	src
 Committed By:	kre
 Date:		Thu Sep 10 17:33:17 UTC 2020

 Modified Files:
 	src/tests/usr.bin/make: t_make.sh

 Log Message:
 Replace use of tr to translate '-' in test names into '_' to satisfy ATF
 requirements (correct sh variable/function name syntax).  Use a sh
 loop instead, and save one fork() one vfork() and one exec of tr for
 each test case (many of which don't need anything done to them at all).

 This might partially mitigate PR misc/55595


 To generate a diff of this commit:
 cvs rdiff -u -r1.9 -r1.10 src/tests/usr.bin/make/t_make.sh

 Please note that diffs are not public domain; they are subject to the
 copyright notices on the relevant files.

From: Andreas Gustafsson <gson@gson.org>
To: "Robert Elz" <kre@netbsd.org>
Cc: gnats-bugs@netbsd.org
Subject: Re: PR/55595 CVS commit: src/tests/usr.bin/make
Date: Sun, 4 Oct 2020 14:08:15 +0300

 On Sep 10, Robert Elz committed:
 >  Modified Files:
 >  	src/tests/usr.bin/make: t_make.sh
 >  
 >  Log Message:
 >  Replace use of tr to translate '-' in test names into '_' to satisfy ATF
 >  requirements (correct sh variable/function name syntax).  Use a sh
 >  loop instead, and save one fork() one vfork() and one exec of tr for
 >  each test case (many of which don't need anything done to them at all).
 >  
 >  This might partially mitigate PR misc/55595
 >  
 >  
 >  To generate a diff of this commit:
 >  cvs rdiff -u -r1.9 -r1.10 src/tests/usr.bin/make/t_make.sh

 Thanks.  On the TNF evbarm-aarch64 testbed, this speeded up the t_make
 test by more than a factor of 10, from 17441 seconds to 1590 seconds,
 dropping it from number 1 to number 10 on the list of tests taking the
 longest to run.  I think this is good enough that the PR can be
 closed.  If the number of test cases grows enough to again make this a
 major problem, the PR can be reopened.
 -- 
 Andreas Gustafsson, gson@gson.org

State-Changed-From-To: open->closed
State-Changed-By: gson@NetBSD.org
State-Changed-When: Sun, 04 Oct 2020 11:25:00 +0000
State-Changed-Why:
Good enough for now.


>Unformatted:

NetBSD Home
NetBSD PR Database Search

(Contact us) $NetBSD: query-full-pr,v 1.46 2020/01/03 16:35:01 leot Exp $
$NetBSD: gnats_config.sh,v 1.9 2014/08/02 14:16:04 spz Exp $
Copyright © 1994-2020 The NetBSD Foundation, Inc. ALL RIGHTS RESERVED.