[1.1.68] noise.if_then_else does not short circuit when contion isn't a constant

[mrvn]

In my FractalMaps mod I generate an elevation function that is rather slow with many nested if_else_chain constructs. The elevation is defined recursively but looking at the result it has very regular squares. So instead of going through 11 levels of recursion before it hits a square I thought I would pull that to the top level and generate them with a simpler noise.less_than and noise.modulo expression and only do the complex recursive expression for the non trivial parts.

But somehow that just got slower. So I tried something simpler just to see how the speed changes. The original code for the recursive defintion is constructed like this:

Code: Select all

    return noise.if_else_chain(
      noise.less_than(48, abs(y)), make(t, x, depth - 1),
      noise.less_than(abs(x), 16), 1,
      noise.less_than(abs(y), 16), x,
      -1
    )

This generates a map preview in 44s. Now if I change it like this:

Code: Select all

    return noise.if_else_chain(
      1, 1,
      noise.less_than(48, abs(y)), make(t, x, depth - 1),
      noise.less_than(abs(x), 16), 1,
      noise.less_than(abs(y), 16), x,
      -1
    )

then it only takes 6s for the map preview. The noise function short circuits the evaluation and everything becomes land. 4.3s are spend on loading modules and 2s for the map preview. That's comparable to the vanilla noise function.

But if I change it like this:

Code: Select all

    return noise.if_else_chain(
      noise.less_than(x, 0), 1,
      noise.less_than(48, abs(y)), make(t, x, depth - 1),
      noise.less_than(abs(x), 16), 1,
      noise.less_than(abs(y), 16), x,
      -1
    )

Now only half the area matches the first condition. So I would expect this to take about 20-25s. But it actually takes 47s.

It looks like a "noise.less_than" expression doesn't allow the "if_else_chain" expression to short circuit and it still evaluates all the other expressions.

[boskid]

As far as i know about the noise expression internals (which is not much), noise programs when running are working as a SIMD, basically a compiled (to internal representation) noise program consists of many instructions and instruction works on a long vector of data: in case of a chunk, such vector will have 1024 values and all operations working on "registers" like adding will be in fact adding such long vectors to produce another vector. Given there may be some deduplication happening that reuses some of the subexpressions, they may still need to be evaluated even if not used by specific if_else branch. That means everything works as expected so far and this is a "not a bug", but i will wait with moving until someone else confirms this.

[Genhis]

Thanks for the report, the issue should be fixed for the 2.0 release.

[mrvn]

As far as i know about the noise expression internals (which is not much), noise programs when running are working as a SIMD, basically a compiled (to internal representation) noise program consists of many instructions and instruction works on a long vector of data: in case of a chunk, such vector will have 1024 values and all operations working on "registers" like adding will be in fact adding such long vectors to produce another vector. Given there may be some deduplication happening that reuses some of the subexpressions, they may still need to be evaluated even if not used by specific if_else branch. That means everything works as expected so far and this is a "not a bug", but i will wait with moving until someone else confirms this.

That sounds like they should get compiled as GPU code. But then why does a map preview use all 8 CPU cores?

Deduplication and reusing subexpressions is something you can also do manually:

Code: Select all

    local t = noise.delimit_procedure(128 * 2 ^ (math.floor(depth / 2)) - abs(y))

I found the internal compiler wasn't smart enough to lift that subexpression out of the formula. I have 11 of those (one per depth) in my noise function so maybe I was just overloading the compiler. Deduplicating that expression by hand was a major speed gain for me (factor 3 iirc). I have a lot of duplicate "abs(x)" and "abs(y)" expressions so maybe I should try deduplicating them by hand too. It stopped optimizing when it became playable.

The "make(t, x, depth - 1)" expression is the recursion and occurs nowhere else so there shouldn't be any deduplication being done there, or at least it shouldn't lift it out of the "if_else_chain". It should only evaluate the deduplicated expression if that branch is taken.

[mrvn]

Thanks for the report, the issue should be fixed for the 1.2 major release.

Thanks, looking forward to it. I keep going back to playing factorio, best money I ever spend.

[Bilka]

It should only evaluate the deduplicated expression if that branch is taken.

In 1.1 if you're not working with constant values (noise.var("x") is not a constant value), every branch of the if else chain is always evaluated. At least, that's afaik how I wrote the code.

If you want to get around that, you can try to not use the if else chain. You can use that less_than returns 0 or 1 and use it as a multiplier instead of as an if condition. From my notes, most likely based on something by Maxreader: "return result * boolean + otherResult * (1-boolean)". No guarantees that this is better, but it should be slightly less naive than 1.1.x if else chain.

[mrvn]

It should only evaluate the deduplicated expression if that branch is taken.

In 1.1 if you're not working with constant values (noise.var("x") is not a constant value), every branch of the if else chain is always evaluated. At least, that's afaik how I wrote the code.

If you want to get around that, you can try to not use the if else chain. You can use that less_than returns 0 or 1 and use it as a multiplier instead of as an if condition. From my notes, most likely based on something by Maxreader: "return result * boolean + otherResult * (1-boolean)". No guarantees that this is better, but it should be slightly less naive than 1.1.x if else chain.

I will give it a try but I can't see that working at all, unless evaluation is operators before operands and right to left. The boolean has to be evaluate first and then the multiplication has to see "Oh, it's 0, I don't need to evaluate the left operand at all". Would surprise me a lot if that works. I mean it's probably operators before operands because that's the tree structure you create for a noise expression. But right to left? I will try "boolean * result" as well in case it only works left to right.

Trying right to left:

Code: Select all

    expression = noise.clamp(make(var_x, var_y, depth), -1, 0) * 0

46s, slight slowdown for the extra multiplication?

Trying left to right:

Well, right to left evaluation might make sense the way the operator overloading is done in noise: "0 * expr" ==> attempt to perform arithmetic on a table value. "tne(0) * expr" it is.

Code: Select all

    expression = tne(0) * noise.clamp(make(var_x, var_y, depth), -1, 0)

45s, same thing withing the margin of error.

Doesn't seem to work either direction. Will have to wait for 1.2 then.

[Genhis]

Thanks for the report, the issue should be fixed for the 1.2 major release.

Thanks, looking forward to it. I keep going back to playing factorio, best money I ever spend.

It seems that I misread your bug report. After reading through it again, the main issue in your report is not fixed, I'm sorry. 'If' expressions with variable conditions can't short-circuit because, as boskid says, values are processed in batches of 1024 (one chunk). Furthermore, procedure operations are computed sequentially with prerequisites resolved beforehand, so 'if' can only compute its result after values of all its inner expressions are known. Therefore, this is not a bug.

You can, however, expect improved performance of 'if' conditions in 1.2. Every condition does its own memory allocation in 1.1, so the performance (excluding complexity of its arguments) scales linearly. In 1.2, conditions re-use the buffer created for each map generation thread.

[mrvn]

Thanks for the report, the issue should be fixed for the 1.2 major release.

Thanks, looking forward to it. I keep going back to playing factorio, best money I ever spend.

It seems that I misread your bug report. After reading through it again, the main issue in your report is not fixed, I'm sorry. 'If' expressions with variable conditions can't short-circuit because, as boskid says, values are processed in batches of 1024 (one chunk). Furthermore, procedure operations are computed sequentially with prerequisites resolved beforehand, so 'if' can only compute its result after values of all its inner expressions are known. Therefore, this is not a bug.

You can, however, expect improved performance of 'if' conditions in 1.2. Every condition does its own memory allocation in 1.1, so the performance (excluding complexity of its arguments) scales linearly. In 1.2, conditions re-use the buffer created for each map generation thread.

I can see how that might apply since every tile of those 1024 might pick another branch of the if-else-chain and the boolean condition is just a selector that selects the pre-computed value A or B. Bug god is that inefficient.

Could there be a special expression to compute a value for a chunk? That would then be a constant for those 1024 tiles.

[Genhis]

This would require a large rework of the noise program system. A noise program, which noise expressions get compiled into, has no concept of branches. All operations in a procedure are sequential and their result can be reused within the procedure if needed. It is similar to delimit_procedure deduplication system but within the same procedure, which is more efficient for standard use case.

Currently, there are no plans to add branches to this system.

[mrvn]

I was thinking of something like this:

Code: Select all

local constant = noise.delimit_procedure_chunk(expression_using_chunk_coordinates)
noise.if_else_chain(constant, expr1, expr2)

It would actually be already enough if "if_else_chain" checks if a variable is identical for all 1024 tiles:

Code: Select all

noise.if_else_chain_chunk(condition, expr1, expr2)

The use of "if_else_chain_chunk" is there so the identical check is only done when the programmer indicates this to be likely to help. If the condition is identical for all tiles then this goes into the same code path as if condition is a constant, if it fails then the other code path is taken. This would probably be the easier thing to implement.

[Genhis]

Yeah, I understand what you mean but it is not easily doable.

The only thing if-else does is deciding which of already computed values should be forwarded/returned from the expression based on the condition. At runtime stage, 'if' has hard depencendies on its arguments, as do all noise operations, i.e. it can't start its logic until all arguments are calculated. This is because all operations in a procedure are computed in sequence. They don't know their dependencies because they were already ordered correctly.

Adding branches and true conditional execution to the system could make it unnecessarily complex and would likely degrade performance for vanilla game or mods which don't use conditions on a large scale.

[mrvn]

Yeah, I understand what you mean but it is not easily doable.

The only thing if-else does is deciding which of already computed values should be forwarded/returned from the expression based on the condition. At runtime stage, 'if' has hard depencendies on its arguments, as do all noise operations, i.e. it can't start its logic until all arguments are calculated. This is because all operations in a procedure are computed in sequence. They don't know their dependencies because they were already ordered correctly.

Adding branches and true conditional execution to the system could make it unnecessarily complex and would likely degrade performance for vanilla game or mods which don't use conditions on a large scale.

But when the condition is a literal then it works. Is that the compiler eliminating the "if" in that case?

[Genhis]

Yes, the compiler can eliminate one of the branches during the compilation process. It can also simplify expressions, such as addition of two constants, to improve runtime preformance as much as possible. The condition doesn't strictly have to be a literal, elimination also works with per-surface constant variables (map seed, starting positions, etc.), or anything which can be simplified into a constant at compile time.

The compilation happens when a surface is created and the resulting noise program is then used for all chunks on that surface. So, only variables which are the same for all chunks can be treated as constants.