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.
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 = 0;
+ bucket->ub_last = bucket->ub_bucket;
bucket->ub_entries = ubz->ubz_entries;
}
@@ -559,11 +559,11 @@
if (zone->uz_keg->uk_flags & UMA_ZONE_MALLOC)
mzone = 1;
- while (bucket->ub_cnt > 0) {
- bucket->ub_cnt--;
- item = bucket->ub_bucket[bucket->ub_cnt];
+ while (bucket->ub_last != bucket->ub_bucket) {
+ bucket->ub_last--;
+ item = *(bucket->ub_last);
#ifdef INVARIANTS
- bucket->ub_bucket[bucket->ub_cnt] = NULL;
+ *(bucket->ub_last) = NULL;
KASSERT(item != NULL,
("bucket_drain: botched ptr, item is NULL"));
#endif
@@ -1820,11 +1820,11 @@
bucket = cache->uc_allocbucket;
if (bucket) {
- if (bucket->ub_cnt > 0) {
- bucket->ub_cnt--;
- item = bucket->ub_bucket[bucket->ub_cnt];
+ if (bucket->ub_last != bucket->ub_bucket) {
+ bucket->ub_last--;
+ item = *(bucket->ub_last);
#ifdef INVARIANTS
- bucket->ub_bucket[bucket->ub_cnt] = NULL;
+ *(bucket->ub_last) = NULL;
#endif
KASSERT(item != 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 !=
cache->uc_freebucket->ub_bucket) {
#ifdef UMA_DEBUG_ALLOC
printf("uma_zalloc: Swapping empty with"
" alloc.\n");
@@ -1880,12 +1880,12 @@
cache = &zone->uz_cpu[cpu];
bucket = cache->uc_allocbucket;
if (bucket != NULL) {
- if (bucket->ub_cnt > 0) {
+ if (bucket->ub_last != bucket->ub_bucket) {
ZONE_UNLOCK(zone);
goto zalloc_start;
}
bucket = cache->uc_freebucket;
- if (bucket != NULL && bucket->ub_cnt > 0) {
+ if (bucket != NULL && bucket->ub_last != bucket->ub_bucket) {
ZONE_UNLOCK(zone);
goto zalloc_start;
}
@@ -1897,7 +1897,7 @@
/* Our old one is now a free bucket */
if (cache->uc_allocbucket) {
- KASSERT(cache->uc_allocbucket->ub_cnt == 0,
+ KASSERT(cache->uc_allocbucket->ub_last ==
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 @@
/* Check the free list for a new alloc bucket */
if ((bucket = LIST_FIRST(&zone->uz_full_bucket)) != NULL) {
- KASSERT(bucket->ub_cnt != 0,
+ KASSERT(bucket->ub_last != bucket->ub_bucket,
("uma_zalloc_arg: Returning an empty bucket."));
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 = flags;
/*
* Try this zone's free list first so we don't allocate extra buckets.
*/
if ((bucket = LIST_FIRST(&zone->uz_free_bucket)) != NULL) {
- KASSERT(bucket->ub_cnt == 0,
+ KASSERT(bucket->ub_last == 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++;
- max = MIN(bucket->ub_entries, zone->uz_count);
+ max = bucket->ub_bucket + MIN(bucket->ub_entries, zone->uz_count);
/* Try to keep the buckets totally full */
- saved = bucket->ub_cnt;
- while (bucket->ub_cnt < max &&
+ saved = bucket->ub_last;
+ while (bucket->ub_last < max &&
(slab = uma_zone_slab(zone, flags)) != NULL) {
- while (slab->us_freecount && bucket->ub_cnt < max) {
- bucket->ub_bucket[bucket->ub_cnt++] =
- uma_slab_alloc(zone, slab);
+ while (slab->us_freecount && bucket->ub_last < max) {
+ *(bucket->ub_last++) = uma_slab_alloc(zone, slab);
}
/* Don't block on the next fill */
@@ -2128,34 +2127,34 @@
* own it.
*/
if (zone->uz_init != NULL) {
- int i;
+ void ** i;
ZONE_UNLOCK(zone);
- for (i = saved; i < bucket->ub_cnt; i++)
- if (zone->uz_init(bucket->ub_bucket[i],
+ for (i = saved; i < bucket->ub_last; i++)
+ if (zone->uz_init(*i,
zone->uz_keg->uk_size, origflags) != 0)
break;
/*
* If we couldn't initialize the whole bucket, put the
* rest back onto the freelist.
*/
- if (i != bucket->ub_cnt) {
- int j;
+ if (i != bucket->ub_last) {
+ void ** j;
- for (j = i; j < bucket->ub_cnt; j++) {
- uma_zfree_internal(zone, bucket->ub_bucket[j],
+ for (j = i; j < bucket->ub_last; j++) {
+ uma_zfree_internal(zone, *j,
NULL, SKIP_FINI);
#ifdef INVARIANTS
- bucket->ub_bucket[j] = NULL;
+ (*j) = NULL;
#endif
}
- bucket->ub_cnt = i;
+ bucket->ub_last = i;
}
ZONE_LOCK(zone);
}
zone->uz_fills--;
- if (bucket->ub_cnt != 0) {
+ if (bucket->ub_last != bucket->ub_bucket) {
LIST_INSERT_HEAD(&zone->uz_full_bucket,
bucket, ub_link);
return (1);
@@ -2281,7 +2280,7 @@
cache = &zone->uz_cpu[cpu];
zfree_start:
- bucket = cache->uc_freebucket;
+ bucket = cache->uc_allocbucket;
if (bucket) {
/*
@@ -2289,14 +2288,14 @@
* check to be slightly out of sync.
*/
- if (bucket->ub_cnt < bucket->ub_entries) {
- KASSERT(bucket->ub_bucket[bucket->ub_cnt] == NULL,
+ if (bucket->ub_last < (bucket->ub_bucket + bucket->ub_entries))
{
+ KASSERT(*(bucket->ub_last) == NULL,
("uma_zfree: Freeing to non free bucket index."));
- bucket->ub_bucket[bucket->ub_cnt] = item;
- bucket->ub_cnt++;
+ *(bucket->ub_last) = 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 ==
cache->uc_freebucket->ub_bucket) {
bucket = cache->uc_freebucket;
cache->uc_freebucket = cache->uc_allocbucket;
cache->uc_allocbucket = bucket;
@@ -2332,14 +2330,14 @@
cpu = curcpu;
cache = &zone->uz_cpu[cpu];
if (cache->uc_freebucket != 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 != 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 != 0,
+ /* ub_last is pointing to the last free item */
+ KASSERT(bucket->ub_last != bucket->ub_bucket,
("uma_zfree: Attempting to insert an empty bucket onto the
full list.\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_allocbucket->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_freebucket->ub_bucket):0);
}
void
@@ -2795,9 +2793,9 @@
continue;
cache = &z->uz_cpu[cpu];
if (cache->uc_allocbucket != NULL)
- cachefree +=
cache->uc_allocbucket->ub_cnt;
+ cachefree +=
(cache->uc_allocbucket->ub_last - cache->uc_allocbucket->ub_bucket);
if (cache->uc_freebucket != NULL)
- cachefree +=
cache->uc_freebucket->ub_cnt;
+ cachefree +=
(cache->uc_freebucket->ub_last - cache->uc_freebucket->ub_bucket);
alloc += cache->uc_allocs;
cache->uc_allocs = 0;
}
@@ -2805,7 +2803,7 @@
alloc += z->uz_allocs;
LIST_FOREACH(bucket, &z->uz_full_bucket, ub_link) {
- cachefree += bucket->ub_cnt;
+ cachefree += (bucket->ub_last - bucket->ub_bucket);
}
totalfree = zk->uk_free + cachefree;
len = 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 @@
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 */
};
signature.asc
Description: Digital signature
