[interfacekit] Re: BBlockCache bug

On 2003-08-29 at 00:53:27 [+0200], Ingo Weinhold wrote:
> 
> On 2003-08-29 at 01:59:12 [+0200], Marcus Overhagen wrote:
> > > I noticed the same thing about the destructor and the implementation.  I
> > > coded up a new
> > > implementation last night using fMark as the delimiter between used and
> > > unused blocks so
> > > it works like this:
> > > 
> > > 1. The fCache member is an array of (void *)'s.  The array is fCacheSize
> > > big and each
> > > element of the array points to a block of memory fBlockSize long.
> > > 
> > > 2. The elements in the array are ordered like this:
> > >      0 ... (fMark - 1) - these pointers are currently in use
> > >      fMark ... (fCacheSize - 1) - these pointers are currently not in 
> > >      use
> > > That way, you only need fMark to know which blocks are in use and which
> > > ones aren't
> > > 
> > > 3. To get a buffer, you just return fCache[fMark] and increment fMark.
> > > This is O(1) which
> > > is good and much better than our current implementation.
> > What happens if fMark is larger than the numbers of existing buffers?
> 
> A new, uncached, one is allocated instead.
> 
> > > 4. To return a buffer back to the cache, it searches from 0 ... (fMark -
> > > 1) to find the
> > > block which is being returned.  Then it swaps the matching element with
> > > the one at (fMark
> > > - 1) and decrements fMark.  Swapping the pointers is a pretty cheap
> > > operation but finding
> > Bad.
> 
> Why?
> 
> > > the buffer in the array is O(n) which isn't the best.  I think Be's
> > > implementation is the
> > Bad.
> >
> > > I have a rough implementation of the above and a couple of simple tests
> > > so far.  I will
> > > try to finish off the tests and compare all three implementations (Be's,
> > > our existing one
> > > and the one proposed above) to see which we should go with.
> > 
> > I'm going to rewrite it using two single linked lists (used and free), 
> > that
> > should be the fastest
> > but still simple implementation. The Get and Save functions will both be
> > O(1).
> 
> If you have to search your used list on Save(), it will be O(n), exactly as
> Be's implementation. Please don't waste you time.
> 
> What one can do to optimize Save() is not to keep track of the used blocks.
> That way you simply check, whether the chunk of memory passed to Save() has
> the right size and, if so, add it to your stack of free blocks. If not, or 
> if
> the cache has reached the maximal number of free blocks, the memory would
> simply be freed. That way both Get() and Save() are O(1).

I had a quick look at the objdump and in fact that's how Be has implemented 
it. fMark is the index of the last free block (i.e. initially fCacheSize - 1) 
-- I would rather rename it to fFreeBlockCount or something like that and 
make it the number of available free blocks (for this seems less error prone 
to me), but that doesn't change the strategy, of course.

CU, Ingo

Other related posts: