On Fri, Dec 30, 2005 at 11:42:44PM +0100, Peter Zijlstra wrote:

From: Peter Zijlstra <redacted>

Originally started by Rik van Riel, I heavily modified the code
to suit my needs.

The nonresident code approximates a clock but sacrifices precision in order
to accomplish faster lookups.

The actual datastructure is a hash of small clocks, so that, assuming an 
equal distribution by the hash function, each clock has comparable order.

TODO:
 - remove the ARC requirements.

Signed-off-by: Peter Zijlstra <redacted>

<snip>

+ *
+ *
+ * Modified to work with ARC like algorithms who:
+ *  - need to balance two FIFOs; |b1| + |b2| = c,
+ *
+ * The bucket contains four single linked cyclic lists (CLOCKS) and each
+ * clock has a tail hand. By selecting a victim clock upon insertion it
+ * is possible to balance them.
+ *
+ * The first two lists are used for B1/B2 and a third for a free slot list.
+ * The fourth list is unused.
+ *
+ * The slot looks like this:
+ * struct slot_t {
+ *         u32 cookie : 24; // LSB
+ *         u32 index  :  6;
+ *         u32 listid :  2;
+ * };

8 and 16 bit accesses are slower than 32 bit on i386 (Arjan pointed this out sometime ago).

Might be faster to load a full word and shape it as necessary, will see if I can do 
something instead of talking. ;)

+/*
+ * For interactive workloads, we remember about as many non-resident pages
+ * as we have actual memory pages.  For server workloads with large inter-
+ * reference distances we could benefit from remembering more. 
+ */

This comment is bogus. Interactive or server loads have nothing to do
with the inter reference distance. To the contrary, interactive loads
have a higher chance to contain large inter reference distances, and
many common server loads have strong locality.

<snip>

What is the meaning of "NR_lost" ? 

+
+#define NR_listid	3
+#define NR_found	0x80000000

--
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/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>