From owner-freebsd-current@freebsd.org Sun Jul 10 11:13:32 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 91CA0B8556F for ; Sun, 10 Jul 2016 11:13:32 +0000 (UTC) (envelope-from mjguzik@gmail.com) Received: from mail-wm0-x242.google.com (mail-wm0-x242.google.com [IPv6:2a00:1450:400c:c09::242]) (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 171FE194F for ; Sun, 10 Jul 2016 11:13:32 +0000 (UTC) (envelope-from mjguzik@gmail.com) Received: by mail-wm0-x242.google.com with SMTP id x83so11957722wma.3 for ; Sun, 10 Jul 2016 04:13:32 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=date:from:to:subject:message-id:mail-followup-to:mime-version :content-disposition:user-agent; bh=mWpddZKaz6Csf/YDxF39RkyeODGk76kzos6Ylt/zwiU=; b=tHXgORaBjYFhxcxabEbCea/2rNveFKdMUj9fU28xuAQdCM7bhVfHp7hbMRXfFEEB68 5rn8I5iIAuPIKZnuRxxvdbPpcyZFA7zjPIepJjt7Pob17wCNvoOENKNpakRgat/x3RU3 lydyY0RXsyrPTJjX5HiQOagO88tkc8nRM4ypwQVjZypZUUENZU+eKLTUWDPkPV+XWOyP vYgVf63/UkhTUaFIBqr0Gz9uDJp3x7SYvrx3+aE8Tp5hqircKaWUjXQcau+9W17Q+WBb nl7vOoDMmlAcDg/mgPt04XyAIvJ1YN1NclfDnMDuyT0Jd+1crs6tw+Doc1KhJYxtF5F/ o9cA== 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:subject:message-id:mail-followup-to :mime-version:content-disposition:user-agent; bh=mWpddZKaz6Csf/YDxF39RkyeODGk76kzos6Ylt/zwiU=; b=YXT6oDT24xugMvk+rg9gQLOkb19KOmhD1pmB0J2hPXpV9FYsn97vJJxy0Yoz4rT208 hmCk7yBs7c+NICXO2l6d0/bvOvnmWAjRQYxchTsPvMZ0LRvjpY3IGUujsMQVZZc5ow1h nduhXqGOwEmRiC9bgLflKwpVYi1Ucpj3Pqoku6PDOF34thB+Fc9W45ZDv5QDuGESJUbD rcyiNYSsHtIP22gNGOdF+v5QJEbdTYhJynnoWHZO9uApfo9tqgtcu+qoxqgiZW3KLJ9f 7B/gh0lg02Cvg/3zR+SReLbWlFLP1ehdVnXmqy1xcWu5gGi7A+Ys8wkaHOALhA+CZuxF QxgQ== X-Gm-Message-State: ALyK8tLGL84o+NhVr5jkVkKbY6ihe+ZYtwDnjJPB+mMoWlnPz+ui8jd+HsY1kWGuYkrqbA== X-Received: by 10.28.51.131 with SMTP id z125mr6725780wmz.15.1468149209211; Sun, 10 Jul 2016 04:13:29 -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 f196sm12817622wmg.15.2016.07.10.04.13.28 for (version=TLS1_2 cipher=AES128-SHA bits=128/128); Sun, 10 Jul 2016 04:13:28 -0700 (PDT) Date: Sun, 10 Jul 2016 13:13:26 +0200 From: Mateusz Guzik To: freebsd-current@freebsd.org Subject: [PATCH] microoptimize locking primitives by introducing randomized delay between atomic ops Message-ID: <20160710111326.GA7853@dft-labs.eu> Mail-Followup-To: Mateusz Guzik , freebsd-current@freebsd.org MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Disposition: inline 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 11:13:32 -0000 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: x vanilla + patched +----------------------------------------------------------------------------------------+ | ++++ + x x x x | |+ ++++ +++ + + + ++ + + x x x xxxxxxxx x x x| | |_____M____A__________| |________AM______| | +----------------------------------------------------------------------------------------+ N Min Max Median Avg Stddev x 20 12.431 15.952 14.897 14.7444 0.74241657 + 20 8.103 11.863 9.0135 9.44565 1.0059484 Difference at 95.0% confidence -5.29875 +/- 0.565836 -35.9374% +/- 3.83764% (Student's t, pooled s = 0.884057) The patch: diff --git a/sys/kern/kern_mutex.c b/sys/kern/kern_mutex.c index 012cf7c..db3b950 100644 --- a/sys/kern/kern_mutex.c +++ b/sys/kern/kern_mutex.c @@ -444,7 +444,7 @@ __mtx_lock_sleep(volatile uintptr_t *c, uintptr_t tid, int opts, m->lock_object.lo_name); while (mtx_owner(m) == owner && TD_IS_RUNNING(owner)) { - cpu_spinwait(); + lock_delay(); #ifdef KDTRACE_HOOKS spin_cnt++; #endif diff --git a/sys/kern/kern_rwlock.c b/sys/kern/kern_rwlock.c index 6a904d2..3b512b5 100644 --- a/sys/kern/kern_rwlock.c +++ b/sys/kern/kern_rwlock.c @@ -438,7 +438,7 @@ __rw_rlock(volatile uintptr_t *c, const char *file, int line) "lockname:\"%s\"", rw->lock_object.lo_name); while ((struct thread*)RW_OWNER(rw->rw_lock) == owner && TD_IS_RUNNING(owner)) { - cpu_spinwait(); + lock_delay(); #ifdef KDTRACE_HOOKS spin_cnt++; #endif @@ -799,7 +799,7 @@ __rw_wlock_hard(volatile uintptr_t *c, uintptr_t tid, const char *file, rw->lock_object.lo_name); while ((struct thread*)RW_OWNER(rw->rw_lock) == owner && TD_IS_RUNNING(owner)) { - cpu_spinwait(); + lock_delay(); #ifdef KDTRACE_HOOKS spin_cnt++; #endif diff --git a/sys/kern/kern_sx.c b/sys/kern/kern_sx.c index 2a81c04..1bfd46f 100644 --- a/sys/kern/kern_sx.c +++ b/sys/kern/kern_sx.c @@ -579,7 +579,7 @@ _sx_xlock_hard(struct sx *sx, uintptr_t tid, int opts, const char *file, GIANT_SAVE(); while (SX_OWNER(sx->sx_lock) == x && TD_IS_RUNNING(owner)) { - cpu_spinwait(); + lock_delay(); #ifdef KDTRACE_HOOKS spin_cnt++; #endif @@ -889,10 +889,10 @@ _sx_slock_hard(struct sx *sx, int opts, const char *file, int line) GIANT_SAVE(); while (SX_OWNER(sx->sx_lock) == x && TD_IS_RUNNING(owner)) { + lock_delay(); #ifdef KDTRACE_HOOKS spin_cnt++; #endif - cpu_spinwait(); } KTR_STATE0(KTR_SCHED, "thread", sched_tdname(curthread), "running"); diff --git a/sys/kern/subr_lock.c b/sys/kern/subr_lock.c index e78d5a9..55a0fb7 100644 --- a/sys/kern/subr_lock.c +++ b/sys/kern/subr_lock.c @@ -103,6 +103,16 @@ lock_destroy(struct lock_object *lock) lock->lo_flags &= ~LO_INITIALIZED; } +void +lock_delay(void) +{ + int i, delay; + + delay = cpu_ticks() % 2048; + for (i = 0; i < delay; i++) + cpu_spinwait(); +} + #ifdef DDB DB_SHOW_COMMAND(lock, db_show_lock) { diff --git a/sys/sys/lock.h b/sys/sys/lock.h index 8d7a068..d076687 100644 --- a/sys/sys/lock.h +++ b/sys/sys/lock.h @@ -204,6 +204,7 @@ extern struct lock_class *lock_classes[]; void lock_init(struct lock_object *, struct lock_class *, const char *, const char *, int); void lock_destroy(struct lock_object *); +void lock_delay(void); void spinlock_enter(void); void spinlock_exit(void); void witness_init(struct lock_object *, const char *);