From owner-freebsd-hackers@FreeBSD.ORG Thu Jun 30 16:31:39 2005 Return-Path: X-Original-To: hackers@freebsd.org Delivered-To: freebsd-hackers@FreeBSD.ORG Received: from mx1.FreeBSD.org (mx1.freebsd.org [216.136.204.125]) by hub.freebsd.org (Postfix) with ESMTP id 2DCCE16A41C for ; Thu, 30 Jun 2005 16:31:39 +0000 (GMT) (envelope-from ntarmos@All-Evil.ceid.upatras.gr) Received: from hermes.ceid.upatras.gr (hermes.ceid.upatras.gr [150.140.141.168]) by mx1.FreeBSD.org (Postfix) with SMTP id 0914F43D1F for ; Thu, 30 Jun 2005 16:31:37 +0000 (GMT) (envelope-from ntarmos@All-Evil.ceid.upatras.gr) Received: (qmail 21100 invoked by uid 1004); 30 Jun 2005 16:31:34 -0000 Received: from ntarmos@All-Evil.ceid.upatras.gr by hermes by uid 1001 with qmail-scanner-1.21st (clamscan: 0.70-rc. spamassassin: 2.63. Clear:RC:1(150.140.141.181):. Processed in 0.029316 secs); 30 Jun 2005 16:31:34 -0000 X-Qmail-Scanner-Mail-From: ntarmos@All-Evil.ceid.upatras.gr via hermes X-Qmail-Scanner: 1.21st (Clear:RC:1(150.140.141.181):. Processed in 0.029316 secs) Received: from diogenis.ceid.upatras.gr (150.140.141.181) by hermes.ceid.upatras.gr with SMTP; 30 Jun 2005 16:31:34 -0000 Received: (qmail 20720 invoked from network); 30 Jun 2005 16:31:33 -0000 Received: from all-evil.ceid.upatras.gr (150.140.143.230) by diogenis.ceid.upatras.gr with SMTP; 30 Jun 2005 16:31:33 -0000 Received: from localhost (localhost.localdomain [127.0.0.1]) by All-Evil.ceid.upatras.gr (Postfix) with ESMTP id C40FF33C4A; Thu, 30 Jun 2005 19:31:33 +0300 (EEST) Received: from All-Evil.ceid.upatras.gr ([127.0.0.1]) by localhost (All-Evil [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id 28394-09; Thu, 30 Jun 2005 19:31:26 +0300 (EEST) Received: by All-Evil.ceid.upatras.gr (Postfix, from userid 1000) id 7C28333B9B; Thu, 30 Jun 2005 19:31:26 +0300 (EEST) Date: Thu, 30 Jun 2005 19:31:26 +0300 From: Nikos Ntarmos To: ant Message-ID: <20050630163126.GA7365@diogenis.ceid.upatras.gr> References: <000d01c57cf7$b9b6f9f0$29931bd9@ertpc> Mime-Version: 1.0 Content-Type: multipart/signed; micalg=pgp-sha1; protocol="application/pgp-signature"; boundary="61jdw2sOBCFtR2d/" Content-Disposition: inline In-Reply-To: <000d01c57cf7$b9b6f9f0$29931bd9@ertpc> Organization: NetCInS Lab., C.E.I.D., U. of Patras, Greece WWW-Homepage: http://noth.ceid.upatras.gr/ X-PGP-Fingerprint: 9680 60A7 DE60 0298 B1F0 9B22 9BA2 7569 CF95 160A Office-Phone: +30-2610-996919 Office-Fax: +30-2610-969011 GPS-Info: 38.2594N, 21.7428E User-Agent: Mutt/1.5.9i X-Virus-Scanned: by amavisd-new-20030616-p10 (Debian) at example.com Cc: hackers@freebsd.org Subject: Re: hot path optimizations in uma_zalloc() & uma_zfree() X-BeenThere: freebsd-hackers@freebsd.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: Technical Discussions relating to FreeBSD List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Thu, 30 Jun 2005 16:31:39 -0000 --61jdw2sOBCFtR2d/ Content-Type: multipart/mixed; boundary="EVF5PPMfhYS0aIcm" Content-Disposition: inline --EVF5PPMfhYS0aIcm Content-Type: text/plain; charset=us-ascii Content-Disposition: inline Hi there. I wouldn't have gone into this if ant hadn't produced that 10% figure for the speed improvement with simply reordering of increments and dereferences (although jhb@ reported the speed-up he noticed was much less than that). I attach* a patch that: (i) incorporates ant's exchange of uc_freebucket for uc_allocbucket, and (ii) throws away the uma_bucket.ub_cnt counter of free bucket entries, in favor of a pointer -- uma_bucket.ub_last -- to the last free bucket entry. If a simple reordering is capable of producing a 10% improvement, this change should do much better, since it saves the 'add-' in the 'add-and-dereference' process of using arrays and counters. The semantics of the pointer closely follow those of the ub_cnt counter: ub_last - ub_bucket should equal the old value of ub_cnt. I grep'ed through the whole source repository and the uses of uma_bucket.ub_cnt seem confined within sys/vm/uma_core.c, so this change must be quite self-contained -- i.e. the change in the fields of uma_bucket doesn't seem to affect any other part of the system. One could argue that it may make the code a bit less readable, but it only affects uma_core.c, so it may be worth the "inconvenience". I don't have a FreeBSD box around any more, so I can't test this patch. Heck, I can't either check it for syntax errors and such, so don't throw things at me if this doesn't even compile. Can somebody with the time and resources give it a try? \n\n * Also online at http://noth.ceid.upatras.gr/Misc/uma_bucket.diff to avoid being bitten by mailers auto{wrapp,indent}ing the diff content. --EVF5PPMfhYS0aIcm Content-Type: text/plain; charset=us-ascii Content-Disposition: attachment; filename="uma_bucket.diff" Content-Transfer-Encoding: quoted-printable diff -urbB src.orig/sys/vm/uma_core.c src/sys/vm/uma_core.c --- src.orig/sys/vm/uma_core.c 2005-06-30 19:09:06.777623184 +0300 +++ src/sys/vm/uma_core.c 2005-06-30 19:12:59.907182104 +0300 @@ -322,7 +322,7 @@ #ifdef INVARIANTS bzero(bucket->ub_bucket, sizeof(void *) * ubz->ubz_entries); #endif - bucket->ub_cnt =3D 0; + bucket->ub_last =3D bucket->ub_bucket; bucket->ub_entries =3D ubz->ubz_entries; } =20 @@ -559,11 +559,11 @@ if (zone->uz_keg->uk_flags & UMA_ZONE_MALLOC) mzone =3D 1; =20 - while (bucket->ub_cnt > 0) { - bucket->ub_cnt--; - item =3D bucket->ub_bucket[bucket->ub_cnt]; + while (bucket->ub_last !=3D bucket->ub_bucket) { + bucket->ub_last--; + item =3D *(bucket->ub_last); #ifdef INVARIANTS - bucket->ub_bucket[bucket->ub_cnt] =3D NULL; + *(bucket->ub_last) =3D NULL; KASSERT(item !=3D NULL, ("bucket_drain: botched ptr, item is NULL")); #endif @@ -1820,11 +1820,11 @@ bucket =3D cache->uc_allocbucket; =20 if (bucket) { - if (bucket->ub_cnt > 0) { - bucket->ub_cnt--; - item =3D bucket->ub_bucket[bucket->ub_cnt]; + if (bucket->ub_last !=3D bucket->ub_bucket) { + bucket->ub_last--; + item =3D *(bucket->ub_last); #ifdef INVARIANTS - bucket->ub_bucket[bucket->ub_cnt] =3D NULL; + *(bucket->ub_last) =3D NULL; #endif KASSERT(item !=3D NULL, ("uma_zalloc: Bucket pointer mangled.")); @@ -1851,7 +1851,7 @@ * We have run out of items in our allocbucket. * See if we can switch with our free bucket. */ - if (cache->uc_freebucket->ub_cnt > 0) { + if (cache->uc_freebucket->ub_last !=3D cache->uc_freebucket->ub_bucket)= { #ifdef UMA_DEBUG_ALLOC printf("uma_zalloc: Swapping empty with" " alloc.\n"); @@ -1880,12 +1880,12 @@ cache =3D &zone->uz_cpu[cpu]; bucket =3D cache->uc_allocbucket; if (bucket !=3D NULL) { - if (bucket->ub_cnt > 0) { + if (bucket->ub_last !=3D bucket->ub_bucket) { ZONE_UNLOCK(zone); goto zalloc_start; } bucket =3D cache->uc_freebucket; - if (bucket !=3D NULL && bucket->ub_cnt > 0) { + if (bucket !=3D NULL && bucket->ub_last !=3D bucket->ub_bucket) { ZONE_UNLOCK(zone); goto zalloc_start; } @@ -1897,7 +1897,7 @@ =20 /* Our old one is now a free bucket */ if (cache->uc_allocbucket) { - KASSERT(cache->uc_allocbucket->ub_cnt =3D=3D 0, + KASSERT(cache->uc_allocbucket->ub_last =3D=3D cache->uc_allocbucket->ub_= backet, ("uma_zalloc_arg: Freeing a non free bucket.")); LIST_INSERT_HEAD(&zone->uz_free_bucket, cache->uc_allocbucket, ub_link); @@ -1906,7 +1906,7 @@ =20 /* Check the free list for a new alloc bucket */ if ((bucket =3D LIST_FIRST(&zone->uz_full_bucket)) !=3D NULL) { - KASSERT(bucket->ub_cnt !=3D 0, + KASSERT(bucket->ub_last !=3D bucket->ub_bucket, ("uma_zalloc_arg: Returning an empty bucket.")); =20 LIST_REMOVE(bucket, ub_link); @@ -2069,14 +2069,14 @@ { uma_bucket_t bucket; uma_slab_t slab; - int16_t saved; + void ** saved; int max, origflags =3D flags; =20 /* * Try this zone's free list first so we don't allocate extra buckets. */ if ((bucket =3D LIST_FIRST(&zone->uz_free_bucket)) !=3D NULL) { - KASSERT(bucket->ub_cnt =3D=3D 0, + KASSERT(bucket->ub_last =3D=3D bucket->ub_bucket, ("uma_zalloc_bucket: Bucket on free list is not empty.")); LIST_REMOVE(bucket, ub_link); } else { @@ -2106,14 +2106,13 @@ #endif zone->uz_fills++; =20 - max =3D MIN(bucket->ub_entries, zone->uz_count); + max =3D bucket->ub_bucket + MIN(bucket->ub_entries, zone->uz_count); /* Try to keep the buckets totally full */ - saved =3D bucket->ub_cnt; - while (bucket->ub_cnt < max && + saved =3D bucket->ub_last; + while (bucket->ub_last < max && (slab =3D uma_zone_slab(zone, flags)) !=3D NULL) { - while (slab->us_freecount && bucket->ub_cnt < max) { - bucket->ub_bucket[bucket->ub_cnt++] =3D - uma_slab_alloc(zone, slab); + while (slab->us_freecount && bucket->ub_last < max) { + *(bucket->ub_last++) =3D uma_slab_alloc(zone, slab); } =20 /* Don't block on the next fill */ @@ -2128,34 +2127,34 @@ * own it. */ if (zone->uz_init !=3D NULL) { - int i; + void ** i; =20 ZONE_UNLOCK(zone); - for (i =3D saved; i < bucket->ub_cnt; i++) - if (zone->uz_init(bucket->ub_bucket[i], + for (i =3D saved; i < bucket->ub_last; i++) + if (zone->uz_init(*i, zone->uz_keg->uk_size, origflags) !=3D 0) break; /* * If we couldn't initialize the whole bucket, put the * rest back onto the freelist. */ - if (i !=3D bucket->ub_cnt) { - int j; + if (i !=3D bucket->ub_last) { + void ** j; =20 - for (j =3D i; j < bucket->ub_cnt; j++) { - uma_zfree_internal(zone, bucket->ub_bucket[j], + for (j =3D i; j < bucket->ub_last; j++) { + uma_zfree_internal(zone, *j, NULL, SKIP_FINI); #ifdef INVARIANTS - bucket->ub_bucket[j] =3D NULL; + (*j) =3D NULL; #endif } - bucket->ub_cnt =3D i; + bucket->ub_last =3D i; } ZONE_LOCK(zone); } =20 zone->uz_fills--; - if (bucket->ub_cnt !=3D 0) { + if (bucket->ub_last !=3D bucket->ub_bucket) { LIST_INSERT_HEAD(&zone->uz_full_bucket, bucket, ub_link); return (1); @@ -2281,7 +2280,7 @@ cache =3D &zone->uz_cpu[cpu]; =20 zfree_start: - bucket =3D cache->uc_freebucket; + bucket =3D cache->uc_allocbucket; =20 if (bucket) { /* @@ -2289,14 +2288,14 @@ * check to be slightly out of sync. */ =20 - if (bucket->ub_cnt < bucket->ub_entries) { - KASSERT(bucket->ub_bucket[bucket->ub_cnt] =3D=3D NULL, + if (bucket->ub_last < (bucket->ub_bucket + bucket->ub_entries)) { + KASSERT(*(bucket->ub_last) =3D=3D NULL, ("uma_zfree: Freeing to non free bucket index.")); - bucket->ub_bucket[bucket->ub_cnt] =3D item; - bucket->ub_cnt++; + *(bucket->ub_last) =3D item; + bucket->ub_last++; critical_exit(); return; - } else if (cache->uc_allocbucket) { + } else if (cache->uc_freebucket) { #ifdef UMA_DEBUG_ALLOC printf("uma_zfree: Swapping buckets.\n"); #endif @@ -2304,8 +2303,7 @@ * We have run out of space in our freebucket. * See if we can switch with our alloc bucket. */ - if (cache->uc_allocbucket->ub_cnt < - cache->uc_freebucket->ub_cnt) { + if (cache->uc_freebucket->ub_last =3D=3D cache->uc_freebucket->ub_bucke= t) { bucket =3D cache->uc_freebucket; cache->uc_freebucket =3D cache->uc_allocbucket; cache->uc_allocbucket =3D bucket; @@ -2332,14 +2330,14 @@ cpu =3D curcpu; cache =3D &zone->uz_cpu[cpu]; if (cache->uc_freebucket !=3D NULL) { - if (cache->uc_freebucket->ub_cnt < + if ((cache->uc_freebucket->ub_last - cache->uc_freebucket->ub_bucket) < cache->uc_freebucket->ub_entries) { ZONE_UNLOCK(zone); goto zfree_start; } if (cache->uc_allocbucket !=3D NULL && - (cache->uc_allocbucket->ub_cnt < - cache->uc_freebucket->ub_cnt)) { + ((cache->uc_allocbucket->ub_last - cache->uc_allocbucket->ub_bucket) < + (cache->uc_freebucket->ub_last - cache->uc_freebucket->ub_bucket))) { ZONE_UNLOCK(zone); goto zfree_start; } @@ -2353,8 +2351,8 @@ #ifdef UMA_DEBUG_ALLOC printf("uma_zfree: Putting old bucket on the free list.\n"); #endif - /* ub_cnt is pointing to the last free item */ - KASSERT(bucket->ub_cnt !=3D 0, + /* ub_last is pointing to the last free item */ + KASSERT(bucket->ub_last !=3D bucket->ub_bucket, ("uma_zfree: Attempting to insert an empty bucket onto the full list= =2E\n")); LIST_INSERT_HEAD(&zone->uz_full_bucket, bucket, ub_link); @@ -2707,9 +2705,9 @@ { printf("alloc: %p(%d), free: %p(%d)\n", cache->uc_allocbucket, - cache->uc_allocbucket?cache->uc_allocbucket->ub_cnt:0, + cache->uc_allocbucket?(cache->uc_allocbucket->ub_last - cache->uc_allocb= ucket->ub_bucket):0, cache->uc_freebucket, - cache->uc_freebucket?cache->uc_freebucket->ub_cnt:0); + cache->uc_freebucket?(cache->uc_freebucket->ub_last - cache->uc_freebuck= et->ub_bucket):0); } =20 void @@ -2795,9 +2793,9 @@ continue; cache =3D &z->uz_cpu[cpu]; if (cache->uc_allocbucket !=3D NULL) - cachefree +=3D cache->uc_allocbucket->ub_cnt; + cachefree +=3D (cache->uc_allocbucket->ub_last - cache->uc_allocbucke= t->ub_bucket); if (cache->uc_freebucket !=3D NULL) - cachefree +=3D cache->uc_freebucket->ub_cnt; + cachefree +=3D (cache->uc_freebucket->ub_last - cache->uc_freebucket-= >ub_bucket); alloc +=3D cache->uc_allocs; cache->uc_allocs =3D 0; } @@ -2805,7 +2803,7 @@ alloc +=3D z->uz_allocs; =20 LIST_FOREACH(bucket, &z->uz_full_bucket, ub_link) { - cachefree +=3D bucket->ub_cnt; + cachefree +=3D (bucket->ub_last - bucket->ub_bucket); } totalfree =3D zk->uk_free + cachefree; len =3D snprintf(offset, linesize, diff -urbB src.orig/sys/vm/uma_int.h src/sys/vm/uma_int.h --- src.orig/sys/vm/uma_int.h 2005-06-30 19:09:00.625558440 +0300 +++ src/sys/vm/uma_int.h 2005-06-30 18:41:16.515541616 +0300 @@ -166,7 +166,7 @@ =20 struct uma_bucket { LIST_ENTRY(uma_bucket) ub_link; /* Link into the zone */ - int16_t ub_cnt; /* Count of free items. */ + void **ub_last; /* Pointer to last free item */ int16_t ub_entries; /* Max items. */ void *ub_bucket[]; /* actual allocation storage */ }; --EVF5PPMfhYS0aIcm-- --61jdw2sOBCFtR2d/ Content-Type: application/pgp-signature; name="signature.asc" Content-Description: Digital signature Content-Disposition: inline -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.1 (GNU/Linux) Comment: Nikos "Nikolai" Ntarmos iD8DBQFCxB5em6J1ac+VFgoRAsx8AJwNcVJI3cnVpyqCSPobkPWM5tjmYACfUGaI lf44GqlwcEbJwBdbUIS7ICU= =UOn7 -----END PGP SIGNATURE----- --61jdw2sOBCFtR2d/--