Monday, June 1, 2009

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

No comments:

Post a Comment

Followers