From nobody Mon Aug 16 22:03:45 2021
X-Original-To: freebsd-hackers@mlmmj.nyi.freebsd.org
Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2610:1c1:1:606c::19:1])
	by mlmmj.nyi.freebsd.org (Postfix) with ESMTP id D391017687C6
	for <freebsd-hackers@mlmmj.nyi.freebsd.org>; Mon, 16 Aug 2021 22:03:55 +0000 (UTC)
	(envelope-from joerg@bec.de)
Received: from relay12.mail.gandi.net (relay12.mail.gandi.net [217.70.178.232])
	(using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits))
	(Client did not present a certificate)
	by mx1.freebsd.org (Postfix) with ESMTPS id 4GpSqG4tFlz3mLk
	for <freebsd-hackers@freebsd.org>; Mon, 16 Aug 2021 22:03:54 +0000 (UTC)
	(envelope-from joerg@bec.de)
Received: (Authenticated sender: joerg@bec.de)
	by relay12.mail.gandi.net (Postfix) with ESMTPSA id 5D127200002
	for <freebsd-hackers@freebsd.org>; Mon, 16 Aug 2021 22:03:47 +0000 (UTC)
Date: Tue, 17 Aug 2021 00:03:45 +0200
From: Joerg Sonnenberger <joerg@bec.de>
To: freebsd-hackers@freebsd.org
Subject: Re: sysctl is too slow
Message-ID: <YRre/rbq2INNYchk@bec.de>
Mail-Followup-To: freebsd-hackers@freebsd.org
References: <CAOtMX2h7xkDM=GsPVyiWNcqxfRo7euZuuquSMn-y=PY5zRZNjg@mail.gmail.com>
 <CAGudoHGxWBLW2D6JX8mQCPwgM=ngt+3uZmwxK5p7yM6XeXXjsQ@mail.gmail.com>
List-Id: Technical discussions relating to FreeBSD <freebsd-hackers.freebsd.org>
List-Archive: https://lists.freebsd.org/archives/freebsd-hackers
List-Help: <mailto:freebsd-hackers+help@freebsd.org>
List-Post: <mailto:freebsd-hackers@freebsd.org>
List-Subscribe: <mailto:freebsd-hackers+subscribe@freebsd.org>
List-Unsubscribe: <mailto:freebsd-hackers+unsubscribe@freebsd.org>
Sender: owner-freebsd-hackers@freebsd.org
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
In-Reply-To: <CAGudoHGxWBLW2D6JX8mQCPwgM=ngt+3uZmwxK5p7yM6XeXXjsQ@mail.gmail.com>
X-Rspamd-Queue-Id: 4GpSqG4tFlz3mLk
X-Spamd-Bar: /
Authentication-Results: mx1.freebsd.org;
	dkim=none;
	dmarc=none;
	spf=none (mx1.freebsd.org: domain of joerg@bec.de has no SPF policy when checking 217.70.178.232) smtp.mailfrom=joerg@bec.de
X-Spamd-Result: default: False [-0.20 / 15.00];
	 ARC_NA(0.00)[];
	 NEURAL_HAM_MEDIUM(-1.00)[-1.000];
	 FREEFALL_USER(0.00)[joerg];
	 FROM_HAS_DN(0.00)[];
	 TO_MATCH_ENVRCPT_ALL(0.00)[];
	 NEURAL_HAM_LONG(-1.00)[-1.000];
	 MIME_GOOD(-0.10)[text/plain];
	 PREVIOUSLY_DELIVERED(0.00)[freebsd-hackers@freebsd.org];
	 TO_DN_NONE(0.00)[];
	 AUTH_NA(1.00)[];
	 RCPT_COUNT_ONE(0.00)[1];
	 RCVD_IN_DNSWL_LOW(-0.10)[217.70.178.232:from];
	 DMARC_NA(0.00)[bec.de];
	 NEURAL_SPAM_SHORT(1.00)[0.997];
	 R_SPF_NA(0.00)[no SPF record];
	 RCVD_COUNT_ZERO(0.00)[0];
	 FROM_EQ_ENVFROM(0.00)[];
	 R_DKIM_NA(0.00)[];
	 MIME_TRACE(0.00)[0:+];
	 ASN(0.00)[asn:29169, ipnet:217.70.176.0/20, country:FR];
	 MID_RHS_MATCH_FROM(0.00)[];
	 RWL_MAILSPIKE_POSSIBLE(0.00)[217.70.178.232:from]
X-ThisMailContainsUnwantedMimeParts: N

On Mon, Aug 16, 2021 at 09:30:51PM +0200, Mateusz Guzik wrote:
> Last time I checked lookup of a sysctl was very bad with linear scans all over.
> 
> Short of complete revamp of the entire thing I would start with
> replacing the scans with a RB tree at each level. As is if you indeed
> have 5000 datasets, you are doing increasingly longer walks.

The RB tree is what NetBSD is doing. The alternative that might be
simpler is to have a flag bit in the node "child nodes are sorted" and
lazily apply a sort whenever the node is scanned first, dropping the
flag when new children are attached or detached. That would allow a
binary search without extra memory cost?

Joerg