Review Request: KImageCache optimization

1 view
Skip to first unread message

Mark Gaiser

unread,
Feb 23, 2012, 1:21:33 PM2/23/12
to David Faure, Michael Pyne, kdelibs
This is an automatically generated e-mail. To reply, visit: http://git.reviewboard.kde.org/r/104052/

Review request for kdelibs, David Faure and Michael Pyne.
By Mark Gaiser.

Description 

I was running KWin through callgrind to see where possible bottlenecks are. I wasn't expecting much since it improved greatly during the 4.8 dev cycle, however one stood out. The saving of PNG images was taking about 1/5th of the time in KWin that i could see directly. That looked like something i might be able to optimize.

What this patch is doing is storing the actual image bits to prevent saving a PNG image to the mmapped cache. That was a hot code path in time (cycles), not even in calls. I've also reduced the amount of memory copies to a bare minimum by adding a rawFind function to KSharedDataCache which fills a QByteArray::fromRawData thus preventing a expensive memory copy. The rawFind is used for looking up an image and fetching it's data without copying it. That is done because QImage seems to make a copy itself internally. I don't have any performance measurements, however, prior to this patch my kwin test was using up ~5.000.000.000 cycles. After this patch it's using up 1.370.000.000. I don't have raw performance numbers to see if the cache itself is actually faster, it certainly has become a lot cheaper to use the cache. Logic wise i would say creating a QImage from the cached data should be way faster now since there is no step involved anymore in decoding the image. Storing is certainly an order of magnitude faster.

Special thanks go to David Faure for helping me a great deal with this.

Testing 

I've also written a bunch of test cases (greatly improved by David Faure) to see if i didn't break anything. According to the test (which is also comparing the actual image bits) it's all passing just fine.

Diffs

  • kdecore/util/kshareddatacache.h (339cecc)
  • kdecore/util/kshareddatacache.cpp (9fe3995)
  • kdeui/tests/CMakeLists.txt (63788f6)
  • kdeui/tests/kimagecachetests.h (PRE-CREATION)
  • kdeui/tests/kimagecachetests.cpp (PRE-CREATION)
  • kdeui/util/kimagecache.cpp (a5bbbe1)

View Diff

Milian Wolff

unread,
Feb 23, 2012, 1:33:42 PM2/23/12
to David Faure, Michael Pyne, kdelibs, Milian Wolff
This is an automatically generated e-mail. To reply, visit: http://git.reviewboard.kde.org/r/104052/ 

given that you have unit tests at hand, why not write a benchmark to get proper before/after numbers that show the impact of this patch?

- Milian


On February 23rd, 2012, 6:21 p.m., Mark Gaiser wrote:

Review request for kdelibs, David Faure and Michael Pyne.
By Mark Gaiser.

Updated Feb. 23, 2012, 6:21 p.m.

Aaron J. Seigo

unread,
Feb 23, 2012, 1:52:47 PM2/23/12
to David Faure, Michael Pyne, kdelibs
This is an automatically generated e-mail. To reply, visit: http://git.reviewboard.kde.org/r/104052/

kdecore/util/kshareddatacache.cpp (Diff revision 1) 
bool KSharedDataCache::insert(const QString &key, const QByteArray &data)
 

    1491
    
            *destination = QByteArray(temp.constData(), temp.size());

  


 





this needs a check on destination being not-null. e.g. if (destination && !temp.isNull()) above









- Aaron J.






On February 23rd, 2012, 6:21 p.m., Mark Gaiser wrote:











Review request for kdelibs, David Faure and Michael Pyne.


By Mark Gaiser.




Updated Feb. 23, 2012, 6:21 p.m.








Description 
Mark Gaiser
unread,
Feb 23, 2012, 2:13:49 PM2/23/12
to David Faure, Michael Pyne, kdelibs

   

    

     
      This is an automatically generated e-mail. To reply, visit:
      http://git.reviewboard.kde.org/r/104052/
     
    

   

   








 
On February 23rd, 2012, 6:33 p.m., Milian Wolff wrote:

 

  
given that you have unit tests at hand, why not write a benchmark to get proper before/after numbers that show the impact of this patch?

 












Right.. That's not exactly easy to "just" do since i would have to read a dir with images, insert it in the cache and read it back from the cache. So not going to do that. What i did do is change the size to "SizeEnormous" so the icon is a bit bigger (128x128) and just let QBENCHMARK do it's thing with insert(write) and find(read). The results are as follows:

-- Before patch --
READ : 0.019 msecs per iteration (total: 79, iterations: 4096)
WRITE: 0.010 msecs per iteration (total: 88, iterations: 8192)

-- After patch --
READ : 0.019 msecs per iteration (total: 79, iterations: 4096)
WRITE: 0.0026 msecs per iteration (total: 87, iterations: 32768)

Reading is equal in speed, writing is ~5x faster after the patch.












- Mark
Mark Gaiser
unread,
Feb 23, 2012, 2:15:38 PM2/23/12
to David Faure, Michael Pyne, kdelibs

   

    

     
      This is an automatically generated e-mail. To reply, visit:
      http://git.reviewboard.kde.org/r/104052/
     
    

   

   











 
On February 23rd, 2012, 6:52 p.m., Aaron J. Seigo wrote:

 

  





 
  

   
    kdecore/util/kshareddatacache.cpp
    

     (Diff revision 1)

    
   
  

 

 
  


   
bool KSharedDataCache::insert(const QString &key, const QByteArray &data)


  

 




 
 



 

  

    
    

    1491
    
            *destination = QByteArray(temp.constData(), temp.size());

  


 




  
this needs a check on destination being not-null. e.g. if (destination && !temp.isNull()) above

 









Ahh, got it. Fixed in code, will update the diff in here in a few minutes.








- Mark
Aaron J. Seigo
unread,
Feb 23, 2012, 2:57:20 PM2/23/12
to David Faure, Michael Pyne, kdelibs

   

    

     
      This is an automatically generated e-mail. To reply, visit:
      http://git.reviewboard.kde.org/r/104052/
     
    

   

   













 
  


   
bool KSharedDataCache::insert(const QString &key, const QByteArray &data)


  

 




 
 



 


  

    
    

    1488
    
    QByteArray temp;

  


  

    
    

    1489
    
    if (rawFind(key, &temp)) {

  


  

    
    

    1490
    
        if (destination && !temp.isNull()) {

  


  

    
    

    1491
    
            *destination = QByteArray(temp.constData(), temp.size());

  


  

    
    

    1492
    
        }

  


  

    
    

    1493
    
        return true;

  


  

    
    

    1494
    
    }

  


  

    
    

    1495
    
    return false;

  


  

    
    

    1496
    
}

  


 





looking at it again, it appears there is room for one more small optimization when destination is null in find(..). if this not a common case, it may not be worthwhile, but it might look sth like:

if (destination) {
     QByteArray temp;
     const bool success = rawFind(key, &temp);
     if (success && destination && !temp.isNull()) {
         *destination = QByteArray(temp.constData(), temp.size());
     }
     return success;
} else {
   return rawFind(key, 0);
}

as this is code in hot-paths it would be nice to make this as efficient as possible without destroying readability/maintainability.









- Aaron J.






On February 23rd, 2012, 7:23 p.m., Mark Gaiser wrote:











Review request for kdelibs, David Faure and Michael Pyne.


By Mark Gaiser.




Updated Feb. 23, 2012, 7:23 p.m.








Description 

 

 

  
   
I was running KWin through callgrind to see where possible bottlenecks are. I wasn't expecting much since it improved greatly during the 4.8 dev cycle, however one stood out. The saving of PNG images was taking about 1/5th of the time in KWin that i could see directly. That looked like something i might be able to optimize.

What this patch is doing is storing the actual image bits to prevent saving a PNG image to the mmapped cache. That was a hot code path in time (cycles), not even in calls. I've also reduced the amount of memory copies to a bare minimum by adding a rawFind function to KSharedDataCache which fills a QByteArray::fromRawData thus preventing a expensive memory copy. The rawFind is used for looking up an image and fetching it's data without copying it. That is done because QImage seems to make a copy itself internally. I don't have any performance measurements, however, prior to this patch my kwin test was using up ~5.000.000.000 cycles. After this patch it's using up 1.370.000.000. I don't have raw performance numbers to see if the cache itself is actually faster, it certainly has become a lot cheaper to use the cache. Logic wise i would say creating a QImage from the cached data should be way faster now since there is no step involved anymore in decoding the image. Storing is certainly an order of magnitude faster.

Benchmark numbers. insert(write) and find(read)

-- Before patch --
READ : 0.019 msecs per iteration (total: 79, iterations: 4096)
WRITE: 0.010 msecs per iteration (total: 88, iterations: 8192)

-- After patch --
READ : 0.019 msecs per iteration (total: 79, iterations: 4096)
WRITE: 0.0026 msecs per iteration (total: 87, iterations: 32768)

Reading is equal in speed, writing is ~5x faster after the patch.

Special thanks go to David Faure for helping me a great deal with this.

  		
 


Christoph Feck
unread,
Feb 23, 2012, 3:55:59 PM2/23/12
to David Faure, Michael Pyne, kdelibs

   

    

     
      This is an automatically generated e-mail. To reply, visit:
      http://git.reviewboard.kde.org/r/104052/
     
    

   

   


















 
  

   
    kdeui/util/kimagecache.cpp
    

     (Diff revision 2)

    
   
  

 

 
  


   
KImageCache::~KImageCache()


  

 




 
 



 

  

    
    

    105
    
    stream << image.format();

  


 





This fails to correctly handle palettized images.

If we do not want to preserve image texts, gamma, and DPI, please document it (the PNG handler did).

Also, did you try setting the compression level for the PNG writer before giving up on compression? The compression is probably wanted. I have not checked if Qt uses quality 0 or 100 for the fastest mode, but the default PNG compression is utterly slow (as you noticed ;)









- Christoph
Mark Gaiser
unread,
Feb 23, 2012, 3:59:58 PM2/23/12
to David Faure, Michael Pyne, kdelibs

   

    

     
      This is an automatically generated e-mail. To reply, visit:
      http://git.reviewboard.kde.org/r/104052/
     
    

   

   










:) Adjusted. If you have another optimization.. please do tell. Otherwise i will update the diff within a few hours. This is how the function looks now:

bool KSharedDataCache::find(const QString &key, QByteArray *destination) const
{
    if (destination) {
        QByteArray temp;
        const bool success = rawFind(key, &temp);
        if (success && destination && !temp.isNull()) {
            *destination = QByteArray(temp.constData(), temp.size());
        }
        return success;
    } else {
        return rawFind(key, 0);
    }
}

Compiles and tested. All pass.
note: rawFind could perhaps use some optimizations as well ;) (and perhaps the internal functions findNamedEntry(..) and page(..)








- Mark
Mark Gaiser
unread,
Feb 23, 2012, 4:08:30 PM2/23/12
to David Faure, Michael Pyne, kdelibs

   

    

     
      This is an automatically generated e-mail. To reply, visit:
      http://git.reviewboard.kde.org/r/104052/
     
    

   

   











 
On February 23rd, 2012, 8:56 p.m., Christoph Feck wrote:

 

  





 
  

   
    kdeui/util/kimagecache.cpp
    

     (Diff revision 2)

    
   
  

 

 
  


   
KImageCache::~KImageCache()


  

 




 
 



 

  

    
    

    105
    
    stream << image.format();

  


 




  
This fails to correctly handle palettized images.

If we do not want to preserve image texts, gamma, and DPI, please document it (the PNG handler did).

Also, did you try setting the compression level for the PNG writer before giving up on compression? The compression is probably wanted. I have not checked if Qt uses quality 0 or 100 for the fastest mode, but the default PNG compression is utterly slow (as you noticed ;)

 









Don't know about that.. Hope someone more knowledgeable could respond in the "image texts, gamma, and DPI".

As for the fastest/slowest mode. No, i haven't tried that. But even then it seems kinda strange to load an image and directly save the exact same image as .png in some mmapped file (which was the behavior). Saving the "compiled" image (the bits) seems more obvious.








- Mark
Christoph Feck
unread,
Feb 23, 2012, 4:40:58 PM2/23/12
to David Faure, Michael Pyne, kdelibs

   

    

     
      This is an automatically generated e-mail. To reply, visit:
      http://git.reviewboard.kde.org/r/104052/
     
    

   

   











 
On February 23rd, 2012, 8:56 p.m., Christoph Feck wrote:

 

  





 
  

   
    kdeui/util/kimagecache.cpp
    

     (Diff revision 2)

    
   
  

 

 
  


   
KImageCache::~KImageCache()


  

 




 
 



 

  

    
    

    105
    
    stream << image.format();

  


 




  
This fails to correctly handle palettized images.

If we do not want to preserve image texts, gamma, and DPI, please document it (the PNG handler did).

Also, did you try setting the compression level for the PNG writer before giving up on compression? The compression is probably wanted. I have not checked if Qt uses quality 0 or 100 for the fastest mode, but the default PNG compression is utterly slow (as you noticed ;)

 




 
On February 23rd, 2012, 9:08 p.m., Mark Gaiser wrote:

 

  
Don't know about that.. Hope someone more knowledgeable could respond in the "image texts, gamma, and DPI".

As for the fastest/slowest mode. No, i haven't tried that. But even then it seems kinda strange to load an image and directly save the exact same image as .png in some mmapped file (which was the behavior). Saving the "compiled" image (the bits) seems more obvious.

 











The KImageCache is not used exclusively for "loaded" images, but also (and especially so) for generated images, e.g. when caching SVG rendered data.

Regarding compression, the type of images that are stored in the cache are usually very compressible, better than text, and thus the memory (or even disk) pressure can be greatly reduced. For example, the 128x128 "text-x-generic" icon is 64 KB uncompressed, while only 13 KB compressed.

I just checked Qt docs. If you use "image.save(buffer, "PNG", quality);" you get uncompressed PNG with quality == 100, and fastest, but moderate compression with quality == 80. Any smaller value improves compression rate, but makes it slower.
Mark Gaiser
unread,
Feb 23, 2012, 2:21:19 PM2/23/12
to David Faure, Michael Pyne, kdelibs

   

    

     
      This is an automatically generated e-mail. To reply, visit:
      http://git.reviewboard.kde.org/r/104052/
     
    

   

   







Review request for kdelibs, David Faure and Michael Pyne.


By Mark Gaiser.




Updated Feb. 23, 2012, 7:21 p.m.





Changes



 

  
   
Added a check for destination existence.

  		
 








Description 

 

 

  
   
I was running KWin through callgrind to see where possible bottlenecks are. I wasn't expecting much since it improved greatly during the 4.8 dev cycle, however one stood out. The saving of PNG images was taking about 1/5th of the time in KWin that i could see directly. That looked like something i might be able to optimize.

What this patch is doing is storing the actual image bits to prevent saving a PNG image to the mmapped cache. That was a hot code path in time (cycles), not even in calls. I've also reduced the amount of memory copies to a bare minimum by adding a rawFind function to KSharedDataCache which fills a QByteArray::fromRawData thus preventing a expensive memory copy. The rawFind is used for looking up an image and fetching it's data without copying it. That is done because QImage seems to make a copy itself internally. I don't have any performance measurements, however, prior to this patch my kwin test was using up ~5.000.000.000 cycles. After this patch it's using up 1.370.000.000. I don't have raw performance numbers to see if the cache itself is actually faster, it certainly has become a lot cheaper to use the cache. Logic wise i would say creating a QImage from the cached data should be way faster now since there is no step involved anymore in decoding the image. Storing is certainly an order of magnitude faster.

Special thanks go to David Faure for helping me a great deal with this.

  		
 






Testing 



 

  
   
I've also written a bunch of test cases (greatly improved by David Faure) to see if i didn't break anything. According to the test (which is also comparing the actual image bits) it's all passing just fine.

  		
 








Diffs (updated)
Mark Gaiser
unread,
Feb 23, 2012, 2:23:05 PM2/23/12
to David Faure, Michael Pyne, kdelibs

   

    

     
      This is an automatically generated e-mail. To reply, visit:
      http://git.reviewboard.kde.org/r/104052/
     
    

   

   







Review request for kdelibs, David Faure and Michael Pyne.


By Mark Gaiser.




Updated Feb. 23, 2012, 7:23 p.m.





Changes



 

  
   
Someone wants benchmarks ;)

  		
 








Description  (updated)

 

 

  
   
I was running KWin through callgrind to see where possible bottlenecks are. I wasn't expecting much since it improved greatly during the 4.8 dev cycle, however one stood out. The saving of PNG images was taking about 1/5th of the time in KWin that i could see directly. That looked like something i might be able to optimize.

What this patch is doing is storing the actual image bits to prevent saving a PNG image to the mmapped cache. That was a hot code path in time (cycles), not even in calls. I've also reduced the amount of memory copies to a bare minimum by adding a rawFind function to KSharedDataCache which fills a QByteArray::fromRawData thus preventing a expensive memory copy. The rawFind is used for looking up an image and fetching it's data without copying it. That is done because QImage seems to make a copy itself internally. I don't have any performance measurements, however, prior to this patch my kwin test was using up ~5.000.000.000 cycles. After this patch it's using up 1.370.000.000. I don't have raw performance numbers to see if the cache itself is actually faster, it certainly has become a lot cheaper to use the cache. Logic wise i would say creating a QImage from the cached data should be way faster now since there is no step involved anymore in decoding the image. Storing is certainly an order of magnitude faster.

Benchmark numbers. insert(write) and find(read)

-- Before patch --
READ : 0.019 msecs per iteration (total: 79, iterations: 4096)
WRITE: 0.010 msecs per iteration (total: 88, iterations: 8192)

-- After patch --
READ : 0.019 msecs per iteration (total: 79, iterations: 4096)
WRITE: 0.0026 msecs per iteration (total: 87, iterations: 32768)

Reading is equal in speed, writing is ~5x faster after the patch.

Special thanks go to David Faure for helping me a great deal with this.

  		
 






Testing 



 

  
   
I've also written a bunch of test cases (greatly improved by David Faure) to see if i didn't break anything. According to the test (which is also comparing the actual image bits) it's all passing just fine.

  		
 








Diffs 


Mark Gaiser
unread,
Feb 23, 2012, 6:33:23 PM2/23/12
to David Faure, Michael Pyne, kdelibs

   

    

     
      This is an automatically generated e-mail. To reply, visit:
      http://git.reviewboard.kde.org/r/104052/
     
    

   

   











 
On February 23rd, 2012, 8:56 p.m., Christoph Feck wrote:

 

  





 
  

   
    kdeui/util/kimagecache.cpp
    

     (Diff revision 2)

    
   
  

 

 
  


   
KImageCache::~KImageCache()


  

 




 
 



 

  

    
    

    105
    
    stream << image.format();

  


 




  
This fails to correctly handle palettized images.

If we do not want to preserve image texts, gamma, and DPI, please document it (the PNG handler did).

Also, did you try setting the compression level for the PNG writer before giving up on compression? The compression is probably wanted. I have not checked if Qt uses quality 0 or 100 for the fastest mode, but the default PNG compression is utterly slow (as you noticed ;)

 




 
On February 23rd, 2012, 9:08 p.m., Mark Gaiser wrote:

 

  
Don't know about that.. Hope someone more knowledgeable could respond in the "image texts, gamma, and DPI".

As for the fastest/slowest mode. No, i haven't tried that. But even then it seems kinda strange to load an image and directly save the exact same image as .png in some mmapped file (which was the behavior). Saving the "compiled" image (the bits) seems more obvious.

 






 
On February 23rd, 2012, 9:40 p.m., Christoph Feck wrote:

 

  
The KImageCache is not used exclusively for "loaded" images, but also (and especially so) for generated images, e.g. when caching SVG rendered data.

Regarding compression, the type of images that are stored in the cache are usually very compressible, better than text, and thus the memory (or even disk) pressure can be greatly reduced. For example, the 128x128 "text-x-generic" icon is 64 KB uncompressed, while only 13 KB compressed.

I just checked Qt docs. If you use "image.save(buffer, "PNG", quality);" you get uncompressed PNG with quality == 100, and fastest, but moderate compression with quality == 80. Any smaller value improves compression rate, but makes it slower.

 











I played a bit with compression and got it working.
The cached sizes (with qCompress(data, 5)) are indeed _way_ smaller then uncompressed. However, it crashes quite often when i use that. Here is the raw code for it: http://paste.kde.org/428102/

The unit tests pass on it yet kwin crashes on the image with this key: "15_1680_1015_hover-_widgets/viewitem". I haven't done further tests.
Compression rate is quite high:

key: "8_8_/usr/share/apps/desktoptheme/default/widgets/viewitem.svgzhover-bottomleft" 
cachedData size (compressed): 151 
cachedData size (uncompressed): 256 
key: "8_8_/usr/share/apps/desktoptheme/default/widgets/viewitem.svgzhover-bottomright" 
cachedData size (compressed): 149 
cachedData size (uncompressed): 256 

However, zlib is slow. If we really desperately want to have compression then we should go for something fast even if it doesn't compress as good: http://code.google.com/p/lz4/ The speed is about 20x faster with LZ4 then it would be with zlib but obviously with a lower ratio. Please do note that adding LZ4 is not hard, it's only 2 files (1 .c and 1 .h)

What i do find strange is that the file sizes of the caches seem to remain the same with and without compression. Yes, i do delete them prior to testing.

I leave it up to you guys where we go from here. I'm fine with adding compression (nice new interesting challenge ^_^), but i'm also fine with leaving it the way it's now in the diff + the edit from Aaron J. Seigo.








- Mark
Michael Pyne
unread,
Feb 23, 2012, 8:16:41 PM2/23/12
to David Faure, Michael Pyne, kdelibs

   

    

     
      This is an automatically generated e-mail. To reply, visit:
      http://git.reviewboard.kde.org/r/104052/
     
    

   

   






 
The big issue is a race condition between finding an entry and its eventual use later... this might be suitable for limited use-cases where end-user code can buy into that arrangement, but is not suitable in general for KSharedDataCache or KImageCache.

To answer a different comment, the cache is always fixed-size because of the design of the underlying data structure (currently a fixed-size hash table). The entire structure is pre-allocated on disk for architectures that support posix_fallocate (IIRC) to avoid crashes for OS'es that overcommit disk space.

 














 
  

   
    kdecore/util/kshareddatacache.h
    

     (Diff revision 2)

    
   
  

 

 
  


   
public:


  

 




 
 



 

  

    
    

    144
    
     * internal copy. You must use the contents of the destination bytearray before

  


 





As you note here in the comment, there is a race condition in general between unlocking the cache and actually finally copying the data to the eventual destination.

Although I deeply appreciate the need for core code like KSharedDataCache to be as efficient as possible, this can't be done by adding even more segfaults (however rare).

One possible alternative that might be possible and keep your core idea is to possibly find a way to invalidate those "fromRawData"'d QByteArrays if the cache (or better yet, the affected data pages) is modified in between, similar to how QPointer<T> knows when the QObject it's pointing to has been deleted. Obviously this is easier said than done for a low-level class like QByteArray.














 
  

   
    kdecore/util/kshareddatacache.cpp
    

     (Diff revision 2)

    
   
  

 

 
  


   
bool KSharedDataCache::insert(const QString &key, const QByteArray &data)


  

 




 
 



 


  

    
    

    1491
    
            *destination = QByteArray(temp.constData(), temp.size());

  


 





The cache is unlocked here but temp is still pointing into its internals (as mentioned above)... it's possible to extract the lock out to wrap around this copy too but then I'm not sure how that would make anything different, you'd still be performing the copy.














 
  

   
    kdeui/util/kimagecache.cpp
    

     (Diff revision 2)

    
   
  

 

 
  


   


  

 




 
 



 

  

    
    

    28
    
#include <QDebug>

  


 





Is this still needed? (I'm assuming not. ;)














 
  

   
    kdeui/util/kimagecache.cpp
    

     (Diff revision 2)

    
   
  

 

 
  


   
KImageCache::~KImageCache()


  

 





 
 


 


  

    101
    
    image.save(&buffer, "PNG");

    
    

  


 





Like some of the other reviewers I would prefer to maintain at least some compression of the image (since in general CPU is nowadays cheaper than memory and memory bandwidth), in addition to the concern with indexed/paletted images (from the Qt docs it seems the color table will still be left empty here).

Of course, the reason the QImage must be constructed that way is mostly related to being able to use the rawData QByteArray directly, which we can't really do without the cache locked... assuming we can find a way around that this construct might still be useful for QImages which we verify have no color table.









- Michael






On February 23rd, 2012, 7:23 p.m., Mark Gaiser wrote:











Review request for kdelibs, David Faure and Michael Pyne.


By Mark Gaiser.




Updated Feb. 23, 2012, 7:23 p.m.








Description 
Mark Gaiser
unread,
Feb 23, 2012, 8:40:02 PM2/23/12
to David Faure, Michael Pyne, kdelibs

   

    

     
      This is an automatically generated e-mail. To reply, visit:
      http://git.reviewboard.kde.org/r/104052/
     
    

   

   











 
On February 24th, 2012, 1:16 a.m., Michael Pyne wrote:

 

  





 
  

   
    kdecore/util/kshareddatacache.h
    

     (Diff revision 2)

    
   
  

 

 
  


   
public:


  

 




 
 



 

  

    
    

    144
    
     * internal copy. You must use the contents of the destination bytearray before

  


 




  
As you note here in the comment, there is a race condition in general between unlocking the cache and actually finally copying the data to the eventual destination.

Although I deeply appreciate the need for core code like KSharedDataCache to be as efficient as possible, this can't be done by adding even more segfaults (however rare).

One possible alternative that might be possible and keep your core idea is to possibly find a way to invalidate those "fromRawData"'d QByteArrays if the cache (or better yet, the affected data pages) is modified in between, similar to how QPointer<T> knows when the QObject it's pointing to has been deleted. Obviously this is easier said than done for a low-level class like QByteArray.

 









I definitely need more info to get your suggestion implemented in this..






 
On February 24th, 2012, 1:16 a.m., Michael Pyne wrote:

 

  





 
  

   
    kdecore/util/kshareddatacache.cpp
    

     (Diff revision 2)

    
   
  

 

 
  


   
bool KSharedDataCache::insert(const QString &key, const QByteArray &data)


  

 




 
 



 

  

    
    

    1491
    
            *destination = QByteArray(temp.constData(), temp.size());

  


 




  
The cache is unlocked here but temp is still pointing into its internals (as mentioned above)... it's possible to extract the lock out to wrap around this copy too but then I'm not sure how that would make anything different, you'd still be performing the copy.

 









This is mimicking the old behavior and i'm in fact returning a copy of the data here, just like how it used to be. This one won't cause a race condition. The temp value should be gone when the function moves out of scope right? Then i don't see the issue..






 
On February 24th, 2012, 1:16 a.m., Michael Pyne wrote:

 

  





 
  

   
    kdeui/util/kimagecache.cpp
    

     (Diff revision 2)

    
   
  

 

 
  


   


  

 




 
 



 

  

    
    

    28
    
#include <QDebug>

  


 




  
Is this still needed? (I'm assuming not. ;)

 









hehehe. Will remove that line.






 
On February 24th, 2012, 1:16 a.m., Michael Pyne wrote:

 

  





 
  

   
    kdeui/util/kimagecache.cpp
    

     (Diff revision 2)

    
   
  

 

 
  


   
KImageCache::~KImageCache()


  

 





 
 


 

  

    101
    
    image.save(&buffer, "PNG");

    
    

  


 




  
Like some of the other reviewers I would prefer to maintain at least some compression of the image (since in general CPU is nowadays cheaper than memory and memory bandwidth), in addition to the concern with indexed/paletted images (from the Qt docs it seems the color table will still be left empty here).

Of course, the reason the QImage must be constructed that way is mostly related to being able to use the rawData QByteArray directly, which we can't really do without the cache locked... assuming we can find a way around that this construct might still be useful for QImages which we verify have no color table.

 









Ehm no. That would beat the entire meaning of this patch. The image.save function was the one causing high clock cycles and should be prevented. And, again, i really don't see why it would be needed to store an actual image (png) in a mmapped file. To me it seems way more obvious to store the bits that make up the image. Compressing the data is fine but then we need to use either qCompress or LZ4.








- Mark
Michael Pyne
unread,
Feb 23, 2012, 9:27:31 PM2/23/12
to David Faure, Michael Pyne, kdelibs

   

    

     
      This is an automatically generated e-mail. To reply, visit:
      http://git.reviewboard.kde.org/r/104052/
     
    

   

   











 
On February 24th, 2012, 1:16 a.m., Michael Pyne wrote:

 

  





 
  

   
    kdecore/util/kshareddatacache.cpp
    

     (Diff revision 2)

    
   
  

 

 
  


   
bool KSharedDataCache::insert(const QString &key, const QByteArray &data)


  

 




 
 



 

  

    
    

    1491
    
            *destination = QByteArray(temp.constData(), temp.size());

  


 




  
The cache is unlocked here but temp is still pointing into its internals (as mentioned above)... it's possible to extract the lock out to wrap around this copy too but then I'm not sure how that would make anything different, you'd still be performing the copy.

 




 
On February 24th, 2012, 1:40 a.m., Mark Gaiser wrote:

 

  
This is mimicking the old behavior and i'm in fact returning a copy of the data here, just like how it used to be. This one won't cause a race condition. The temp value should be gone when the function moves out of scope right? Then i don't see the issue..

 











The data does get copied here, but the copy must be complete *before* we get to this point. As it stands the cache becomes unlocked (which means **no guarantees** can be made about the lifetime of entries still in the cache) as soon as rawFind() completes. You'd never notice this error unless you can torture test KSharedDataCache to expose the race condition, but it's a race nonetheless.

Either the lock can be broken out and wrapped around the rawFind()/copy combination (but then why make the switch at all) or some way can be implemented to detect that the required cache entry has been changed and just return a failure value (which is perfectly acceptable, this is a cache after all).






 
On February 24th, 2012, 1:16 a.m., Michael Pyne wrote:

 

  





 
  

   
    kdeui/util/kimagecache.cpp
    

     (Diff revision 2)

    
   
  

 

 
  


   
KImageCache::~KImageCache()


  

 





 
 


 

  

    101
    
    image.save(&buffer, "PNG");

    
    

  


 




  
Like some of the other reviewers I would prefer to maintain at least some compression of the image (since in general CPU is nowadays cheaper than memory and memory bandwidth), in addition to the concern with indexed/paletted images (from the Qt docs it seems the color table will still be left empty here).

Of course, the reason the QImage must be constructed that way is mostly related to being able to use the rawData QByteArray directly, which we can't really do without the cache locked... assuming we can find a way around that this construct might still be useful for QImages which we verify have no color table.

 




 
On February 24th, 2012, 1:40 a.m., Mark Gaiser wrote:

 

  
Ehm no. That would beat the entire meaning of this patch. The image.save function was the one causing high clock cycles and should be prevented. And, again, i really don't see why it would be needed to store an actual image (png) in a mmapped file. To me it seems way more obvious to store the bits that make up the image. Compressing the data is fine but then we need to use either qCompress or LZ4.

 











So let's work on this first (especially since in the end we'll still be needing to copy data in/out anyways).

Storing an image in a container format is certainly not required (it was done simply because it was expedient)... it seems that we just need to check that the image doesn't actually require a color table of some sort (if it does we can just fall back to what we do now).

One problem I didn't mention on my last review is that changing the binary format of the KImageCache is binary-incompatible with existing KImageCaches... and I don't think KImageCache has a versioning field, only KSharedDataCache. I wouldn't mind bumping the KSharedDataCache version to support this (and potentially adding a sub-version field while I'm at it), so let me know if there's no other solution.
Ingo Klöcker
unread,
Feb 25, 2012, 5:55:50 PM2/25/12
to David Faure, Michael Pyne, Ingo Klöcker, kdelibs

   

    

     
      This is an automatically generated e-mail. To reply, visit:
      http://git.reviewboard.kde.org/r/104052/
     
    

   

   











 
On February 24th, 2012, 1:16 a.m., Michael Pyne wrote:

 

  





 
  

   
    kdecore/util/kshareddatacache.cpp
    

     (Diff revision 2)

    
   
  

 

 
  


   
bool KSharedDataCache::insert(const QString &key, const QByteArray &data)


  

 




 
 



 

  

    
    

    1491
    
            *destination = QByteArray(temp.constData(), temp.size());

  


 




  
The cache is unlocked here but temp is still pointing into its internals (as mentioned above)... it's possible to extract the lock out to wrap around this copy too but then I'm not sure how that would make anything different, you'd still be performing the copy.

 




 
On February 24th, 2012, 1:40 a.m., Mark Gaiser wrote:

 

  
This is mimicking the old behavior and i'm in fact returning a copy of the data here, just like how it used to be. This one won't cause a race condition. The temp value should be gone when the function moves out of scope right? Then i don't see the issue..

 






 
On February 24th, 2012, 2:27 a.m., Michael Pyne wrote:

 

  
The data does get copied here, but the copy must be complete *before* we get to this point. As it stands the cache becomes unlocked (which means **no guarantees** can be made about the lifetime of entries still in the cache) as soon as rawFind() completes. You'd never notice this error unless you can torture test KSharedDataCache to expose the race condition, but it's a race nonetheless.

Either the lock can be broken out and wrapped around the rawFind()/copy combination (but then why make the switch at all) or some way can be implemented to detect that the required cache entry has been changed and just return a failure value (which is perfectly acceptable, this is a cache after all).

 











A possible solution would be a redesign of the cache using some kind of shared pointers for the pages and weak pointers for the returned cached data. Just an idea. Might be complete nonsense for this use case.








- Ingo






On February 25th, 2012, 10:08 p.m., Mark Gaiser wrote:











Review request for kdelibs, David Faure and Michael Pyne.


By Mark Gaiser.




Updated Feb. 25, 2012, 10:08 p.m.








Description 

 

 

  
   
I was running KWin through callgrind to see where possible bottlenecks are. I wasn't expecting much since it improved greatly during the 4.8 dev cycle, however one stood out. The saving of PNG images was taking about 1/5th of the time in KWin that i could see directly. That looked like something i might be able to optimize.

What this patch is doing is storing the actual image bits to prevent saving a PNG image to the mmapped cache. That was a hot code path in time (cycles), not even in calls. I've also reduced the amount of memory copies to a bare minimum by adding a rawFind function to KSharedDataCache which fills a QByteArray::fromRawData thus preventing a expensive memory copy. The rawFind is used for looking up an image and fetching it's data without copying it. That is done because QImage seems to make a copy itself internally. I don't have any performance measurements, however, prior to this patch my kwin test was using up ~5.000.000.000 cycles. After this patch it's using up 1.370.000.000. I don't have raw performance numbers to see if the cache itself is actually faster, it certainly has become a lot cheaper to use the cache. Logic wise i would say creating a QImage from the cached data should be way faster now since there is no step involved anymore in decoding the image. Storing is certainly an order of magnitude faster.

-- update --
After spending a lot more time trying to get compression in the mix "someone" came with the suggestion to use KFilterDev. Never heard of it, but i gave it a shot anyway. It turned out to be the bull-eye in this case. Data is now greatly compressed using bzip (any other compression available in KFilterDev makes it a lot slower) with no speed loss compared to my previous benchmark results, the opposite is true, speedups!

New benchmarks compared to the stock 4.8.0 KImageCache:
Read: ~8x faster (was 5x in my previous patch)
Write: ~5x faster (equally fast compared to stock, no speedup here in my previous patch)

I've also added a more detailed description of insertImage for the details that it saves. My point of view is that KImageCache should be used for caching of (system)images and perhaps thumbnails. Things like image text should not be stored since that should be fetched from the originating image. The color table (when available) is stored.

There are still a few major speedups that can be taken here, but are a lot more complicated to do.
- use a faster compression method, that will probably greatly speedup insertion and retrieval! (i keep saying it: LZ4!)
- somehow store the bits separate so that only the bits can be fetched for insertion checking. I actually did do this already, but the added overhead of more QIODevice objects and more QBuffers is causing it to not be beneficial at all. It's even a little slower.

As for the issues marked below for race conditions. I need help in that area. I can't do what's suggested (i lack the knowledge for it).

Special thanks go to David Faure for helping me a great deal with this.

  		
 






Testing 



 

  
   
I've also written a bunch of test cases (greatly improved by David Faure) to see if i didn't break anything. According to the test (which is also comparing the actual image bits) it's all passing just fine.

  		
 








Diffs 


    

 
  • kdecore/util/kshareddatacache.h (339cecc)
    • 

 
  • kdecore/util/kshareddatacache.cpp (9fe3995)
    • 

 
  • kdeui/tests/CMakeLists.txt (c8b8c85)
    

 
  • kdeui/tests/kimagecachetests.h (PRE-CREATION)
    • 

 
  • kdeui/tests/kimagecachetests.cpp (PRE-CREATION)
    • 

 
  • kdeui/util/kimagecache.cpp (a5bbbe1)
    • 






Mark Gaiser
unread,
Feb 25, 2012, 3:45:15 PM2/25/12
to David Faure, Michael Pyne, kdelibs

   

    

     
      This is an automatically generated e-mail. To reply, visit:
      http://git.reviewboard.kde.org/r/104052/
     
    

   

   







Review request for kdelibs, David Faure and Michael Pyne.


By Mark Gaiser.




Updated Feb. 25, 2012, 8:45 p.m.





Changes



 

  
   
Greatly changed the diff.
Added:
- gzip compression using KFilterDev
- prevent image insertion when the current image from the cache is exactly the same as the one we want to insert.
- heavily improved speed
(changed main description for this)

  		
 








Description  (updated)

 

 

  
   
I was running KWin through callgrind to see where possible bottlenecks are. I wasn't expecting much since it improved greatly during the 4.8 dev cycle, however one stood out. The saving of PNG images was taking about 1/5th of the time in KWin that i could see directly. That looked like something i might be able to optimize.

What this patch is doing is storing the actual image bits to prevent saving a PNG image to the mmapped cache. That was a hot code path in time (cycles), not even in calls. I've also reduced the amount of memory copies to a bare minimum by adding a rawFind function to KSharedDataCache which fills a QByteArray::fromRawData thus preventing a expensive memory copy. The rawFind is used for looking up an image and fetching it's data without copying it. That is done because QImage seems to make a copy itself internally. I don't have any performance measurements, however, prior to this patch my kwin test was using up ~5.000.000.000 cycles. After this patch it's using up 1.370.000.000. I don't have raw performance numbers to see if the cache itself is actually faster, it certainly has become a lot cheaper to use the cache. Logic wise i would say creating a QImage from the cached data should be way faster now since there is no step involved anymore in decoding the image. Storing is certainly an order of magnitude faster.

-- update --
After spending a lot more time trying to get compression in the mix "someone" came with the suggestion to use KFilterDev. Never heard of it, but i gave it a shot anyway. It turned out to be the bull-eye in this case. Data is now greatly compressed using bzip (any other compression available in KFilterDev makes it a lot slower) with no speed loss compared to my previous benchmark results, the opposite is true, speedups!

New benchmarks compared to the stock 4.8.0 KImageCache:
Read: ~8x faster (was 5x in my previous patch)
Write: ~5x faster (equally fast compared to stock, no speedup here in my previous patch)

There are still a few major speedups that can be taken here, but are a lot more complicated to do.
- use a faster compression method, that will probably greatly speedup insertion and retrieval! (i keep saying it: LZ4!)
- somehow store the bits separate so that only the bits can be fetched for insertion checking. I actually did do this already, but the added overhead of more QIODevice objects and more QBuffers is causing it to not be beneficial at all. It's even a little slower.

As for the issues marked below for race conditions. I need help in that area. I can't do what's suggested (i lack the knowledge for it).

Special thanks go to David Faure for helping me a great deal with this.

  		
 






Testing 



 

  
   
I've also written a bunch of test cases (greatly improved by David Faure) to see if i didn't break anything. According to the test (which is also comparing the actual image bits) it's all passing just fine.

  		
 








Diffs (updated)


    

 
  • kdecore/util/kshareddatacache.h (339cecc)
    • 

 
  • kdecore/util/kshareddatacache.cpp (9fe3995)
    • 

 
  • kdeui/tests/CMakeLists.txt (c8b8c85)
    

 
  • kdeui/tests/kimagecachetests.h (PRE-CREATION)
    • 

 
  • kdeui/tests/kimagecachetests.cpp (PRE-CREATION)
    • 

 
  • kdeui/util/kimagecache.cpp (a5bbbe1)
    • 






Mark Gaiser
unread,
Feb 25, 2012, 5:08:25 PM2/25/12
to David Faure, Michael Pyne, kdelibs

   

    

     
      This is an automatically generated e-mail. To reply, visit:
      http://git.reviewboard.kde.org/r/104052/
     
    

   

   







Review request for kdelibs, David Faure and Michael Pyne.


By Mark Gaiser.




Updated Feb. 25, 2012, 10:08 p.m.








Description  (updated)

 

 

  
   
I was running KWin through callgrind to see where possible bottlenecks are. I wasn't expecting much since it improved greatly during the 4.8 dev cycle, however one stood out. The saving of PNG images was taking about 1/5th of the time in KWin that i could see directly. That looked like something i might be able to optimize.

What this patch is doing is storing the actual image bits to prevent saving a PNG image to the mmapped cache. That was a hot code path in time (cycles), not even in calls. I've also reduced the amount of memory copies to a bare minimum by adding a rawFind function to KSharedDataCache which fills a QByteArray::fromRawData thus preventing a expensive memory copy. The rawFind is used for looking up an image and fetching it's data without copying it. That is done because QImage seems to make a copy itself internally. I don't have any performance measurements, however, prior to this patch my kwin test was using up ~5.000.000.000 cycles. After this patch it's using up 1.370.000.000. I don't have raw performance numbers to see if the cache itself is actually faster, it certainly has become a lot cheaper to use the cache. Logic wise i would say creating a QImage from the cached data should be way faster now since there is no step involved anymore in decoding the image. Storing is certainly an order of magnitude faster.

-- update --
After spending a lot more time trying to get compression in the mix "someone" came with the suggestion to use KFilterDev. Never heard of it, but i gave it a shot anyway. It turned out to be the bull-eye in this case. Data is now greatly compressed using bzip (any other compression available in KFilterDev makes it a lot slower) with no speed loss compared to my previous benchmark results, the opposite is true, speedups!

New benchmarks compared to the stock 4.8.0 KImageCache:
Read: ~8x faster (was 5x in my previous patch)
Write: ~5x faster (equally fast compared to stock, no speedup here in my previous patch)

I've also added a more detailed description of insertImage for the details that it saves. My point of view is that KImageCache should be used for caching of (system)images and perhaps thumbnails. Things like image text should not be stored since that should be fetched from the originating image. The color table (when available) is stored.

There are still a few major speedups that can be taken here, but are a lot more complicated to do.
- use a faster compression method, that will probably greatly speedup insertion and retrieval! (i keep saying it: LZ4!)
- somehow store the bits separate so that only the bits can be fetched for insertion checking. I actually did do this already, but the added overhead of more QIODevice objects and more QBuffers is causing it to not be beneficial at all. It's even a little slower.

As for the issues marked below for race conditions. I need help in that area. I can't do what's suggested (i lack the knowledge for it).

Special thanks go to David Faure for helping me a great deal with this.

  		
 






Testing 



 

  
   
I've also written a bunch of test cases (greatly improved by David Faure) to see if i didn't break anything. According to the test (which is also comparing the actual image bits) it's all passing just fine.

  		
 








Diffs 


Mark Gaiser
unread,
Feb 26, 2012, 1:46:14 PM2/26/12
to David Faure, Michael Pyne, kdelibs, Ingo Klöcker

   

    

     
      This is an automatically generated e-mail. To reply, visit:
      http://git.reviewboard.kde.org/r/104052/
     
    

   

   







Review request for kdelibs, David Faure and Michael Pyne.


By Mark Gaiser.




Updated Feb. 26, 2012, 6:46 p.m.





Changes



 

  
   
Added the use of a checksum using MurmurHash3_x86_32 (v3 is faster because the data could be quite a bit.)
Adding the same image with the same key is now very fast to determine and cheap (6x faster then previously). Both insertImage and findImage benefit of this checksum in terms of speed though just a little.
Updated the MurmurHash in KSharedDataCache to v2 (v3 isn't faster for the data in there) It gives a little speedup.

  		
 








Description  (updated)

 

 

  
   
I was running KWin through callgrind to see where possible bottlenecks are. I wasn't expecting much since it improved greatly during the 4.8 dev cycle, however one stood out. The saving of PNG images was taking about 1/5th of the time in KWin that i could see directly. That looked like something i might be able to optimize.

What this patch is doing is storing the actual image bits to prevent saving a PNG image to the mmapped cache. That was a hot code path in time (cycles), not even in calls. I've also reduced the amount of memory copies to a bare minimum by adding a rawFind function to KSharedDataCache which fills a QByteArray::fromRawData thus preventing a expensive memory copy. The rawFind is used for looking up an image and fetching it's data without copying it. That is done because QImage seems to make a copy itself internally. I don't have any performance measurements, however, prior to this patch my kwin test was using up ~5.000.000.000 cycles. After this patch it's using up 1.370.000.000. I don't have raw performance numbers to see if the cache itself is actually faster, it certainly has become a lot cheaper to use the cache. Logic wise i would say creating a QImage from the cached data should be way faster now since there is no step involved anymore in decoding the image. Storing is certainly an order of magnitude faster.

-- update 26-02-2012 --
After spending a lot more time trying to get compression in the mix "someone" came with the suggestion to use KFilterDev. Never heard of it, but i gave it a shot anyway. It turned out to be the bull-eye in this case. Data is now greatly compressed using gzip (any other compression available in KFilterDev makes it a lot slower). Gzip gives some loss in speed, but compared to the current stock KImageCache it's still a _lot_ faster.

New benchmarks compared to the stock 4.8.0 KImageCache:
Read: ~8x faster (was 5x in my previous patch)
Write: ~5x faster (equally fast compared to stock, no speedup here in my previous patch)
Inserting the same image with the same key twice is now about free (depending on the size of the image, it's about free for icon sized images with 48x48).

I've also added a more detailed description of insertImage for the details that it saves. My point of view is that KImageCache should be used for caching of (system)images and perhaps thumbnails. Things like image text should not be stored since that should be fetched from the originating image. The color table (when available) is stored.

A last massive performance improvement that is possible but complicated to get is by using the IZ compression from "kdepepo". Just using IZ to compress the bits will make the image size a lot smaller then is currently done with gzip and will do it at the very least about 5x faster as well. That means insertion will benefit massively here. However, that will also mean that the stored image data is only going to be:
- width
- height
- format
- bits
No color tables! But this is something for the future. Right now the current diff is about fine. The last remaining issues are the possible race conditions as mentioned in the comments below. 
I need help in that area. I can't do what's suggested (i lack the knowledge to do it myself).

Special thanks go to David Faure for helping me a great deal with this.

  		
 






Testing 



 

  
   
I've also written a bunch of test cases (greatly improved by David Faure) to see if i didn't break anything. According to the test (which is also comparing the actual image bits) it's all passing just fine.

  		
 








Diffs (updated)


      

 
    • kdecore/util/kshareddatacache.h (339cecc)
      • 

 
    • kdecore/util/kshareddatacache.cpp (9fe3995)
      • 

 
    • kdeui/tests/CMakeLists.txt (c8b8c85)
      • 

 
    • kdeui/tests/kimagecachetests.h (PRE-CREATION)
      • 

 
    • kdeui/tests/kimagecachetests.cpp (PRE-CREATION)
      • 

 
    • kdeui/util/kimagecache.h (54112de)
      • 

 
    • kdeui/util/kimagecache.cpp (a5bbbe1)
      • 


    


    View Diff
    




      		
 
    

    




  
    
 
    



    Mark Gaiser
    unread,
    Feb 26, 2012, 3:08:40 PM2/26/12
    to David Faure, Michael Pyne, kdelibs, Ingo Klöcker
    
   
    
    
    
     
      This is an automatically generated e-mail. To reply, visit:
      http://git.reviewboard.kde.org/r/104052/
     
    
    
   
    
   
    



    


    Review request for kdelibs, David Faure and Michael Pyne.
    

    By Mark Gaiser.
    



    Updated Feb. 26, 2012, 8:08 p.m.
    




    Changes
    

    
 
    
  
   
    Revision 6.. rawFind removed. My initial test data was from kwin. That was filled with data from all over the place. I saw QImage::copy calls, but those where not from the KImageCache. The clean testcase that i've been using indicated that so a copy of the data has to be made for QImage which makes rawFind obsolete. The performance gets only a minor hit from this. The numbers as posted before still stand.
    
      		
 
    

    





    Description  (updated)
    
 
    
 
    
  
   
    I was running KWin through callgrind to see where possible bottlenecks are. I wasn't expecting much since it improved greatly during the 4.8 dev cycle, however one stood out. The saving of PNG images was taking about 1/5th of the time in KWin that i could see directly. That looked like something i might be able to optimize.

What this patch is doing is storing the actual image bits to prevent saving a PNG image to the mmapped cache. That was a hot code path in time (cycles), not even in calls.

-- update 26-02-2012 --
After spending a lot more time trying to get compression in the mix "someone" came with the suggestion to use KFilterDev. Never heard of it, but i gave it a shot anyway. It turned out to be the bull-eye in this case. Data is now greatly compressed using gzip (any other compression available in KFilterDev makes it a lot slower). Gzip gives some loss in speed, but compared to the current stock KImageCache it's still a _lot_ faster.

New benchmarks compared to the stock 4.8.0 KImageCache:
Read: ~8x faster (was 5x in my previous patch)
Write: ~5x faster (equally fast compared to stock, no speedup here in my previous patch)
Inserting the same image with the same key twice is now about free (depending on the size of the image, it's about free for icon sized images with 48x48).

I've also added a more detailed description of insertImage for the details that it saves. My point of view is that KImageCache should be used for caching of (system)images and perhaps thumbnails. Things like image text should not be stored since that should be fetched from the originating image. The color table (when available) is stored.

A last massive performance improvement that is possible but complicated to get is by using the IZ compression from "kdepepo". Just using IZ to compress the bits will make the image size a lot smaller then is currently done with gzip and will do it at the very least about 5x faster as well. That means insertion will benefit massively here. However, that will also mean that the stored image data is only going to be:
- width
- height
- format
- bits
No color tables! But this is something for the future. Right now the current diff is about fine. The last remaining issues are the possible race conditions as mentioned in the comments below. 
I need help in that area. I can't do what's suggested (i lack the knowledge to do it myself).

Special thanks go to David Faure for helping me a great deal with this.
    
      		
 
    

    Michael Pyne
    unread,
    Feb 26, 2012, 5:09:42 PM2/26/12
    to David Faure, Michael Pyne, kdelibs
    
   
    
    
    
     
      This is an automatically generated e-mail. To reply, visit:
      http://git.reviewboard.kde.org/r/104052/
     
    
    
   
    
   
    





 
    Overall I like the idea of taking a more direct role in KImageCache compression to ensure that only the bare necessities are put into the cache (and done so quickly). A bit more work is needed to get it library-quality but it's coming along nicely.

The hashing of the image contents (since KSDC already hashes the keys) is to ensure that we don't waste time overwriting an entry that's already cached, no? It *might* be better to see why such an entry is being cached in the first place and just avoid making the redundant insertImage call (the fastest thing a computer can do is nothing ;) but I'll leave the analysis of that to your existing KWin benchmarks to see if that's feasible/useful.
    
 
    






    





    
 
  
    
   
    kdecore/util/kshareddatacache.cpp
    

     (Diff revision 5)

    
   
  
    
     

 
  
    

   
    int ksdcArea()
    		

  
    
     




 
 



 

  
    
    
    
    		
    56
    
    // Performance will be lower than MurmurHash2
    		
  
    

     


    


    Lower than MurmurHash2 or higher than? (If it's lower than MH2 then why not use that?)
    

    

    


    





    
 
  
    
   
    kdecore/util/kshareddatacache.cpp
    

     (Diff revision 5)

    
   
  
    
     

 
  
    

   
    int ksdcArea()
    		

  
    
     




 
 



 

  
    
    
    
    		
    62
    
    static unsigned int MurmurHashAligned2 ( const void * key, int len, unsigned int seed )
    		
  
    

     


    


    Please don't change the coding style (the extra spaces added).
    

    

    


    





    
 
  
    
   
    kdecore/util/kshareddatacache.cpp
    

     (Diff revision 5)

    
   
  
    
     

 
  
    

   
    int ksdcArea()
    		

  
    
     



 
 




 

  
    
    63
    
        const unsigned char * data = reinterpret_cast<const unsigned char *>(key);
    		
    67
    
      const unsigned char * data = (const unsigned char *)key;
    		
  
    

     


    


    Please use the C++-style cast here, if anything so that it's easier to grep for.
    

    

    


    





    
 
  
    
   
    kdecore/util/kshareddatacache.cpp
    

     (Diff revision 5)

    
   
  
    
     

 
  
    

   
    static unsigned int MurmurHashAligned(const void *key, int len, unsigned int seed)
    		
   
    int ksdcArea()
    		

  
    
     



 
 




 

  
    
    94
    
                d = *reinterpret_cast<const unsigned int *>(data);
    		
    98
    
          d = *(unsigned int *)data;
    		
  
    

     


    


    Likewise with the cast here.
    

    

    


    





    
 
  
    
   
    kdecore/util/kshareddatacache.cpp
    

     (Diff revision 5)

    
   
  
    
     

 
  
    

   
    static unsigned int MurmurHashAligned(const void *key, int len, unsigned int seed)
    		
   
    int ksdcArea()
    		

  
    
     



 
 




 

  
    
    128
    
                h += *reinterpret_cast<const unsigned int *>(data);
    		
    163
    
          unsigned int k = *(unsigned int *)data;
    		
  
    

     


    


    And another reinterpret_cast<> change here.
    

    

    


    





    
 
  
    
   
    kdecore/util/kshareddatacache.cpp
    

     (Diff revision 5)

    
   
  
    
     

 
  
    

   
    struct SharedMemory
    		

  
    
     






 
 

 

  
    
    317
    
            PIXMAP_CACHE_VERSION = 12,
    		
    351
    
            PIXMAP_CACHE_VERSION = 12,
    		
  
    

     


    


    This would need to become a 16 here so that KSharedDataCache knows to re-generate existing (older) caches when encountered.
    

    

    


    





    
 
  
    
   
    kdecore/util/kshareddatacache.cpp
    

     (Diff revision 5)

    
   
  
    
     

 
  
    

   
    		
   
    bool KSharedDataCache::rawFind(const QString &key, QByteArray *destination) const
    		

  
    
     




 
 



 

  
    
    
    
    		
    1534
    
    bool KSharedDataCache::rawFind(const QString &key, QByteArray *destination) const
    		
  
    

     


    


    Your comment had mentioned that rawFind() was removed but it's still present in this version of the diff (unless I'm reviewing the wrong one...)
    

    

    


    





    
 
  
    
   
    kdeui/util/kimagecache.cpp
    

     (Diff revision 5)

    
   
  
    
     

 
  
    

   
    		
   
    FORCE_INLINE quint64 fmix ( quint64 k )
    		

  
    
     




 
 



 

  
    
    
    
    		
    278
    
            if (cache->rawFind(checksumKey, &cachedData)) {
    		
  
    

     


    


    This approach can't work in general. You can't rely on 2 different items remaining in the cache at the same time.

What needs to happen instead is that the checksum is stored /with/ the image's cached data (i.e. all in the same QByteArray).

If the image remains cached then it will always have its checksum with it.

You might want to pad the checksum out to 16 bytes to ensure that the image data is aligned to at least 16 bytes for performance.
    

    

    


    





    
 
  
    
   
    kdeui/util/kimagecache.cpp
    

     (Diff revision 5)

    
   
  
    
     

 
  
    

   
    KImageCache::~KImageCache()
    		

  
    
     




 
 



 

  
    
    
    
    		
    341
    
        QIODevice* dev = KFilterDev::device(&compressedData, "application/x-gzip", false);
    		
  
    

     


    


    You should use a QScopedPointer<QIODevice> here to hold the filter device, as it will make sure the destructor is called correctly. You could then delete the two "delete dev" lines.
    

    

    


    





    
 
  
    
   
    kdeui/util/kimagecache.cpp
    

     (Diff revision 5)

    
   
  
    
     

 
  
    

   
    KImageCache::~KImageCache()
    		

  
    
     




 
 



 

  
    
    
    
    		
    346
    
        QDataStream stream(dev);
    		
  
    

     


    


    QDataStream requires a bit of care.

You should explicitly set a version on the QDataStream before you use it (see QDataStream::setVersion and http://developer.qt.nokia.com/doc/qt-4.8/qdatastream.html#versioning).

As recommended in that versioning guide you should also add a version parameter (and a unique identifier "magic") as the first parameter so that it's possible to upgrade KImageCache without having to bump the version on KSharedDataCache in the future.

Finally, you should cast the integer values you're inputting/outputting to/from the QDataStream to the desired type (e.g. qint32). It would be acceptable to use C-style casts here IMHO.

For example:

QDataStream stream(dev);

stream << (quint32) 0x1C022012; // magic
stream << (quint32) 0x00010001; // version

// Must be set before streaming Qt types
stream.setVersion(QDataStream::Qt_4_6);

stream << givenImageBits;
// etc.
    

    

    


    





    
 
  
    
   
    kdeui/util/kimagecache.cpp
    

     (Diff revision 5)

    
   
  
    
     

 
  
    

   
    KImageCache::~KImageCache()
    		

  
    
     




 
 



 

  
    
    
    
    		
    357
    
        dev->close();
    		
  
    

     


    


    The QDataStream status should be checked before closing the device and inserting the QByteArray to ensure that there were no problems (unlikely as that should be).
    

    

    


    





    
 
  
    
   
    kdeui/util/kimagecache.cpp
    

     (Diff revision 5)

    
   
  
    
     

 
  
    

   
    bool KImageCache::insertPixmap(const QString &key, const QPixmap &pixmap)
    		

  
    
     




 
 



 

  
    
    
    
    		
    389
    
            int height = 0;
    		
  
    

     


    


    Don't forget to adjust here based on the changes from line 346 for specific types, versioning, etc. This would include ignoring entries of the wrong version and setting the right Qt version on the QDataStream being used.
    

    

    


    





    
 
  
    
   
    kdeui/util/kimagecache.cpp
    

     (Diff revision 5)

    
   
  
    
     

 
  
    

   
    bool KImageCache::insertPixmap(const QString &key, const QPixmap &pixmap)
    		

  
    
     




 
 



 

  
    
    
    
    		
    397
    
            QIODevice* dev = KFilterDev::device(&buffer, "application/x-gzip", false);
    		
  
    

     


    


    QScopedPointer here as well please.
    

    

    


    





    
 
  
    
   
    kdeui/util/kimagecache.cpp
    

     (Diff revision 5)

    
   
  
    
     

 
  
    

   
    bool KImageCache::insertPixmap(const QString &key, const QPixmap &pixmap)
    		

  
    
     




 
 



 

  
    
    
    
    		
    414
    
            QImage image((const uchar*)bits.constData(), width, height, (QImage::Format)format);
    		
  
    

     


    


    The QDataStream device status should be checked to ensure no errors occurred before using the result.
    

    

    


    





    
 
  
    
   
    kdeui/util/kimagecache.cpp
    

     (Diff revision 5)

    
   
  
    
     

 
  
    

   
    bool KImageCache::insertPixmap(const QString &key, const QPixmap &pixmap)
    		

  
    
     



 
 




 

  
    
    151
    
            return false;
    		
    441
    
            *destination = QPixmap::fromImage(image);
    		
  
    

     


    


    This shouldn't matter once rawFind() is eliminated anyways, but this must happen *after* the check that the destination pointer is actually set.
    

    

    




    - Michael
    



    

    On February 26th, 2012, 8:08 p.m., Mark Gaiser wrote:
    







    


    Review request for kdelibs, David Faure and Michael Pyne.
    

    By Mark Gaiser.
    



    Updated Feb. 26, 2012, 8:08 p.m.
    







    Description 
    
 
    
 
    
  
   
    I was running KWin through callgrind to see where possible bottlenecks are. I wasn't expecting much since it improved greatly during the 4.8 dev cycle, however one stood out. The saving of PNG images was taking about 1/5th of the time in KWin that i could see directly. That looked like something i might be able to optimize.

What this patch is doing is storing the actual image bits to prevent saving a PNG image to the mmapped cache. That was a hot code path in time (cycles), not even in calls.

-- update 26-02-2012 --
After spending a lot more time trying to get compression in the mix "someone" came with the suggestion to use KFilterDev. Never heard of it, but i gave it a shot anyway. It turned out to be the bull-eye in this case. Data is now greatly compressed using gzip (any other compression available in KFilterDev makes it a lot slower). Gzip gives some loss in speed, but compared to the current stock KImageCache it's still a _lot_ faster.

New benchmarks compared to the stock 4.8.0 KImageCache:
Read: ~8x faster (was 5x in my previous patch)
Write: ~5x faster (equally fast compared to stock, no speedup here in my previous patch)
Inserting the same image with the same key twice is now about free (depending on the size of the image, it's about free for icon sized images with 48x48).

I've also added a more detailed description of insertImage for the details that it saves. My point of view is that KImageCache should be used for caching of (system)images and perhaps thumbnails. Things like image text should not be stored since that should be fetched from the originating image. The color table (when available) is stored.

A last massive performance improvement that is possible but complicated to get is by using the IZ compression from "kdepepo". Just using IZ to compress the bits will make the image size a lot smaller then is currently done with gzip and will do it at the very least about 5x faster as well. That means insertion will benefit massively here. However, that will also mean that the stored image data is only going to be:
- width
- height
- format
- bits
No color tables! But this is something for the future. Right now the current diff is about fine. The last remaining issues are the possible race conditions as mentioned in the comments below. 
I need help in that area. I can't do what's suggested (i lack the knowledge to do it myself).

Special thanks go to David Faure for helping me a great deal with this.
    
      		
 
    

    



    Testing 
    

    
 
    
  
   
    I've also written a bunch of test cases (greatly improved by David Faure) to see if i didn't break anything. According to the test (which is also comparing the actual image bits) it's all passing just fine.
    
      		
 
    

    





    Diffs 
    

    Reply all
    Reply to author
    Forward
    0 new messages