linux-mm.kvack.org archive mirror
 help / color / mirror / Atom feed
* [PATCH 00/34] mm: Page Replacement Policy Framework
@ 2006-03-22 22:31 Peter Zijlstra
  2006-03-22 22:31 ` [PATCH 01/34] mm: kill-page-activate.patch Peter Zijlstra
                   ` (34 more replies)
  0 siblings, 35 replies; 50+ messages in thread
From: Peter Zijlstra @ 2006-03-22 22:31 UTC (permalink / raw)
  To: linux-mm, linux-kernel
  Cc: Bob Picco, Andrew Morton, IWAMOTO Toshihiro, Peter Zijlstra,
	Christoph Lameter, Wu Fengguang, Nick Piggin, Linus Torvalds,
	Rik van Riel, Marcelo Tosatti

This patch-set introduces a page replacement policy framework and 4 new 
experimental policies.

The page replacement algorithm determines which pages to swap out.
The current algorithm has some problems that are increasingly noticable, even
on desktop workloads. As said, this patch-set introduces 4 new algorithms.

Patches 01 - 25:

  Introduction of the general framework. Piece by piece the current 
use-once LRU-2Q policy is isolated. With each patch a piece of the framework
API is introduced.

Patches 26 - 29: 

  Adds a policy based on CLOCKPro. (http://linux-mm.org/PeterZClockPro2)

Patches 30 - 32: 

  Adds a policy based on CART. (http://linux-mm.org/PeterZCart)

Patch 33: 

  Adds a variation of the CART policy that tries to incorporate 
cyclic access patterns.

Patch 34: 

  Adds a random page replacement policy, simple policy that uses a simple
PRNG to take the decision. More of a toy example than a real alternative.


Individual patches and a rollup can be found here:
  http://programming.kicks-ass.net/kernel-patches/page-replace/


Measurements:

(Walltime, so lower is better)

cyclic-anon ; Cyclic access pattern with anonymous memory.
              (http://programming.kicks-ass.net/benchmarks/cyclic-anon.c)

2.6.16-rc6              14:28
2.6.16-rc6-useonce      15:11
2.6.16-rc6-clockpro     10:51
2.6.16-rc6-cart          8:55
2.6.16-rc6-random     1:09:50

cyclic-file ; Cyclic access pattern with file backed memory.
              (http://programming.kicks-ass.net/benchmarks/cyclic-file.c)

2.6.16-rc6              11:24
2.6.16-rc6-clockpro      8:14
2.6.16-rc6-cart          8:09

webtrace ; Replay of an IO trace from the Umass trace repository
           (http://programming.kicks-ass.net/benchmarks/spc/)

2.6.16-rc6               8:27
2.6.16-rc6-useonce       8:24
2.6.16-rc6-clockpro     10:23
2.6.16-rc6-cart         15:30
2.6.16-rc6-random       15:52

mdb-bench ; Low frequency benchmark.
            (http://linux-mm.org/PageReplacementTesting)

2.6.16-rc6            4:20:44
2.6.16-rc6 (mlock)    3:52:15
2.6.16-rc6-useonce    4:20:59
2.6.16-rc6-clockpro   3:56:17
2.6.16-rc6-cart       4:11:54
2.6.16-rc6-random     5:21:30

(I should do more runs to get error bounds on these values, 
 this is the avg of 3)

Aside from tweaking the policies, the big thing left is NUMA-ify the 
nonresident page trackers.

The results merit further attention, please consider for 2.6.18.

Peter

---

 Documentation/vm/page_replacement_api.txt |  216 +++++++
 fs/cifs/file.c                            |    4 
 fs/exec.c                                 |    4 
 fs/mpage.c                                |    5 
 fs/ntfs/file.c                            |    4 
 fs/ramfs/file-nommu.c                     |    2 
 include/linux/mm_cart_data.h              |   39 +
 include/linux/mm_cart_policy.h            |  141 ++++
 include/linux/mm_clockpro_data.h          |   21 
 include/linux/mm_clockpro_policy.h        |  143 +++++
 include/linux/mm_inline.h                 |   39 -
 include/linux/mm_page_replace.h           |  146 +++++
 include/linux/mm_page_replace_data.h      |   19 
 include/linux/mm_random_data.h            |    9 
 include/linux/mm_random_policy.h          |   47 +
 include/linux/mm_use_once_data.h          |   16 
 include/linux/mm_use_once_policy.h        |  175 ++++++
 include/linux/mmzone.h                    |    8 
 include/linux/nonresident-cart.h          |   34 +
 include/linux/nonresident.h               |   12 
 include/linux/page-flags.h                |   11 
 include/linux/pagevec.h                   |    8 
 include/linux/percpu.h                    |    5 
 include/linux/rmap.h                      |    4 
 include/linux/swap.h                      |   10 
 init/main.c                               |    2 
 mm/Kconfig                                |   32 +
 mm/Makefile                               |    6 
 mm/cart.c                                 |  723 +++++++++++++++++++++++++
 mm/clockpro.c                             |  855 ++++++++++++++++++++++++++++++
 mm/filemap.c                              |   20 
 mm/hugetlb.c                              |    5 
 mm/memory.c                               |   42 +
 mm/mempolicy.c                            |   13 
 mm/mmap.c                                 |    5 
 mm/nonresident-cart.c                     |  362 ++++++++++++
 mm/nonresident.c                          |  167 +++++
 mm/page_alloc.c                           |   76 --
 mm/random_policy.c                        |  292 ++++++++++
 mm/readahead.c                            |    9 
 mm/rmap.c                                 |   26 
 mm/shmem.c                                |    2 
 mm/swap.c                                 |  206 +------
 mm/swap_state.c                           |    6 
 mm/swapfile.c                             |   17 
 mm/useonce.c                              |  489 +++++++++++++++++
 mm/vmscan.c                               |  552 +++----------------
 47 files changed, 4226 insertions(+), 803 deletions(-)

--
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>

^ permalink raw reply	[flat|nested] 50+ messages in thread

end of thread, other threads:[~2006-03-28 23:05 UTC | newest]

Thread overview: 50+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2006-03-22 22:31 [PATCH 00/34] mm: Page Replacement Policy Framework Peter Zijlstra
2006-03-22 22:31 ` [PATCH 01/34] mm: kill-page-activate.patch Peter Zijlstra
2006-03-22 22:32 ` [PATCH 02/34] mm: page-replace-kconfig-makefile.patch Peter Zijlstra
2006-03-22 23:03   ` Jeff Garzik
2006-03-22 22:32 ` [PATCH 03/34] mm: page-replace-insert.patch Peter Zijlstra
2006-03-22 22:32 ` [PATCH 04/34] mm: page-replace-use_once.patch Peter Zijlstra
2006-03-22 22:32 ` [PATCH 05/34] mm: page-replace-generic-pagevec.patch Peter Zijlstra
2006-03-22 22:32 ` [PATCH 06/34] mm: page-replace-activate.patch Peter Zijlstra
2006-03-22 22:32 ` [PATCH 07/34] mm: page-replace-move-macros.patch Peter Zijlstra
2006-03-22 22:33 ` [PATCH 08/34] mm: page-replace-move-scan_control.patch Peter Zijlstra
2006-03-22 22:33 ` [PATCH 09/34] mm: page-replace-move-isolate_lru_pages.patch Peter Zijlstra
2006-03-22 22:33 ` [PATCH 10/34] mm: page-replace-reinsert.patch Peter Zijlstra
2006-03-22 22:33 ` [PATCH 11/34] mm: page-replace-should_reclaim_mapped.patch Peter Zijlstra
2006-03-22 22:33 ` [PATCH 12/34] mm: page-replace-shrink.patch Peter Zijlstra
2006-03-22 22:33 ` [PATCH 13/34] mm: page-replace-mark-accessed.patch Peter Zijlstra
2006-03-22 22:34 ` [PATCH 14/34] mm: page-replace-remove-mm_inline.patch Peter Zijlstra
2006-03-22 22:34 ` [PATCH 15/34] mm: page-replace-rotate.patch Peter Zijlstra
2006-03-22 22:34 ` [PATCH 16/34] mm: page-replace-init.patch Peter Zijlstra
2006-03-22 22:34 ` [PATCH 17/34] mm: page-replace-info.patch Peter Zijlstra
2006-03-22 22:34 ` [PATCH 18/34] mm: page-replace-counts.patch Peter Zijlstra
2006-03-22 22:34 ` [PATCH 19/34] mm: page-replace-data.patch Peter Zijlstra
2006-03-22 22:35 ` [PATCH 20/34] mm: page-replace-pg_flags.patch Peter Zijlstra
2006-03-22 22:35 ` [PATCH 21/34] mm: page-replace-nonresident.patch Peter Zijlstra
2006-03-22 22:35 ` [PATCH 22/34] mm: page-replace-shrink-new.patch Peter Zijlstra
2006-03-22 22:35 ` [PATCH 23/34] mm: page-replace-documentation.patch Peter Zijlstra
2006-03-22 22:35 ` [PATCH 24/34] mm: sum_cpu_var.patch Peter Zijlstra
2006-03-22 22:35 ` [PATCH 25/34] mm: kswapd-writeout-wait.patch Peter Zijlstra
2006-03-22 22:36 ` [PATCH 26/34] mm: clockpro-nonresident.patch Peter Zijlstra
2006-03-22 22:36 ` [PATCH 27/34] mm: clockpro-ignore_token.patch Peter Zijlstra
2006-03-22 22:36 ` [PATCH 28/34] mm: clockpro-PG_reclaim2.patch Peter Zijlstra
2006-03-22 22:36 ` [PATCH 29/34] mm: clockpro-clockpro.patch Peter Zijlstra
2006-03-22 22:36 ` [PATCH 30/34] mm: cart-nonresident.patch Peter Zijlstra
2006-03-22 22:36 ` [PATCH 31/34] mm: cart-PG_reclaim3.patch Peter Zijlstra
2006-03-22 22:37 ` [PATCH 32/34] mm: cart-cart.patch Peter Zijlstra
2006-03-22 22:37 ` [PATCH 33/34] mm: cart-r.patch Peter Zijlstra
2006-03-22 22:37 ` [PATCH 34/34] mm: random.patch Peter Zijlstra
2006-03-22 22:51 ` [PATCH 00/34] mm: Page Replacement Policy Framework Andrew Morton
2006-03-23  2:21   ` Nick Piggin
2006-03-23 21:13     ` Marcelo Tosatti
2006-03-23  4:01   ` Rik van Riel
2006-03-23 20:53   ` Marcelo Tosatti
2006-03-23 18:15     ` Linus Torvalds
2006-03-23 18:26       ` Rik van Riel
2006-03-23 18:48       ` Diego Calleja
2006-03-23 19:03       ` Peter Zijlstra
2006-03-23 22:30       ` Marcelo Tosatti
2006-03-23 20:49         ` Linus Torvalds
2006-03-23 20:59           ` Rik van Riel
2006-03-24 15:06       ` Helge Hafting
2006-03-28 23:05       ` Elladan

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox