Friday Facts #176 - Belts optimization for 0.15

Regular reports on Factorio development.
roy7
Filter Inserter
Filter Inserter
Posts: 341
Joined: Fri Dec 12, 2014 4:24 pm
Contact:

Re: Friday Facts #176 - Belts optimization for 0.15

Post by 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
Fast Inserter
Fast Inserter
Posts: 203
Joined: Sun Mar 27, 2016 7:25 am
Contact:

Re: Friday Facts #176 - Belts optimization for 0.15

Post by 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
Filter Inserter
Filter Inserter
Posts: 681
Joined: Sat Jan 18, 2014 11:23 am
Contact:

Re: Friday Facts #176 - Belts optimization for 0.15

Post by 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
Fast Inserter
Fast Inserter
Posts: 190
Joined: Tue Apr 26, 2016 4:32 pm
Contact:

Re: Friday Facts #176 - Belts optimization for 0.15

Post by Xeanoa »

Neemys wrote:
Xeanoa wrote: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
Burner Inserter
Burner Inserter
Posts: 8
Joined: Sun Aug 21, 2016 11:21 am
Contact:

Re: Friday Facts #176 - Belts optimization for 0.15

Post by 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 :D

kanvil
Burner Inserter
Burner Inserter
Posts: 7
Joined: Fri Jan 13, 2017 5:48 pm
Contact:

Re: Friday Facts #176 - Belts optimization for 0.15

Post by kanvil »

hoho wrote: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
Burner Inserter
Burner Inserter
Posts: 9
Joined: Thu Jun 02, 2016 3:26 am
Contact:

Re: Friday Facts #176 - Belts optimization for 0.15

Post by bjohnsonmn »

Thank you for keeping us all in the loop!

dauphin
Inserter
Inserter
Posts: 38
Joined: Fri Aug 19, 2016 1:59 am
Contact:

Re: Friday Facts #176 - Belts optimization for 0.15

Post by dauphin »

sparr wrote:
dauphin wrote: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
Factorio Staff
Factorio Staff
Posts: 5291
Joined: Thu Jun 11, 2015 1:35 pm
Contact:

Re: Friday Facts #176 - Belts optimization for 0.15

Post by posila »

dauphin wrote: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
Inserter
Inserter
Posts: 39
Joined: Tue Mar 01, 2016 8:03 pm
Contact:

Re: Friday Facts #176 - Belts optimization for 0.15

Post by 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
Inserter
Inserter
Posts: 23
Joined: Sat Oct 01, 2016 12:53 am
Contact:

Re: Friday Facts #176 - Belts optimization for 0.15

Post by 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
Inserter
Inserter
Posts: 27
Joined: Wed Mar 11, 2015 11:14 pm
Contact:

Re: Friday Facts #176 - Belts optimization for 0.15

Post by 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! :D

Lilly
Inserter
Inserter
Posts: 49
Joined: Mon Apr 11, 2016 6:42 pm
Contact:

Re: Friday Facts #176 - Belts optimization for 0.15

Post by 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.
dauphin wrote: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
Inserter
Inserter
Posts: 33
Joined: Sat Aug 08, 2015 12:37 am
Contact:

Re: Friday Facts #176 - Belts optimization for 0.15

Post by psychomuffin »

SaintFlow wrote:
MrGrim wrote:
SaintFlow wrote: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
Smart Inserter
Smart Inserter
Posts: 1417
Joined: Fri Feb 14, 2014 5:52 pm
Contact:

Re: Friday Facts #176 - Belts optimization for 0.15

Post by sparr »

Gotbread wrote: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
Inserter
Inserter
Posts: 48
Joined: Fri Mar 18, 2016 6:13 pm
Contact:

Re: Friday Facts #176 - Belts optimization for 0.15

Post by SaintFlow »

psychomuffin wrote: 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 :P

Marconos
Filter Inserter
Filter Inserter
Posts: 301
Joined: Mon Jun 02, 2014 10:46 pm
Contact:

Re: Friday Facts #176 - Belts optimization for 0.15

Post by 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
Fast Inserter
Fast Inserter
Posts: 207
Joined: Fri Sep 02, 2016 9:23 am
Contact:

Re: Friday Facts #176 - Belts optimization for 0.15

Post by Harkonnen »

dauphin wrote: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.
Cyberboss_JHCB wrote:Will underground belts still be any faster than regular belts, even if it's just miniscule?
No.
keyboardhack wrote: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.
Optera wrote:Will the changes in belt mechanic break the unintended splitter feature know as magic splitters?
No. Splitters logics remains as it was.
Tankh wrote: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.
Zeblote wrote:There's a bug in your first gif :D
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! :D Thanks for pointing that out.
SaintFlow wrote: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 :(
hoho wrote: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.
GuiltyBystander wrote: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.
Gotbread wrote: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.
Lilly wrote: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.
psychomuffin wrote: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.
Marconos wrote: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
Inserter
Inserter
Posts: 48
Joined: Fri Mar 18, 2016 6:13 pm
Contact:

Re: Friday Facts #176 - Belts optimization for 0.15

Post by SaintFlow »

Harkonnen wrote:
psychomuffin wrote: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
Manual Inserter
Manual Inserter
Posts: 2
Joined: Sat Feb 04, 2017 9:26 am
Contact:

Re: Friday Facts #176 - Belts optimization for 0.15

Post by 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.

Post Reply

Return to “News”