From: Dave Hansen <dave@linux.vnet.ibm.com>
To: Seth Jennings <sjenning@linux.vnet.ibm.com>
Cc: Dan Magenheimer <dan.magenheimer@oracle.com>,
gregkh@suse.de, devel@driverdev.osuosl.org, ngupta@vflare.org,
cascardo@holoscopio.com, rdunlap@xenotime.net,
linux-kernel@vger.kernel.org
Subject: Re: [PATCH 0/3] staging: zcache: xcfmalloc support
Date: Thu, 01 Sep 2011 09:54:47 -0700 [thread overview]
Message-ID: <1314896087.13161.30.camel@nimitz> (raw)
In-Reply-To: <4E5FB3CF.3020703@linux.vnet.ibm.com>
On Thu, 2011-09-01 at 11:33 -0500, Seth Jennings wrote:
> xcfmalloc is also 0(1) in that the number of freelists
> at that have to be checked is constant and not increasing
> with the number of allocations. The constant hidden
> in the O(1) for finding a suitable block is NUM_FREELISTS.
The algorithm is technically O(n^2) since there are
XCF_MAX_BLOCKS_PER_ALLOC searches through XCF_NUM_FREELISTS. There's
also the reserved pages refill loop, which is linear too.
xcfmalloc's big compromise is that it doesn't do any searching or
fitting. It might needlessly split larger blocks when two small ones
would have worked, for instance.
-- Dave
next prev parent reply other threads:[~2011-09-01 16:54 UTC|newest]
Thread overview: 14+ messages / expand[flat|nested] mbox.gz Atom feed top
2011-08-31 14:40 [PATCH 0/3] staging: zcache: xcfmalloc support Seth Jennings
2011-08-31 14:40 ` [PATCH 1/3] staging: zcache: xcfmalloc memory allocator for zcache Seth Jennings
2011-09-01 15:43 ` Seth Jennings
2011-09-06 23:51 ` Greg KH
2011-08-31 14:40 ` [PATCH 2/3] staging: zcache: replace xvmalloc with xcfmalloc Seth Jennings
2011-08-31 14:40 ` [PATCH 3/3] staging: zcache: add zv_page_count and zv_desc_count Seth Jennings
2011-08-31 19:46 ` [PATCH 0/3] staging: zcache: xcfmalloc support Dan Magenheimer
2011-08-31 22:06 ` Seth Jennings
2011-09-01 15:17 ` Dan Magenheimer
2011-09-01 16:33 ` Seth Jennings
2011-09-01 16:54 ` Dave Hansen [this message]
2011-09-01 22:01 ` Seth Jennings
2011-09-01 23:44 ` Dave Hansen
2011-09-01 22:42 ` Seth Jennings
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=1314896087.13161.30.camel@nimitz \
--to=dave@linux.vnet.ibm.com \
--cc=cascardo@holoscopio.com \
--cc=dan.magenheimer@oracle.com \
--cc=devel@driverdev.osuosl.org \
--cc=gregkh@suse.de \
--cc=linux-kernel@vger.kernel.org \
--cc=ngupta@vflare.org \
--cc=rdunlap@xenotime.net \
--cc=sjenning@linux.vnet.ibm.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).