Friday Facts #176 - Belts optimization for 0.15

[roy7]

nou_spiro on Reddit pointed this out:

Hmm actually 0xFFFF seems invalid accordig to RFC1624

Since there is guaranteed to be at least one non-zero field in the IP header, and the checksum field in the protocol header is the complement of the sum, the checksum field can never contain ~(+0), which is -0 (0xFFFF).

[mattj256]

I posted about this last week. I did a quick Google search. In the definition of the UDP protocol, a checksum of zero means "no checkum" and you're supposed to change it to 0xFFFF instead. I have no idea why a router would drop packets with a checksum of 0xFFFF.

[hoho]

Hm, so if I gather this correctly, if I have two parallel lines moving stuff around and I use a single splitter as a "poor man belt balancer", it'll cause relatively big slowdown compared to not having that splitter? Or will it not really be any more expensive than just a regular belt section mergeing point?


@people complaining about release and lack of communication, there has been quite a bit of communication and it has been "when it's done, hopefully soon-ish". Obviously I too would like to get something more specific but you gain nothing by wining.

[Xeanoa]

The first release in months, and it fixes what, 3 of the dozens of reported bugs?

Lots of bug were fixed but only in 0.15 (no ETA yet) (see here for list of resolved bug), this release exist only to address critical bug

From my (a consumer/customer's) point of view, they are not fixed until a fix is released.

[Omez]

At this point I would just assume this ISP(and some other few ISPs around the world) have some faulty hardware or software that do not handle these special cases of UDP checksums.

*scratches the far reaches of the mind*.. 0x0000 should be flagged correctly as faulty checksum, but 0xffff is valid.. If my memory serves.
If checksum is computed as all 0's, its set to all 1's.. This might be part of the issue, if both are used in the data.

If it hadn't been resolved, and I had the time, just for shits and giggles I might have tried and see if I can find out what manufacturer does this (got access to network with most major network equipment).

I hadn't read about this issue before this FF post. I just might have to look more on the forum for more network issues that I might help with

[kanvil]

Hm, so if I gather this correctly, if I have two parallel lines moving stuff around and I use a single splitter as a "poor man belt balancer", it'll cause relatively big slowdown compared to not having that splitter? Or will it not really be any more expensive than just a regular belt section mergeing point?

If you have a single splitter, it won't have much effect. It sounds like this might only be a problem if you had a lot of them spaced apart. The worst case would be putting a splitter every other tile, which would make it impossible to merge any belts. Since belts with inserters are planned to be limited in how much they can merge, sprinkling splitters through the active part of your factory isn't likely to do much harm.

[bjohnsonmn]

Thank you for keeping us all in the loop!

[dauphin]

I assume one of the big caveats for the performance increase on the belts is that, in order to render, you still have to calculate the absolute position of each item on the belt?

you don't have to separately calculate each one. you calculate the first one, then just increment it in the appropriate direction for the distance to the next item, with some logic to handle corners.

This still means calculating an absolute position for each item. Each individual item has a calculation associated with it for rendering.

Put another way, the rendering algorithm is still O(N) even though the new update algorithm is O(1).

[posila]

Put another way, the rendering algorithm is still O(N) even though the new update algorithm is O(1).

In Factorio, rendering is usually cheap operation compared to update, because only small portion of a factory is rendered.

[Vinnie_NL]

I don't have any programming knowledge but I just love reading about how these optimizations. I like to know about the creative ways to fix a problem, and knowing how the game will be better in the future. I'm thinking about upgrading my i7 860 from 2010 somewhere in Q1 expecting to keep the UPS up while my factory gets bigger. Of course not only that, there will be other new games too that I like to play, but Factorio is still my main timesink. But with 0.15 somewhere this year maybe I can delay my cpu some longer and end up with a better one instead.

Of course I'm looking forward to 0.15 with all the new promised features, and if there is any info on a date I really want to know it. But as long as there is no news I'm not worried. The guys @ Wube know their stuff so I'm sure it will be good when finished. And with the FFF's they release more information about the development than most devs

[GuiltyBystander]

I'm excited for the new belt optimization changes, however, I have one question.

With 0.15 you will never ever have to build underground belts for the sake of performance Factorio's heart is beating nicely now and will not distract from blueprinting the truly important things.

Currently, if you want max compression coming out of any high output line of machines, you need to have your inserters outputting onto a underground belt because inserters can't put items into the tiny gaps that sometimes exist between items. Will this new code allow inserters to create fully compressed line without the undeground belt tricks?

[Gotbread]

All these performance optimizations. Awesome!

I have a nagging fear that the code moves from inefficient but clear to very efficient but very convoluted. And at some point, you cant change a data structure anymore
without having many side effects in different code pieces. the FFF sounds like the inserters are highly dependent on the belt structure.

But speaking of optimizations, you are trying to exploit similarities between objects (relative distance is constant during belt movement) to compress the data further.
This got me thinking, factorio has many repeating states. If you look at a big smelting factory and assume coal and ore supply are without gaps, and all iron plates
are removed so they dont block the belt, after exactly 1 smelting time all objects are back in the same state, including furnaces, inserters, belts, items and internal states
like "how much smelting is done". You dont need to simulate these states over and over if you cache one iteration and just look it up later. That would mean your computation
reduces from:
"Simulate all objects, belts, and inserters 60 times per second"
to:
"another 105 ticks have passed, remove 1 ore and produce 1 iron plate"

I have done this technique with cellular automata, wireworld in particular. Once you have simulated an area for a few ticks you can store the layout and the result in memory.
If you encounter the same state again, you just need to look up the cached state. The best part is, if you dont need to look at the state (for rendering, maybe the factory
is off screen), you dont need to decompress the state. So you just need to compute "state 2256 evolves to state 9735 which evolves to 9825 which evolves back to 2256".

Because you are only moving around state IDs (integers) which represent a rather large area (i used 12 x 12 cells for 12 iterations) you gain an enormous speedup.

Of course this would be harder to implement in factorio because the states are more complex...

Just my thought on it. Great Game!

[Lilly]

Instead of storing the distance between items, you can store for each item the time/tick when it will reach the end of the segment (if it won't block or be removed). Then segments only need to be updated when items are inserted/removed/side loaded. The distance to the end of the segment, also taking blocking into account, can be computed as follows:

Code: Select all

distance to end of segment = max( index in array * item width, (tick when item is at end of segment - current tick) * belt speed )

Upon removing a blocked item, the 'tick when item is at end of segment' for all previously blocked items on the belt needs to be updated. However, as the items are probably stored in an array (for data locality and to reduce memory usage), all items on the segment need to be updated anyway.

If the end of the segment does not connect to another belt segment, then the segment only needs to be updated as part of an item insertion/removal. If it does connect to another belt, then an additional optimization is to 'suspend' the belt until the tick that the next item reaches the end of the belt segment.

For inserters, it can be computed at what tick the next item will be in range, such that the inserter can be 'suspended' until that tick.

I assume one of the big caveats for the performance increase on the belts is that, in order to render, you still have to calculate the absolute position of each item on the belt?

That is probably not an issue. Absolute positions only need to be computed for belt segments that are within view and computing them is relatively cheap.

[psychomuffin]

Nice ideas for belt optimization!

I am very sad that its Feb now... and you still didn't say a word about 0.15 planning. You guys know that people are looking forward to it quite a lot and I guess many of those looking forward expected at least some information in this fff today... No info about 0.15 --> sad.

...It will be out when it's done, and it'll be better because it wasn't rushed to meet some arbitrary deadline...

Well, I suppose you don't refer to me as a youngster... Again, it is not about rushing, but about communication....I think people are way more relaxed the earlier they get to know such things.

I don't want you guys to rush either. I am dying to do another Factorio binge though, and knowing when it might come (even if it's a moving target), helps. If I hear it is July, I will probably do a .14 binge. But if .15 is a couple weeks, or even a month away, I'll probably wait. Again, it's just nice knowing. Even if you have to change it later. No one here wants you to rush.

[sparr]

But speaking of optimizations, you are trying to exploit similarities between objects (relative distance is constant during belt movement) to compress the data further.
This got me thinking, factorio has many repeating states. If you look at a big smelting factory and assume coal and ore supply are without gaps, and all iron plates
are removed so they dont block the belt, after exactly 1 smelting time all objects are back in the same state, including furnaces, inserters, belts, items and internal states
like "how much smelting is done". You dont need to simulate these states over and over if you cache one iteration and just look it up later. That would mean your computation
reduces from:
"Simulate all objects, belts, and inserters 60 times per second"
to:
"another 105 ticks have passed, remove 1 ore and produce 1 iron plate"

I have done this technique with cellular automata, wireworld in particular. Once you have simulated an area for a few ticks you can store the layout and the result in memory.
If you encounter the same state again, you just need to look up the cached state. The best part is, if you dont need to look at the state (for rendering, maybe the factory
is off screen), you dont need to decompress the state. So you just need to compute "state 2256 evolves to state 9735 which evolves to 9825 which evolves back to 2256".

This is a neat idea. I would think of it as memoizing a piece of the game state and progression. I think the hard part would be efficiently identifying pieces of the world that are repeating in a cycle, although I guess an easy way to start would be to just start at each assembler and work outwards a few tiles.

[SaintFlow]

I don't want you guys to rush either. I am dying to do another Factorio binge though, and knowing when it might come (even if it's a moving target), helps. If I hear it is July, I will probably do a .14 binge. But if .15 is a couple weeks, or even a month away, I'll probably wait. Again, it's just nice knowing. Even if you have to change it later. No one here wants you to rush.

Exactly my thoughts muffin. A few friends and I want to start a Factorio journey once again as soon as 0.15 hits and we plan to go DEEP!....That is why some time for preparation would indeed be nice

[Marconos]

Was a very interesting read. I love the optimizations you are having to do.

Curious if the multi-threaded work amounted to anything or did that basically have to be scrapped?

[Harkonnen]

I assume one of the big caveats for the performance increase on the belts is that, in order to render, you still have to calculate the absolute position of each item on the belt?

That required some pre-sorting effort to keep it O(N) instead of O(N^2), but yeah - it makes me itching at times. one of reasons transport lines will be limited to like 100 tiles because off-screen items still have to be iterated to render what's after them.

Will underground belts still be any faster than regular belts, even if it's just miniscule?

No.

At this point is it still true that bots are better for performance than belts in 0.15?

Hope not. I don't want performance issues to be governing how factories look.

Will the changes in belt mechanic break the unintended splitter feature know as magic splitters?

No. Splitters logics remains as it was.

I'm guessing you also tested this for items going from a slow belt to fast belt. It's probably treated like a separate belt section.

Yes. Speed is one of criterias for possibility of merge. Another one is belt being deactivated through circuit network.

There's a bug in your first gif

That's an interesting case, investigating. That first gif was filmed with belts unmerged (one belt - one sequence, like in good old times). So far looks like I screwed up logics of inter-sequence connection item distances which showed up nowhere but at FFF... I will check it, fix it and give this bug your name! Thanks for pointing that out.

You guys know that people are looking forward to it quite a lot and I guess many of those looking forward expected at least some information in this fff today.

This is never easy for us as well to postpomne releasing 0.15 for next week all over again for several weeks in a row. We are just damn perfectionists

Hm, so if I gather this correctly, if I have two parallel lines moving stuff around and I use a single splitter as a "poor man belt balancer", it'll cause relatively big slowdown compared to not having that splitter? Or will it not really be any more expensive than just a regular belt section mergeing point?

Not really more expensive than just a regular belt section merging point.

Will this new code allow inserters to create fully compressed line without the undeground belt tricks?

A lot of logics regarding belt movement and compression was rewritten from the scratch. Evil people like Zeblote already start finding bugs in it I saw some magical numbers in that code that were removed, algorithm is generic now and "fair". I can't say if that nasty trick will work for underground belts or not, what I can say - it will either work for both or work for none.

Because you are only moving around state IDs (integers) which represent a rather large area (i used 12 x 12 cells for 12 iterations) you gain an enormous speedup.

Content-addressable hash is something that would hardly work for Factorio Unless we are in age of 1024-bit computers that treat current 64-bit era as CGA graphics.

Instead of storing the distance between items, you can store for each item the time/tick when it will reach the end of the segment (if it won't block or be removed).

That reminds me of what kovarex initially proposed and we had ton of arguments about it thereafter. The biggest problem - you also have to predict the time when that last item reaches end of the belt and the belt gets into blocked state. While happening relatively not that often, this is still an issue. My original idea was to keep bidirectional list of bidirectional lists of packed items - working solution, but a hell for cache locality. and a hell to code without mistakes. Later I realized that all operations happen only at head, tail or pre-tail only - which was compacted into cache-friendly list-free form that was described in FFF.

Again, it's just nice knowing. Even if you have to change it later. No one here wants you to rush.

Expected feb-march, but may shift, but unlikely. Releasing new version of Factorio is like showing your most favourite movie to your best friend. You want everything to be perfect.

Curious if the multi-threaded work amounted to anything or did that basically have to be scrapped?

That work was 90% getting knowledge of codebase and 10% doing actual multithreading keyboard-typing. Codebase is just that perfectly clean. If you know codebase, you can do it in a week in Factorio.

[SaintFlow]

Again, it's just nice knowing. Even if you have to change it later. No one here wants you to rush.

Expected feb-march, but may shift, but unlikely. Releasing new version of Factorio is like showing your most favourite movie to your best friend. You want everything to be perfect.

Thanks Harkonnen! That's some info I can work with at least. Lowering the it's finally February hype a bit might be a good thing than. Thanks for the update!

[Nican]

Interesting that you guys posted about the belts. I was thinking about how you guys implemented that yesterday. xD

I had modeled a way in my head such that belts had two parts:
1. A ring buffer. Each segment of a belt was a ring buffer, and during every tick, the game would change the head of the buffer, making the items move forward.
2. When a belt was full, and the items could not move forward the segment of the belt would change to a list. Like you have it currently implemented.

In my experience most belts are always moving items, so they would just be ring-buffers, and would just be iterating one integer.
And in some places of the factory, where items would be backed-up, it would be stored as a list.



And for multi-threading, I had a different idea in mind. I had thought of a system where the game would separate the different "sections" of a base on various threads. Meaning, the main base would run on one thread, each mining base would run on a separate thread, and each smelting base on another thread, and so on. With this, also encourage mega-base builders to modularize their bases with trains.

This model has the disadvantage that the different sections could get off-sync pretty easily, but would help with large PVP servers. Also, with this model, it could be a lot simpler to make the game scale to multi-server game instances.


Curious to hear your thoughts on my ideas. I think they have potential, but I am not the one developing the game. xD

EDIT: I see there was already some discussion on a ring-buffer-like idea on the thread.

EDIT2:

Hope not. I don't want performance issues to be governing how factories look.

Unfortunately, I feel like this game is always going to be CPU-bound, and there will always be strategies for players to reduce CPU.