[interfacekit] Re: BBlockCache bug

So, I have the tests done now.  You can find them here:

http://www.magma.ca/~jrand/BBlockCacheTests.zip

I don't have CVS access so if someone can volunteer to check this in, I 
would appreciate it.

However, there is a minor issue.  Marcus has checked in a linked list 
implementation which looks very good and much better than the one which 
was there before.  But, there is a deviation in his implementation from 
Be's.

Imagine this scenario with a 4 block cache.  The blocks on the cache 
are A, B, C, D.  If a caller gets five blocks from the cache, the 
following is returned: A, B, C, D, E.  The first four come from the 
cache and the fifth (E) is allocated dynamically to satisfy the caller.  
What happens if the caller then repeatedly Save()'s E and then performs 
a Get() again over
and over again?

In Be's implementation, when E is Save()'ed, E is placed on the list of 
free blocks in the cache.  Even though E was not in the cache 
initially, since it is the right size it isn't freed and just put in 
the cache for a caller to get later.  So, if E is Save()'ed and gotten 
again repeatedly, Be's implementation does this:
  - put E on the cache
  - take E off the cache and pass back to the caller
  - put E on the cache
  - etc.

This means that Be intends that the cache will hold up to 4 blocks in 
this case but the total number of blocks on the cache plus those handed 
out through the Get() method may exceed 4 perhaps by a great deal.

But in Marcus' implementation, if you Get() 5 elements from a 4 element 
cache and then return one, he will not start putting elements back into 
the cache right away.  When the 5th element is gotten from the cache, 
it tracks that there is an "excess block" oustanding.  While excess 
blocks are outstanding, any attempt to return one of them to the cache 
will actually result in them being freed.  So, with Marcus' 
implementation, the following would occur if E is Save()'ed and gotten 
again repeatedly:
  - E is freed
  - a new block (possibly the same as E) is allocated
  - the block is freed again
  - etc.

Marcus' implementation guarantees that there will not be any blocks in 
the cache if there are 4 or more blocks returned by Get() which are 
still outstanding.  Be's implementation will be faster in this case by 
avoiding the calls to the memory allocator.  Plus, my tests detect this 
difference in behaviour and will fail on Marcus' current 
implementation.

In the zip file, I have two updated implementations of BBlockCache:
  - src/kits/support/BBlockCache.new and headers/os/support/
BBlockCache.new: This is a minor modification of Marcus' implementation 
based on linked lists to match Be's behaviour when returning blocks to 
an empty cache.

  - src/kits/support/BBlockCache.jer and headers/os/support/
BBlockCache.jer: This is an implementation which I expect is 99.9% the 
same as Be's.  Its Get() and Save() methods are O(1) and the cache is 
implemented as an array of (void *)'s.

Both implementations pass the tests with very similar performance.  
Either is fine and I try to be as "egoless" as possible about these 
things.  Truth be known, Marcus' implementation does have some great 
debugging features like setting and checking magic numbers in it which 
we should probably hold on to.

So, I am looking for someone to decide what should get checked in and 
then do it for me.  Thanks!

> 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).
> 
> CU, Ingo

--
Jeremy Rand
jrand@xxxxxxxx

Other related posts: