[prev in list] [next in list] [prev in thread] [next in thread]
List: kde-kimageshop
Subject: Re: My ideas about GSOC Tiles project
From: Dmitry Kazakov <dimula73 () gmail ! com>
Date: 2009-03-24 19:44:08
Message-ID: ae32c1ef0903241244y620a8d61q3b9eec06d2a4fc70 () mail ! gmail ! com
[Download RAW message or body]
[Attachment #2 (multipart/alternative)]
On Tue, Mar 24, 2009 at 8:34 AM, Boudewijn Rempt <boud@valdyas.org> 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:
*-
| MIPMAPPED PART
|
|--convertToQImageNew(zoomlevel_struct zoomlevel)
|--drawSomething(zoomlevel_struct zoomlevel)
|--...
|
|----------------
| LEGACY PART (works only at 100% zoom)
|
|--convertToQImage()->
|--drawSomething()->
|--...
|
*-
struct zoomlevel_struct {
enum {
ORIGINAL=0,
NOT_ORIGINAL
} 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.
filters)
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
that.
> > 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
PS:
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?
PPS:
/* in the beginning */
heh.. let's sit down and write a short reply...
=)
--
Dmitry Kazakov
[Attachment #5 (text/html)]
<div class="gmail_quote">On Tue, Mar 24, 2009 at 8:34 AM, Boudewijn Rempt <span \
dir="ltr"><<a href="mailto:boud@valdyas.org">boud@valdyas.org</a>></span> \
wrote:<br><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, \
204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;"> <div class="im">
> 1) The first thing to implement is Mipmapping. I've come to a conclusion<br>
> that mipmapping should be done at the level of Layer's projection (e.g.<br>
> KisPaintLayer::Private {KisMipmappedPaintDevice projection; ...}). This<br>
> KisMipmappedPaintDevice class should be derived from KisPaintDevice and<br>
> support most of it's methods. The difference is that mipmapped class \
will<br> > have pyramid of scaled images.<br>
<br>
</div>Are you sure that KisPaintDevice is the right level, instead of<br>
KisDataMananager/KisTiledDataManager -- I'd have thought that adding a<br>
KisMipMappedDataManager would be a more likely solution. I was also thinking<br>
of havinga KisUntiledDataManager for those paint devices that are ephemeral<br>
and small, like brush footprints.<br>
<div class="im"></div></blockquote><div><br>Well, my motivation were cases A and B \
=)<br><br>caseA {<br></div><blockquote class="gmail_quote" style="border-left: 1px \
solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;"> <div>
> Why should it be put here? Let's look at the case when we have the only<br>
> PaintLayer. In such a case, applying of any paintop we'll change 1-2 \
tiles.<br> > All the rest tiles will be untouched, and of course their \
scaled-down<br> > versions will stay untouched too. It turnes out that we have to \
scale only <br></div></blockquote><blockquote class="gmail_quote" style="border-left: \
1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;"> <div \
class="im"> > 1-2 tiles instead of scaling the whole image.<br>
</div></blockquote><div>}; <br><br></div><div>caseB { <br></div><blockquote \
class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt \
0pt 0.8ex; padding-left: 1ex;"><div class="im"> > The things are a bit more \
difficult with Adjustment Layers because most of<br> > them need the whole image \
for processing. But there are a few filters that<br> > could benefit from \
mipmapping at the layer stage. E.g. Perchannel Filter.<br> > It could process \
scaled-down picture while previewing (previewing is the<br> > _worst_ thing in \
this filter at the moment). All the filters could have a<br> > method \
KisFilter::NeedsOriginalImage() that would say whether filter can<br> > work on \
downscaled image.<br> </div></blockquote><div>};<br> <br>Maybe we are both right ;) \
The implementation should be spread between KisDataManager and KisPaintDevice. Now \
i've got how to describe that:<br><br>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:<br> <br>1) PaintOp \
changes a couple of pixels on some tile (scale 100%)<br>2) KisGroupLayer activates \
KisMergeVisitor, that in turn copies KisPaintLayer->d->m_paintDevice to ... to \
__root_layer->d_m_projection<br>3) Then KisQPainterCanvas::paintEvent comes, this \
function in turn:<br> a) calls KisImage::convertToQImage through classes \
KisPrescaledProjection and KisProjectionCache<br> /**<br> \
* 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<br>
*/<br> b) KisImage::convertToQImage converts entire image \
stored in __root_layer->d_m_projection to QImage<br> /**<br> * \
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.<br>
*/<br> c) KisPrescaledProjection scales down image<br> d) \
result returned to KisQPainterCanvas<br>4) KisQPainterCanvas draws these two pixels \
=)<br><br><br>Have i understood the architecture right?<br><br><br> 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).<br> <br>So, i see "zoom levels" like that:<br><br><span \
style="font-family: courier new,monospace;"> Tiles subsystem \
KisTiledPaintDevice<br>| ---------------- | \
|-------------- |<br> | *stores pyramids |<----some------>| it's \
*only* |<br>| *caches tiles |<-*!internal!*->| inteface \
|<-...External <br>| *scales tiles |<----links----->| to tiles \
|<-...interface<br> | *etc... | | \
subsystem |<br>| | \
| (with drawing, |<br>*------------------* | of course) \
|<br> \
*----------------*<br style="font-family: courier new,monospace;"> \
</span><br>External interface should be smth like:<br><br><font face="courier \
new,monospace">*-<br>| MIPMAPPED PART<br>|<br>|--convertToQImageNew(zoomlevel_struct \
zoomlevel)<br>|--drawSomething(zoomlevel_struct zoomlevel)<br> \
|--...<br>|<br>|----------------<br>| LEGACY PART (works only at 100% \
zoom)<br>|<br>|--convertToQImage()-><br>|--drawSomething()-><br>|--...<br>|<br>*-</font><br><br>struct \
zoomlevel_struct {<br> enum {<br> ORIGINAL=0,<br> \
NOT_ORIGINAL<br> } should_use_m_scale;<br> double \
m_scale;<br>}<br><br><br>In such a case algorithm for caseA will be much simplier and \
more efficient:<br><br>1) PaintOp changes a couple of pixels on some tile (scale \
100%)<br>
2) KisGroupLayer activates KisMergeVisitor, that in turn copies
KisPaintLayer->d->m_paintDevice to ... to
__root_layer->d_m_projection<br> This step is like in previous case, except \
of _all the operations are made in current zoom-level_ (disputable?) and \
prescaled-down tiles cached<br> 3) Then KisQPainterCanvas::paintEvent comes, this \
function in turn:<br>
a) calls KisImage::convertToQImage just copies __root_layer->d_m_projection \
(all the work is already done).<br> 4) KisQPainterCanvas draws these two pixels \
=)<br><br><br><br></div><blockquote class="gmail_quote" style="border-left: 1px solid \
rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;"><div class="im"> \
</div>Yes, such a flag is needed. We might want to do a little refactoring with \
all<br> our flags, though. Maybe create an enum and a test function, \
</blockquote><div> </div><blockquote class="gmail_quote" style="border-left: 1px \
solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">following \
Qt4 api<br>
conventions.</blockquote><div>Where should i read about it?<br><br> \
</div><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, \
204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;"><div class="im"> > More than \
that, layer-level mipmapping can be used while creating the<br> > projection of \
the root layer.<br> ><br>
> Question. Could someone tell me, will the result be different in these two<br>
> situautions:<br>
> Assume we have two *PaintLayers*.<br>
> 1) first we Merge them, then Scale down<br>
> 2) first we Scale them down, then Merge<br>
> Will the result be different? (or, more precisely, will the result be<br>
> *much* different)<br>
<br>
</div><br>I think we need to experiment with this. My gut feeling says "yes, \
there'll<br> be a discernable difference".</blockquote><div> \
</div><div>Mine agrees with yours=) But i guess it's bearable for preview (e.g. \
filters)<br><br></div><blockquote class="gmail_quote" style="border-left: 1px solid \
rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;"> Also note that \
the current zoom level of the<br> canvas is rarely stable, people tend to zoom in and \
out a lot, which means<br> that we don't win much by not compositing the levels \
that aren't in current<br> use.</blockquote><div> </div><div>Ideally we \
shouldn't compose layers at all, we should compose tiles, but i can't imagine \
how atm :)<br> </div><blockquote class="gmail_quote" style="border-left: 1px solid \
rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
The gimp, btw, has currently already something like this, I believe. I \
haven't<br> had time to check their source code yet, though.<br>
<div class="im"><br>
> If the difference is too small, then we could use pyramid in<br>
> KisMergeVisitor to create a projection.<br>
><br>
> (the last issue can't be applied in case we have at least one Adjustment<br>
> Filter in the stack, in this case we should consult with<br>
> KisFilter::NeedsOriginalImage() first. BUT this approach works well with<br>
> Filter Masks, as in such a case filters brake only one pyramid that can be<br>
> quickly recalculated)<br>
><br>
> 2) Locking and threading. I think locking should be made something like<br>
> linux kernel's deferred irq subsystem. Every MipmappedPaintDevice should<br>
> have its own working thread. Most of the time it sleeps on it's<br>
> working_queue's semaphore. When work appears it goes to work_queue, the<br>
> semaphore gets up and thread goes on calculating piramids for the tiles<br>
> listed in workqueue.<br>
<br>
</div>Sounds good.<br>
<div class="im"><br>
> In addition every tile should have it's own read/write semaphore.<br>
<br>
</div>Also think of COW and concurrent reads and so on.</blockquote><div>Something \
like Read-copy-update (RCU) in linux? I guess it's too weird for that.<br><br> \
</div><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, \
204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;"> <div class="im">
> 2b) Swapping. Again, one KisTiledDataManager - one swapper thread. This<br>
> thread could work without workqueue. Just go though existing tiles and find<br>
> unneeded. The concurrent access to tiles is controlled by tile's<br>
> RW-semaphore.<br>
<br>
</div><br>Right now I thin, we have one swapper thread -- if it's a thread and \
not part<br> of the main loop -- because we have one big pool of tiles instead of \
separate<br> pools for every paint device. This did give us quite a bit of \
performance<br> boost back in the days when it was created this way.<br>
<div class="im"></div></blockquote><div><br>What was the cause of this boost? \
<br>I'll think over idea of united storage. But on new processors the more \
threads the better ;)<br><br> </div><blockquote class="gmail_quote" \
style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; \
padding-left: 1ex;"> <div class="im">
> 3) In memory compression. I'm not sure i'll have time for good \
on-the-fly<br> > compression engine, but it can be made in swapper thread.<br>
<br>
</div>We have a good compression engine for on-the-fly work already -- Ariya \
Hidayat<br> made it and did some experiments that showed that keeping lesser-used \
stuff in<br> compressed form in memory before swapping (and uncompressing on undo) \
would<br> indeed save us a lot of memory and also quite a bit of performance, since \
the<br> compressed tile would take fewer memory reads to get into the processor \
cache.<br><div class="im"></div></blockquote><div><br>I've not thought about \
compressing of mementoed tiled. Sounds great.<br> </div><blockquote \
class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt \
0pt 0.8ex; padding-left: 1ex;"> <div class="im">
> Could someone comment on this plan and tell me what should i do next?<br>
<br>
</div>It looks cool. Chew a bit on it and then enter a proposal with Google.<br>
<div class="im"></div></blockquote><div><br> </div><blockquote class="gmail_quote" \
style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; \
padding-left: 1ex;"><div class="im"> > PS:<br>
> What does KisProjection do? Where is it used? I've not seen it's<br>
> declarations in layers' classes.<br>
<br>
</div>It used to do multi-threading of recompositing and was owned by KisImage. \
I'm<br> currently reworking it to work with the new stateless recompositing \
scheme,<br> but I've run into a Threadweaver bug I haven't had time to fix \
yet.<br> <font color="#888888"></font></blockquote></div><br>i \
see<br><br>PS:<br>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?<br> <br>PPS:<br>/* in \
the beginning */<br>heh.. let's sit down and write a short reply...<br>=)<br><br \
clear="all"><br>-- <br>Dmitry Kazakov<br>
_______________________________________________
kimageshop mailing list
kimageshop@kde.org
https://mail.kde.org/mailman/listinfo/kimageshop
[prev in list] [next in list] [prev in thread] [next in thread]
Configure |
About |
News |
Add a list |
Sponsored by KoreLogic