I ran a brief series of tests on a small crash box. the intention was to
see what sort of figures and conclusions could be gathered with VM Regress
in it's current public release. VM Regress is the beginnings of a tool
that ultimatly aims to answer questions about the VM by testing and
benchmarking individual parts of it. The conclusions drawn here are
extremly ad-hoc so take them with a very large grain of salt.
4 tests were run on each machine each related to anonymous memory used in
a mmaped region. Two reference patterns were used. smooth_sin and
smooth_sin-random . Both sets show a sin curve when the number of times
each page is referenced is graphed (See the green line in the graph Pages
Present/Swapped). With smooth_sin, the pages are reffered to in order.
With smooth_sin-random, the pages are referenced in a random order but the
amount of times a page is referenced.
Both patterns are tested with 2,000,000 page references made to a mmaped
region. The first memory mapped region is 25000 pages large, about the
size of physical memory on the machine. The second was with 50000.
Unfortunatly detailed statistical information is unavailable, but some
conclusions can still be drawn. Statistical information is aimed to be
available at least by 0.9
Test 1 - smooth-sin_25000
http://www.csn.ul.ie/~mel/vmr/2.4.19/smooth_sin_25000/mapanon.html
http://www.csn.ul.ie/~mel/vmr/2.4.19-rmap14a/smooth_sin_25000/mapanon.html
Behaviour is pretty much comparable. The average page access times look
roughly the same so at the very least the performance is similiar. rmap14a
did perform faster but hte test wasn't long enough to be conclusive. All
in all, when enough physical memory is avilable, rmap14a and stock will
perform roughly the same with a linear reference pattern and enough memory
is available.
Test 2 - smooth-sin-random_25000
http://www.csn.ul.ie/~mel/vmr/2.4.19/smooth_sin-random_25000/mapanon.html
http://www.csn.ul.ie/~mel/vmr/2.4.19-rmap14a/smooth_sin-random_25000/mapanon.html
here, the average performanceremains roughly the same. It is interesting
to note that rmap14a had periodic large access times to pages and it's
unclea. Despite this, rmap14a still completed the test faster. So again,
with enough memory available, the performance remains roughly the same
even with a relatively random page reference pattern
Test 3 - smooth_sin_50000
http://www.csn.ul.ie/~mel/vmr/2.4.19/smooth_sin_50000/mapanon.html
http://www.csn.ul.ie/~mel/vmr/2.4.19-rmap14a/smooth_sin_50000/mapanon.html
This test is interesting. Remember that the references are linear in
memory. At about the 1,000,000 page reference, physical memory is
exhausted. Both tests completed in the same time so in "raw performance"
they would appear the same but not so. The time access graph shows that
for most of the test, rmap14a performed much better on average except
for the occasional large spikes. At the end, it degrades very quickly but
is still faster than the stock kernel about about 300000 microseconds to
access a page which the unscaled graphs show
http://www.csn.ul.ie/~mel/vmr/2.4.19/smooth_sin_50000/mapanon-time-unscaled.png
http://www.csn.ul.ie/~mel/vmr/2.4.19-rmap14a/smooth_sin_50000/mapanon-time-unscaled.png
This would appear consistent with reports that the stock kernel degrades
slowly where rmap seems to fall apart really quickly in some situations.
It is suspected that the large periodic spikes are where the proper page
to select out is found but it's pure guesswork and VM Regress is not at
the point where it can investigate more.
The second point of note is the present pages at the end of the test.
stock makes no attempt to keep certain pages in memory. When physical
memory is out, it swaps out enitre processes unconditionally. rmap14a
tries to keep the proper pages in memory and the page reference vs
presense graph shows that it did. stock has a large block of pages
present, rmap14a had swapped out some pages from the beginning of the
test.
In this case, stock just happened to swap out correctly because the pages
remove were not going to be used again in this particular case
Test 4 - smooth_sin-random
http://www.csn.ul.ie/~mel/vmr/2.4.19/smooth_sin-random_50000/mapanon.html
http://www.csn.ul.ie/~mel/vmr/2.4.19-rmap14a/smooth_sin-random_50000/mapanon.html
With this test, the page references are in random order so determining
which page to remove is much more difficult. rmap14a completed this test
almost 10 minutes quicker than stock.
The average time for the stock kernel is consistently bad. I am guessing
that this is because the kernel consistently ends up swapping out the
entire process. rmap has periods of quick accesses with unfortunatly large
spikes because it is trying to keep the right pages in memory and a lot of
the time gets it right. This is better than stock kernel which never keeps
the right pages in memory.
Conclusion
It is hard to draw solid conclusions because large gaps still exist in the
data but some can be drawn. I am sure an experienced VM developer will be
able to draw much more reliable conclusions :-)
First, when enough physical memory is available, rmap and stock perform
more or less the same so appreciatable overhead is not introduced for
normal anonymous memory use.
Second, when memory is tight, the type of memory reference behaviour will
determine how good or bad the two will perform. With a strictly linear
pattern, stock will perform better because it just dumps all the old pages
en-mass. I seriously doubt this reference is common.
For other patterns with large anonymous page use, rmap is more likely to
perform better because it tries to keep anonymous pages in memory. Even
with a totally random pattern, it'll perform reasonably well.
Lastly, it is obvious from the tests that for deciding which page to swap,
age is more important than frequency but that is already known. The page
age graphs are on the way and will be available in VM Regress 0.7
--
Mel Gorman
MSc Student, University of Limerick
http://www.csn.ul.ie/~mel
On Monday 26 August 2002 00:22, Mel Gorman wrote:
> 4 tests were run on each machine each related to anonymous memory used in
> a mmaped region. Two reference patterns were used. smooth_sin and
> smooth_sin-random . Both sets show a sin curve when the number of times
> each page is referenced is graphed (See the green line in the graph Pages
> Present/Swapped). With smooth_sin, the pages are reffered to in order.
> With smooth_sin-random, the pages are referenced in a random order but the
> amount of times a page is referenced.
Could you please provide pseudocode, to specify these reference patterns
more precisely?
--
Daniel
On Mon, 26 Aug 2002, Daniel Phillips wrote:
> Could you please provide pseudocode, to specify these reference patterns
> more precisely?
>
Rather than providing pseudo code, here is a link to the actual function
that generates the smooth_sin references
http://www.csn.ul.ie/~mel/vmr/smooth_sin.html
It is really crude and written to generate any type of data until I
found the time to generate more realistic data which is a project in
itself. Anyone who wants to generate better data only has to edit the
References.pm file.
It takes there inputs
references - number of references to generate
range - the size in pages of the region to reference
output - the output filename
the function has three parts
part 1: Plot a sin wave so that the sum of all the integer values of each
part of it would generate enough references to satisify at least
half of the requessted number
part 2: Starting at the beginning of the range, reference each page in a
linear pattern until all the required references are generated
part 3: Dump all references to disk
now that I think of it, it would have made more sense to begin with the
linear reference pattern and then generate the sin curve but seeing as
this pattern is nothing resembling real life, I didn't worry about it too
much. It is probably something I should change as it would illustrate
better what pages are kept in memory.
smooth_sin-random
http://www.csn.ul.ie/~mel/vmr/randomize_references.txt
This is a perl script for randomizing an input file. It takes an input
file generated by the smooth_sin function and outputs a randomized version
of it. It is pretty simple
1. For each input reference, output a random number between 0 and range
followed by the input reference
2. Sort the file numerically with sort. This will efficively randomize the
input
3. Reread the randomized input and strip away the generated random number
--
Mel Gorman
MSc Student, University of Limerick
http://www.csn.ul.ie/~mel
On Monday 26 August 2002 17:13, Mel Gorman wrote:
> On Mon, 26 Aug 2002, Daniel Phillips wrote:
>
> > Could you please provide pseudocode, to specify these reference patterns
> > more precisely?
> >
>
> Rather than providing pseudo code, here is a link to the actual function
> that generates the smooth_sin references
>
> http://www.csn.ul.ie/~mel/vmr/smooth_sin.html
>
> It is really crude and written to generate any type of data until I
> found the time to generate more realistic data which is a project in
> itself. Anyone who wants to generate better data only has to edit the
> References.pm file.
>
> It takes there inputs
>
> references - number of references to generate
> range - the size in pages of the region to reference
> output - the output filename
>
> the function has three parts
>
> part 1: Plot a sin wave so that the sum of all the integer values of each
> part of it would generate enough references to satisify at least
> half of the requessted number
> part 2: Starting at the beginning of the range, reference each page in a
> linear pattern until all the required references are generated
> part 3: Dump all references to disk
>
> now that I think of it, it would have made more sense to begin with the
> linear reference pattern and then generate the sin curve but seeing as
> this pattern is nothing resembling real life, I didn't worry about it too
> much. It is probably something I should change as it would illustrate
> better what pages are kept in memory.
The perl script that writes tables isn't too informative without knowing
how the tables are used. Pseudocode that says exactly what your final
reference pattern is would be a lot more useful. Just leave out the part
about generating the tables and express it as if you were computing the
distribution at the same time as generating the references, unless it's
really impossible to do that. I don't think it's impossible to do that
in this case.
It would also be useful to state what you define as a reference. A user
space program read-accesses a single byte from some address?
--
Daniel
On Thu, 29 Aug 2002, Daniel Phillips wrote:
> The perl script that writes tables isn't too informative without knowing
> how the tables are used. Pseudocode that says exactly what your final
> reference pattern is would be a lot more useful.
I guessed that after I thought about it for a while and reworked the
algorithm for 0.7. To make things easier again, I added a new graph to the
reports which is in 0.7 called "Page Index Reference over Time"
see
http://www.csn.ul.ie/~mel/projects/vmregress/output_sample/mmap/read/25000/mapanon.html
It is the second graph. At the beginning, it is at the 0th page and it
moves through the address space over time. A totally random one would make
this graph look like noise. The graph should give a good idea how memory
was referenced.
In 0.6 and with these tests, it would have been a similar curve except the
last page would have been hit around 40000 references before the end of
the test. After that, the pages were referenced in a linear pattern which
was a mistake after reviewing it a bit.
If people are still interested, I'll run a full set of tests again on
2.4.19 and 2.4.19-rmap14a with 0.7 and post up the results complete with
the page reference information so you don't have to guess this time. It
takes about a full day to run a complete series. Any taker?
> It would also be useful to state what you define as a reference. A user
> space program read-accesses a single byte from some address?
>
A reference in this test was reading a full page of information using
copy_from_user()
--
Mel Gorman
MSc Student, University of Limerick
http://www.csn.ul.ie/~mel
