xserver: Branch 'master' - 2 commits
Fredrik Höglund
fredrik at kemper.freedesktop.org
Mon Mar 31 12:33:04 PDT 2008
exa/exa.h | 2
exa/exa_offscreen.c | 132 ++++++++++++++++++++++++++--------------------------
exa/exa_priv.h | 1
3 files changed, 69 insertions(+), 66 deletions(-)
New commits:
commit 8074676d2df8d577b443e3fa5e22d7c71c944bd1
Author: Fredrik Höglund <fredrik at kde.org>
Date: Mon Mar 31 21:24:59 2008 +0200
EXA: Optimize the eviction scanning loop in exaOffscreenAlloc.
Reduce the cost of the inner loop, by keeping a set of pointers to the
first and the last areas in the series, subtracting the cost of the first
area from the score, and adding the cost of the last area while walking
the list. This commit also moves the scanning loop from exaOffscreenAlloc
into a separate function.
Idea by Michel Dänzer.
diff --git a/exa/exa_offscreen.c b/exa/exa_offscreen.c
index 2701e84..85b5388 100644
--- a/exa/exa_offscreen.c
+++ b/exa/exa_offscreen.c
@@ -73,6 +73,62 @@ ExaOffscreenKickOut (ScreenPtr pScreen, ExaOffscreenArea *area)
#define AREA_SCORE(area) (area->size / (double)(pExaScr->offScreenCounter - area->last_use))
+static ExaOffscreenArea *
+exaFindAreaToEvict(ExaScreenPrivPtr pExaScr, int size, int align)
+{
+ ExaOffscreenArea *begin, *end, *best;
+ double score, best_score;
+ int avail, real_size, tmp;
+
+ best_score = UINT_MAX;
+ begin = end = pExaScr->info->offScreenAreas;
+ avail = 0;
+ score = 0;
+ best = 0;
+
+ while (end != NULL)
+ {
+ restart:
+ while (begin != NULL && begin->state == ExaOffscreenLocked)
+ begin = end = begin->next;
+
+ if (begin == NULL)
+ break;
+
+ /* adjust size needed to account for alignment loss for this area */
+ real_size = size;
+ tmp = begin->base_offset % align;
+ if (tmp)
+ real_size += (align - tmp);
+
+ while (avail < real_size && end != NULL)
+ {
+ if (end->state == ExaOffscreenLocked) {
+ /* Can't more room here, restart after this locked area */
+ avail = 0;
+ score = 0;
+ begin = end;
+ goto restart;
+ }
+ avail += end->size;
+ score += AREA_SCORE(end);
+ end = end->next;
+ }
+
+ /* Check the score, update best */
+ if (avail >= real_size && score < best_score) {
+ best = begin;
+ best_score = score;
+ }
+
+ avail -= begin->size;
+ score -= AREA_SCORE(begin);
+ begin = begin->next;
+ }
+
+ return best;
+}
+
/**
* exaOffscreenAlloc allocates offscreen memory
*
@@ -98,7 +154,7 @@ exaOffscreenAlloc (ScreenPtr pScreen, int size, int align,
ExaOffscreenSaveProc save,
pointer privData)
{
- ExaOffscreenArea *area, *begin, *best;
+ ExaOffscreenArea *area;
ExaScreenPriv (pScreen);
int tmp, real_size = 0;
#if DEBUG_OFFSCREEN
@@ -145,54 +201,8 @@ exaOffscreenAlloc (ScreenPtr pScreen, int size, int align,
if (!area)
{
- double best_score;
- /*
- * Kick out existing users to make space.
- *
- * First, locate a region which can hold the desired object.
- */
+ area = exaFindAreaToEvict(pExaScr, size, align);
- /* prev points at the first object to boot */
- best = NULL;
- best_score = UINT_MAX;
- for (begin = pExaScr->info->offScreenAreas; begin != NULL;
- begin = begin->next)
- {
- int avail;
- double score;
- ExaOffscreenArea *scan;
-
- if (begin->state == ExaOffscreenLocked)
- continue;
-
- /* adjust size needed to account for alignment loss for this area */
- real_size = size;
- tmp = begin->base_offset % align;
- if (tmp)
- real_size += (align - tmp);
-
- avail = 0;
- score = 0;
- /* now see if we can make room here, and how "costly" it'll be. */
- for (scan = begin; scan != NULL; scan = scan->next)
- {
- if (scan->state == ExaOffscreenLocked) {
- /* Can't make room here, start after this locked area. */
- begin = scan;
- break;
- }
- score += AREA_SCORE(scan);
- avail += scan->size;
- if (avail >= real_size)
- break;
- }
- /* Is it the best option we've found so far? */
- if (avail >= real_size && score < best_score) {
- best = begin;
- best_score = score;
- }
- }
- area = best;
if (!area)
{
DBG_OFFSCREEN (("Alloc 0x%x -> NOSPACE\n", size));
commit 93d876891dbba41b920a9a29a5de77f647f43928
Author: Fredrik Höglund <fredrik at kde.org>
Date: Mon Mar 31 21:15:50 2008 +0200
EXA: Improve the algorithm used for tracking offscreen pixmap use.
Replace the current score keeping algorithm with a rolling counter that's
incremented in ExaOffscreenMarkUsed, with the previous value being stored
in the area. exaOffscreenAlloc uses the difference between the counter
value and the value in the area when deciding which area to evict.
It now also takes the size of the areas into account, and favors evicting
smaller areas.
The credit for these ideas goes to Michel Dänzer.
diff --git a/exa/exa.h b/exa/exa.h
index 0774a70..97ae6c0 100644
--- a/exa/exa.h
+++ b/exa/exa.h
@@ -56,7 +56,7 @@ struct _ExaOffscreenArea {
int base_offset; /* allocation base */
int offset; /* aligned offset */
int size; /* total allocation size */
- int score;
+ unsigned last_use;
pointer privData;
ExaOffscreenSaveProc save;
diff --git a/exa/exa_offscreen.c b/exa/exa_offscreen.c
index c666b00..2701e84 100644
--- a/exa/exa_offscreen.c
+++ b/exa/exa_offscreen.c
@@ -71,6 +71,8 @@ ExaOffscreenKickOut (ScreenPtr pScreen, ExaOffscreenArea *area)
return exaOffscreenFree (pScreen, area);
}
+#define AREA_SCORE(area) (area->size / (double)(pExaScr->offScreenCounter - area->last_use))
+
/**
* exaOffscreenAlloc allocates offscreen memory
*
@@ -98,7 +100,7 @@ exaOffscreenAlloc (ScreenPtr pScreen, int size, int align,
{
ExaOffscreenArea *area, *begin, *best;
ExaScreenPriv (pScreen);
- int tmp, real_size = 0, best_score;
+ int tmp, real_size = 0;
#if DEBUG_OFFSCREEN
static int number = 0;
ErrorF("================= ============ allocating a new pixmap %d\n", ++number);
@@ -143,6 +145,7 @@ exaOffscreenAlloc (ScreenPtr pScreen, int size, int align,
if (!area)
{
+ double best_score;
/*
* Kick out existing users to make space.
*
@@ -151,11 +154,12 @@ exaOffscreenAlloc (ScreenPtr pScreen, int size, int align,
/* prev points at the first object to boot */
best = NULL;
- best_score = INT_MAX;
+ best_score = UINT_MAX;
for (begin = pExaScr->info->offScreenAreas; begin != NULL;
begin = begin->next)
{
- int avail, score;
+ int avail;
+ double score;
ExaOffscreenArea *scan;
if (begin->state == ExaOffscreenLocked)
@@ -177,8 +181,7 @@ exaOffscreenAlloc (ScreenPtr pScreen, int size, int align,
begin = scan;
break;
}
- /* Score should only be non-zero for ExaOffscreenRemovable */
- score += scan->score;
+ score += AREA_SCORE(scan);
avail += scan->size;
if (avail >= real_size)
break;
@@ -230,7 +233,7 @@ exaOffscreenAlloc (ScreenPtr pScreen, int size, int align,
new_area->size = area->size - real_size;
new_area->state = ExaOffscreenAvail;
new_area->save = NULL;
- new_area->score = 0;
+ new_area->last_use = 0;
new_area->next = area->next;
area->next = new_area;
area->size = real_size;
@@ -244,7 +247,7 @@ exaOffscreenAlloc (ScreenPtr pScreen, int size, int align,
area->state = ExaOffscreenRemovable;
area->privData = privData;
area->save = save;
- area->score = 0;
+ area->last_use = pExaScr->offScreenCounter++;
area->offset = (area->base_offset + align - 1);
area->offset -= area->offset % align;
@@ -395,7 +398,7 @@ exaOffscreenFree (ScreenPtr pScreen, ExaOffscreenArea *area)
area->state = ExaOffscreenAvail;
area->save = NULL;
- area->score = 0;
+ area->last_use = 0;
/*
* Find previous area
*/
@@ -427,23 +430,11 @@ ExaOffscreenMarkUsed (PixmapPtr pPixmap)
{
ExaPixmapPriv (pPixmap);
ExaScreenPriv (pPixmap->drawable.pScreen);
- static int iter = 0;
if (!pExaPixmap || !pExaPixmap->area)
return;
- /* The numbers here are arbitrary. We may want to tune these. */
- pExaPixmap->area->score += 100;
- if (++iter == 10) {
- ExaOffscreenArea *area;
- for (area = pExaScr->info->offScreenAreas; area != NULL;
- area = area->next)
- {
- if (area->state == ExaOffscreenRemovable)
- area->score = (area->score * 7) / 8;
- }
- iter = 0;
- }
+ pExaPixmap->area->last_use = pExaScr->offScreenCounter++;
}
/**
@@ -472,10 +463,11 @@ exaOffscreenInit (ScreenPtr pScreen)
area->size = pExaScr->info->memorySize - area->base_offset;
area->save = NULL;
area->next = NULL;
- area->score = 0;
+ area->last_use = 0;
/* Add it to the free areas */
pExaScr->info->offScreenAreas = area;
+ pExaScr->offScreenCounter = 1;
ExaOffscreenValidate (pScreen);
diff --git a/exa/exa_priv.h b/exa/exa_priv.h
index 89f4718..e41f46a 100644
--- a/exa/exa_priv.h
+++ b/exa/exa_priv.h
@@ -120,6 +120,7 @@ typedef struct {
Bool checkDirtyCorrectness;
unsigned disableFbCount;
Bool optimize_migration;
+ unsigned offScreenCounter;
} ExaScreenPrivRec, *ExaScreenPrivPtr;
/*
More information about the xorg-commit
mailing list