Krita: transactions, swapping and new fastBitBlt for tiled data manager

It was almost two weeks ago when I blogged last time. It was very tough those weeks because I had to merge two processes at the same time: preparations for an examination at the university and coding on Krita. But nevertheless, I'm glad announce much progress in my project for Krita!

Transactions refactoring

I've finally commited my patchset for transactions in Krita [1]. So now there is almost nothing common between Qt's QUndoCommand and Krita's KisTransaction (from the public side :)). It was needed to allow pooler (and upcoming swapper) threads to work efficiently. Now every transaction has the beginning and the end. So when you end a stroke on the canvas you finish a transaction as well. The pooler recognizes this signal and starts doing his routine job to optimize your next stroke (while you are still thinking about it ;)).

There are big changes from a developer point of view as well. Now you can create a transaction in a stack instead of a heap, that makes the code much simplier. And the most curious artefact of Krita's past was removed. There was a "global variable" in every KisDoc2 that used to disable saving undo information while loading the document. This variable had to be checked thoughout all the code of Krita: in every tool, in every action. Now it has gone. New tile engine does initial document loading in a cheap and fast way.

If you are interested in details of the new transactions system you can read a design document here. Examples are given!

Region() interface for paint devices

After finishing with transaction I continued my work on preparation to Filter API redesign. I've added a feature to a paint device for getting a QRegion of non-transparent (non-default) pixels. Of course it is based on tiles, and the region is rounded by 64. It is intended to be used as optimization of filter's application. You can read the details in Filter API Discussion Notes, that happend between Cyrille Berger and me in Deventer.

FastBitBlt interface for paint devices

This is part of Filter API redesign as well. The interface simply shares tiles between different paint devices. It allows us to create clones of devices really fast! It is intended to be used in layer merging subsystem and during filter application. There are limitation in this interface as well: it cannot be used when paint devices are shifted and when their color spaces do not coincide.

Framework for tile compression

After some discussion with Cyrille and his experiments with LZF algorithm, I started implementing tile compression framework inside the tile engine (Cyrille has already added nessecary features into KoStore to allow delegating compression to it). I'm going to kill two rabbits with one shoot, by doing this. The first "rabbit": Krita will be able to work with various formats of saved tiles. It means that we will be able to modernize the tile format without losing back compatibility. And the second: this framework will be the first stone in the swapper subsystem's building!

Krita: New Transaction System For Review

Today the new API for transactions has been finished!

It turned out that Krita can't fully rely on QUndoCommand functionality, so on Deventer sprint it was suggested to modify our transactions [1]. Now I'm glad to show you results of the work done.

Shortly, the new system is based on two classes, the first represents the boundaries of the transaction, while the second defines the lifetime of the undo information. Touching base transaction classes caused much code to be revised, but now it is done.

So now, if you want to get more details about new system, you can read a complete description on our wiki page.

You can even take part in testing of the new system by applying the patch.

[1] - http://wiki.koffice.org/index.php?title=Krita/Filter_API_Discussion_Notes

Krita: canvas will not flicker anymore!

Many have already seen this annoying bug in Krita canvas update system. It was seen when you painted with big and complex brushes like Hairy Brush on a multilayer image. Now I'm glad to announce that the patch is produced! And it will be in trunk soon!
The bug was caused by a race condition between Image and UI threads. The latter one tried to read the data from the merged projection while the former one was preparing it. I have fixed this by splitting the update process into two parts. The first part reads data from the image. It is executed in the context of the Image thread. Then the thread saves update information got from the canvas to the external structure called KisUpdateInformation and passes it to the UI thread, that continues updating doing rescaling and other slow operations.

This patch touches much code in canvas subsystem, so there will be a short delay for reviewing and testing the patch. And if you want to see it in trunk faster, you can help testing it! [0]

There are some technical details of implementation in our wiki [1]

[0] - http://dimula73.narod.ru/canvas-split-single-v2.patch
[1] - http://wiki.koffice.org/index.php?title=Krita/KisCanvas2_Update_Split_Reasoning

GSoC Krita tile engine wrap-up

The summer has almost gone, GSoC has finished..

I had two aims for my project: the first was to make a new, good, able to swap and compress tile engine for Krita and the second was to make a mipmapping subsystem. They are in trunk now, but they both are in testing state.

Features

Let's take a look what features do they suggest:

Tile engine

I had to refactor most of tile-subsystem code. New tiles can be easily shared, that helps much during saving undo information. Speaking strictly, now we don't have to save this undo information just before painting. This is done in deferred way, in a separate thread. It means that new engine has a very good perspective on multiprocessor systems.

Unfortunately i didn't manage to finish swapper thread in time. Too much time was spent on the second task. That is one of the resons why this engine is still in a "testing" state.

Mipmapping

This task was quite difficult to perform. Adding new canvas caching and prescaling engine caused much code of KisPrescaledProjection to be refactored. So i spent most of the time on that. Now mipmapping stuff itself is finished, but much of Krita merging and threading code must be revised. We've faced with many paint artefacts caused by race conditions in a merging mechanism. That is why at the moment i'm working on that part of Krita. After solving all the issues with threading mipmapping will be a very good option for users to optimize their zooming.

How to activate

As i said these features are being tested for now. This means they are not turned on by default, but if you are interested, you can always try them out!

New tile engine activation HOWTO:

This feature needs recompilation of Krita.

1) svn co svn://anonsvn.kde.org/home/kde/trunk/koffice
2) cd koffice
3) .. edit a file ./krita/image/CMakeLists.txt ..
.. change a line ..
set(USE_TILESYSTEM 1)
.. to ..
set(USE_TILESYSTEM 3)
4) make -j3 install

Mipmapping activation HOWTO:

For mipmapping you needn't recompile anything :)
Just set an option in your kritarc configuration file

useMipmapping=true

This file is usually stored in ~/.kde4/share/config/kritarc

We are in trunk!

New Krita tile engine is in trunk now on! You can try, test, see, change it! =)

Just checkout a trunk and switch engine in krita/image/CMakeLists.txt file
To activate a new one set USE_TILESYSTEM to '3'

Mipmapping for Krita's canvas subsys

Hi, all!

The tile engine has already come over to a quite stable state by this moment. I think today i'll publish patches for trunk. So now i'm publishing my ideas about mipmapping feature of viewing mechanism.

Well, mipmapping could be added in two parts of krita: the first - before actual merging and the second - after merging.

* The first could be done inside KisPaintDevice class and all merging would be done with prescaled images.

Pros:
+ we merge only small images, not fullsized big ones
+ as a consequence, filter layers and masks are applied much
faster

Cons:

- too much overhead, in memory and in cpu time. Actually, a huge

piece of work is done for nothing. Parts of image pyramids
will never be used at all.
- complexity of the system: alignment between layers
- probable artefacts caused by merging after scaling

* The second - in KisPrescaledProjection. We merge original images, then create a pyramid of a projection and scale at last.

Pros:
+ not so much overhead as we create only one pyramid for a view
+ zooming works fast thanks to the pyramid
+ no scale-merge artefacts.
+ no problems with alignment

Cons:
- no help to filter layers

I think the second variant is better. At least for the beginning. So i'm going to add it to KisPrescaledProjection. More than that, i could try to make this image pyramid as encapsulated of the canvas subsystem as possible, so in fueature it could be ported to a paint device if needed, or even made as a template.

As i investigated, KisPrescaledProjection have three main entry points (input methods):

->updateCanvasProjection(rect)
->preScale()
->resizePrescaledImage(size)

These methods fit for image pyramid very well:

updateCanvasProjection() would start a thread that would eventually update pyramid

preScale() would request scaled image from pyramid.
It would look like:
QPainter gc(m_prescaledQImage);
...
m_imagePyramid.drawScaledImage(gc, ..., ..., scale);


Here is a mockup of an interface of a KisImagePyramidClass:

class KisImagePyramid {
public:
        void updateCanvasProjection(QRect rect);
       
        /**
         * Here are some problems with scaleX/scaleY
         * as for image pyramid they should be equal
         */
        void drawScaledImage(QPainter gc,
             QPointF topLeftScaled /* target topLeft point */,
             QRect rectUnscaled /* source rect in image */,
             qreal scale);
private:
        QVector m_pyramid;

        KisProjectionCache /* or QImage */ m_original;
        QThreadPool m_pyramidUpdater;
};

What do you think about this idea? Maybe i've missed something?
As always, comments are welcome! =)

PS:
There are some points where i'm in doubt now:

1) Should we use KisProjectionCache for storing original image or simple QImage? I guess not, because it could be used much in drawScaledImage much.

2) Which zoom-levels should be stored inside m_pyramid? I saw that when you press Ctrl+'+'/'-' Krita switches across some finite number of levels. Which part of Krita/Koffice decides, which levels to use? I guess, these levels and levels in m_pyramid should agree :)

3) KisPresceledProjection::Private::prescaledQImage vs
KisPresceledProjection::Private::prescaledQPixmap?
What is the difference and where are they mostly used?

The Memento Manager started his work

The Memento Manager subsystem has been added into new Krita tile engine. It's quite raw, but passes tests in tests/dm_consistancy_test/ folder. Some names changed, but idea is the same.

Here are the links to test:

http://websvn.kde.org/?view=rev&revision=981347

or

svn co svn://anonsvn.kde.org/home/kde/branches/work/koffice-feature-tiles-ng/

To run a test:

cd krita/image/tiles3/tests/dm_consistancy_test/
qmake
make
./dm_consistancy_test |less

PS:

I already know that i should make
s/dm_consistancy_test/dm_consistency_test :)
Next time =)

Krita: Memento story

Every post brings us nearer and nearer to a new working tiled data-manager. This time i'd like to share my ideas about new Memento-subsystem for KisTiledDataManager.

The main goal of refactoring current KisMemento-system is to reject the idea of “ensuringTileMementoed” inside data-manager (DM) class. I think DM should know nothing about internals of memento-mechanism. From some point of view mementos should work in a way like SVN or Git does. DM should know just how to “commit” a newly created revision into repository (KisMementoManager class) and “checkout“ some previously created one. And no ensureTileMementoed() needed.

Well, that was an idea. Here are details about implementation.

How am I going to throw away ensureTileMementoed? COWing. We should base all our system on COWing. Lets imagine...

Once upon a time there was a Memento Manager. He was very pedantic and knew history of every citizen (tile) in his town. He stored it in a list that was called m_revisionsList. It consisted of smaller lists of KisMementos which stored citizen's accomodation (m_col, m_row) and state (m_tileData). How did he know everybody's history? It's simple! They said it to him themselves! Every time a tile wanted to write some data (KisTile::lockForWrite called) it checked whether there were some other users of the tile-data (TD). If there were some, it got new piece of tile-data and registered it in a Memento Manager's office (KisMementoManager ::registerTileData(td, col, row)) saying: “Hey, doc! I've got a new data!”. The Memento Manager saved this TD in a temporary list (m_indexList) called “index” (do you remember “index” term in Git?) and incremented KisTileData::m_refCount counter. By this time TD structure had only one COW-user (it was our KisTile object), so all lockForWrite() calls wouldn't cause any COWing. But TD-object itself couldn't be freely deleted from memory and corrupt m_indexList's pointres, because The Manager held it's m_refCount counter.

Time flied and DM decided to make a commit. He said about it to The Memento Manager (KisMementoManager::commit()) and the latter one appended m_indexList into the end of m_revisionsList acquiring all items of index for COW'ing (incrementing KisTileData::m_usersCount). From this moment all call's to KisTile::lockForWrite() would cause activation of COW. So tile-datas stored in m_revisionsList were untouched.

When DM would want to restore some revision it would get a bunch of tiles, committed by last commit, would search their's parents and restore them.

=)

* Deletion of tiles should be done in the same way.

* The thing I haven't thought over properly is searching parents of mementos.

If you have some comments or ideas or objections you are welcome to say them here or in the maillist! =)

TledDataManager first tests

Here is a commit that adds a first rough draft of KisTiledDataManager.

http://websvn.kde.org/branches/work/koffice-feature-tiles-ng/

At the moment it can't be fully attached to krita, it doesn't have mementoes and so on.. But it's able to perform tests.. But we shall speak about them a bit later.

First thing to discuss is implementation. The thing i don't like in current engine is that all functions of datamanager are done in the only class (hash table, tile walkers, parts of memento mechanism are all places into KisTiledDataManager). I tried to split those things and got three classes (not counting memento subsys.): KisTiledDataManager itself, KisTileHashTable and KisTileProcessor. Let's look at them.

KisTileHashTable is the simplest one. There is just simple hash table that creates elements on demand. It relies on COW mechanism so no difficult work should be done inside it. The only problem is race condition is getTileLazy(). m_RWLock is taken twice in this function: firstly in getTile for read, and secondly in linkTile() for write. Theoretically it can happen that another tile with the same (col,row) will be created and added between these locks. There are two ways to solve it: write __getTile() function that doesn't lock anything (all the things in linux kernel are done this way), or just write class KisReadWriteLock : public QReadWriteLock {...}; that implements public relockForWrite() method (i can't remember for sure, but linux kernel has such an ability too). I'm thinking which way to choose... :) Of course this is not so important atm... ;) Well, here are some tests in image/tiles3/tests/test_tiles_cow/ folder, that include testing KisHashTable. The first test performed by this program creates tileHashTable of 300x100 tiles, then deletes some of them. It wouldn't be so interesting if it didn't print details of this operations. After each of these two steps it shows object distribution inside hash table. More exactly, how many tiles are stored inside every head of hash-list. Of course it doesn't show every head of 1024, the table looks like [number of tiles] - [how many heads have that very amount of tiles]. The most interesting thing is that about 80% of heads have the same number of items in the list. It means that access to the tiles is done in almost constant time. (btw, hash function is taken from old datamanager, so that is not an invention =) )

Let's perceed to KisTileProcessor class. I wanted to have a unified object that could be applied to tiles in unified way. More than that it could be done in threaded way. And i have done it. Done it for read/write operations inside data manager. These classes are KisTileReadWrite{,Planar}Processor. They work, they read and write perfectly! And that is corroborated by the last two tests in .../test_tiles_cow/ folder. The problem is, object oriented approach creates a great overhead in time. And that is disappoiningly corroborated by tests in image/tiles3/tests/dm_perfomance_test. On uniprocessor PC tile-processors work 20% slower than old data-manager. I'm thinking over this problem now... Much time is spent in constructors, destructors, shared-ptrs... If someone is interested, i could give him a callgrind.out...

And the most interesting thing about KisTileProcessor is that there is NO gain in multithreading. *Absolutely nothing!*. I tried it on T7250. Most of the time both cores are stalled. They are simply waiting for memory request to finish.

So by this moment i decided to perform read/write in non-threaded way. But i want to leave processors inside data-manager so as a great number of operations could be done with them.

Well, thinking...

PS:
HOW TO RUN TESTS
There are two tests:

   image/tiles3/tests/test_tiles_cow/
   image/tiles3/tests/dm_perfomance_test/

Both of them are qmake projects, so the only thing you should do:

   $ cd [whatever you want]
   $ qmake
   $ make
   $ ./[executable]

If it won't compile, check include paths in [folder_name].pro
=)

First step of tile engine

Today i've implemented the things projected in previous post. I couldn't imagine that multithreading programming is so exciting! =) It's a pretty good exercise for brains :)

The three classes mentioned earlier are committed to http://websvn.kde.org/branches/work/koffice-feature-tiles-ng/. New tiles engine called "tiles3" ;). Some details are changed, but the idea remained the same. Of course you can't build krita with this engine =), but you can test some features of it with a simple test suite located in krita/image/tiles3/tests/test_tiles_cow/. The list of "features" is quite short yet. Atm it simply creates a few tiles and shares tile data between them with CopyOnWrite mechanism.

And there are a few issues i have already faced with. The main is deadlocks. There can be a plenty of situations when the tilesystem will be stuck in the lock forever. And the worst thing we can't use "Ostrich algorithm" suggested by Tannenbaum! =). At the moment i see the only solution for this problem: locking rules.

So "the first great locking rule" sounds like:

Everytime lock for read first.

E.g. if you want to copy some data from one tile to another (and they both share the same tiledata) you should acquire the source first, and only then acquire the destination.

Here is kind of "variations table". Imagine tile1 has already acquired some lock, but tile2 wants to acquire it too (both use the same tiledata).
A guess there are many rules to be discovered. But i hope they i'll be able to encapsulate them inside iterators.

Krita's tilesystem project idea

Some days ago i've thought over my GSoC project for Krita. Here are my ideas how to refactor KisTilesDataManager.

I'll begin with the lowest level: KisTile. New KisTile class will be an abstraction of a tile that doesn't store the actual data of the image itself (actual data is stored in tile-data object, that can be shared by several tiles). Tile-class will encapsulate locking and copy-on-write mechanisms.

Tile-data objects are created by special class that is in charge of storing, compressing and swapping data. It's name is KisTileDataStore. Tile-data objects are stored in linked list. New objects always added in the tail of the list so swapper thread can walk from head to tail and swap out old stuff; the old stuff will be accessed first.

Let's imagine the situation when we need to access some tile for read.

1. We call tile->acquireForRead
2. It acquires tile->m_tileData->m_RWLock for read
3. Checks whether tile->m_tileData->m_state==NORMAL
   a) if not calls tileDataStore->getTileDataToMemory
4. Allows user to read tile->m_tileData->m_data

Access for write:

1. We call tile::acquireForWrite
2. It acquires tile->m_tileData->m_RWLock for write
3. Checks whether m_refCount==1 (we are the only user of tile-data)
   a) m_refCount--
   b) if not, COW. tile->m_tileData = tileDataStore->allocNewTileData()
4. Checks whether tile->m_tileData->m_state==NORMAL
   a) if not calls tileDataStore->getTileDataToMemory()
5. Allows user to read tile->m_tileData->m_data

Creating new tile object (KisTile::KisTile):

1. tile->m_tileData = tileDataStore::getDefaultTileData()
   defaultTileData object is shared by all tiles, so it has m_refCount field higher than 1, so it'll be replaced by a new tile-date on the first write request.