Date: Thu, 30 Jun 2005 19:31:26 +0300 From: Nikos Ntarmos <ntarmos@ceid.upatras.gr> To: ant <andrit@ukr.net> Cc: hackers@freebsd.org Subject: Re: hot path optimizations in uma_zalloc() & uma_zfree() Message-ID: <20050630163126.GA7365@diogenis.ceid.upatras.gr> In-Reply-To: <000d01c57cf7$b9b6f9f0$29931bd9@ertpc> References: <000d01c57cf7$b9b6f9f0$29931bd9@ertpc>
next in thread | previous in thread | raw e-mail | index | archive | help
--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 <ntarmos@ceid.upatras.gr> iD8DBQFCxB5em6J1ac+VFgoRAsx8AJwNcVJI3cnVpyqCSPobkPWM5tjmYACfUGaI lf44GqlwcEbJwBdbUIS7ICU= =UOn7 -----END PGP SIGNATURE----- --61jdw2sOBCFtR2d/--
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?20050630163126.GA7365>