Re: page coloring
Hi. 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. 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. Rather than choose a random page, the odd-looking loop in _vm_page_list_find() tries to find a page whose color is unlikely to equal the neighboring pages in the vm object if colored allocation for them succeeded. Alan To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-current" in the body of the message
Re: page coloring
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.) If this isn't applicable, my apologies for confusing the matter. -- ... 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-current" in the body of the message
Re: Significant page coloring improvement
Ah, interesting. I understand the second bit. The first bit seems somewhat odd, though - the automatic page coloring adjustment made by _vm_object_allocate() doesn't work well enough for kmem_object? -Matt Matthew Dillon dil...@backplane.com :When reviewing the VM code regarding another issue (another significant :VM contributor had found an interesting anomoly), I noticed that the :coloring wasn't as complete as it should be. : :Attached is a patch that appears to make a reasonable improvement in :performance, when using both my slightly more advanced VM kernel, and :also the stuff in -current. I seem to see a fork() only performance :improvement of about 10% on a 2 processor SMP PPro, using lmbench. On :vfork (which isn't completely implemented on a PPro, but is still faster :than fork), the improvement appears to be about 5%. : :Of course, any page coloring improvement is dependent on alot of factors, :but the missing object coloring handling is a problem... : :-- :John | Never try to teach a pig to sing, :dy...@iquest.net | it makes one look stupid :jdy...@nc.com | and it irritates the pig. : :... :Index: vm/vm_object.c :=== :RCS file: /local/home/ncvs/src/sys/vm/vm_object.c,v :retrieving revision 1.144 :diff -r1.144 vm_object.c :215a216 : kmem_object-pg_color = (kernel_object-pg_color + PQ_L2_SIZE/4) PQ_L2_MASK; :945a947 : result-pg_color = (source-pg_color + OFF_TO_IDX(*offset)) PQ_L2_MASK; : :--ELM918368107-256-0_-- : :To Unsubscribe: send mail to majord...@freebsd.org :with unsubscribe freebsd-current in the body of the message : To Unsubscribe: send mail to majord...@freebsd.org with unsubscribe freebsd-current in the body of the message
Re: Significant page coloring improvement
Matthew Dillon said: Ah, interesting. I understand the second bit. The first bit seems somewhat odd, though - the automatic page coloring adjustment made by _vm_object_allocate() doesn't work well enough for kmem_object? The problem with it was that there appeared to be a clash. The color allocation in _vm_object_allocate is ad-hoc, and tuned for a general case, essentially randomizing the coloring (but also statistically coloring processes approximately correctly.) My original code (and I forget if the current code does this) attempts to color the objects (or pages in the objects) so that there isn't much overlap in normal processes. There is still an opportunity to improve the color allocations. I also have some mods that remove the L1 coloring (since it is overkill, and just complicates the code.) L2 coloring (or L3 as appropriate on machines like Alphas) is all that is needed!!! I did the L1 coloring for an exercise, and forgot reality when I committed the code :-). (Okay, that isn't quite true, I did think that L1 coloring would have been useful -- but after alot of thought and paper research, have decided that L1 page coloring for a small L1 cache is kind-of useless.) If you want to see the L1 mods and perhaps remove the L1 coloring, you are welcome and it would be a good thing to remove it. The L1 mods are pretty much straight-forward, and might be a compromise between removing the coloring all together and keeping all of the complexity. I do suggest that the base color allocation (and proper management of the coloring) would be a good day or so project to clean-up. Again, right now, the coloring looks okay, and the kernel page coloring choices were just a degenerate case. The low level coloring code is good -- so improving the upper level mgmt is fertile ground. -- John | Never try to teach a pig to sing, dy...@iquest.net | it makes one look stupid jdy...@nc.com | and it irritates the pig. To Unsubscribe: send mail to majord...@freebsd.org with unsubscribe freebsd-current in the body of the message
Re: Significant page coloring improvement
:Matthew Dillon said: : : Ah, interesting. I understand the second bit. The first bit seems : somewhat odd, though - the automatic page coloring adjustment made : by _vm_object_allocate() doesn't work well enough for kmem_object? : : :The problem with it was that there appeared to be a clash. The color :allocation in _vm_object_allocate is ad-hoc, and tuned for a general :case, essentially randomizing the coloring (but also statistically :coloring processes approximately correctly.) My original code (and :I forget if the current code does this) attempts to color the objects :(or pages in the objects) so that there isn't much overlap in normal :processes. The standard increment in _vm_object_allocate() is: if ( size (PQ_L2_SIZE / 3 + PQ_PRIME1)) incr = PQ_L2_SIZE / 3 + PQ_PRIME1; else incr = size; next_index = (next_index + incr) PQ_L2_MASK; Which, for the kmem_object you are overriding with: kmem_object-pg_color = (kernel_object-pg_color + PQ_L2_SIZE/4) PQ_L2_MASK; Would it make more sense to change vm_object_allocate() to simply increment by PQ_L2_SIZE/4 plus an additional 1 if it rolls over and then not do anything special for kmem_object? Like this: next_index += PQ_L2_SIZE/4; if (next_index PQ_L2_MASK) next_index = (next_index + 1) PQ_L2_MASK; I don't see much point in trying to include the object size in the pg_color optimization since an objects tends to be acted upon in a non-contiguous manner relative to other objects. In fact, dividing PQ_L2_SIZE by 3 and adding 5 ( for PQ_NORMALCACHE case ) doesn't even give us a pseudo-random distribution since that increment is '10', which is an even number. :If you want to see the L1 mods and perhaps remove the L1 coloring, you are :welcome and it would be a good thing to remove it. The L1 mods are pretty :much straight-forward, and might be a compromise between removing the coloring :all together and keeping all of the complexity. If the L1 coloring doesn't help, I'd love to remove it. It wouldn't be a big deal, though, since presumably the only two routines we are talking about are vm_page_select_free() and vm_page_list_find(). Still, there are a bunch of #if 0's ( surrounding the now defunct object-page_hint stuff ) in vm_page.c that I could clean up at the same time, so lay those diffs on me! :I do suggest that the base color allocation (and proper management of the :coloring) would be a good day or so project to clean-up. Again, right :now, the coloring looks okay, and the kernel page coloring choices were just :a degenerate case. The low level coloring code is good -- so improving :the upper level mgmt is fertile ground. : :dy...@iquest.net | it makes one look stupid -Matt Matthew Dillon dil...@backplane.com To Unsubscribe: send mail to majord...@freebsd.org with unsubscribe freebsd-current in the body of the message
Re: Significant page coloring improvement
: next_index += PQ_L2_SIZE/4; : if (next_index PQ_L2_MASK) : next_index = (next_index + 1) PQ_L2_MASK; Oops, make that: next_index += PQ_L2_SIZE/4; if (next_index PQ_L2_MASK) next_index = (next_index + PQ_PRIME1) PQ_L2_MASK; Or even just: next_index = (next_index + PQ_PRIME1) PQ_L2_MASK; Both seem to work pretty well w/ lmbench, though nothing really sticks its nose out. -Matt Matthew Dillon dil...@backplane.com To Unsubscribe: send mail to majord...@freebsd.org with unsubscribe freebsd-current in the body of the message
Re: Significant page coloring improvement
Matthew Dillon said: : next_index += PQ_L2_SIZE/4; : if (next_index PQ_L2_MASK) : next_index = (next_index + 1) PQ_L2_MASK; Oops, make that: next_index += PQ_L2_SIZE/4; if (next_index PQ_L2_MASK) next_index = (next_index + PQ_PRIME1) PQ_L2_MASK; Or even just: next_index = (next_index + PQ_PRIME1) PQ_L2_MASK; Both seem to work pretty well w/ lmbench, though nothing really sticks its nose out. The reason why you might want to incr by PQ_L2_SIZE/N (or some other large number) is that it will likely decrease conflicts for larger objects. Note that the color should be chosen with more context (virtual address or memory region type like shared lib) than I originally implemented. There are better approaches that take into consideration dynamic conflicts. Such dynamic conflicts might be more complex to determine, and a good static choice adds only minimal overhead, yet provides some improvement. I suggest that until a major project can be undertaken, the static stuff is the right thing. It is easy to screw things up (as you can tell by my original choice for coloring being suboptimal, but not necessarily destructive.) I am agnostic regarding the coloring scheme, but I am glad that removing L1 coloring might be acceptable... If anything, it will decrease instruction cache footprint, and not cause a significant (hopefully any) decrease in performance. I will try to package up the patches (it is an issue of merging them in from my codebase.) They are essentially a result of hand optimizing the case of setting PQ_L1_SIZE to 1. Give me a day or so to put it together. -- John | Never try to teach a pig to sing, dy...@iquest.net | it makes one look stupid jdy...@nc.com | and it irritates the pig. To Unsubscribe: send mail to majord...@freebsd.org with unsubscribe freebsd-current in the body of the message
Re: Significant page coloring improvement
Matthew Dillon said: Ah, interesting. I understand the second bit. The first bit seems somewhat odd, though - the automatic page coloring adjustment made by _vm_object_allocate() doesn't work well enough for kmem_object? There appears to be a clash. I haven't really carefully evaluate it, but did see a small improvement. (I hate tweaks though!!!) I guess until a more scientific approach can be established, better tweaks are better than worse tweaks :-). -- John | Never try to teach a pig to sing, dy...@iquest.net | it makes one look stupid jdy...@nc.com | and it irritates the pig. To Unsubscribe: send mail to majord...@freebsd.org with unsubscribe freebsd-current in the body of the message
Significant page coloring improvement
When reviewing the VM code regarding another issue (another significant VM contributor had found an interesting anomoly), I noticed that the coloring wasn't as complete as it should be. Attached is a patch that appears to make a reasonable improvement in performance, when using both my slightly more advanced VM kernel, and also the stuff in -current. I seem to see a fork() only performance improvement of about 10% on a 2 processor SMP PPro, using lmbench. On vfork (which isn't completely implemented on a PPro, but is still faster than fork), the improvement appears to be about 5%. Of course, any page coloring improvement is dependent on alot of factors, but the missing object coloring handling is a problem... -- John | Never try to teach a pig to sing, dy...@iquest.net | it makes one look stupid jdy...@nc.com | and it irritates the pig. Index: vm/vm_object.c === RCS file: /local/home/ncvs/src/sys/vm/vm_object.c,v retrieving revision 1.144 diff -r1.144 vm_object.c 215a216 kmem_object-pg_color = (kernel_object-pg_color + PQ_L2_SIZE/4) PQ_L2_MASK; 945a947 result-pg_color = (source-pg_color + OFF_TO_IDX(*offset)) PQ_L2_MASK;
