Projects/Summer of Code/2007/Projects/Icon Cache: Difference between revisions

Latest revision as of 13:52, 31 May 2007

Abstract

To improve startup times of KDE applications, I plan to create an icon cache which would store all icons in a common location. This would eliminate the need to scan tens of directories for icon locations, thus reducing disk seeking. And as the cache would consist of only two files, it would often be wholly cached in the memory by the operating system, eliminating disk access completely. Furthermore, the cache enables loading icons directly from SVGs, using any scale, as the SVGs need to be converted into pixmaps only on the first use. Finally, the cache would make it possible to support simple icon compositing, making it much easier for third-party applications to provide icons which always fit into user's current icon theme.

Author: Rivo Laks

Mentor: Aaron Seigo

Code

Code will be available from KDE's SVN server, under /branches/work/soc-iconcache

Implementation

The icon cache will consist of two files: one will be index and the other will hold the actual data.

Index

Index will be implemented using AVL- or B-tree

Every entry in the index consists of:

Hash (e.g. md5) of the icon, computed using:
- Icon name
- Icon size
- Effects applied to the icon?
- ...
offset of this icon's data in the data file

Data

The data file entries have:

Icon name
Icon size
Effects applied to the icon?
Statistics?
- Last used timestamp
- Number of uses
Path of the original icon file?
and of course data, probably compressed with e.g. qCompress()
- is there any advantage in storing uncompressed data? would it make it possible to use mmap() and share the icon data between processes?

Those entries are written directly one after another. As we needn't support deletion of entries, this will be the most simple & fastest way.

Daemon

To keep the cache's size within reasonable limits, a daemon similar to kio_http_cache_cleaner would periodically check it's size. If the cache is too big, the daemon would rebuild it from scratch, using most recently and frequently used entries until cache's size is 80% or so of the limit. This would avoid having to support on-the-fly deletion of entries and thus make the cache faster. This would

Additionally the daemon can be used to periodically rebuild the cache, arranging it's contents into a more favourable pattern:

move most often used icons to the beginning of the file -> might reduce seeking
move icons with similar last-used timestamps together -> icons used by single app would be together
- makes sense only for icons which aren't very frequently used (frequently used ones go to the beginning of the file)

@@ Line 1: / Line 1: @@
-==KDE Icon Cache==
+==Abstract==
-===Author===
-Name: Rivo Laks
-Mentor is Aaron Seigo
-===Abstract===
 To improve startup times of KDE applications, I plan to create an icon cache which would store all icons in a common location. This would eliminate the need to scan tens of directories for icon locations, thus reducing disk seeking. And as the cache would consist of only two files, it would often be wholly cached in the memory by the operating system, eliminating disk access completely.
 Furthermore, the cache enables loading icons directly from SVGs, using any scale, as the SVGs need to be converted into pixmaps only on the first use.
 Finally, the cache would make it possible to support simple icon compositing, making it much easier for third-party applications to provide icons which always fit into user's current icon theme.
+Author: Rivo Laks
+Mentor: Aaron Seigo
-===Code===
+==Code==
 Code will be available from KDE's SVN server, under /branches/work/soc-iconcache
-===Implementation===
+==Implementation==
 The icon cache will consist of two files: one will be index and the other will hold the actual data.
-The index file will hold pairs of keys and offsets where key is md5 or similar hash of the requested data (e.g. "<icon name> <size> ...") and offset is offset of the data associated with this key in the data file.
+===Index===
-Index will probably be implemented using either AVL- or B-tree.
+Index will be implemented using AVL- or B-tree
+Every entry in the index consists of:
+* Hash (e.g. md5) of the icon, computed using:
+** Icon name
+** Icon size
+** Effects applied to the icon?
+** ...
+* offset of this icon's data in the data file
+===Data===
+The data file entries have:
+* Icon name
+* Icon size
+* Effects applied to the icon?
+* Statistics?
+** Last used timestamp
+** Number of uses
+* Path of the original icon file?
+* and of course '''data''', probably compressed with e.g. qCompress()
+** is there any advantage in storing uncompressed data? would it make it possible to use mmap() and share the icon data between processes?
+Those entries are written directly one after another. As we needn't support deletion of entries, this will be the most simple & fastest way.
-The data file will consist of icon datas, written one after another. One such data would contain name of the icon, last used timestamp, it's size, applied effects (e.g. greyscale) and of course the pixmap data itself (probably in a compressed format).
+===Daemon===
+To keep the cache's size within reasonable limits, a daemon similar to kio_http_cache_cleaner would periodically check it's size. If the cache is too big, the daemon would rebuild it from scratch, using most recently and frequently used entries until cache's size is 80% or so of the limit. This would avoid having to support on-the-fly deletion of entries and thus make the cache faster.
+This would
-To keep the cache's size within reasonable limits, a daemon similar to kio_http_cache_cleaner would periodically check it's size. If the cache is too big, the daemon would rebuild it from scratch, inserting 80% or so of the most recently used entries. This would avoid having to support on-the-fly deletion of entries and thus make the cache faster.
+Additionally the daemon can be used to periodically rebuild the cache, arranging it's contents into a more favourable pattern:
+* move most often used icons to the beginning of the file -> might reduce seeking
+* move icons with similar last-used timestamps together -> icons used by single app would be together
+** makes sense only for icons which aren't very frequently used (frequently used ones go to the beginning of the file)