lkml.org 
[lkml]   [2011]   [Sep]   [1]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
SubjectRe: [PATCH 0/3] staging: zcache: xcfmalloc support
From
Date
On Thu, 2011-09-01 at 17:01 -0500, Seth Jennings wrote:
> I was seeing n as the number of allocations. Since
> XCF_MAX_BLOCKS_PER_ALLOC and XCF_NUM_FREELISTS are constant (i.e.
> not increasing with the number of allocations) wouldn't it be
> O(1)?

It's the difference between your implementation and the _algorithm_
you've chosen. If someone doubled XCF_MAX_BLOCKS_PER_ALLOC and
XCF_NUM_FREELISTS, you'd see the time quadruple, not stay constant.
That's a property of the _algorithm_.

> > 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.
>
> Splitting a larger block is the last option. I might not
> be understanding you correctly, but find_remove_block() does try to
> find the optimal block to use, which is "searching and fitting" in my
> mind.

I don't want to split hairs on the wording. It's obvious, though, that
xcfmalloc does not find _optimal_ fits. It also doesn't use the
smallest-possible blocks to fit the alloction. Consider if you wanted a
1000 byte allocation (with 10 100-byte buckets and no metadata for
simplicity), and had 4 blocks:

900
500,500,500

I think it would split a 500 into 100,400, and leave the 400:

500,500
400

It took the largest (most valuable) block, and split a 500 block when it
didn't have to. The reason it doesn't do this is that it doesn't
_search_. It just indexes and guesses. That's *fast*, but it errs on
the side of speed rather than being optimal. That's OK, we do it all
the time, but it *is* a compromise. We should at least be thinking of
the cases when this doesn't perform well.

-- Dave



\
 
 \ /
  Last update: 2011-09-02 01:47    [W:0.049 / U:0.228 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site