[RFC][PATCH 0/6] CART Implementation

a.p.zijlstra
2005-08-27T22:02:49Z

Hi All,

(now split as per request)

After another day of hard work I feel I have this CART implementation
complete.

It survives a pounding and the stats seem pretty stable.

The things that need more work:
1) the hash function seems pretty lousy
2) __cart_remember() called from shrink_list() needs zone->lru_lock

The whole non-resident code is based on the idea that the hash function
gives an even spread so that:

B1_j B1
------ ~ ----
B2_j B2

However after a pounding the variance in (B1_j - B2_j) as given by the
std. deviation: sqrt(<x^2> - <x>^2) is around 10. And this for a bucket
with 57 slots.

The other issue is that __cart_remember() needs the zone->lru_lock. This
function is called from shrink_list() where the lock is explicitly
avoided, so this seems like an issue. Alternatives would be atomic_t for
zone->nr_q or a per cpu counter delta. Suggestions?

Also I made quite some changes in swap.c and vmscan.c without being an
expert on the code. Did I foul up too bad?

Then ofcourse I need to benchmark, suggestions?

Some of this code is shamelessly copied from Rik van Riel, other parts
are inspired by code from Rahul Iyer.

Any comments appreciated.

Kind regards,

Peter Zijlstra