MetropolisSampler::GetLazyValues() rng offset question

[Lord Crc]

Hi,

I was looking at the metropolis sampler, and there's a bit in GetLazyValues() I don't quite get. Here's the snippet

Code: Select all

         // If the node has not yet been initialized, do it now
         // otherwise get the last known value from the sample image
         if (time == -1) {
            const u_int roffs = data->rngOffset * static_cast<u_int>(stampLimit);
            for (u_int i = offset; i < offset + size; ++i)
               data->sampleImage[i] = rngGet2(i, roffs);
            time = 0;
         }
         for (u_int i = offset; i < offset + size; ++i)
            data->currentImage[i] = data->sampleImage[i];
         currentTime = time;
      }
      // Mutate as needed
      for (; currentTime < stampLimit; ++currentTime) {
         const u_int roffs = data->rngOffset * static_cast<u_int>(stampLimit - currentTime + 1);
         for (u_int i = offset; i < offset + size; ++i)
            data->currentImage[i] = mutate(data->currentImage[i], rngGet2(i, roffs));
      }


Now, the way I understand this is that time = -1 if the last value was from a large mutation, and then we mutate the value for the number of small mutations that we "missed" by not calling GetLazyValues for that value. What I don't get is the computation of "roffs" in the two blocks here.

Imagine the situation where time = -1 and stampLimit = 4. Then in the first block we compute roffs using stampLimit, which if of course 4. Then while "mutating up" the value we start by calculating roffs using stampLimit - currentTime + 1 = 4 - 0 + 1 = 5, then 4, etc down to 2.

This means that we use the same roffs value twice?

Also, why do we use stampLimit to initialize the value?

I don't have a solid grasp over this new QMC stuff in metropolis at all, it just raised a red flag: is it supposed to be like this?

An additional questions:
- Why do we use a non-zero offset to initialize the value in GetLazyValues if a small mutation has occurred after the large one?
- Why don't we use an offset when mutating "normal" values in GetNextSample?

edit: if these are dumb questions feel free to let me know, as I haven't had the time to study the paper you based this on.

[jeanphi]

Hi,

I guess you're right that there's something fishy and a -1 would probably be better than the current +1.
The initialization is done with stampLimit so that for the last mutation we end up in the right pseudo random numbers range, and using negative values is would require special treatments to prevent reading data outside the memory range.
GetNextSample does not have to use those offsets because it is called at every new sampling iteration so it never has to catch up.

Jeanphi

[Lord Crc]

Thanks for the answers. I'm still not 100% sure about the logic here, but I'll take a few more passes over the code.

The reason I started looking into this was due to A-man's lovely cornell box. Metropolis starts out good (~35kS/s) but quickly grinds to a halt, slowing down by a factor of 7 (~5kS/s).

I did some profiling and found that 95% (!!!) of the total rendering time is spent in MetropolisSampler::GetLazyValues(), specifically on the bit which updates the mutations.

I've now just tried a version which mutates all the values always, ie in GetNextSample, so that GetLazyValues just returns the correct pointer. For this scene it seems to be a lot faster, about 15x faster (~75kS/s) than doing the "lazy mutations".

From my debugging the problem is that the "currentTime" is far behind the "stampLimit", for example with values 0 and 7 respectively. And it seems this happens a lot. I'm trying to understand how this can come about.

If this is an intended behavior, perhaps we could have a parameter to control if we should do lazy mutations or not, for scenes like this.

[SATtva]

perhaps we could have a parameter to control if we should do lazy mutations or not

Can you describe implications of each option in a few words, please?

[Lord Crc]

Can you describe implications of each option in a few words, please?

If you have a scene where most paths terminates after a few bounces, but some important ones can have many bounces, then you need a high maxdepth.

The current scheme (lazy, or on-demand, evaluation) fits well with this setup, as it avoids doing a lot of work mutating the sample values for "deep bounces" that is seldom used.

The alternative is to fully mutate all the values right away, instead of on-demand. For scenes described above this can lead to wasted work.

However the way it is currently implemented, it seems that the work done mutating a value on-demand is somewhat more time consuming than if it was generated right away. Thus for scenes where the average path length is close to the max, this will lead to more work. For such scenes it would be best to compute everything up front.

However do note that I don't fully understand the current scheme, especially if this behavior of the lazy evaluation is intended or a defect.

[A-man]

I've now just tried a version which mutates all the values always, ie in GetNextSample, so that GetLazyValues just returns the correct pointer. For this scene it seems to be a lot faster, about 15x faster (~75kS/s) than doing the "lazy mutations".

I want this

[SATtva]

Thanks for the explanation Lord Crc, very interesting. I guess we need some testing.

[jeanphi]

Hi,

I guess most of the penalty comes from cache misses because you'll end up spanning a large range over the pseudo random data, the computations themselves are not that complex.
I agree this code is a bit of a hack and maybe removing some of the "smartness" in there might allow the optimizer to do a better job. When I introduced the feature the speed boost was really impressive, so the issue might be elsewhere. I've never seen a render grinding to a halt like that in recent times. It was often because one forgot to clear the contributions list in the sample.

Jeanphi

[Lord Crc]

I'll have to analyze the behavior a bit more. My current theory is that for some reason it "forgets" the mutations it's performed in GetLazyValues, restarting from scratch more often than it has to. I can't see how cache can have that much of an effect.

I'll dig some more

[jeanphi]

Hi,

A question I've never really answered is the possibility to not apply any mutation at all for the first time a value is requested: since the first value is random mutating it around shouldn't or not shouldn't make a difference, however we are using pseudo random values so I'm not sure this applies. This would remove a lot of computations by simply initializing the initial time to the current time.

Jeanphi