On Thu, 13 Apr 2000, Joseph A. Martin wrote:
>:: Andrea Arcangeli <andrea@suse.de>
> >On Wed, 12 Apr 2000, Joseph A. Martin wrote:
> >
> >>+ while ((page = alloc_pages(GFP_USER, order)) != 0) {
> >
> >It has bad complexity problems. An allocation have to keep working in O(1)
> >as now.
>
>I don't think I understand. Is "It" the whole thing or the quoted
>line? What does "0(1)" mean?
The whole thing due the quoted line.
Note it's not 0(1) but O(1). In this context it means that right now when
you want a page, you get it at a fixed cost that doesn't change in
function of how many pages are available and how many of them are of the
kind we are interested about.
Take these two symbols:
O(1)
O(N)
N is a variable number. Assume N to be infinite. O(N) means that an
algorithm needs to check all the N objects to give you a result, and in
our case it will take infinite time. If the algorithm would had O(1)
complexity it would instead take the usual fixed time despite of how many
N objects exists in the system.
> >BTW, that's not either static or dynamic page coloring but it's "random"
> >page coloring ;) and it can't work if you spawn multiple tasks at the same
> >time.
>
>That depends on the size of the cache and the size of the tasks. In
>fact, if the total memory used by the simultaneous tasks is less than
>the cache size, then not only will these tasks not compete with
>themselves, but also they won't compete with each other for cache. If
This looks a red herring to me, IMHO you'll always run out of cache
someway at least at once per boot. Otherwise you should replace the ram
with the cache ;).
Andrea
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.rutgers.edu
Please read the FAQ at http://www.tux.org/lkml/
This archive was generated by hypermail 2b29 : Sat Apr 15 2000 - 21:00:21 EST