From owner-freebsd-current@freebsd.org Sun Jul 10 12:44:33 2016 Return-Path: Delivered-To: freebsd-current@mailman.ysv.freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2001:1900:2254:206a::19:1]) by mailman.ysv.freebsd.org (Postfix) with ESMTP id 76D7CB84490 for ; Sun, 10 Jul 2016 12:44:33 +0000 (UTC) (envelope-from mjguzik@gmail.com) Received: from mail-wm0-x231.google.com (mail-wm0-x231.google.com [IPv6:2a00:1450:400c:c09::231]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (Client CN "smtp.gmail.com", Issuer "Google Internet Authority G2" (verified OK)) by mx1.freebsd.org (Postfix) with ESMTPS id 098D11542 for ; Sun, 10 Jul 2016 12:44:33 +0000 (UTC) (envelope-from mjguzik@gmail.com) Received: by mail-wm0-x231.google.com with SMTP id f126so62841787wma.1 for ; Sun, 10 Jul 2016 05:44:32 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=date:from:to:cc:subject:message-id:mail-followup-to:references :mime-version:content-disposition:in-reply-to:user-agent; bh=/UEUPfdUTju9jUbTL4cWmyeK3I/3/Wjze0Amjs/O4To=; b=IJN4VSPcVRi9kyVr/wv9njpUUGFwLy3VRrtbTmlZBANymZEfD1fvYhNbq0YJvMG0Ic x6R0anL8o9Uaaa+Mkx5x7AsPQjJqRoi6yLSvSk0TO5yqkUrMCHTFlTXCE++DEejkJd3v QFJ29tDth/eTvO9HqSc36ee29yIEXJe0jSvm2IHPcpSZbscf9BzqQmqkdUlPtp7dZsgN xhUWTnnI5lE1o6on4WyxM+HSkUI1/1mGCA2gNR5ll1LYAm+XBCS0fnfj52ciMK8743ko 4DF3zbshdZPih3Ccp+vxuB/Hvmxkjd/egk15hscY2DASIP9CGzM5fVFGGPzxBekr+72Q HbGQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:date:from:to:cc:subject:message-id :mail-followup-to:references:mime-version:content-disposition :in-reply-to:user-agent; bh=/UEUPfdUTju9jUbTL4cWmyeK3I/3/Wjze0Amjs/O4To=; b=FOKnBkfqCa8gFC0KJfrozQhj86ip5Fp3egUUSGGBCZ4BwfsAuI7BY2JFTHsr5tqpaV 6WafUoUBtLp++cZ7T8eiKHdGO3mJH80yPB0JIxzgJ+JqdZkHVsHgCVVoK/s9NPaEtNvC oM3sv5VbqFvik4qnv8LR/9jIjM2AjfcRjCA7nVlRg2lcntAcTZ4aktDkRwUD5sCBHdo+ jCXp/YTRnFC8txquZRoh4UMRIyqJ1P3jUGDyzUToRATWwhkx0Gz/egaTCjLsm8EAAFcr Se395Kqw/SJq2kBcYP4Hl0zQnl/pbGzLIgPCl/a5JS1bx8F6h1+84hqa1CfMpPjL3X8S 3YWQ== X-Gm-Message-State: ALyK8tJIqDKBeeOc33L86vhhj7rqG2uL9pJ3jNZszD5ZPdQGliV1rh+YGA9bMNZB8BDK/w== X-Received: by 10.28.212.211 with SMTP id l202mr12251809wmg.6.1468154671472; Sun, 10 Jul 2016 05:44:31 -0700 (PDT) Received: from dft-labs.eu (n1x0n-1-pt.tunnel.tserv5.lon1.ipv6.he.net. [2001:470:1f08:1f7::2]) by smtp.gmail.com with ESMTPSA id z5sm4144863wme.5.2016.07.10.05.44.30 (version=TLS1_2 cipher=AES128-SHA bits=128/128); Sun, 10 Jul 2016 05:44:30 -0700 (PDT) Date: Sun, 10 Jul 2016 14:44:28 +0200 From: Mateusz Guzik To: Konstantin Belousov Cc: freebsd-current@freebsd.org Subject: Re: [PATCH] microoptimize locking primitives by introducing randomized delay between atomic ops Message-ID: <20160710124428.GB7853@dft-labs.eu> Mail-Followup-To: Mateusz Guzik , Konstantin Belousov , freebsd-current@freebsd.org References: <20160710111326.GA7853@dft-labs.eu> <20160710122247.GS38613@kib.kiev.ua> MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Disposition: inline In-Reply-To: <20160710122247.GS38613@kib.kiev.ua> User-Agent: Mutt/1.5.21 (2010-09-15) X-BeenThere: freebsd-current@freebsd.org X-Mailman-Version: 2.1.22 Precedence: list List-Id: Discussions about the use of FreeBSD-current List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Sun, 10 Jul 2016 12:44:33 -0000 On Sun, Jul 10, 2016 at 03:22:47PM +0300, Konstantin Belousov wrote: > On Sun, Jul 10, 2016 at 01:13:26PM +0200, Mateusz Guzik wrote: > > If the lock is contended, primitives like __mtx_lock_sleep will spin > > checking if the owner is running or the lock was freed. The problem is > > that once it is discovered that the lock is free, multiple CPUs are > > likely to try to do the atomic op which will make it more costly for > > everyone and throughput suffers. > > > > The standard thing to do is to have some sort of a randomized delay so > > that this kind of behaviour is reduced. > > > > As such, below is a trivial hack which takes cpu_ticks() into account > > and performs % 2048, which in my testing gives reasonbly good results. > > > > Please note there is definitely way more room for improvement in general. > > > > In terms of results, there was no statistically significant change in > > -j 40 buildworld nor buildkernel. > > > > However, a 40-way find on a ports tree placed on tmpfs yielded the following: > > I am curious why did you added randomizer to sx adaptive loop but not to > lockmgr loop, and probably most important, to the spinlocks (unless I > misread the patch). This is a simple first step where I modified loops which I suspect benefit the most from the trivial change. lockmgr and other places do have loops with a configurable but the same delay for everyone. So they are already somewhat randomized by the time of the arrival in the primitive. On the other hand loops modified in the patch all check for the availability of the lock without constant delay and thus are significantly more suspectible to trying to grab it at the same time. That said, I do intent to take care of the "static" loops as well later. Meanwhile, running: time (find . -depth 2 -type dir | xargs -n 1 -P 40 -I DIR make -C DIR build-depends-list > /dev/null 2> /dev/null) drops from ~4:00 minutes to ~2:42 with the patch applied, -- Mateusz Guzik