[PATCH] Request review for KSharedDataCache

[Michael Pyne]

On Saturday, April 10, 2010 06:42:19 Oswald Buddenhagen wrote:
> moin,
> 
> On Sat, Apr 10, 2010 at 12:54:51AM -0400, Michael Pyne wrote:
> > I think it's at least in good enough shape to get some eyeballs on it
> > other than mine.
> 
> backreferencing from the page table to the entry it contains is only
> ever interesting during defragmentation, which is done seldomly and by
> only one process at a time. consequently, it would be acceptable to
> build up the backlink information only when it is needed, making it
> possible to turn the page table into a bitmap and thus making it 32
> times smaller (btw, the comment indicates that you intended to make it a
> qint16 in fact).

It's something I thought about, but haven't been able to convince myself is 
worth the extra implementation effort yet. Although I realize it's very 
important to get it right the first time so that we can avoid binary 
incompatible changes later. I'll see if it can be done without too much 
effort.

> the note about aligning to the os page size (*) for performance is
> incorrect - one should only minimize the number of crossed page
> boundaries (and as one can save/add exactly one extra crossing, the
> impact is bigger for smaller objects).
> 
> (*) which is btw typically 4k on 32bit and 8k on 64bit, not 1k as the
> default size together with the comments suggest. the sysconf() call can
> be used to determine it dynamically.

Yeah, good point, those comments were from around when I first started. I 
think I use the proper sysconf() call elsewhere when positioning the start of 
the pages (another reason it's OK in a lot of cases for the page table to be 
32 times larger)

> for an 16x16 icon cache, a page size of 1k will already cause a lot of
> slack. for a background image cache it will cause some unnecessary
> allocation overhead.
> consequently i think the page size should be user-configurable.

I was thinking it would be a ton of work but honestly all I have to do is 
embed sharedPage::PAGE_SIZE into the cache header so I can see about making 
this adjustable for cache creation. Either that or just add an enum for 
expected item sizes and use that to determine an appropriate page size.

> i've also been pondering to suggest a more modern tree based allocator
> with no paging at all, but this most probably makes no sense for the
> scalability requirements of a cache.

Paging wasn't my first idea, but it seemed easiest to implement while still 
meeting most of the requirements. The other problem is I don't often have to 
program in a no-dynamic-allocation class so it's hard for me to find 
algorithms that operate well in this mode without requiring malloc.

> nitpick: you often seem to forget the space between control flow keyword
> and opening parenthesis.

Hmm, yes, good point, I'm still in JuK hacking mode, I need to convert it a 
bit to conform to the kdelibs style policy.

> > +class KDEUI_EXPORT KSharedDataCache
> 
> this class belongs into kdecore.

Now that you mention it, that's exactly right. I'll have to figure out where 
to stash it.

> > +{
> > +public:
> > +    /*
> > +     * Creates and attaches to an icon cache.
> 
> no, it doesn't. ;)

Yeah, that's one of the things I noted at the end of my email. I'll seek out 
and destroy those extraneous old comments. :)

> > +    KSharedDataCache(const QString &cacheName, unsigned defaultCacheSize
> > = 0); +
> 
> i think the default size is a property just like the others. ergo it
> does not belong into the c'tor (except as a convenience overload maybe)
> and it should be dynamically changeable. yes, it is harder to implement
> that, but the user should not be concerned with it. and the end user
> does not want to discard the cache just to grow it.

I had actually added code to support such over quite a few hours a couple of 
nights ago, but realized I'd forgotten to account for the fact that the index 
table and page tables would need resized as well, it's not just a matter of 
adding or removing pages.  I can make it a matter of adding or removing pages 
by storing the index and page table sizes with the cache instead of basing 
them off of the cache size, but there's still other issues that make doing 
that non-trivial (for instance, recalculating all of the hash codes with the 
new index table size. It can be done since all the keys are stored, but yuck)

A workaround already exists though: delete the cache and regenerate at the 
larger/smaller size.

I would also quibble about whether the user really wants the cache to grow. 
There are a few bugs about KPixmapCache related to /var filling up, so there's 
at least a few users who would like the cache to never grow again. ;)

> > +    enum CacheRemovalPolicy
> > +    CacheRemovalPolicy entryRemovalPolicy() const;
> > +
> 
> inconsistent and suboptimal naming. use EvictionPolicy.

OK.

> > Index: kdeui/util/kshareddatacache.cpp
> > +template<class T>
> > +T* alignTo(const void *start, uint size = ALIGNOF(T))
> > +{
> > +    quintptr mask = size - 1;
> > +
> > +    // Cast to int-type to handle bit-twiddling
> > +    quintptr basePointer = reinterpret_cast<quintptr>(start);
> > +
> > +    // If we are not aligned, mask off the offending bits and add size
> > (which +    // moves us to the next highest aligned byte in memory)
> > 
> > +    if(basePointer & mask) {
> > +        basePointer = (basePointer & ~mask) + size;
> > +    }
> > +

> basePointer = (basePointer + mask) & ~mask;

Hmm, that does seem nicer. Thanks

> > +    return reinterpret_cast<T *>(basePointer);
> > +}
> > +
> > +// Returns a pointer to a const object of type T, assumed to be offset
> > *BYTES* +// greater than the base address.
> > +template<class T>
> > +const T *offsetAs(const void *const base, qint32 offset)
> > +{
> > +    const char *ptr = reinterpret_cast<const char*>(base);
> > +    return reinterpret_cast<const T*>(ptr + offset);
> 
> this function makes no sense without built-in alignTo as the use cases
> show.

Fair enough, both uses of offsetAs required alignment so I can make it more 
proper that way.

> > +}
> > +
> > +/**
> > + * @return the smallest integer greater than or equal to (@p a / @p b).
> > + */
> > +template<class T>
> > +T intCeil(T a, T b)
> > +{
> > 
> > +    T result = a / b;
> > +    result += (a % b) ? 1 : 0;  // Round up if needed
> > +    return result;
> 
> return (a + b - 1) / b;

Wouldn't this be more susceptible to overflow in the intermediate calculation?

Either way, thanks for the detailed review.

Regards,
 - Michael Pyne
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 836 bytes
Desc: This is a digitally signed message part.
URL: <http://mail.kde.org/pipermail/kde-core-devel/attachments/20100410/52e2afab/attachment.sig>