Re: how not to write a search algorithm

[Daniel Phillips <phillips@arcor.de>]

On Monday 05 August 2002 01:03, Andrew Morton wrote:
> The list walk is killing us now.   I think we need:
> 
> struct pte_chain {
> 	struct pte_chain *next;
> 	pte_t *ptes[L1_CACHE_BYTES/4 - 4];
> };

Strongly agreed.  A full 64 bytes might be a little much though.  Let me see, 
for 32 bytes the space breakeven is 4X sharing, for 64 bytes it's 8X and 
we'll rarely hit that, except in contrived benchmarks.

A variation on this idea makes the size of the node a property of an antire 
page's worth of nodes, so that nodes of different sizes can be allocated.  
The node size can be recorded at the base of the page, or in a vector of 
pointers to such pages.  Moving from size to size is by copying rather than 
list insertion, and only the largest size needs a list link.

-- 
Daniel
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/