[PATCH] slob: reduce list scanning

The version of SLOB in -mm always scans its free list from the
beginning, which results in small allocations and free segments
clustering at the beginning of the list over time. This causes the
average search to scan over a large stretch at the beginning on each
allocation.

By starting each page search where the last one left off, we evenly
distribute the allocations and greatly shorten the average search.

Without this patch, kernel compiles on a 1.5G machine take a large
amount of system time for list scanning. With this patch, compiles are
within a few seconds of performance of a SLAB kernel with no notable
change in system time.

Signed-off-by: Matt Mackall <mpm RemoveThis @selenic.com>

Index: mm/mm/slob.c
===================================================================
--- mm.orig/mm/slob.c 2007-07-13 17:51:25.000000000 -0500
+++ mm/mm/slob.c 2007-07-13 18:42:59.000000000 -0500
@@ -293,6 +293,7 @@ static void *slob_page_alloc(struct slob
static void *slob_alloc(size_t size, gfp_t gfp, int align, int node)
{
struct slob_page *sp;
+ struct list_head *prev;
slob_t *b = NULL;
unsigned long flags;

@@ -307,12 +308,22 @@ static void *slob_alloc(size_t size, gfp
if (node != -1 && page_to_nid(&sp->page) != node)
continue;
#endif
+ /* Enough room on this page? */
+ if (sp->units < SLOB_UNITS(size))
+ continue;

- if (sp->units >= SLOB_UNITS(size)) {
- b = slob_page_alloc(sp, size, align);
- if (b)
- break;
- }
+ /* Attempt to alloc */
+ prev = sp->list.prev;
+ b = slob_page_alloc(sp, size, align);
+ if (!b)
+ continue;
+
+ /* Improve fragment distribution and reduce our average
+ * search time by starting our next search here. (see
+ * Knuth vol 1, sec 2.5, pg 449) */
+ if (free_slob_pages.next != prev->next)
+ list_move_tail(&free_slob_pages, prev->next);
+ break;
}
spin_unlock_irqrestore(&slob_lock, flags);



--
Mathematics is the supreme nostalgia of our time.
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo RemoveThis @vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/

Matt Mackall wrote:
> The version of SLOB in -mm always scans its free list from the
> beginning, which results in small allocations and free segments
> clustering at the beginning of the list over time. This causes the
> average search to scan over a large stretch at the beginning on each
> allocation.
>
> By starting each page search where the last one left off, we evenly
> distribute the allocations and greatly shorten the average search.
>
> Without this patch, kernel compiles on a 1.5G machine take a large
> amount of system time for list scanning. With this patch, compiles are
> within a few seconds of performance of a SLAB kernel with no notable
> change in system time.

This looks pretty nice, and performance results sound good too.
IMO this should probably be merged along with the previous
SLOB patches, because they removed the cyclic scanning to begin
with (so it may be possible that introduces a performnace
regression in some situations).

I wonder what it would take to close the performance gap further.
I still want to look at per-cpu freelists after Andrew merges
this set of patches. That may improve both cache hotness and
CPU scalability.

Actually SLOB potentially has some fundamental CPU cache hotness
advantages over the other allocators, for the same reasons as
its space advantages. It may be possible to make some workloads
faster with SLOB than with SLUB! Maybe we could remove SLAB and
SLUB then

--
SUSE Labs, Novell Inc.
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo.TakeThisOut@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/