Non-throughput-limited 8+ belt balancers?

Circuit-free solutions of basic factory-design to achieve optimal item-throughput.
Involving: Belts (balancers, crossings), Inserters, Chests, Furnaces, Assembling Devices ...
Optimized production chains. Compact design.
Please provide blueprints!
Forum rules
Circuit-free solutions of basic factory-design to achieve optimal item-throughput
ribsngibs
Long Handed Inserter
Long Handed Inserter
Posts: 70
Joined: Mon Mar 28, 2016 5:42 am
Contact:

Non-throughput-limited 8+ belt balancers?

Post by ribsngibs »

I designed an 8 belt balancer a few days ago and noticed it suffered from a problem if I was not using all outputs and not supplying all inputs - it was throughput limited. I searched these forums and reddit and it looks like every 8 belt and up balancer that I could find suffers from this problem. Is this issue well known? Perhaps nobody runs into it because their inputs or outputs are well behaved. If it is well known, are there large balancers around that avoid this issue?

This is the scenario in which I noticed the problem: Two sets of 4 lane inputs (call them IA and IB) go into an 8 belt balancer that outputs two sets of 4 lane outputs (OA and OB). IA is supplied 4 fully compressed belts of iron, IB is supplied nothing (future-proof input for next train station perhaps). OA is using as much iron as it can get and OB is unused and backed up.

I would expect that since I am giving the balancer 4 compressed belts (IA) and using only 4 belts worth (OA), that I would get 4 compressed belts out, but instead I only get 2 belts worth of throughput balanced among the 4 belts.

Here's a well known 8 balancer showing the issue:
throughputfailsmall1.gif
throughputfailsmall1.gif (4.58 MiB) Viewed 45455 times
Should be fairly obvious to see why - going into the final splitters there are only 2 belts worth of materials coming in.

These are at least most of the balancers I found, all of which suffer from this:
These two balancers
This balancer
These balancers
Any of the balancers 8 and up here
The balancer shown before
I think a balancer will only be non throughput limited if, "for all arbitrary slices taken through the balancer between the inputs and outputs, for every subset of N outputs and M inputs there must be at least min(N,M) belts along that slice which you can trace to both those N selected inputs and M outputs". Or perhaps easier stated - "draw all paths between all N inputs and M outputs - every slice you take between the inputs and outputs must intersect at least min(N,M) drawn paths".

I made this sort of monstrosity (actually not that large, 12x12, but I'm sure smart people on this forum can figure out something better):
throughputsuccesssmall1.gif
throughputsuccesssmall1.gif (6.98 MiB) Viewed 45455 times
but it is not universally non-throughput-limited. It is only non-throughput limited in those "4 input" chunks. e.g. You can put 4 full belts into the left and pull 4 full belts out the left, or pull 4 full belts out the right, but if you were to put in 2 full belts on input belt 1 and 2 you would only get one belt's worth if you tried to pull out of output 1 and 2 (you could pull 2 belts worth out of input 1 and 3, or 1 and 5, or 4 and 7, etc. but not 1 and 2). If I expanded this balancer with a small shuffle (swap outputs 1 and 3 and shift output 6 so that it becomes output 8), the balancer would be guaranteed to be non-throughput-limited in every case where your input and output belts matched, so you could put 3 belts worth into inputs 1, 3, 4 and then be guaranteed that you can pull 3 belts out of outputs 1, 3, 4. It would be non-throughput-limited in many other cases as well, but not all.

Is anybody up for a challenge of making a non-throughput-limited balancer for all cases? I was unable to make a reasonable sized one. Or a more compact version of mine (non-throughput-limited in chunks of 4)?

BTW, the "standard" 4 belt balancer (the one in the middle of this image) is non-throughput-limited, but only if you include the last set of splitters. Sometimes that last row is omitted because the outputs are already even at that point, but that is not perfectly non-throughput-limited - if you put two full belts into inputs 1 and 2 you would only be able to get 1 belts worth out of outputs 2 and 3. The other two balancers in that image are throughput limited (inputs 1 and 2 to outputs 1 and 2).

Peppe
Fast Inserter
Fast Inserter
Posts: 223
Joined: Fri Nov 28, 2014 6:48 pm
Contact:

Re: Non-throughput-limited 8+ belt balancers?

Post by Peppe »

Won't they all drive full throughput if you plug at least one belt into each input splitter? So instead of input on lane 1-4, do 1, 3, 5 , 7?

Not sure this requires new designs... Just knowledge that each splitter on the input side in a balancer should get input.

ribsngibs
Long Handed Inserter
Long Handed Inserter
Posts: 70
Joined: Mon Mar 28, 2016 5:42 am
Contact:

Re: Non-throughput-limited 8+ belt balancers?

Post by ribsngibs »

Well, like most things in Factorio, it's not entirely necessary, more of an identification of a fault and a self challenge to make it perfect :)

Sure, if you know you're going to put in 4 inputs and take out 4 you can put them into every odd input, but it's not a real general solution. What if you only feed in two lanes and take two lanes out? You have to remember that you have to feed 1 and 3 and also take out 1 and 3, (you can't feed 1 and 3 and take out from 1 and 2, or vice versa). I just thought it'd be a fun challenge to design a balancer that also allowed maximum throughout no matter what subset of inputs and outputs you happened to use. As an extreme example, you could think of all incoming 8 lines as coming from different train stations and all 8 output lines as going to different parts of the factory, and hey, only trains 3 and 7 are running and you're only making steel and green circuits which happen to be on outputs 4 and 8. It would be nice to have a general balancer solution so that no matter which inputs and outputs are used that there's no unnecessary bottleneck...

I don't know how many people actually use those 16 or 32 balancers, but I imagine actually putting together enough train stations to actually fill a 16 blue belt would take many hours and almost certainly they aren't using all the outputs during the build time either - almost certainly those in-progress factories are hamstrung by this issue (just like my "mega"ish base was by my 8 belt balancer)!

CMH
Fast Inserter
Fast Inserter
Posts: 152
Joined: Mon May 02, 2016 3:02 am
Contact:

Re: Non-throughput-limited 8+ belt balancers?

Post by CMH »

I've used 32 belt balancer systems, and earlier in the game when I didn't need so many inputs/outputs I just staggered the inputs/outputs 1-3-5-7 etc. Easiest way to fix it, especially if you're expecting to use up all 32 lanes in the future. No need to reinvent the wheel. Don't forget, you only run into this issue because all those inputs are empty anyway.

However, I did run into trouble when trains aren't running perfectly and you end up with empty lanes because they prefer one station over another. For this, I just put another balancer between the station and the inputs to the 32-lane balancer. Worked like a charm. Probably not the most efficient way to do things though, but still beats having to re-engineer the 32 lane balancer to deal with empty lanes (might even use fewer splitters/belts to do it too)

Frightning
Filter Inserter
Filter Inserter
Posts: 807
Joined: Fri Apr 29, 2016 5:27 pm
Contact:

Re: Non-throughput-limited 8+ belt balancers?

Post by Frightning »

I think there is a relatively systematic theoretical way of knowing if the balancer can suffer from this problem or not. Consider the 8-belt balancer in the first gif. Notice that belts 1-4 on the input are the only ones with throughput happening. A plate on belt 1 can only end up on belts 1,2,3,4,5,6. It cannot end up on belts 7 or 8. Similar issues are present for plates on the other belts. Why is this a problem? Consider that under non-ideal conditions, the throughput of any given belt needs to be able to be redistributed among any number of belts in order to ensure that the output is balanced (otherwise, what happens if all of belt m's throughput needed to end up on belt n? That's impossible if plates on belt m cannot end up on belt n.

So the way to know if your balancer can avoid this problem is to ask: Can an object on any given input side belt be moved to any belt on the output side? If yes, then I suspect that you have a balancer design that won't suffer from this throughput bottleneck problem.

Edit: This condition is necessary but not sufficient (as you showed with your 12x12 system having throughput on input belts 1-2 needing to go to throughput on output belts 1-2; the problem being that in order for a plate on input belt 1 end up on output belt 1, it must cross input belt 2 after the first splitter to take the 2nd splitter to get on the 3rd line, which eventually becomes output belt 1).

Frightning
Filter Inserter
Filter Inserter
Posts: 807
Joined: Fri Apr 29, 2016 5:27 pm
Contact:

Re: Non-throughput-limited 8+ belt balancers?

Post by Frightning »

ribsngibs wrote: BTW, the "standard" 4 belt balancer (the one in the middle of this image) is non-throughput-limited, but only if you include the last set of splitters. Sometimes that last row is omitted because the outputs are already even at that point, but that is not perfectly non-throughput-limited - if you put two full belts into inputs 1 and 2 you would only be able to get 1 belts worth out of outputs 2 and 3. The other two balancers in that image are throughput limited (inputs 1 and 2 to outputs 1 and 2).
Actually, if my calculations are right, you would get 2 belts worth of throughput (first splitter does nothing, 2nd divides belt 2 evenly between 2 and 3, 3rd splitter divides belt 1 onto belts 1 and 4 evenly, final splitters would refill missing half of belt 2 from belt 1 and belt 3 from belt 4).

Edit: Or do mean that standard splitter without the last set would be throughput limited? Which is true.

Edit2: The standard 4-belt balancer is not universally throughput unlimited. Consider inputs on belts 1,2,3 going to outputs on belts 1,2,4 (belt 3 is assumed backlogged). In this case, the first set of splitters does nothing to belts 1 and 2, but splits belt 3 evenly onto belts 3 and 4 (1/2 throughput on each). Now the splitter on belts 2 and 3 will balance the full throughput on belt 2 with the half on belt 3 into 3/4's throughput on both belts. The splitter on belts 1 and 4 has full throughput on belt 1 with half on belt 4, so it will output 3/4 on belts 1 and 4. Now at the final set of splitters, we have 3/4 in belt 1 plus 3/4 in belt 2 to be divided onto belts 1 and 2; that's 3/2 total, so each belt gets 3/4 throughput (!), meanwhile, belts 3 and 4 have 3/4 and 3/4 respectively, all of which needs to end up on belt 4, which is 3/2 on belt 4 (bottleneck!!). So what's going wrong? There is no splitters between 1 and 3, and between 2 and 4. Swap lanes 2 and 3 via underground belts (not as compact layout) and I believe this problem can be avoided.

Frightning
Filter Inserter
Filter Inserter
Posts: 807
Joined: Fri Apr 29, 2016 5:27 pm
Contact:

Re: Non-throughput-limited 8+ belt balancers?

Post by Frightning »

I just experimentally confirmed my edit2 to my previous post (nabbed some screenshots showing the failure to saturate belts 1 and 2 on output side (there was also so visible hitches in throughput on belts 1 and 2 on the input side, but that doesn't show in a screenshot; how do you make a gif for factorio?)
20160507043859_1.jpg
20160507043859_1.jpg (462.31 KiB) Viewed 45354 times
Shows failure to saturate.

Frightning
Filter Inserter
Filter Inserter
Posts: 807
Joined: Fri Apr 29, 2016 5:27 pm
Contact:

Re: Non-throughput-limited 8+ belt balancers?

Post by Frightning »

Decided to ask the related theoretical question on math stack exchange: http://math.stackexchange.com/questions ... m-factorio
For those that are interested to see what comes out of it.

Frightning
Filter Inserter
Filter Inserter
Posts: 807
Joined: Fri Apr 29, 2016 5:27 pm
Contact:

Re: Non-throughput-limited 8+ belt balancers?

Post by Frightning »

ribsngibs wrote:~snip
Is anybody up for a challenge of making a non-throughput-limited balancer for all cases? I was unable to make a reasonable sized one. Or a more compact version of mine (non-throughput-limited in chunks of 4)?
~snip~
The more I think about this problem, the more convinced I am that it is not possible for n>2. A useful thing to notice is that if an n-belt balancer is universally throughput unlimited, then the corresponding (n-1)-belt balancers for every set of (n-1) inputs and (n-1) outputs must also satisfy the universally throughput unlimited condition (or the original n-belt balancer wouldn't have the property). This means that as soon as we find a k for which it is not possible, then it is not possible for any n>k. I suspect 3 is the relevant k, but I am still working on a theoretical proof of it.

ribsngibs
Long Handed Inserter
Long Handed Inserter
Posts: 70
Joined: Mon Mar 28, 2016 5:42 am
Contact:

Re: Non-throughput-limited 8+ belt balancers?

Post by ribsngibs »

Interesting 1,2,3 -> 1,2,4 experiment of that 4 lane splitter. I feel like that splitter (again, only with the last row of splitters) should be theoretically non throughput limited, but maybe not perfectly non throughput limited in practice because of some quirk in moving discrete items? It seems like with the Factorio game mechanics of splitters attempting to alternate lanes but being happy to push to only one belt if the other is blocked completely, that the 1,2,3->1,2,4 path should be not throughput limited: belts 1 and 2 can go straight through while 3 can switch to 4 at the first splitter, so there exists a non-throughput-limited path for all belts! I would expect that the bottleneck you found would indeed throughput limit the balancer, but only until the bottleneck propagated the traffic jam backwards through the splitter until the overflow can spill through a belt which can flow freely. Did you run your experiment for a "long" time to allow the splitter to find a better path?

I think a non-throughput-limited balancer should be possible: as CMH noted, if you put two balancers together in series that should work - it's just big!

Your analysis of the 8 splitter wasn't quite right: belt 1 does indeed connect to outputs 7 and 8 - otherwise it would not be a balancer! It's the second to last splitter, just before the splitter between outputs 5,6. I think there is a way to theoretically determine if a balancer is throughput limited, and it is simply to look for bottlenecks (number of possible paths from inputs to outputs must be >=N if you use N inputs and N outputs the entire length of the splitter). In the 8 balancer example, you can look just ahead of the first splitters or just behind the last splitters and see that only two belts carry the material, so the max output is 2 belts worth. The 1,2,3->1,2,4 experiment you ran is surprising precisely because the test should succeed; there are 3 belts or more along the whole splitter - I will replicate the experiment when I get some free time this weekend!

Animated gif: I use nvidia shadowplay to capture (lots of capture programs exist) and virtualdub to crop and encode as gif.
Last edited by ribsngibs on Sat May 07, 2016 4:13 pm, edited 1 time in total.

Frightning
Filter Inserter
Filter Inserter
Posts: 807
Joined: Fri Apr 29, 2016 5:27 pm
Contact:

Re: Non-throughput-limited 8+ belt balancers?

Post by Frightning »

ribsngibs wrote:Interesting 1,2,3 -> 1,2,4 experiment of that 4 lane splitter. I feel like that splitter (again, only with the last row of splitters) should be theoretically non throughput limited, but maybe not perfectly non throughput limited in practice because of some quirk in moving discrete items? It seems like with the Factorio game mechanics of splitters attempting to alternate lanes but being happy to push to only one belt if the other is blocked completely, that the 1,2,3->1,2,4 path should be not throughput limited: belts 1 and 2 can go straight through while 3 can switch to 4 at the first splitter, so there exists a non-throughput-limited path for all belts! I would expect that the bottleneck you found would indeed throughput limit the balancer, but only until the bottleneck propagated the traffic jam backwards through the splitter until the overflow can spill through a belt which can flow freely. Did you run your experiment for a "long" time to allow the splitter to find a better path?

I think a non-throughput-limited balancer should be possible: as CMH noted, if you put two balancers together in series that should work - it's just big!

Your analysis of the 8 splitter wasn't quite right: belt 1 does indeed connect to outputs 7 and 8 - otherwise it would not be a balancer! It's the second to last splitter, just before the splitter between outputs 5,6. I think there is a way to theoretically determine if a balancer is throughput limited, and it is simply to look for bottlenecks (number of possible paths from inputs to outputs must be >=N if you use N inputs and N outputs the entire length of the splitter. In the 8 balancer example, you can look just ahead of the first splitters or just behind the last splitters and see that only two belts carry the material, so the max output is 2 belts worth. The 1,2,3->1,2,4 experiment you ran is surprising precisely because the test should succeed; there are 3 belts or more along the whole splitter - I will replicate the experiment when I get some free time this weekend!

Animated gif: I use nvidia shadowplay to capture (lots of capture programs exist) and virtualdub to crop and encode as gif.
Good catch on the 8-belt analysis, I missed the splitter because it was sideways and I just didn't see it, lmao.

I think you're also right about the theoretical soundness of the 4-belt balancer because I noticed that it did indeed backlog into the balancer as you predicted, but it did not actually balance out perfectly (I ran 900+500 plates in each lane, 900 in outer chest because that one gets full throughput of 4 Fast Inserters unlike inner chest which is just for belt compression and filling missing capacity). The problem is that splitters default to 50/50 split unless faced with a backlog, where they shunt all excess beyond the first bottlenecked belt to the second. The reason for the imperfect balancing can be seen by doing "backlog" calculations and seeing how load is redistributed, it does not adjust perfectly in finitely many steps, so because items are indeed discrete units and cannot be arbitrarily subdivided, you get enforced regular 'flebs' (visible on belts 1 and 2 in my picture), which result in submaximal throughput. If these were 'pipes' with arbitrary divisible units then I suppose it would converge to a stable and theoretically optimal outcome, though probably not in finite time.

I am increasingly convinced that the above type of 'fleb' problem due to backlogging into the splitter is in general unavoidable in 3+ belt balancers (thankfully the losses seem to be on the order of less than 10% based on what I saw with the pictured 4-belt experiment; I think I will spend more time with that basic setup testing 3-belt balancers to test a theory I have about why it's unavoidable)

Frightning
Filter Inserter
Filter Inserter
Posts: 807
Joined: Fri Apr 29, 2016 5:27 pm
Contact:

Re: Non-throughput-limited 8+ belt balancers?

Post by Frightning »

So I ran the experiment w/ the 4-belt configuration again, and watched closely at the start to see what happened, and indeed it did backlog into the balancer, specifically along the rightmost lane heading into the final pair of splitters (as was theoretically predicted), once that backlog found the splitter between the outside lanes, it stabilized into the previously described submaximal throughput pattern with the 'flebs' I observed before.

So now I changed up the balancer into a simple 3-belt design (feature which I will call a 'forbidden triangle' for reasons to be explained later).

First test I ran input belts 1 and 3 to output belts 1 and 3, which according to theory, should work fine, and it basically did:
20160507090652_1.jpg
20160507090652_1.jpg (333.38 KiB) Viewed 43092 times
...except....every once in awhile...a 'fleb' crept in:
20160507090742_1.jpg
20160507090742_1.jpg (184.62 KiB) Viewed 43092 times
I am not entirely sure why that happened, but it was quite infrequent (I only saw it about 10 times in 1500 plates/belt) and probably related to rounding errors and the tick rate of the game in some way.
Next I changed the outputs to be belts 1 and 2. The result?
20160507090910_1.jpg
20160507090910_1.jpg (354.18 KiB) Viewed 43092 times
That's some serious loss of throughput, it even changed its lane staggering after a bit to:
20160507090932_1.jpg
20160507090932_1.jpg (258.09 KiB) Viewed 43092 times
The end result was that throughput was lower, but still distributed evenly on the output side, with all of the throughput losses being absorbed by input belt 3 (nearly 1/3 of throughput was lost from this belt!) (?!)

This is related to the theory and why I call that configuration a forbidden triangle. If you math out the desired division of the input, you see that after the first splitter its:
1/2 1/2 1
After the second:
1/2 3/2 (!) 0
So the problems begin with the 'middle' splitter being oversaturated, it passes this backlog back up both lanes which impacts the first splitter, causing it to shunt more input to belt 1. However, because stuff is still moving through the middle splitter, soon enough, there's room on belt 2 for the first splitter to put items again, hence what it actually does is alternate between all on belt 1 and 50-50 belt 1 and belt 2 (hence the patterned appearance of the belts and their lanes).

The given triangular configuration of splitters always results in this oversaturation problem, leading to backlogging and eventually patterned 'flebs' which apparently can be pretty severe in worst case scenarios. The worst part is that, in any balancer with at least 3 belts, this problem is unavoidable. There will always be 3 belts of input and 3 belts of output such that the configuration of splitters that affect them form such a triangle, or a configuration containing such a triangle (or else it wouldn't even be a balancer!)

ribsngibs
Long Handed Inserter
Long Handed Inserter
Posts: 70
Joined: Mon Mar 28, 2016 5:42 am
Contact:

Re: Non-throughput-limited 8+ belt balancers?

Post by ribsngibs »

Frightning wrote: The worst part is that, in any balancer with at least 3 belts, this problem is unavoidable. There will always be 3 belts of input and 3 belts of output such that the configuration of splitters that affect them form such a triangle, or a configuration containing such a triangle (or else it wouldn't even be a balancer!)
Great work on all theses tests! It's interesring to see the 3 splitter triangle, such a simple example, fail so obviously, especially since I see that construction not super infrequently to split off lines from a bus.

However... I'm not convinced it's strictly unavoidable! The issue only exists if two belts combine to a >1 throughput, yes? So you could, again just as a non-optimized brute force kind of thing, split each input into 2 (say, input 1 splits into input 1a and 1b, etc.), then put 1a-8a into an 8 belt balancer and 1b-8b into a second balancer, and then recombine all the respective outputs (output 1a and 1b to output 1), and that should be strictly non-throughput-limited, right? Since all the places where the belts would combine to >1 would now combine to <=1 (in my original example, the worst case was after splitter #2, 2 belts would have required throughputs of 2 each, so worst case they would only require throughput of 1 if divided by 2).

I think; this is all theorycrafting - will have to test tomorrow (I'm posting from a child's birthday party right now... zzzzzzz).

Frightning
Filter Inserter
Filter Inserter
Posts: 807
Joined: Fri Apr 29, 2016 5:27 pm
Contact:

Re: Non-throughput-limited 8+ belt balancers?

Post by Frightning »

ribsngibs wrote:
Frightning wrote: The worst part is that, in any balancer with at least 3 belts, this problem is unavoidable. There will always be 3 belts of input and 3 belts of output such that the configuration of splitters that affect them form such a triangle, or a configuration containing such a triangle (or else it wouldn't even be a balancer!)
Great work on all theses tests! It's interesring to see the 3 splitter triangle, such a simple example, fail so obviously, especially since I see that construction not super infrequently to split off lines from a bus.

However... I'm not convinced it's strictly unavoidable! The issue only exists if two belts combine to a >1 throughput, yes? So you could, again just as a non-optimized brute force kind of thing, split each input into 2 (say, input 1 splits into input 1a and 1b, etc.), then put 1a-8a into an 8 belt balancer and 1b-8b into a second balancer, and then recombine all the respective outputs (output 1a and 1b to output 1), and that should be strictly non-throughput-limited, right? Since all the places where the belts would combine to >1 would now combine to <=1 (in my original example, the worst case was after splitter #2, 2 belts would have required throughputs of 2 each, so worst case they would only require throughput of 1 if divided by 2).

I think; this is all theorycrafting - will have to test tomorrow (I'm posting from a child's birthday party right now... zzzzzzz).
I admit I haven't done a careful proof yet, but I did actually consider the idea of splitting the lanes into more lanes, and the problem inevitably shows right back up when you try to recombine the lanes (you'll end up with two belts needing to combine to one but they have >1 belt's worth of combined throughput between them). Why does this happen? Same reason the no lanes split example has one belt trying to receive >1 belt worth of throughput: there's a forbidden triangle.

So why is the forbidden triangle a problem? See my previous post where I detail how the split yields oversaturation on one of the belts (if your triangle is not labeled the same as my example, simply relabel the inputs and outputs until it is like my example).

Why is a forbidden triangle unavoidable?
This is because of a basic property of balancers already mentioned: Every lane must be able to be moved to any other lane.
This means that, without loss of generality (meaning relabeling if needed), there must be a splitter between belts 1 and 2.
After which...there must be another splitter involving belt 3 (and again, without loss of generality, we can arrange that the other belt is belt 2 by relabeling if needed).
But because that splitter comes after the splitter between belts 1 and 2, we have still yet ensure that input from belt 3 can end up on belt 1.
That requires a splitter further down the belts that involved belt 1 again.
It is those 3 splitters that form a forbidden triangle. This happens no matter how many other splitters and belts you have, as soon as you have three belts, there must be such a triangle, and then all that's needed to express the problem is for only those 3 belts to be involved and only (the wrong) two of them to have input and (the wrong) two of them to accept outputs, and bam, you have the forbidden triangle bottleneck problem.

Frightning
Filter Inserter
Filter Inserter
Posts: 807
Joined: Fri Apr 29, 2016 5:27 pm
Contact:

Re: Non-throughput-limited 8+ belt balancers?

Post by Frightning »

So I decided to test the 4-belt balancer some more to test a prediction of the aforementioned 'forbidden triangle' theorem. Which is that their should exist a trio of input belts and a trio output belts, and among those trios a pair for each, such that the throughput fails to be maximal. However, in game testing did not produce an example (I believe I tried, up to symmetry, every pairing that can exist) and only issues I saw were extremely rare single missed plate type 'flebs' which are most likely roundoff/tick-rate related errors and not theoretically inherent to the problem. This made me revisit an old hypothesis: The reason for the failure of the 3-belt balancer in my previous experiment would be due to the fact that input belts 1 and 3 never have a splitter between them (the splitters are 1 and 2, 2 and 3, and another 1 and 2). This satisfies the definition of a balancer (every lane can go to every other), but clearly failed to be universally throughput unlimited (as shown experimentally). So I made a new design for the 3-belt balancer that made the final splitter between belts 1 and 3. This involved shifting output lane 1 to the far right of the layout, via underground belt (this also made me realize that the proper way to label the output belts so that they correspond to the input belts is to ask: If you never change belts at any splitter, where do you end up?)

I put this new layout to the exact same input-output setup that my previous design failed and:
20160507170525_1.jpg
20160507170525_1.jpg (191.92 KiB) Viewed 43057 times
lo and behold: No loss of throughput!!

It would seem, at least from experimental evidence, that the required condition is that every pair of input and corresponding output belts has a splitter between them somewhere in the layout (order is does not appear to be important, but what is important is that a splitter is on every pair of belts) This gives a quick check necessary condition (that is not too much harder to show sufficiency from): The number of splitters in a universally throughput unlimited n-belt balancer must be:
n(n-1)/2
(sum of 1 to n-1)
Note that this alone is not sufficient because you also need to check that every pair of corresponding belts has a splitter between them (more work to check, but not hard). I am not certain how to prove that this satisfies the universally throughput unlimited condition, but it also suggests that my earlier comment about switching belts 2 and 3 in the 4-belt balancer might in fact be a correct fix for the throughput problem that my experiments revealed.

Frightning
Filter Inserter
Filter Inserter
Posts: 807
Joined: Fri Apr 29, 2016 5:27 pm
Contact:

Re: Non-throughput-limited 8+ belt balancers?

Post by Frightning »

After looking carefully at my previous post, I noticed why there was no throughput problems: Both outputs came from the last splitter. Sure enough, change that, and the familiar throughput issues come right back:
20160507174418_1.jpg
20160507174418_1.jpg (193.34 KiB) Viewed 43052 times
This highlights why the forbidden triangle causes the trouble that it does: Because the last splitter on each output belt is different, imbalances will propagate to the 'first' splitter of the triangle, and said splitter will not solve the imbalance because of the way splitters behave: They split input evenly across output belts up to their available throughput and assign all remaining throughput to the belt that has capacity remaining if there is enough capacity to do so. If not, than, both input belts suffer from a reduced throughput in proportion to the output reduction (across both output belts). For example, in the forbidden triangle I worked earlier, we have 3/2 attempting to go into the final splitter which only has 1 belt to output to, so it backlogs to both of the other splitters (we get 2/3 of available input as throughput on the relevant belts). The middle splitter can do nothing about this situation, and first belt shifting more output to the belt which contains both it and last splitter does not solve the imbalance because it began at the last splitter. The real problem is that the middle splitter is not assigning all of its throughput to the output belt that does not contain the last splitter (which is one of the two available output belts, and needs full throughput in order to avoid oversaturation on other available output belt). But so long as items are moving on the belt that contains both middle and last splitter, it will always move some of its throughput to that belt, thereby depriving the output belt that does not contain the last splitter of it's full throughput (experimentally we saw roughly 1/3 of that belt's maximum throughput was lost this way; or in otherwords, we saw that actual throughput was 2/3 of maximum, which is exact what the preceding theoretical calculations predict will happen).

Shokubai
Filter Inserter
Filter Inserter
Posts: 470
Joined: Mon May 02, 2016 3:17 pm
Contact:

Re: Non-throughput-limited 8+ belt balancers?

Post by Shokubai »

Frightning wrote:I just experimentally confirmed my edit2 to my previous post (nabbed some screenshots showing the failure to saturate belts 1 and 2 on output side (there was also so visible hitches in throughput on belts 1 and 2 on the input side, but that doesn't show in a screenshot; how do you make a gif for factorio?)
20160507043859_1.jpg
Shows failure to saturate.
I think the saturation issue is due to the introduction of spacing created by splitting 3 into 4 at the start of your balancer. I've long thought that any unused balancer input will introduce gaps.

AccidentalChef
Burner Inserter
Burner Inserter
Posts: 14
Joined: Sun May 08, 2016 2:27 am
Contact:

Re: Non-throughput-limited 8+ belt balancers?

Post by AccidentalChef »

I played around with the 8 belt balancer and came up with an idea that appears to work. It does take up quite a bit more space than my usual balancer, but perhaps someone better with layouts can come up with a way to compact it.

Image

I think the last row of splitters are probably redundant. It seems to me that 2, 8 belt balancers in a row would also not be throughput limited, and that a 16 belt balancer with 8 outputs fed back into the inputs would also work.

Frightning
Filter Inserter
Filter Inserter
Posts: 807
Joined: Fri Apr 29, 2016 5:27 pm
Contact:

Re: Non-throughput-limited 8+ belt balancers?

Post by Frightning »

Shokubai wrote:
Frightning wrote:I just experimentally confirmed my edit2 to my previous post (nabbed some screenshots showing the failure to saturate belts 1 and 2 on output side (there was also so visible hitches in throughput on belts 1 and 2 on the input side, but that doesn't show in a screenshot; how do you make a gif for factorio?)
20160507043859_1.jpg
Shows failure to saturate.
I think the saturation issue is due to the introduction of spacing created by splitting 3 into 4 at the start of your balancer. I've long thought that any unused balancer input will introduce gaps.
That would not surprise me, but I am rather doubtful that you can solve the problem for all cases with some alternate design for a 4-belt balancer (see subsequent tests and discussion of forbidden triangle problem).

Frightning
Filter Inserter
Filter Inserter
Posts: 807
Joined: Fri Apr 29, 2016 5:27 pm
Contact:

Re: Non-throughput-limited 8+ belt balancers?

Post by Frightning »

So I did some extensive testing of the standard 4-belt balancer, trying to find a pair of inputs and outputs which failed to support full throughput. I did not test all (4 choose 2)*(4 choose 2)=6*6=36 possibilities, but that's because I don't need to, thanks to symmetry of the balancer. I tested, up to symmetry every possible combination, and sure enough, none of them failed to give full throughput, though many had some small flebs that were sporadic, and quite rare (typically only saw them one in 10 secs if that), which are probably not indicative of theoretical problems. So I did some more graph theory modeling of the problem, this time looking at the standard 4-belt balancer to see why every pair of inputs will give full throughput to any pair of outputs. It turns out that in every case, both used outputs are formed by two belts of material collapsing to one belt (once you remove the parts of the full balancer that are not in use and become backlogged with no throughput). This is not the case for the 3-belt balancer's problem cases (in all of those cases, one of the outputs came from a splitter whose other output went to the final splitter before the other output. Why might this detail matter? It has to do w/ backlogging and whether or not the splitter that has been backlogged to can correct the problem in a way that can 'stabilize'. In the forbidden triangle, the required equilibrium is not inherently stable because the belt segments that connect the first splitter to the middle splitter would have to remain immobile as though backlogged while all of the throughput of the middle splitter was coming from the other belt on that splitter's input side (and going to the output belt with no other splitter on it). That equilibrium is impossible because splitter don't behave like that. They always move items from both input belts to supply any throughput that is being accepted on the output side. This causes the final splitter to always be assigned more than 1 belt's worth of throughput, which is more than it has available on the output side, hence it backlogs and throughput is lost (mathematically, we can calculate that 1/3 of a belt in throughput is lost, and this is consistent with my experiments too!)

So then I decided to look at the theoretical situation involving 3 of 4 belts being used on the standard 4-belt balancer (now suspecting that it might effectively be a universally throughput unlimited 3-belt balancer if you choose the right 3 input and output belts to use). Interestingly enough, the graph theoretic analysis showed that it doesn't matter which 3 input belts or output belts you use, the result sequence of splitters that are involved is structurally the same (up to a relabeling). Hence no trio of input and trio output belts on the standard 4-belt balancer will give full throughput (so we still don't have a 3-belt balancer that is universally throughput unlimited because it fails under full load!)

Post Reply

Return to “Mechanical Throughput Magic (circuit-free)”