Saturday, June 13, 2009

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:


svn co svn://

To run a test:

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

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

Monday, June 8, 2009

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! =)

Monday, June 1, 2009

TledDataManager first tests

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

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...

There are two tests:


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