4 ms·

The title is misleading. As far as the article goes, this pertains only to tunnel digging. That's at least in part because the "dig, move rubble, dig" task is v

by dmos62 8y ago

The title is misleading. As far as the article goes, this pertains only to tunnel digging. That's at least in part because the "dig, move rubble, dig" task is vulnerable to congestion.

pier25 8y ago
Is programming vulnerable to congestion?
- brianpan 8y ago
  Merges
- plussed_reader 8y ago
  Sure, check out 'garbage collection'.
- tedmiston 8y ago
  If anyone still uses centralized version control where only one person can check out a given file at a time, that's the epitome of programmer congestion.
thaumasiotes 8y ago
Congestion is an issue if you're using the painter's algorithm to dig the tunnel (pick up a chunk of dirt from the end of the tunnel, carry it all the way back to the beginning, trudge back down to the end, pick up a second chunk of dirt...). Any number of ants can apply that strategy in parallel, but they'll be stymied by congestion in a tight tunnel. But that algorithm is terrible. Most of your time is wasted walking back and forth. You can do a lot better by setting up a relay, where one ant is responsible for a fixed length of tunnel, and its job is to pick up dirt from one end and drop that dirt at the other end for the next ant. Congestion is still a problem for that strategy, but the whole issue is different in kind. This task scales better with more ants than the stupid way -- the more ants you have, the shorter you can make each relay leg, without having two ants contend for the same physical space at any point.
- repsilat 8y ago
  > Most of your time is wasted walking back and forth If the tunnel is two ants wide then the relay is basically the same as a long circuit. Every bit of dirt needs to be carried the entire length of the tunnel, so it doesn't really matter if one and carries it the whole way or if n ants do -- the number of ant-miles full and empty are the same, it's just the relative cost of passing manoeuvres and handoffs that matter (or nonlinear carrying costs -- maybe it's easier on the ants to have shorter, more frequent changes between carrying and not carrying.)
  - thaumasiotes 8y ago
    What if the tunnel is two ants wide and seven relay-legs long? You can usefully employ 14 ants that way, where you'd be stuck at two without the relays. You're right about the ant-miles full and empty being constant; I guess the advantage of the relay is purely the ability to scale without congesting.
    - repsilat 8y ago
      > you'd be stuck at two without the relays. You mean if you had two ants walking side-by-side? If it's two ants wide you can have one lane in each direction and use all the ants you like.

by dmos62 8y ago

The title is misleading. As far as the article goes, this pertains only to tunnel digging. That's at least in part because the "dig, move rubble, dig" task is vulnerable to congestion.

pier25 8y ago

Is programming vulnerable to congestion?

brianpan 8y ago
Merges
plussed_reader 8y ago
Sure, check out 'garbage collection'.
tedmiston 8y ago
If anyone still uses centralized version control where only one person can check out a given file at a time, that's the epitome of programmer congestion.

thaumasiotes 8y ago

Congestion is an issue if you're using the painter's algorithm to dig the tunnel (pick up a chunk of dirt from the end of the tunnel, carry it all the way back to the beginning, trudge back down to the end, pick up a second chunk of dirt...). Any number of ants can apply that strategy in parallel, but they'll be stymied by congestion in a tight tunnel. But that algorithm is terrible. Most of your time is wasted walking back and forth. You can do a lot better by setting up a relay, where one ant is responsible for a fixed length of tunnel, and its job is to pick up dirt from one end and drop that dirt at the other end for the next ant. Congestion is still a problem for that strategy, but the whole issue is different in kind. This task scales better with more ants than the stupid way -- the more ants you have, the shorter you can make each relay leg, without having two ants contend for the same physical space at any point.

repsilat 8y ago
> Most of your time is wasted walking back and forth If the tunnel is two ants wide then the relay is basically the same as a long circuit. Every bit of dirt needs to be carried the entire length of the tunnel, so it doesn't really matter if one and carries it the whole way or if n ants do -- the number of ant-miles full and empty are the same, it's just the relative cost of passing manoeuvres and handoffs that matter (or nonlinear carrying costs -- maybe it's easier on the ants to have shorter, more frequent changes between carrying and not carrying.)
- thaumasiotes 8y ago
  What if the tunnel is two ants wide and seven relay-legs long? You can usefully employ 14 ants that way, where you'd be stuck at two without the relays. You're right about the ant-miles full and empty being constant; I guess the advantage of the relay is purely the ability to scale without congesting.
  - repsilat 8y ago
    > you'd be stuck at two without the relays. You mean if you had two ants walking side-by-side? If it's two ants wide you can have one lane in each direction and use all the ants you like.