Redstone dust updates cause lag

Dupe of MC-76561

@Sonic I disagree. He is talking about lag, not knowing what causes it, as well as talking specifically about 1.7 worlds running in 1.8 servers. I am talking about (pretty much) all versions of Minecraft, while also providing proof and a thorough explanation of the phenomenon.

Is any of this a "feature" to Redstone designers that would have to be considered before rewriting the implementation? (The performance savings sounds worthwhile regardless. I'm just curious.) For example, if two things on the same circuit are at power-13 and power-12, will the power-12 one always depower first, and does that ever matter?

I read your note about the affected versions but you should still specify it as all the versions it allows you to select.

@@unknown as of this moment you can only select the current version 1.8.7, so he has selected everything he can.

Well this explains a lot.

@m0rsk - It might matter for some very specific redstone designs, but very few if it does. Don't think it does. The order things get powered makes a lot more difference than the order they lose power.

could you test it with your mod + optifine on? im curious to see if optifine has this fixed

Interesting. @unknown has talked about overhauling how redstone is implemented for various reasons, but hasn't gotten around to it because they've been busy with other massive changes to the game engine. Considering Notch's coding style, the current implementation was probably designed as a brute force approach to ensuring signals propagated correctly under all circumstances, knowing that a more efficient solution probably existed, but not wanting to expend the effort to find it unless necessary. You say that this is a simple fix, can you provide some code examples of the necessary changes?

Is this the same bug? youtu.be/uNX6evLpAkw?t=7m35s
It seems to be way worse in 1.9 than in 1.8.

Not really the place for it, but that most definitely looks to be because of lag, but I see not reason to assume it's just because of the redstone. I'd think there's something else going on on that server, or they just decided to take the 10 dollar option this time. Anyway, no real point in thinking about what could be the cause on someone else's server with many other things going on.

No, they have run an 1.8 world with about 20-30 redstone related YouTubers on it without mayor problems. This is the start of a new world in 1.9 and it already lags that much.

There is no reason to think this has changed from 1.8 to 1.9. This isn't the place for baseless assumptions.

Ok, then this is probably not the bug report I'm looking for. Thank you!

Performance video/example attached. Edit: Look not only at the lagspikes, have an eye on "chunk updates"

Although one needs to assume that the real lag "culprit" are light updates, the lag caused by redstone seems to add to it, as far as we can tell.

Comparing the lag/lag spikes of the same thing between 1.8 and 1.9 shows that it was already existing in 1.8, but 1.9 made it worse.

Whatever caused this change, it's making redstone-/piston-related contraptions unplayable even for more than decent hardware, let alone people with generic normal or bad computers.

@Mods: Is there any bugpost where people complain about lag caused possibly by light updates?

After MC-94438 I feel we should gather all lag posts if that would be possible in a way, to have an overview.
"Relates to" would be likely not the correct term, but I'm out of my wits in how we could gather and address all possible lag issues, so Mojang could work on all of them alongside.

@Meri Diana

There is a bug report for lag created by huge lighting updates MC-11571, but not one specifically for 1.9.

The only source of light reaching the pistons in that video is the redstone torch, right? Does the lag disappear if you remove it(and power the pistons differently)?

@unknown I just asked Spire (RedstoneSpire) to be so kind to reply to that, he setup that contraption and is more suited than I could ever be regarding redstone };]
He'll get back to you asap.
^{sorry for meta-discussing @mods}

I attempted to create a fix for this and MC-11193.
There is a more lengthy post about it over at MC-11193.

Also I can confirm for 1.10.2 😉

I wonder if having redstone set itself to its highest received power level, instead of decreasing by 1, would not break anything. Should in theory cut, by about 50%, the number of updates when turning off a wire. I still think the mod Panda made is better but I'm just trying to suggest something Mojang could do that would be better than what we have now.

Confirmed for 16w41a.

Hi, Everyone,

I have been investigating this issue and MC-11193 for some time now. I have two optimizations that I want to present, both of which affect exclusively BlockRedstoneWire. I have a more advanced optimization (also confined to BlockRedstoneWire) that is so far making redstone wire depowering 23 times faster and also fixes MC-11193, without breaking any of the numerous tests we have performed (other than removing nondeterminism and counterintuitive update orderings). More on that when I am more confident.

But for right now, I'm just going to present a really simple change that results in a 45% improvement in speed for redstone wire depowering.

I'm working from MCP code decompiled from 1.12.2. There is a method called BlockRedstoneWire.calculateCurrentChanges, with the following signature:

private IBlockState calculateCurrentChanges(World worldIn, BlockPos pos1, BlockPos pos2, IBlockState state)

And here is pseudocode for important steps it performs:

1. Set i to the current redstone power based on the state passed in.

2. Set j to the current redstone power of pos2, by calling this.getMaxCurrentStrength.

3. Set k to what is returned by worldIn.isBlockIndirectlyGettingPowered(pos1).

4. If (k > 0 && k > j - 1), set j equal to k.

5. for (EnumFacing enumfacing : EnumFacing.Plane.HORIZONTAL), setting l to the maximum power of neighbor blocks.

6. If l > j, set j to l-1; otherwise decrement j.

7. If k > j-1, set j to k.

8. If the power level of this wire is going to change (i.e. if (i != j), then compute a new block state and add this block and its neighbors to the list of blocks to update.

The optimization is as follows:

• Remove the whole if statement at #4. It's redundant to #7.

• Wrap the whole for loop at #5 with if (k<15), because if k is 15, then this redstone wire will be set to 15 no matter what.

• Remove the testing at #6 and #7.

• Replace them with this:

j = l-1;
if (k > j) j = k;

If you're super paranoid that k might be out of range for whatever reason, you can put back in otherwise redundant checks to make sure that j is in the range of 0 to 15.

Here is what this accomplishes:

• When a redstone wire block sees that its neighbors' values have reduced, instead of decrementing, its power level is set directly to the highest neighbor minus 1.

• When depowering a whole wire or mesh, most wire values will go down by 2 at a time instead of 1. Consider the following arrangement or a redstone torch and three pieces of wire: torch, 15, 14, 13. If you break the torch, then the 15 will get an update and notice that it has a neighbor at level 14, so it will now set itself to 13.

• For wire blocks that have odd values, their last update will go down only by 1 (from 1 to 0). As a result, block updates are reduced only by 45% on average.

• Redstone dots drop directly from 15 to 0.

• Due to the use of HashMap, update ordering is completely unchanged. Only the number of updates is reduced.

I and several others (people from SciCraft, two from Mojira, and other technical users and modders) have tested this extensively. Nobody has observed any behavioral changes at all. All they noticed was that you could do about twice as much work before experiencing lag. In fact, Xcom added it to carpet mod, and SciCraft's creative server has been running it for a while now, and nobody has noticed anything.

I hope the developers will consider implementing this simple change.

Thanks.

Update: I totally didn't notice Bengineer8's comment, which anticipated what I implemented by more than a year. He totally deserves recognition for his suggestion. And to answer his question, YES. We've had maybe a dozen people (modders, mojira moderators, expert players) testing the heck out of this implementation. Absolutely no behavioral changes have been identified. The change has been in carpet mod for some time now on SciCraft CMP for quite a while, and even the most esoteric things that rely on quirks of redstone update order seem to be completely unchanged in behavior.

I realize that the devs are busy with a snapshot. But snapshots are naturally times when people expect bugs and instability. So now might actually be the best time to introduce this optimization.

@Timothy Miller
Thank you for the recognition. Glad that it doesn't break anything and som1 implemented it. : )
I agree that now would be a great time to implement it but I doubt they will but who knows?

Hi, everyone,

I have been working for nearly a month, in most of my spare time, on finding ways to improve the performance and undesirable behaviors of redstone wire. Depowering can be especially compute-intensive, and update order is both random and nondeterministic due to HashSet behavior. I have focused my attention on the execution critical path for computing new wire power levels and propagating them to neighbors, and I have found many inefficiencies whose mitigation would improve Minecraft performance across the board. For instance, there are multiple methods in World that compute the 6 cardinal neighbors of a given block position. During redstone wire depowering, the neighbors of the same positions are recomputed over and over again. BlockPos objects are immutable, so repeating the same work introduces wastes a great deal of time, and I found a simple caching mechanism to yield a significant performance boost. However, since this and other such global optimizations are not specific to redstone wire, I will not be presenting them here.

Before I continue, I realize that the developers are very busy with the 1.13 snapshot. However, it is during snapshot periods that instabilities and behavioral changes are expected, making this an ideal opportunity to identify any undesirable effects. Moreover, this is also an opportunity for developers to offer an olive branch to the technical community, addressing two problems that affect them severely, serious lag and inconsistent behavior.

Some time ago, our esteemed friend Panda4994 uploaded an improved implementation of BlockRedStoneWire. I skimmed quickly over his code, and I had also read a great deal of the comments on this bug report, albeit a very long time ago, so some statements below may be inaccurate. From what I can gather, the reasons that Mojang declined to implement Panda's improvements include the following:

• It affected code outside of BlockRedstoneWire and/or replicated code from elsewhere in Minecraft.

• Concerns were raised about changes to block update order breaking existing redstone contraptions.

• It's a ground-up rewrite of BlockRedstoneWire, which would require too much developer time to analyze and reimplement in the real Minecraft code.

• Something about it being "messy," although I'm not sure what that's supposed to mean.

While I would not be at all surprised if Panda's implementation outperformed mine, I have set out to develop an accelerator for redstone wire that is more likely to be adopted because it addresses each of the above concerns, as follows:

• No Minecraft code outside of BlockRedstoneWire is affected by this accelerator.

• Changes to BlockRedstoneWire are minimal.

• The bulk of the new functionality is implemented in a new helper class, making it straightforward to drop the new code into Minecraft with negligible refactoring.

• The helper code is carefully written, with copious commenting in order to make its operation as clear as possible.

You can think of this accelerator code as being analogous to a bolt-on after-market supercharger that is designed for minimal installation effort. (Despite the fact that I used the word 'Turbo' in the class name, I do know the difference between a supercharger and a turbocharger. 'Turbo' sounds cooler and uses fewer letters.)

You can find the new code in the file "RedstoneWireTurbo.zip" attached to this bug report. Inside, you will find the following files:

• BlockRedstoneWire.java – Updated version of BlockRedstoneWire that implements the 45% performance improvement I posted about earlier and hooks into the helper class that contains the optimized redstone wire code.

• BlockRedstoneWire.diff – The differences between the vanilla BlockRedstoneWire code (from MCP for 1.12.2) and the modified version.

• RedstoneWireTurbo.java – Helper class that implements the improved and performance-optimized redstone wire update algorithm.

Main features of this redstone wire performance accelerator include the following:

• As stated above, changes to BlockRedstoneWire are very limited and no other classes are affected.

• The choice between old and new redstone wire update algorithms is switchable on-line.

• The unmodified Minecraft code relies on World.notifyNeighborsOfStateChange for redstone wire blocks to communicate power level changes to each other, generating 36 block updates per call. This optimized implementation propagates power level changes directly between redstone wire blocks. Redstone wire power levels are therefore computed more quickly. Since redstone power level states are computed internally, no block updates are necessary from redstone wire to redstone wire. Block updates are sent only to non-redstone blocks, many of which may perform an action when informed of a change in redstone power level.

• Of the 36 block updates generated by a call to World.notifyNeighborsOfStateChange, 12 of them are obviously redundant (e.g. the west neighbor of the east neighbor). These are eliminated.

• Updates to redstone wire and other connected blocks are propagated in a breath-first manner, radiating out from the initial trigger (a block update to a redstone wire from something other than redstone wire).

• Block updates are scheduled both deterministically and in an intuitive order. This addresses bug MC-11193.

• All redstone behavior that used to be locational now works the same in all locations.

• A few behaviors still depend on orientation; for instance, west is processed before east.

• Information that is otherwise computed over and over again or which is expensive to to compute is cached internally for faster lookup. This includes coordinates of block position neighbors and block states that won't change behind our backs during the execution of the search algorithm.

• Redundant block updates (both to redstone wire and to other blocks) are heavily consolidated.

• For worst-case scenarios (depowering of redstone wire) this results in a reduction of block updates by as much as 95% (factor of 1/20). Due to new overheads and old inefficiencies, empirical testing shows a speedup better than 6x. This addresses bug MC-81098.

• Worst-case powering-on has block updates reduced by a factor of about 8.8. Real time performance performance boost is about 61%.

Extensive testing has been performed to ensure that existing redstone contraptions still behave as expected. Results of early testing that had identified undesirable behavior changes were addressed. Additionally, real-time performance testing revealed compute inefficiencies with earlier implementations of this accelerator. Some compatibility adjustments and performance optimizations resulted in harmless increases in block updates above the theoretical minimum. That being said, 1.13 already introduces some important changes to redstone behavior. For instance, observer and comparator update priority have been reversed, which risks breaking many redstone designs that rely on specific within-tick update orders. Any changes to update order caused by my accelerator are likely to have less impact.

This redstone accelerator was first implemented on my testing server and has now also been added to carpet mod. The consensus of the testers (which include moderators from Mojira, members of SciCraft and ProtoTech, and other experts in redstone design) is that the changes are a distinct improvement over the current implementation. Observations include:

• Block updates that used to be random and nondeterministic all now make sense.

• The activation of other redstone components now follows an order that is strictly a function distance from the input signal.

• Some machines that used to work or not work depending on location now work the same regardless of location.

• Zero-tick behaviors are preserved and are now 100% reliable regardless of position and orientation.

• Numerous complex test cases were built, none of which showed any breakages (with one caveat, explained below), and the only changes observed were some really behaviors that made no sense before are eliminated, replaced by reliable, deterministic, intuitive behavior.

The only "breakage" that remains is one found by ilmango. To get an instant dropper line, there is this weird hack involving powered and activator rails and quasiconnectivity. This trick wasn't completely reliable, though, sometimes breaking depending on position or orientation. With the optimized redstone code, it no longer works at all. HOWEVER, with the optimizations, all you have to do to get an instant dropper line is to lay redstone wire on top of a line of droppers and power the wire at the input end of the dropper line. Where this previously did not work in all orientations, it now world 100% reliably in ALL orientations. This includes vertical (where you spiral blocks and redstone wire up or down around the droppers).

As I mentioned above, there are many other optimizations that can be made, but most of them can be implemented independently and will synergize with this one.

I have the following individuals and more to thank for their help in testing this new code:

• pokechu22 (Mojira)

• MethodZz (SciCraft)

• WARBEN

• NarcolepticFrog (ProtoTech and SciCraft)

• CommandHelper, aka nessie (ProtoTech)

• ilmango (SciCraft)

• OreoLamp

• Xcom6000 (SciCraft)

• tryashtar (Mojira)

• RedCMD

• Smokey95Dog (ProtoTech)

• EDDxample

• Rays Works (ProtoTech)

• Nodnam

• BlockyPlays (FrostCraft)

• TT (Dugged), for his jungle tree farm

I uploaded a replacement RedstoneWireTurbo.zip. I took some suggestions for clearer variable names, spelling correction in the comments, etc.

After some time of people testing my older redstone wire accelerator and using it in Carpet Mod, I was very pleased to have the opportunity to show it to Grum. He liked the fact that it was non-locational and deterministic. His main complaint was that it was still directional (some behaviors would change depending on orientation).

After a lot of work and a few false starts, I solved that problem too. The bread-first traversal of redstone wire implemented by the accelerator works out the direction of information flow, which we'll call "forward." The redstone wire and other block updates are now stored in a left-to-right ordering, which is inherited through wire fanouts. As a result, the new implementation is now also non-directional, where left always wins over right when there are conflicts (like pistons pushing into the same space). Overall, this enhancement makes redstone wire faster, behave the same regardless of position and orientation, deterministic (exception explained below), and much more intuitive. (Other redstone components are unchanged, so it's still possible to get directionally-affected behavior when using things like repeaters, redstone torches, etc.)

It is possible to build ambiguous machines, where "forward" cannot be determined (e.g. wire is powered from below); in that case, initial ordering is decided randomly. (Something that Grum said he prefers over position and orientation dependencies.) Since you can design your machines explicitly to have ambiguous orientation, this randomization can be made to occur when you want it to and put to good use. (NarcolepticFrog built one such machine on my testing server.)

My previous version (the one uploaded to Mojira) also broke compatibility with a few obscure redstone designs. For instance, ilmango showed me an instant dropper line that used alternative powered and activator rails. I found ways of fixing these incompatibilities by generating some specific extra block updates (e.g. above and below the current position at Y+2 and Y-2 get double updates, but at different times). (With the accelerator, you can now make instant dropper lines just by laying redstone wire on top of droppers.) On my redstone testing server, as far as I know, there are no contraptions that work with vanilla but break with the accelerator. On the other hand, there are lots of new contraptions that used to behave in weird or inconsistent ways that now all work in completely sensible ways. Xcom put my latest code into Carpet Mod, so SciCraft CMP and a few other tech servers have been running this for some time now, with no complaints.

While I was at it, I made some other code optimizations, and now the accelerator boosts redstone peformance by about a factor of 10. (That factor of 10 accounts for both powering and depowering of redstone wire, along with other CPU overhead on the main thread.)

Before I attach my new code here, Pokechu22 has been working on some improvements to code clarity. There are a few arrays of ints that are hard to interpret, although the comments explain them. He has been working on turning those into enums. If Enum.ordinal() isn't completely optimized away by the JIT compiler, or there are other performance impacts, one thing we can do is provide the code wth arrays of Enums that are converted at load time, in a static {} block, into int arrays.

If you want to look at my latest version, here is a link to my dropbox:
https://www.dropbox.com/sh/hk586vbdb9pl18o/AADNLMisAzIL2yzHQclObpCua?dl=0

BlockRedstoneWire.java is the MCP decompile of the redstone wire class, plus the changes necessary to bolt on the accelerator. A unified diff against the original is provided in BlockRedstoneWire.diff. RedstoneWireTurbo.java contains the accelerator itself. The source files also include some boolean flags to enable/disable different acceleration features. The code is very heavily commented, and I have tried very hard to make it understandable, but I would be happy to receive constructive criticism (probably on /r/Mojira or EigenCraft).

I was able to lag a strong server to less than 1tps with a lot of blinking redstone dust
But with the fix enabled I could run at a solid 20tps, even on my Chromebook!

This would be a very good fix to do in 1.15 as it's intended as a bug fix update. Incredible work by the community, it fixes almost any redstone lag on my test server.

My redstone accelerator is now integrated into the core of the Paper server modding framework. You can turn it on using a config file entry. Thank egg82 for doing the integration work.

Still in 20w18a

Can confirm 1.16 pre release 5

Still present in 1.16.1

Related to MC-190891

Can confirm for 20w27a

In 1.17.1 and 21w39a with setting priority updates: nearby

21w44a

can confirm in 1.18.1

Extra code analysis can be found in MC-164476

Hi all,

Like a few before me I have attempted to fix some of the issues with the current implementation of redstone dust. It is both laggy and unpredictable, making it a pain to work with, and leading to it being the most avoided redstone component in the game. Before I get to my solution to these issues, though, I want to acknowledge the work done by @unknown and @unknown, as both have been an inspiration in one way or another.

My implementation is mainly developed as a Fabric mod but has also been implemented into Paper.

Like the other two implementations, mine does not solely address the lag issue. It is a complete re-write of the power propagation code, fixing MC-11193 in the process. It is not a re-write of redstone as a whole, however. I attempted to keep existing behaviors as much as possible while fixing the lag of and inconsistencies with redstone dust that make it hard to rely on. To be more specific, it addresses the following issues:

1. Redstone wire does unnecessarily many calculations. Each wire in a network may calculate and update its power level over half a dozen times before settling on its final value. Moreover, each time it does so, it updates itself six times, doing even more completely redundant calculations.
2. Redstone wire emits unnecessarily many shape and block updates. This is, of course, related to the previous point, as a wire updates all neighboring blocks (and itself) each time it updates its power level. However, even if only the previous point is fixed, there would be many redundant shape and block updates that can be removed.
3. Redstone wire behaves unpredictably. The order in which a wire updates neighboring blocks is dependent on the location of the wire. Combined with the chaotic nature of the brute-force algorithm with which it updates, this makes it nigh impossible to predict and rely on how a wire network behaves.

I have designed a wire handler that addresses these issues in the following ways:

• When a wire is updated, a breadth-first search through the network identifies all wires that require power changes, and finds any power sources around the network. 

• If a wire is found to be unsupported, its removal and subsequent effects on power propagation are integrated into the search.

• Power is spread from the power sources outward to give each wire its new power level.

• Wires are updated in order of power level, from highest to lowest. This ensures power is spread most efficiently and makes the update order very predictable and intuitive.

• Each wire emits shape updates as it updates its block state, in the standard { west, east, north south, below, above } order.

• Shape updates to neighboring wires are avoided, as they are redundant.

• Each wire emits block updates in an order dependent on the local direction of power flow. This leaves the update order nearly completely consistent across all locations and all orientations. All credit goes to @unknown for this idea. Unlike RedstoneWireTurbo, however, my implementation exibits directional rather than random behavior in the cases where the direction of power flow is ambiguous, though this is trivial to change.

• Block updates to neighboring wires are avoided, as they are redundant.

• While Vanilla parity is not 100% preserved, by far the biggest change is that contraptions that are locational in Vanilla work either everywhere or nowhere with this implementation. Beyond that parity issues appear to be rare.

• The number of shape and block updates emitted is reduced by ~20x.

• The MSPT contributions of redstone dust are reduced by up to ~20x.

Can confirm in 23w07a.

Can confirm in 24w13a.

Can confirm in 1.20.5.

Affects 1.21