The DOs and DON'Ts of Filter Construction

I'm wondering whether we should start setting up broader categories for the entries. We've already got several entries on 'Blur' and 'Noise' for example...

Quote
Sphinx. wrote: Yeah, that might a good idea.. I have one more entry on blur, high passes and sharpens brewing..

Alright, I'll reorganize the entries once that second entry of yours has landed.

Quote
Crapadilla wrote: Btw. how about merging in the "Optimizing Filters for Speed" section?

Yup. That might be a good idea, since its also about efficiency!

Reorganized!

An interesting side-effect of collecting random blips of FF wisdom for writing this article appears to be that I'm checking out all my filters to see whether I could optimize them further. During this process I'm finding that - here and there - I haven't always exactly practised what I preached!

Looks like I'll be updating some filters soon...

Quote
Sphinx. wrote: Seems like its a generic mechanism: last coordinate and sample is cached at the output, and if next sample request has the same coordinate, it will return the cached sample, and implicitly if the coordinate doesn't match, a new sample will be calculated and saved as the new cached sample..

Yes, this is correct.

Quote
Vladimir Golovin wrote: Yes, we render a bitmap version of the source input, then blur it. There's a short article in the Help on this -- it is linked from help articles of Blur, HighPass etc.

Oh, its not as much the functionality of the bitmap based components I'm asking to - its the way I utilize that rasterization process as a way of buffering the input and thereby reducing the rendering time. Look at this filter and the comments for it. If you don't fancy this approach, I don't want to promote it further

Quote
Vladimir Golovin wrote: There's an option 'Show Elapsed Rendering Time' in Tools > Options -- use it to measure the rendering time.

Ah..great! I missed that option. Btw. I know this has been up to discussion before.. but some sort of rendering "report" would be really great - this report could describe where the performance culprits are - perhaps an option we can enable in filter construction mode, which then adds some sort of rendering time percentage to each module (including its subtree)...

Quote
Crapadilla wrote: Did you check this?

Yes, but the idea is different and more complicated there, and also the sample count may not be exact in expressing how fast a filteris - its the calculation of the sample that matters..

It should be easier to sum up performance percentages from subtrees simply by timing the individual components. Lets say we have a simple filter with three perlins equally fast connected to the surface result, then each component would have the timing labels:

result: 100%
perlin 1: 33.33%
perlin 2: 33.33%
perlin 3: 33.33%

or perhaps more realistic:

result: 100%
perlin 1: 30%
perlin 2: 30%
perlin 3: 30%

Which tells us that the result alone is resposible for 9.99% of the overall rendering time.

hmm.. looking at that filter now.. are you talking about the cluster that creates the red and blue fringe artifacts?

Quote
Sjeiti wrote: The weird thing is that my render time went up with ~175% after I applied the channels thing. So sometimes three offsets is faster than one offset plus some assemble disassemble RGB.

I have revisited some of my older filters and played around with the 'Channels' trick as well. Apparently it doesn't necessarily speed things up in all cases, so be careful! I'll have to experiment some more on this phenomenon.

It appears you'll have to take into account the speed of the component you wish to concatenate. Offsets are 'ultra-fast' while the Channel operations are just 'fast'.

So, did anyone toil through all that wiki rambling so far? Any critique, comments, suggestions, wishes, hate-mail?

Quote
Kraellin wrote: you lost me at the second post

Which one?

Quote
Kraellin wrote: but i just go to sleep when you start talking technical

Well, I guess that can't be helped then. The wiki article is about efficiency considerations, which will always be technical in nature.

Actually, I was hoping the articles would convey a glimpse at the 'mindset' that one needs to develop as a filter author, an attention to certain details. It's always a balancing act between the technical on the one and the artistical on the other hand...

Quote
Kraellin wrote: i still have no idea how a blur speeds things up

Me neither, I'm afraid.

Quote
Kraellin wrote: though i notice you've been revising quite a few filters lately, so, at least you learned something

Just optimizations mostly, but I will do a few complete overhauls here and there.

Quote
Vladimir Golovin wrote: Sphinx. wrote: Seems like its a generic mechanism: last coordinate and sample is cached at the output, and if next sample request has the same coordinate, it will return the cached sample, and implicitly if the coordinate doesn't match, a new sample will be calculated and saved as the new cached sample.. Yes, this is correct.

My question would be: If indeed the coordinate doesn't match, do the calculations for new sample draw upon the sample cache to retrieve their data, or does the original component that the cache was derived from get reevaluated?

Quote
Sphinx. wrote: For example using two duplicated components (with same settings) can be faster than using multiple outbound connections from one, if one or more (but not all) of the incoming coordinates have been changed by offsets or distortions (remember that the coordinate flow is "backward", i.e. going in through the outputs, which then returns a sample based on this).

Sphinx,

I'll have to admit I fail to understand how this could be the case (and what you mean by "backward" for that matter). If you ask me, this would go against the logic of the sample caching system, at least the way I understand it.

An example: If you have a high-detail worley noise with six outgoing connections, the noise gets calculated once. All six subsequent operations on this noise would then draw upon one-and-the-same preprocessed sample cache, making things much speedier. However, if there were six duplicate worleys instead, it is logical that FF would need to prepare six noises instead of one. Consequently, I would dare speculate that multiple connections are always faster than duplicates.



Vlad,

would you shed some light on this?

Quote
Crapadilla wrote: An example: If you have a high-detail worley noise with six outgoing connections, the noise gets calculated once. All six subsequent operations on this noise would then draw upon one-and-the-same preprocessed sample cache, making things much speedier.(...)

This is correct when the coordinates recieved from the outbound connections all are the same, but if the coordinates are different, it will cause a new sample to be calculated and as a generic behaviour the last calculated sample will always be stored in the cache - thats what Vlad confirmed.

Quote
Crapadilla wrote: I'll have to admit I fail to understand how this could be the case (and what you mean by "backward" for that matter). If you ask me, this would go against the logic of the sample caching system, at least the way I understand it.

Yes you are right, it seems counter intuitive, but let me explain how I understand it:

Lets first get perfectly clear on the difference btwn sample and coordinate flow. Each module can very simplified be thought of as a function that produces a sample from a coordinate (x, y). So in other words a module takes a coordinate and gives a sample, in that order! And we can then say that the sample flow direction goes from component to result, but the coordinate flow goes from result to component, because the coordinates are used to calculate the samples.

That FF uses a procedural sampling approach means that your filter will be executed for each pixel in the final image. If the image you are rendering is 2x2 pixels (and no AA enabled), the filter executes 2x2 times. For the first pixel, the result component will request a sample from the connected component, lets say this is a perlin noise, by feeding it the coordinate (0, 0). When the perlin noise has calculated the sample value, it stores the sample to a local variable/cache along with the coordinate that produced it.

Remember that this cache at all times hold only one sample: the last calculated. This goes on for the rest of the pixels, (0, 1), (1, 0) and (1, 1). So in a simple setup like this: [PERLIN]--->[RESULT], it is evident that the sample cache system can't improve anything, since the perlin only recieves a given coordinate one time per pixel - we need several outbound connections for this system to do any good.

So if there are six outbound connections from the perlin to a multiblend, which then goes to the result, the actual sample is only calculated once in the perlin, because the following five requests from the multiblend match the coordinate associated with the perlin cached sample.

If we have an offset inbetween the result and the multiblend, which offsets by 1 horizontally, then we would have this change in coordinate flow:

[RESULT]--(0, 0)-->[OFFSET X + 1]--(1, 0)-->[MULTIBLEND]-->[PERLIN]

And this means that the perlin would cache the sample for the coordinate (1, 0) and not (0, 0). Again we have no problem if there is many connections between the perlin and multiblend, because all coordinates have been offset by the same value.

The problem start showing if we move the offset in between the multiblend and perlin for only some of the connections, because then the perlin would recieve a mix of the coordinate (0, 0) for those connections without offset, and (1, 0) for those going through offset. How bad the cache flushing will be, depends on the actual setup.. The example filter I posted earlier in the thread shows how to contruct a bad case of constant sample cache flushing.

Actually there is a solution that could free us from worrying about this at all - an improvement to the samplecache system:

Any component that changes coordinates, should attach an ID number to its sources, making the sources spawn a new sample cache reserved for incoming requests with that ID

Quote
Crapadilla wrote: Very interesting! So which components apart from Offsets and Noise Distortions actually DO modify sample coordinates? I'm guessing pattern components with the jumble fill mode active, and maybe Kaleidoskopes?

Yep, and as mentioned also Refraction. Also I think the bitmap based components will change the sources cached samples as the bitmap based components buffer a large tile of samples, but it might not be as frequent though - I know too little about the actual blur rasterization to tell, but I think its split up into small cells of samples for optimization reasons..

The elevation gradient will also change the coordinates for its gradient source, as only the top row is used from the gradient source..

Quote
Sphinx. wrote: also my "danglish" could be a problem (I'm danish and my english is way too influenced by danish sentence constructions

I don't think this is the case Actually, when I visited Denmark, I was surprised by the fact that many people there speak English, and do this quite well -- especially young people.

Quote
Crapadilla wrote: Knowing this "order of processing" would allow us to predict when sample cache flushing would occur, wouldn't it?

Yeah, definitely - actually I'm experimenting with that just now, but it is getting really complicated, specially when you have "interbranch" connections (i.e. connections btwn two major branches/clusters of components) - predicting in which order things are executed is not very easy, and to get things even messier it seems that for some cases it doesn't matter which of two connections are executed first and therefore the execution order is the order by which you actually connected "parallel" components.. ouch, my analysis skills starts to dissolve here .. Vlad.. how about some indexed sample caching like proposed

Btw. another option for optimizing the coordinate "flow" would be to do a "test run" and for components with many outbound connections then sort the execution order so that sample requests belonging to a given coordinate are executed in sequence (it is probably more complicated than the indexed solution, but it should be slightly more memory and performance efficient). Here's the idea:

A component with several outbound connections as it is now, could receive the following sequence of coordinates (from different offset and so on) in a given branched filter construction:

(0, 0) - first sample
(10, 3) - cache flush/new sample
(0, 0) - cache flush/new sample
(10, 3) - cache flush/new sample
(7, 3) - cache flush/new sample
(0, 0) - cache flush/new sample

"recording" these changes in coordinate flow in a test run
would then allow the optimizer to sort the execution order so that we'd have the following order instead:

(0, 0) - first sample
(0, 0) - cache match
(0, 0) - cache match
(10, 3) - cache flush/new sample
(10, 3) - cache match
(7, 3) - cache flush/new sample

effectively reducing the cache flushes to a minimum

Quote
Crapadilla wrote: Vlad.. how about some indexed sample caching like proposed Wink

... or how about a 'console' that logs sample cache building and flushing on a per-component basis?

Quote
Crapadilla wrote: ... or how about a 'console' that logs sample cache building and flushing on a per-component basis?

This would require at least one conditional jump in the innermost cycle, which we definitely wouldn't like -- it will slow the rendering down for everyone, even for people who have the console turned off.

Quote
Sphinx. wrote: Quote Crapadilla wrote: Same here. And it shows drastic speed differences (28 sec VS. 49 sec). Ok! thats pretty significant - here the numbers are 1:34 for the duplicated and 2:44 for the non-dup. So there is definitely something to gain by having this fact in mind when hooking up components in a complex system

Inspired by this indexed sample cache proposal, I just made an interesting observation!
Try inserting an Invert component (disable invert) between the Perlin and the Offset in the non-duplicated branch It rendered at 1:36 which is very close to the duplicated branch. So it seems that the Invert's sample cache takes over somehow.. can you confirm that it works?

Quote
Crapadilla wrote: So, should we conclude this means that each and every component always maintains its own sample cache, regardless of the number of outgoing connections?

Yeah, every component has its own output sample cache, but only one sample cached - the last rendered/requested - so if you have different coordinate connections interleaved (like in my example filter), it causes constant recalculation (and cache flushing). By introducing a new intermediate component, like the Invert, you also add a new cache - very much like the indexed cache idea.

I think what is happening is that the Invert draws one time from the perlin, and from there on, the Invert's own sample cache will match all the next offset requests, effectively minimizing the flushes. This is more elegant than the duplicated component solution I think

But since every component has its own cache, this is also why the "problem" is not more prominent than it is, but there are still quite many situations where you could spare a sample calculation here and there by throwing in an Invert (with "invert" unchecked) and then dragging connections for a certain coordinate branch from that one..

This is quite interesting, and I definitely have to look at some of my filters in this regard.
Another related thing: IIRC the height tree draws more samples per output sample than the other surface inputs.. is that right? If so, then there could be some very significant optimizations by seperating connections to components shared btwn the height tree input and the other surface inputs.. haven't tested this though..

Quote
Crapadilla wrote: So which components apart from Offsets and Noise Distortions actually DO modify sample coordinates? I'm guessing pattern components with the jumble fill mode active, and maybe Kaleidoskopes?

Quote

Sphinx. wrote: Yep, and as mentioned also Refraction. Also I think the bitmap based components will change the sources cached samples as the bitmap based components buffer a large tile of samples, but it might not be as frequent though - I know too little about the actual blur rasterization to tell, but I think its split up into small cells of samples for optimization reasons.. The elevation gradient will also change the coordinates for its gradient source, as only the top row is used from the gradient source..

Vlad, could you give us an official confirmation on this list?

* Offset
* Noise Distortion
* Bricks (jumble)
* Pavements (jumble)
* Tiles (jumble)
* Kaleidoskope
* Refraction
* Bitmap-based components (?)
* Elevation Gradient