Re: [hackers] Re: Page Coloring Defines in vm_page.h
On Wed, Jun 25, 2003, David Gilbert wrote: Matthew == Matthew Dillon [EMAIL PROTECTED] writes: Matthew The primes are designed such that the page allocation Matthew code covers *ALL* the free lists in the array, so it will Matthew still be able to find any available free pages if its first Matthew choice(s) are empty. Matthew For example, prime number 3 an array size 8 will scan the Matthew array in the following order N = (N + PRIME) Matthew (ARRAY_SIZE_MASK). N = (N + 3) 7: Matthew 0 3 6 1 4 7 2 5 ... 0 Matthew As you can see, all the array entries are covered before Matthew the sequence repeats. So if we want a free page in array Matthew slot 0 but the only free pages available happen to be in Matthew array slot 5, the above algorithm is guarenteed to find it. Matthew Only certain prime number / power-of-2-array size Matthew combinations have this effect, but it is very easy to write a Matthew little program to test combinations and find the numbers best Matthew suited to your goals. For the mathematically inclined, 3 would be a 'generator' of the group. That's the part I already know. I want to know why 4 MB and 2 MB caches use primes less than 32, 1 MB caches use primes less than 16, 512K caches use a non-prime, and 256K caches use primes smaller than 8. The code refers to PQ_HASH_SIZE, which has never existed as far as I can tell... ___ [EMAIL PROTECTED] mailing list http://lists.freebsd.org/mailman/listinfo/freebsd-hackers To unsubscribe, send any mail to [EMAIL PROTECTED]
Re: [hackers] Re: Page Coloring Defines in vm_page.h
David Schultz wrote: On Wed, Jun 25, 2003, David Gilbert wrote: Matthew == Matthew Dillon [EMAIL PROTECTED] writes: Matthew The primes are designed such that the page allocation Matthew code covers *ALL* the free lists in the array, so it will Matthew still be able to find any available free pages if its first Matthew choice(s) are empty. Matthew For example, prime number 3 an array size 8 will scan the Matthew array in the following order N = (N + PRIME) Matthew (ARRAY_SIZE_MASK). N = (N + 3) 7: Matthew 0 3 6 1 4 7 2 5 ... 0 Matthew As you can see, all the array entries are covered before Matthew the sequence repeats. So if we want a free page in array Matthew slot 0 but the only free pages available happen to be in Matthew array slot 5, the above algorithm is guarenteed to find it. Matthew Only certain prime number / power-of-2-array size Matthew combinations have this effect, but it is very easy to write a Matthew little program to test combinations and find the numbers best Matthew suited to your goals. For the mathematically inclined, 3 would be a 'generator' of the group. That's the part I already know. I want to know why 4 MB and 2 MB caches use primes less than 32, 1 MB caches use primes less than 16, 512K caches use a non-prime, and 256K caches use primes smaller than 8. The code refers to PQ_HASH_SIZE, which has never existed as far as I can tell... Substitute PQ_L2_SIZE for PQ_HASH_SIZE in those comments. Going a step further, globally substituting PQ_COLORS for PQ_L2_SIZE would make sense. PQ_L2_SIZE is a misleading name. (Please consider this encouragement to commit such a change. :-)) Alan ___ [EMAIL PROTECTED] mailing list http://lists.freebsd.org/mailman/listinfo/freebsd-hackers To unsubscribe, send any mail to [EMAIL PROTECTED]
Re: Page Coloring Defines in vm_page.h
Bruce M Simpson wrote: Something occurred to me whilst I was re-reading the 'Design Elements' article over the weekend; our page coloring algorithm, as it stands, might not be optimal for non-Intel CPUs. Actually, it does very well for most architectures, and was originally developed into product for SPARC and MIPS (by Sun and MIPS Inc., respectively). There are 29 research papers that specifically mention page coloring; here is the citation: http://citeseer.nj.nec.com/cs?q=page+coloringcs=1 I'm going to claim that this is one of the better ones (;^)), mostly because it has some nice real statistics, and represents a rather fun approach to the problem, which doesn't actually involve page coloring, and touches on the rather neat idea of doing cache affinity as part of the scheduler operation: http://citeseer.nj.nec.com/410298.html Also, it has a couple of nice references to related works you aren't going to find online: you will need to find yourself a technical library; references 1, 6, 8, 9, and 12 especially. - Why is this important? The vm code as it stands assumes that we colour for L2 cache. This might not be optimal for all architectures, or, indeed, forthcoming x86 chips. The code previously colored for both L1 and L2. It turns out that the penalty you pay for L1 set overlap is relatively low, comparatively, due to the difference in comparative size between L1 and L2. See also: http://citeseer.nj.nec.com/kessler92page.html - The defines in vm_page.h seem to assume a 4-way set associative cache organization. Yes. This was the most common L2 cache hardware arrangement at the time. There were a couple of good postings on page coloring on the FreeBSD lists back in the mid 1990's by John Dyson, who was the original implementor of both the page coloring code and the unified VM and buffer cache code, which Poul was complaining was incomplete, in the recent FS stacking thread on -arch. You can probably find them in the archives on Minnie (Warren Toomey's archival machine). - If someone could fill me in on how the primes are arrived at that would be very helpful. It's an attempt to get a perfect hash without collision; page coloring relies on avoiding cache line overlap, if at all possible (sometimes it isn't, which is why the page coloring compiler work and the cache affinity scheduler are such intriguing ideas, to me at least, though the compiler work would probably be incredibly hard to tune in any useful fashion to work across an entire CPU family, rather than specific CPU instances). -- Terry ___ [EMAIL PROTECTED] mailing list http://lists.freebsd.org/mailman/listinfo/freebsd-hackers To unsubscribe, send any mail to [EMAIL PROTECTED]
Re: Page Coloring Defines in vm_page.h
Bruce M Simpson wrote: Yes, that was what I was really getting at; if you look at how PQ_L2_SIZE is computed from PQ_CACHESIZE, it implies 4-way set associative is the default optimization. This is fine for Intel chips but not for AMD ones. FWIW, I'd like to see this automatically optimized, if possible; when the code was originally written, you couldn't easily get the cache size for either cache, except by having a human tell the code. The names of the definitions as they stand are perhaps slightly misleading in this respect. PQ_L2_SIZE might be better renamed PQ_SETSIZE and defined in terms of PQ_CACHESIZE/PQ_NSETS. Per before: the L1 code was ripped out; the ripping out left all sorts of little pieces of gore like this lying around. Personally, I'd like to see the L1 code put back in, now that L1 caches are getting huge, and the L2 caches aren't so much larger than the L1, on some processors. The page queue structures are sized according to the number of cache colors in use. These structures are allocated once for the lifetime of the kernel. So auto-tuning for an architecture's L2 cache organization at boot-time is not out of the question. Yes, if you can get the information on the cache sizes from the hardware... this may pessimize (even worse) older hardware, so you may even want to consider turning it off, in those cases. Whilst it might be said that people who want to diddle with these defines will generally know what they're doing anyway, it would be nice to make these optimizations a wee bit more accessible; also, as we grow to support more Tier 1 architectures, having page coloring work 'out-of-the-box' across them might be seen as a desirable feature. I'd like to know people's feelings on this. I would really, really like to see this happen. There's some original research ahppening on FreeBSD, but not enough (IMO). really want to color for the L2 cache, though; the L1 instruction and data caches are usually small and hard to color for, and occasional false sharing there doesn't cost much if you have an L2. There used to be L1 coloring support, but it was removed some time ago. I concur. So does the paper I referenced earlier. I'm not so sure that it's not dated. The cost of accessing L1 is down, but the realtive cost of reloading it from L2 is getting up there; there's about a factor of 7, between the fastest L2 and the fastest P4 it could be attached to, for example. Worst case, it'd be nice to diddle the code to get benchmark numbers from the Novell Standard SMP workload, just to see what the effects are. The second paper I referenced implied from their numbers that the benefits for kernel would approach 10%, and user space 15%, assuming you did everything right (which is what their cache preloading on context switch simulated, in the limit). Good question. I know why they're prime numbers slightly smaller than a power of two, but I can't figure out how that power of two was chosen. I'd need to work this out before being confident enough to even begin adding the above feature. They are for perfect hashing to avoid cache line collisions. The best reference on getting the numbers for this is the Sun Micrososystems paper from (I think) 1993 or so. John Dyson's posts are also relevent (sorry to repeat myself here, but at the time his posts really helped me understand the Sun paper much better). -- Terry ___ [EMAIL PROTECTED] mailing list http://lists.freebsd.org/mailman/listinfo/freebsd-hackers To unsubscribe, send any mail to [EMAIL PROTECTED]
[hackers] Re: Page Coloring Defines in vm_page.h
Matthew == Matthew Dillon [EMAIL PROTECTED] writes: Matthew The primes are designed such that the page allocation Matthew code covers *ALL* the free lists in the array, so it will Matthew still be able to find any available free pages if its first Matthew choice(s) are empty. Matthew For example, prime number 3 an array size 8 will scan the Matthew array in the following order N = (N + PRIME) Matthew (ARRAY_SIZE_MASK). N = (N + 3) 7: Matthew 0 3 6 1 4 7 2 5 ... 0 Matthew As you can see, all the array entries are covered before Matthew the sequence repeats. So if we want a free page in array Matthew slot 0 but the only free pages available happen to be in Matthew array slot 5, the above algorithm is guarenteed to find it. Matthew Only certain prime number / power-of-2-array size Matthew combinations have this effect, but it is very easy to write a Matthew little program to test combinations and find the numbers best Matthew suited to your goals. For the mathematically inclined, 3 would be a 'generator' of the group. Dave. -- |David Gilbert, Velocet Communications. | Two things can only be | |Mail: [EMAIL PROTECTED] | equal if and only if they | |http://daveg.ca | are precisely opposite. | =GLO ___ [EMAIL PROTECTED] mailing list http://lists.freebsd.org/mailman/listinfo/freebsd-hackers To unsubscribe, send any mail to [EMAIL PROTECTED]
Re: Page Coloring Defines in vm_page.h
On Tue, Jun 24, 2003, Bruce M Simpson wrote: Hi all, Something occurred to me whilst I was re-reading the 'Design Elements' article over the weekend; our page coloring algorithm, as it stands, might not be optimal for non-Intel CPUs. Spiel: - Dillon's VM article talks about L1 cache reference, rather than L2. This is a fair assumption to make as previously L2 caches were not located on the die. With most i386 processors these days the cache is located on the die and runs at full CPU clock speed, as well as having a dedicated cache access bus on the die. Notably Katmai's runs at half the processor speed; Coppermine and later run the cache at full processor speed. The coloring is based on the size and associativity of the cache, not its speed relative to the processor's. - Why is this important? The vm code as it stands assumes that we colour for L2 cache. This might not be optimal for all architectures, or, indeed, forthcoming x86 chips. The code makes no assumptions about whether the cache is primary or secondary, except that the variables are named that way, and the default is optimized for a 4-way 512K cache. (You could determine the actual L2 cache size at boot time via the CPUID instruction on PII and later Intel chips if you wanted to.) You really want to color for the L2 cache, though; the L1 instruction and data caches are usually small and hard to color for, and occasional false sharing there doesn't cost much if you have an L2. There used to be L1 coloring support, but it was removed some time ago. - If someone could fill me in on how the primes are arrived at that would be very helpful. Good question. I know why they're prime numbers slightly smaller than a power of two, but I can't figure out how that power of two was chosen. ___ [EMAIL PROTECTED] mailing list http://lists.freebsd.org/mailman/listinfo/freebsd-hackers To unsubscribe, send any mail to [EMAIL PROTECTED]
Re: Page Coloring Defines in vm_page.h
On Tue, Jun 24, 2003 at 06:17:48AM -0700, David Schultz wrote: The coloring is based on the size and associativity of the cache, not its speed relative to the processor's. Yes. My comments were originally aimed at the fact the article seemed to imply we were coloring for L1 rather than L2, sorry about the confusion. Also, I was offline at the weekend; reading the CVS history confirms I'm on the right track. The code makes no assumptions about whether the cache is primary or secondary, except that the variables are named that way, and the default is optimized for a 4-way 512K cache. (You could determine the actual L2 cache size at boot time via the CPUID instruction on PII and later Intel chips if you wanted to.) You Yes, that was what I was really getting at; if you look at how PQ_L2_SIZE is computed from PQ_CACHESIZE, it implies 4-way set associative is the default optimization. This is fine for Intel chips but not for AMD ones. The names of the definitions as they stand are perhaps slightly misleading in this respect. PQ_L2_SIZE might be better renamed PQ_SETSIZE and defined in terms of PQ_CACHESIZE/PQ_NSETS. The page queue structures are sized according to the number of cache colors in use. These structures are allocated once for the lifetime of the kernel. So auto-tuning for an architecture's L2 cache organization at boot-time is not out of the question. Whilst it might be said that people who want to diddle with these defines will generally know what they're doing anyway, it would be nice to make these optimizations a wee bit more accessible; also, as we grow to support more Tier 1 architectures, having page coloring work 'out-of-the-box' across them might be seen as a desirable feature. I'd like to know people's feelings on this. Currently, the only arch in our tree which maintains cache organization info is sparc64. amd64 reports this info but does not maintain it. really want to color for the L2 cache, though; the L1 instruction and data caches are usually small and hard to color for, and occasional false sharing there doesn't cost much if you have an L2. There used to be L1 coloring support, but it was removed some time ago. I concur. - If someone could fill me in on how the primes are arrived at that would be very helpful. Good question. I know why they're prime numbers slightly smaller than a power of two, but I can't figure out how that power of two was chosen. I'd need to work this out before being confident enough to even begin adding the above feature. Never knowingly bikeshedded, BMS ___ [EMAIL PROTECTED] mailing list http://lists.freebsd.org/mailman/listinfo/freebsd-hackers To unsubscribe, send any mail to [EMAIL PROTECTED]
Re: Page Coloring Defines in vm_page.h
: - The page queue structures are sized according to these :defines at boot-time. : : - If someone could fill me in on how the primes are arrived at that :would be very helpful. : :Comments/discussion/correction welcomed, it would be good to get some :feedback on this before I start patching my tree. : :BMS The primes are designed such that the page allocation code covers *ALL* the free lists in the array, so it will still be able to find any available free pages if its first choice(s) are empty. For example, prime number 3 an array size 8 will scan the array in the following order N = (N + PRIME) (ARRAY_SIZE_MASK). N = (N + 3) 7: 0 3 6 1 4 7 2 5 ... 0 As you can see, all the array entries are covered before the sequence repeats. So if we want a free page in array slot 0 but the only free pages available happen to be in array slot 5, the above algorithm is guarenteed to find it. Only certain prime number / power-of-2-array size combinations have this effect, but it is very easy to write a little program to test combinations and find the numbers best suited to your goals. -Matt Matthew Dillon [EMAIL PROTECTED] ___ [EMAIL PROTECTED] mailing list http://lists.freebsd.org/mailman/listinfo/freebsd-hackers To unsubscribe, send any mail to [EMAIL PROTECTED]
Re: Page Coloring Defines in vm_page.h
On Tue, Jun 24, 2003 at 02:38:13PM +0100, Bruce M Simpson wrote: The names of the definitions as they stand are perhaps slightly misleading in this respect. PQ_L2_SIZE might be better renamed PQ_SETSIZE and defined in terms of PQ_CACHESIZE/PQ_NSETS. [snip] Bikeshed, but it would still be nice to document the above. BMS ___ [EMAIL PROTECTED] mailing list http://lists.freebsd.org/mailman/listinfo/freebsd-hackers To unsubscribe, send any mail to [EMAIL PROTECTED]
Re: Page Coloring Defines in vm_page.h
Matthew Dillon wrote: For example, prime number 3 an array size 8 will scan the array in the following order N = (N + PRIME) (ARRAY_SIZE_MASK). N = (N + 3) 7: 0 3 6 1 4 7 2 5 ... 0 As you can see, all the array entries are covered before the sequence repeats. Only certain prime number / power-of-2-array size combinations have this effect, U Actually, Matt, the property you've stated is much more common than you seem to believe. If you generate a sequence N = ( N + Stride ) % ArraySize then you will visit every element of (0 ... ArraySize-1) as long as the Stride and ArraySize are relatively prime (have no prime factors in common). In particular, if the ArraySize is a power of 2, then it suffices for the stride to be odd. Like 1, for example. ;-) The real motivation for a prime stride is avoiding hash table collisions. Many hash functions have cyclic properties; for example, using a memory address as a hash code tends to give multiples of 4, 8, and 16. You want your stride to be relatively prime to any cycles in the hash function. Since hash functions tend to be hard to analyze, you generally just pick a number that's likely to be relatively prime to any cycles in the hash function; a large prime is a good candidate. For that reason, many hash table algorithms simply select the largest prime less than the array size as the stride. Tim Kientzle ___ [EMAIL PROTECTED] mailing list http://lists.freebsd.org/mailman/listinfo/freebsd-hackers To unsubscribe, send any mail to [EMAIL PROTECTED]
Re: Page Coloring Defines in vm_page.h
: :Matthew Dillon wrote: : For example, prime number 3 an array size 8 will scan the array in : the following order N = (N + PRIME) (ARRAY_SIZE_MASK). : N = (N + 3) 7: : : 0 3 6 1 4 7 2 5 ... 0 : : As you can see, all the array entries are covered before the sequence : repeats. Only certain prime number / power-of-2-array size : combinations have this effect, : :U Actually, Matt, the property you've stated is much more :common than you seem to believe. If you generate a sequence :N = ( N + Stride ) % ArraySize :then you will visit every element of (0 ... ArraySize-1) as long as I was just answering a question. Most people aren't interested in that level of detail (or, if they are, I'm sure Terry would happily chime in), they just want to know the purpose. -Matt ___ [EMAIL PROTECTED] mailing list http://lists.freebsd.org/mailman/listinfo/freebsd-hackers To unsubscribe, send any mail to [EMAIL PROTECTED]
Re: Page Coloring Defines in vm_page.h
Hi,
:U Actually, Matt, the property you've stated is much more
:common than you seem to believe. If you generate a sequence
:N = ( N + Stride ) % ArraySize
:then you will visit every element of (0 ... ArraySize-1) as long as
I was just answering a question. Most people aren't interested in that
level of detail (or, if they are, I'm sure Terry would happily chime in),
they just want to know the purpose.
I admit, this has nothing to do with FreeBSD, but this thread aroused my
interest ...
Theorem (informal version)
For every array length n and every stride p, that has no common
divisors with n (apart from 1), the function
f_{i+1} = f_i + p mod n
will generated a sequence that will visit very element of
{0, ..., n-1}.
Since this is a tail recursion, one can also write:
f_i = i*p mod n
Theorem (formal version):
For every n, p in Z, gcd (n, p) = 1 the function
f: Z_n - Z_n
f: i |- i*p mod n
is a bijection.
Proof:
f is a surjection (we can choose every i in {0, ..., n-1} we want to).
f is a injection.
Proof by contradiction. Let's assume that f is not an injection, i.e.
there exist j != k mod n such that
f (j) = f (k) mod n =
j*p = k*p mod n
By definition this means, that there exists t, such that
j*p - k*p = t*n =
(j-k)*p = t*n
Since p and n are relatively prime, this condition can only hold if
(j-k) = s*n, which is a contradiction of our assumption that
j != k mod n.
Hence, f is a bijection.
Since array lengths, that are powers of 2, are relatively prime to every
odd number, every stride apart from 2 will work.
Regards,
Simon
___
[EMAIL PROTECTED] mailing list
http://lists.freebsd.org/mailman/listinfo/freebsd-hackers
To unsubscribe, send any mail to [EMAIL PROTECTED]
Re: Page Coloring
:If I remember correctly from reading a thesis (can't remember its :author) on the page coloring which I believe widely introduced this :concept, page coloring adds a lot of efficiency to the directly :mapped caches but even for the 2-way caches is nearly pointless. : :-SB For the most part, yes. 2-way set associative caches handle standard compiled programs reasonably well. 4-way set associative caches handle standard interpreted programs reasonably well. Page-coloring helps keep things consistent between program runs but typically has very little effect on machines which already have set-associative caches. The main thing is the consistency - for example, if you have a medium-sized buffer in memory which you are accessing randomly, page coloring will prevent degenerate cache cases that can occur in cases where the VM system (without coloring) happens to assign the same cache page to every page of the buffer. But you wouldn't notice unless your buffer had more then N pages (N = set associativity). For the same reason, 'random' also works fairly well (just in a less consistent way), which is why page coloring doesn't add much when doing a performance comparison on a system with a 2-way or better associative cache. -Matt To Unsubscribe: send mail to [EMAIL PROTECTED] with unsubscribe freebsd-hackers in the body of the message
Re: Page Coloring
In article [EMAIL PROTECTED], Mike Smith [EMAIL PROTECTED] wrote: It looks about right, but page colouring is pointless unless and until we can determine the processor cache characteristics at runtime. Which we can't. Why can't we do this at least on the i386 with the CPUID instruction, initial %eax == 2? It returns cache size, associativity, and line size for both the L1 and L2 caches. As far as I can tell, it works for the Pentium Pro and subsequent processors. John -- John Polstra [EMAIL PROTECTED] John D. Polstra Co., Inc.Seattle, Washington USA Disappointment is a good sign of basic intelligence. -- Chögyam Trungpa To Unsubscribe: send mail to [EMAIL PROTECTED] with unsubscribe freebsd-hackers in the body of the message
Re: Page Coloring
:In article [EMAIL PROTECTED], :Mike Smith [EMAIL PROTECTED] wrote: : : It looks about right, but page colouring is pointless unless and until we : can determine the processor cache characteristics at runtime. : : Which we can't. : :Why can't we do this at least on the i386 with the CPUID instruction, :initial %eax == 2? It returns cache size, associativity, and line :size for both the L1 and L2 caches. As far as I can tell, it works :for the Pentium Pro and subsequent processors. : :John :-- : John Polstra [EMAIL PROTECTED] Well, first of all the page coloring is not pointless with the sizes hardwired. The cache characteristics do not have to match exactly for page coloring to work. The effectiveness is like a log-graph, and you don't lose a lot by guessing wrong. Once you get past a designated cache size of 4-pages or so you've already reaped 90% of the benefit on systems which use N-way (2, 4, 8) associative caches (which is most systems these days). For systems with direct-mapped caches you reap 90% of the benefits once you get past 16 pages or so. Since most L1 caches these days are at least 16K and most L2 caches these days are at least 64K (and often much higher, such as on the IA32), our hardwired page coloring constants wind up being about 95% effective across the entire range of chips our OS currently runs on. -Matt To Unsubscribe: send mail to [EMAIL PROTECTED] with unsubscribe freebsd-hackers in the body of the message
Re: Page Coloring
In article [EMAIL PROTECTED], Matt Dillon [EMAIL PROTECTED] wrote: :In article [EMAIL PROTECTED], :Mike Smith [EMAIL PROTECTED] wrote: : : It looks about right, but page colouring is pointless unless and until we : can determine the processor cache characteristics at runtime. : : Which we can't. : :Why can't we do this at least on the i386 with the CPUID instruction, :initial %eax == 2? It returns cache size, associativity, and line :size for both the L1 and L2 caches. As far as I can tell, it works :for the Pentium Pro and subsequent processors. : :John :-- : John Polstra [EMAIL PROTECTED] Well, first of all the page coloring is not pointless with the sizes hardwired. The cache characteristics do not have to match exactly for page coloring to work. The effectiveness is like a log-graph, and you don't lose a lot by guessing wrong. Once you get past a designated cache size of 4-pages or so you've already reaped 90% of the benefit on systems which use N-way (2, 4, 8) associative caches (which is most systems these days). For systems with direct-mapped caches you reap 90% of the benefits once you get past 16 pages or so. Since most L1 caches these days are at least 16K and most L2 caches these days are at least 64K (and often much higher, such as on the IA32), our hardwired page coloring constants wind up being about 95% effective across the entire range of chips our OS currently runs on. Yes, I understand that. I'm just trying to find out why Mike keeps saying we cannot determine the processor cache characteristics at runtime. John -- John Polstra [EMAIL PROTECTED] John D. Polstra Co., Inc.Seattle, Washington USA Disappointment is a good sign of basic intelligence. -- Chögyam Trungpa To Unsubscribe: send mail to [EMAIL PROTECTED] with unsubscribe freebsd-hackers in the body of the message
Re: Page Coloring
: :If I added this to a man page would I be telling the truth :). : :Note, these are my notes and not the exact text that I would :add, and I have not bother with anything to do with object :coloring etc. I just want to make sure I've got this part :down. : :Chad It's a good description but it might be better to simplify it a bit. You don't need to go into that level of detail. There is a short page coloring explanation at the end of my VM article which might be more suitable to a man page: http://www.daemonnews.org/21/freebsd_vm.html -Matt (quoted from the article): Ok, so now onto page coloring: All modern memory caches are what are known as *physical* caches. They cache physical memory addresses, not virtual memory addresses. This allows the cache to be left alone across a process context switch, which is very important. But in the UNIX world you are dealing with virtual address spaces, not physical address spaces. Any program you write will see the virtual address space given to it. The actual *physical* pages underlying that virtual address space are not necessarily physically contiguous! In fact, you might have two pages that are side by side in a processes address space which wind up being at offset 0 and offset 128K in *physical* memory. A program normally assumes that two side-by-side pages will be optimally cached. That is, that you can access data objects in both pages without having them blow away each other's cache entry. But this is only true if the physical pages underlying the virtual address space are contiguous (insofar as the cache is concerned). This is what Page coloring does. Instead of assigning *random* physical pages to virtual addresses, which may result in non-optimal cache performance , Page coloring assigns *reasonably-contiguous* physical pages to virtual addresses. Thus programs can be written under the assumption that the characteristics of the underlying hardware cache are the same for their virtual address space as they would be if the program had been run directly in a physical address space. Note that I say 'reasonably' contiguous rather than simply 'contiguous'. From the point of view of a 128K direct mapped cache, the physical address 0 is the same as the physical address 128K. So two side-by-side pages in your virtual address space may wind up being offset 128K and offset 132K in physical memory, but could also easily be offset 128K and offset 4K in physical memory and still retain the same cache performance characteristics. So page-coloring does *NOT* have to assign truely contiguous pages of physical memory to contiguous pages of virtual memory, it just needs to make sure it assigns contiguous pages from the point of view of cache performance and operation. To Unsubscribe: send mail to [EMAIL PROTECTED] with unsubscribe freebsd-hackers in the body of the message
Re: Page Coloring
: Since most L1 caches these days are at least 16K and most L2 caches : these days are at least 64K (and often much higher, such as on the IA32), : our hardwired page coloring constants wind up being about 95% effective : across the entire range of chips our OS currently runs on. : :Yes, I understand that. I'm just trying to find out why Mike keeps :saying we cannot determine the processor cache characteristics at :runtime. : :John :-- : John Polstra [EMAIL PROTECTED] You can find out from the cpuid or something like that, but it's probably easier to simply do it programmatically, or not bother at all. It's not worth the effort. We would not reap any additional benefit from knowing. It is interesting to note that one effect of the page-coloring code is that the VM CACHE and FREE VM page queues are actually multi-queues, which means that when I extend the SMP locking down into them we will wind up with fine-grained locking for memory allocations. But before I can even begin contemplating that I have to change the way the vm_page BUSY'ing stuff works so page operations (such as allocations) can occur without having to hold long term mutexes. -Matt To Unsubscribe: send mail to [EMAIL PROTECTED] with unsubscribe freebsd-hackers in the body of the message
Re: Page Coloring
In article [EMAIL PROTECTED], Matt Dillon [EMAIL PROTECTED] wrote: :Yes, I understand that. I'm just trying to find out why Mike keeps :saying we cannot determine the processor cache characteristics at :runtime. : :John You can find out from the cpuid or something like that, Yes. As I said, you can find out from the CPUID instruction by passing it the value 2 in %eax. but it's probably easier to simply do it programmatically, or not bother at all. It's not worth the effort. We would not reap any additional benefit from knowing. Opinions on that seem to vary wildly. Mike said just the opposite. Since that was not the point I addressed, I'll let the two of you debate it out. John -- John Polstra [EMAIL PROTECTED] John D. Polstra Co., Inc.Seattle, Washington USA Disappointment is a good sign of basic intelligence. -- Chögyam Trungpa To Unsubscribe: send mail to [EMAIL PROTECTED] with unsubscribe freebsd-hackers in the body of the message
Re: Page Coloring
On Sun, Aug 05, 2001 at 12:20:36PM -0700, Matt Dillon wrote: It's a good description but it might be better to simplify it a bit. You don't need to go into that level of detail. There is a short page coloring explanation at the end of my VM article which might be more suitable to a man page: http://www.daemonnews.org/21/freebsd_vm.html That got pulled in to the documentation project a while ago, and can be found at http://www.freebsd.org/doc/en_US.ISO8859-1/articles/vm-design/index.html This makes it pretty easy for us (you) to keep it up to date as you change FreeBSD's VM system. . . :-) N -- FreeBSD: The Power to Serve http://www.freebsd.org/ FreeBSD Documentation Project http://www.freebsd.org/docproj/ --- 15B8 3FFC DDB4 34B0 AA5F 94B7 93A8 0764 2C37 E375 --- PGP signature
Re: Page Coloring
Yes, I understand that. I'm just trying to find out why Mike keeps saying we cannot determine the processor cache characteristics at runtime. Because I believed we couldn't. It appears I'm wrong. 8) The only question left really then is whether it's worth actually trying to tune for cache size, or if our defaults are good enough, whether we shouldn't just keep them as they are... -- ... every activity meets with opposition, everyone who acts has his rivals and unfortunately opponents also. But not because people want to be opponents, rather because the tasks and relationships force people to take different points of view. [Dr. Fritz Todt] V I C T O R Y N O T V E N G E A N C E To Unsubscribe: send mail to [EMAIL PROTECTED] with unsubscribe freebsd-hackers in the body of the message
Re: Page Coloring
Matt Dillon wrote: Well, first of all the page coloring is not pointless with the sizes hardwired. The cache characteristics do not have to match exactly for page coloring to work. The effectiveness is like a log-graph, and you don't lose a lot by guessing wrong. Once you get past a designated cache size of 4-pages or so you've already reaped 90% of the benefit on systems which use N-way (2, 4, 8) associative caches (which is most systems these days). For systems with direct-mapped caches you reap 90% of the benefits once you get past 16 pages or so. If I remember correctly from reading a thesis (can't remember its author) on the page coloring which I believe widely introduced this concept, page coloring adds a lot of efficiency to the directly mapped caches but even for the 2-way caches is nearly pointless. -SB To Unsubscribe: send mail to [EMAIL PROTECTED] with unsubscribe freebsd-hackers in the body of the message
Re: Page Coloring
On Sun, Aug 05, 2001 at 10:33:08PM +0100, Nik Clayton wrote: On Sun, Aug 05, 2001 at 12:20:36PM -0700, Matt Dillon wrote: It's a good description but it might be better to simplify it a bit. You don't need to go into that level of detail. There is a short page coloring explanation at the end of my VM article which might be more suitable to a man page: http://www.daemonnews.org/21/freebsd_vm.html That got pulled in to the documentation project a while ago, and can be found at http://www.freebsd.org/doc/en_US.ISO8859-1/articles/vm-design/index.html This makes it pretty easy for us (you) to keep it up to date as you change FreeBSD's VM system. . . Thanks, I will use some of this text if I can, and be sure to give Matt credit. If that was too much detail, is there a place for the detail? Next week I am going to attempt to determine the cache size via the cpuid instruction, and export some of the calculation parameters via sysctl (to help with some simulations that we are going to be doing). Given that nobody has done this yet, am I missing something that will bite me? The intel IA32 manuals seem to indicate that most of the (intel) cpu's in use today should support cpuid 2 lookup? Thanks. Chad To Unsubscribe: send mail to [EMAIL PROTECTED] with unsubscribe freebsd-hackers in the body of the message
Re: Page Coloring
If I added this to a man page would I be telling the truth :). Note, these are my notes and not the exact text that I would add, and I have not bother with anything to do with object coloring etc. I just want to make sure I've got this part down. It looks about right, but page colouring is pointless unless and until we can determine the processor cache characteristics at runtime. Which we can't. Plus the code hardcodes all the relevant numbers. The code needs fixing as well as documenting. 8( -- ... every activity meets with opposition, everyone who acts has his rivals and unfortunately opponents also. But not because people want to be opponents, rather because the tasks and relationships force people to take different points of view. [Dr. Fritz Todt] V I C T O R Y N O T V E N G E A N C E To Unsubscribe: send mail to [EMAIL PROTECTED] with unsubscribe freebsd-hackers in the body of the message
Re: page coloring
It skips queue pq[index PQ_L2_MASK]. That's correct. The inline function vm_page_list_find() in vm_page.h has already failed to allocate a page of the desired color, index, and so _vm_page_list_find() is called to allocate a page of ANY other color it can find. Oh, yes. I didn't look at that macro. Mikulas To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-hackers" in the body of the message
Re: page coloring
On Thu, Nov 23, 2000 at 12:48:09PM -0800, Mike Smith wrote: Isn't the page coloring algoritm in _vm_page_list_find totally bogus? No, it's not. The comment is, however, misplaced. It describes the behavior of an inline function in vm_page.h, and not the function it precedes. Hrm. My comment was based on John Dyson's own observations on its behaviour, and other discussions which concluded that the code wasn't flexible enough (hardcoded assumptions on cache organisation, size etc.) Yes, it would be nice if it was "auto-configuring", because many people who use it misconfigure it. They configure the number of colors based upon the size of their cache rather than cache size/degree of associativity. (Having too many colors makes it less likely that you'll get a page of the right color when you ask for one because that queue will be empty.) Overall, it's my experience that people have absurb expectations of page coloring. They think of it as an optimization. It's not. It's better thought of as a necessary evil: Suppose you're writing a numerical application and either you or your compiler goes to a lot of trouble to "block" the algorithm for the L2 cache size. If the underlying OS doesn't do page coloring, it's likely that your program will still experience conflict misses despite your efforts to avoid them. Furthermore, you'll see a different number of conflict misses each time you run the program (assuming the typical random page allocation strategies). So, the execution time will vary. In short, page coloring simply provides a machine whose performance is more deterministic/predictable. Alan P.S. I noticed that I mistakenly cc'ed my previous message to -current rather than -hackers. I've changed it back to -hackers. To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-hackers" in the body of the message
