From owner-dev-commits-src-all@freebsd.org Fri Apr 2 02:46:43 2021 Return-Path: Delivered-To: dev-commits-src-all@mailman.nyi.freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2610:1c1:1:606c::19:1]) by mailman.nyi.freebsd.org (Postfix) with ESMTP id 34C295BF5B9; Fri, 2 Apr 2021 02:46:43 +0000 (UTC) (envelope-from git@FreeBSD.org) Received: from mxrelay.nyi.freebsd.org (mxrelay.nyi.freebsd.org [IPv6:2610:1c1:1:606c::19:3]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (4096 bits) server-digest SHA256 client-signature RSA-PSS (4096 bits) client-digest SHA256) (Client CN "mxrelay.nyi.freebsd.org", Issuer "R3" (verified OK)) by mx1.freebsd.org (Postfix) with ESMTPS id 4FBPZq130xz3RFB; Fri, 2 Apr 2021 02:46:43 +0000 (UTC) (envelope-from git@FreeBSD.org) Received: from gitrepo.freebsd.org (gitrepo.freebsd.org [IPv6:2610:1c1:1:6068::e6a:5]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (4096 bits) server-digest SHA256) (Client did not present a certificate) by mxrelay.nyi.freebsd.org (Postfix) with ESMTPS id 1692C18780; Fri, 2 Apr 2021 02:46:43 +0000 (UTC) (envelope-from git@FreeBSD.org) Received: from gitrepo.freebsd.org ([127.0.1.44]) by gitrepo.freebsd.org (8.16.1/8.16.1) with ESMTP id 1322kg0p017796; Fri, 2 Apr 2021 02:46:42 GMT (envelope-from git@gitrepo.freebsd.org) Received: (from git@localhost) by gitrepo.freebsd.org (8.16.1/8.16.1/Submit) id 1322kgH5017795; Fri, 2 Apr 2021 02:46:42 GMT (envelope-from git) Date: Fri, 2 Apr 2021 02:46:42 GMT Message-Id: <202104020246.1322kgH5017795@gitrepo.freebsd.org> To: src-committers@FreeBSD.org, dev-commits-src-all@FreeBSD.org, dev-commits-src-branches@FreeBSD.org From: Lawrence Stewart Subject: git: 9141b58b50a8 - stable/13 - stats(3): Improve t-digest merging of samples which result in mu adjustment underflow. MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: 8bit X-Git-Committer: lstewart X-Git-Repository: src X-Git-Refname: refs/heads/stable/13 X-Git-Reftype: branch X-Git-Commit: 9141b58b50a86a94667a79f221dcba59240ce3f4 Auto-Submitted: auto-generated X-BeenThere: dev-commits-src-all@freebsd.org X-Mailman-Version: 2.1.34 Precedence: list List-Id: Commit messages for all branches of the src repository List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Fri, 02 Apr 2021 02:46:43 -0000 The branch stable/13 has been updated by lstewart: URL: https://cgit.FreeBSD.org/src/commit/?id=9141b58b50a86a94667a79f221dcba59240ce3f4 commit 9141b58b50a86a94667a79f221dcba59240ce3f4 Author: Lawrence Stewart AuthorDate: 2021-04-02 01:29:29 +0000 Commit: Lawrence Stewart CommitDate: 2021-04-02 02:29:55 +0000 stats(3): Improve t-digest merging of samples which result in mu adjustment underflow. Allow the calculation of the mu adjustment factor to underflow instead of rejecting the VOI sample from the digest and logging an error. This trades off some (currently unquantified) additional centroid error in exchange for better fidelity of the distribution's density, which is the right trade off at the moment until follow up work to better handle and track accumulated error can be undertaken. Obtained from: Netflix MFC after: immediately (cherry picked from commit 1eb402e47af35b3980e6bd51ec462de3a3faa2c8) --- sys/kern/subr_stats.c | 38 ++++++++++++++++++++++++++++++++++++-- 1 file changed, 36 insertions(+), 2 deletions(-) diff --git a/sys/kern/subr_stats.c b/sys/kern/subr_stats.c index 9dd874fcbcf8..946999263898 100644 --- a/sys/kern/subr_stats.c +++ b/sys/kern/subr_stats.c @@ -3255,9 +3255,41 @@ stats_v1_vsd_tdgst_add(enum vsd_dtype vs_dtype, struct voistatdata_tdgst *tdgst, if (is32bit) { ctd32 = (struct voistatdata_tdgstctd32 *)closest; error = Q_QSUBQ(&x, ctd32->mu); + /* + * The following calculation "x / (cnt + weight)" + * computes the amount by which to adjust the centroid's + * mu value in order to merge in the VOI sample. + * + * It can underflow (Q_QDIVI() returns ERANGE) when the + * user centroids' fractional precision (which is + * inherited by 'x') is too low to represent the result. + * + * A sophisticated approach to dealing with this issue + * would minimise accumulation of error by tracking + * underflow per centroid and making an adjustment when + * a LSB's worth of underflow has accumulated. + * + * A simpler approach is to let the result underflow + * i.e. merge the VOI sample into the centroid without + * adjusting the centroid's mu, and rely on the user to + * specify their t-digest with sufficient centroid + * fractional precision such that the accumulation of + * error from multiple underflows is of no material + * consequence to the centroid's final value of mu. + * + * For the moment, the latter approach is employed by + * simply ignoring ERANGE here. + * + * XXXLAS: Per-centroid underflow tracking is likely too + * onerous, but it probably makes sense to accumulate a + * single underflow error variable across all centroids + * and report it as part of the digest to provide + * additional visibility into the digest's fidelity. + */ error = error ? error : Q_QDIVI(&x, ctd32->cnt + weight); - if (error || (error = Q_QADDQ(&ctd32->mu, x))) { + if ((error && error != ERANGE) + || (error = Q_QADDQ(&ctd32->mu, x))) { #ifdef DIAGNOSTIC KASSERT(!error, ("%s: unexpected error %d", __func__, error)); @@ -3276,7 +3308,9 @@ stats_v1_vsd_tdgst_add(enum vsd_dtype vs_dtype, struct voistatdata_tdgst *tdgst, error = Q_QSUBQ(&x, ctd64->mu); error = error ? error : Q_QDIVI(&x, ctd64->cnt + weight); - if (error || (error = Q_QADDQ(&ctd64->mu, x))) { + /* Refer to is32bit ERANGE discussion above. */ + if ((error && error != ERANGE) + || (error = Q_QADDQ(&ctd64->mu, x))) { KASSERT(!error, ("%s: unexpected error %d", __func__, error)); return (error);