My ideas about GSOC Tiles project

Dmitry Kazakov dimula73 at
Tue Mar 24 20:44:08 CET 2009

On Tue, Mar 24, 2009 at 8:34 AM, Boudewijn Rempt <boud at> wrote:

> > 1) The first thing to implement is Mipmapping. I've come to a conclusion
> > that mipmapping should be done at the level of Layer's projection (e.g.
> > KisPaintLayer::Private {KisMipmappedPaintDevice projection; ...}). This
> > KisMipmappedPaintDevice class should be derived from KisPaintDevice and
> > support most of it's methods. The difference is that mipmapped class will
> > have pyramid of scaled images.
> Are you sure that KisPaintDevice is the right level, instead of
> KisDataMananager/KisTiledDataManager -- I'd have thought that adding a
> KisMipMappedDataManager would be a more likely solution. I was also
> thinking
> of havinga  KisUntiledDataManager for those paint devices that are
> ephemeral
> and small, like brush footprints.

Well, my motivation were cases A and B =)

caseA {

> > Why should it be put here? Let's look at the case when we have the only
> > PaintLayer. In such a case, applying of any paintop we'll change 1-2
> tiles.
> > All the rest tiles will be untouched, and of course their scaled-down
> > versions will stay untouched too. It turnes out that we have to scale
> only
> 1-2 tiles instead of scaling the whole image.

caseB {

> > The things are a bit more difficult with Adjustment Layers because most
> of
> > them need the whole image for processing. But there are a few filters
> that
> > could benefit from mipmapping at the layer stage. E.g. Perchannel Filter.
> > It could process scaled-down picture while previewing (previewing is the
> > _worst_ thing in this filter at the moment). All the filters could have a
> > method KisFilter::NeedsOriginalImage() that would say whether filter can
> > work on downscaled image.

Maybe we are both right ;) The implementation should be spread between
KisDataManager and KisPaintDevice. Now i've got how to describe that:

We have to add a new layer of abstraction (not sure this term is right here)
to these classes: that is "current zoom level". The problem of current code
is hiding in impossibility to work with image sizes different from original,
so to say we _always_ have to work (modify, compose from layers, project
them) with entire unscaled image. In some cases (see "caseA") this make a
huge overhead. As i've understood from the code, the caseA in the current
revision of the code works like that:

1) PaintOp changes a couple of pixels on some tile (scale 100%)
2) KisGroupLayer activates KisMergeVisitor, that in turn copies
KisPaintLayer->d->m_paintDevice to ... to __root_layer->d_m_projection
3) Then KisQPainterCanvas::paintEvent comes, this function in turn:
    a) calls KisImage::convertToQImage through classes
KisPrescaledProjection and KisProjectionCache
         * 2boud: Why this KisProjectionCache is needed at all? I guess if
caching and zooming is done in Tiles, this class (and KisPrescaledProjection
too) will be happily removed
    b) KisImage::convertToQImage converts entire image stored in
__root_layer->d_m_projection to QImage
      * Till this moment we have done a dozen of operations on *original
unscaled image*. Remember point 1) - we've changed a couple of pixels of the
only tile.
    c) KisPrescaledProjection scales down image
    d) result returned to KisQPainterCanvas
4) KisQPainterCanvas draws these two pixels =)

Have i understood the architecture right?

When we introduce "zoom levels", we'll be able to request from paintDevice
any zoomed-version of original image. Speaking about caseA, the Tiles
subsystem will know that only one tile changed and will scale it down.
Resulting projection will consist of prescaled old tiles and the new one.
Writing to the paintDevice by all the paintOps should always be done to 100%
level, but reading at any level. There is only exception - previewing (see
caseB). Preview mechanism will feed filters with scaled-down versions of
image, stored in internal m_previewPaintDevice (or just checkout scaled-down
version from paintDev. to m_previewQImage, that is issue for dispute).

So, i see "zoom levels" like that:

  Tiles subsystem                    KisTiledPaintDevice
| ---------------- |                |--------------  |
| *stores pyramids |<----some------>|   it's *only*  |
| *caches tiles    |<-*!internal!*->|    inteface    |<-...External
| *scales tiles    |<----links----->|    to tiles    |<-...interface
| *etc...          |                |   subsystem    |
|                  |                | (with drawing, |
*------------------*                |   of course)   |

External interface should be smth like:

|--convertToQImageNew(zoomlevel_struct zoomlevel)
|--drawSomething(zoomlevel_struct zoomlevel)
| LEGACY PART (works only at 100% zoom)

struct zoomlevel_struct {
    enum {
    } should_use_m_scale;
    double m_scale;

In such a case algorithm for caseA will be much simplier and more efficient:

1) PaintOp changes a couple of pixels on some tile (scale 100%)
2) KisGroupLayer activates KisMergeVisitor, that in turn copies
KisPaintLayer->d->m_paintDevice to ... to __root_layer->d_m_projection
    This step is like in previous case, except of _all the operations are
made in current zoom-level_ (disputable?) and prescaled-down tiles cached
3) Then KisQPainterCanvas::paintEvent comes, this function in turn:
    a) calls KisImage::convertToQImage just copies
__root_layer->d_m_projection (all the work is already done).
4) KisQPainterCanvas draws these two pixels =)

Yes, such a flag is needed. We might want to do a little refactoring with
> all
> our flags, though. Maybe create an enum and a test function,

> following Qt4 api
> conventions.

Where should i read about it?

> > More than that, layer-level mipmapping can be used while creating the
> > projection of the root layer.
> >
> > Question. Could someone tell me, will the result be different in these
> two
> > situautions:
> > Assume we have two *PaintLayers*.
> > 1) first we Merge them, then Scale down
> > 2) first we Scale them down, then Merge
> > Will the result be different? (or, more precisely, will the result be
> > *much* different)
> I think we need to experiment with this. My gut feeling says "yes, there'll
> be a discernable difference".

Mine agrees with yours=) But i guess it's bearable for preview (e.g.

Also note that the current zoom level of the
> canvas is rarely stable, people tend to zoom in and out a lot, which means
> that we don't win much by not compositing the levels that aren't in current
> use.

Ideally we shouldn't compose layers at all, we should compose tiles, but i
can't imagine how atm :)

> The gimp, btw, has currently already something like this, I believe. I
> haven't
> had time to check their source code yet, though.
> > If the difference is too small, then we could use pyramid in
> > KisMergeVisitor to create a projection.
> >
> > (the last issue can't be applied in case we have at least one Adjustment
> > Filter in the stack, in this case we should consult with
> > KisFilter::NeedsOriginalImage() first. BUT this approach works well with
> > Filter Masks, as in such a case filters brake only one pyramid that can
> be
> > quickly recalculated)
> >
> > 2) Locking and threading. I think locking should be made something like
> > linux kernel's deferred irq subsystem. Every MipmappedPaintDevice should
> > have its own working thread. Most of the time it sleeps on it's
> > working_queue's semaphore. When work appears it goes to work_queue, the
> > semaphore gets up and thread goes on calculating piramids for the tiles
> > listed in workqueue.
> Sounds good.
> > In addition every tile should have it's own read/write semaphore.
> Also think of COW and concurrent reads and so on.

Something like Read-copy-update (RCU) in linux? I guess it's too weird for

> > 2b) Swapping. Again, one KisTiledDataManager - one swapper thread. This
> > thread could work without workqueue. Just go though existing tiles and
> find
> > unneeded. The concurrent access to tiles is controlled by tile's
> > RW-semaphore.
> Right now I thin, we have one swapper thread -- if it's a thread and not
> part
> of the main loop -- because we have one big pool of tiles instead of
> separate
> pools for every paint device. This did give us quite a bit of performance
> boost back in the days when it was created this way.

What was the cause of this boost?
I'll think over idea of united storage. But on new processors the more
threads the better ;)

> > 3) In memory compression. I'm not sure i'll have time for good on-the-fly
> > compression engine, but it can be made in swapper thread.
> We have a good compression engine for on-the-fly work already -- Ariya
> Hidayat
> made it and did some experiments that showed that keeping lesser-used stuff
> in
> compressed form in memory before swapping (and uncompressing on undo) would
> indeed save us a lot of memory and also quite a bit of performance, since
> the
> compressed tile would take fewer memory reads to get into the processor
> cache.

I've not thought about compressing of mementoed tiled. Sounds great.

> > Could someone comment on this plan and tell me what should i do next?
> It looks cool. Chew a bit on it and then enter a proposal with Google.

> > PS:
> > What does KisProjection do? Where is it used? I've not seen it's
> > declarations in layers' classes.
> It used to do multi-threading of recompositing and was owned by KisImage.
> I'm
> currently reworking it to work with the new stateless recompositing scheme,
> but I've run into a Threadweaver bug I haven't had time to fix yet.

i see

Taking into account the parallel thread about full-time working. I have four
exams at the university in the beginning of June, but i hope to manage to
pass two of them in advance in May. So at least two of them are left for
June and it'll take at least 9 days. Can it prevent me from GSOC?

/* in the beginning */
heh.. let's sit down and write a short reply...

Dmitry Kazakov
-------------- next part --------------
An HTML attachment was scrubbed...

More information about the kimageshop mailing list