4 ms·

Nice analogy, I wouldn't have thought of that. But I'm unconvinced that this is a good measure of software complexity; for one, there are only three nontrivial

Nice analogy, I wouldn't have thought of that. But I'm unconvinced that this is a good measure of software complexity; for one, there are only three nontrivial complexity levels (2, 3, 4). But it's also unstable: a circle with an odd number of nodes (e.g. a triangle) requires three colours, while a circle with an even number of nodes needs only two, even though both models seem similarly complex.

throwaway080383 9y ago
(2, 3, 4) only applies to planar graphs, which the graph of a code base need not be. E.g. if you have n classes which all pairwise talk to each other, you'll need n colors.
- amelius 9y ago
  Yes. He has a point with the circle though.
rbalicki 9y ago
This analogy has some strength, but one of the most obvious complaints is as follows. Having everything go through one central bus (e.g. `bus.setItem` and `bus.getItem`) requires only two colors, one for the bus and one for everything else. But of course, that just hides all of the complexity. Nonetheless, focusing on reducing complexity and simplifying dependency graphs is good, mmkay.
- Someone 9y ago
  You can even get it down to one color by writing a big ball of mud (https://en.m.wikipedia.org/wiki/Big_ball_of_mud https://en.m.wikipedia.org/wiki/Big_ball_of_mud)
- ballenf 9y ago
  The complexity inside an interface should also be considered -- how the components of the 'bus' interact with each other with one connection to the outside world. If the 'bus' is simple enough to need few colors, then great. Same goes for the sibling comment regarding a ball of mud. It makes the analysis more complex but you should consider every global variable as connected to every other global in constructing the graph. Balls of mud, in my thinking, then need nearly as many colors as they have globals since every component theoretically interacts with every other. And when I mixed all the water colors as a kid, I was always disappointed to get a muddy color.
- adrianratnapala 9y ago
  Its important to remember that complexity matters at all levels of abstraction and you don't improve things by merely moving it from the level you are looking to one you are ignoring. Simplifying your depgraph by writing on big ball of mud means pushing the complexity down. Instead of a complex module graph, you have a complex dependency graph between variables/functions/whatever in your mudball. Oversimplify your individual modules and you complexify your module graph, or even your production infrastructure (one-line microservices anyone?). Forced to choose, I would prefer a mudball to dependency hell. But really I would like the complexity to be intelligently and somewhat evenly distributed to each level.
deleted 9y ago
[deleted]
aphextron 9y ago
>But I'm unconvinced that this is a good measure of software complexity; for one, there are only three nontrivial complexity levels (2, 3, 4) But can we even reason beyond 4 levels? This point made a lot of sense to me. My intuition is that this comes down to our fundamental inability to generally solve quintics. There are also topological proofs to this which fit the author's point perfectly [0]. 4th degree is the limit of formal proof. [0] https://en.wikipedia.org/wiki/Topological_Galois_theory https://en.wikipedia.org/wiki/Topological_Galois_theory
pdpi 9y ago
> there are only three nontrivial complexity levels (2, 3, 4). That's only true if your dependency graph is planar. That said, the sentiment is spot on: you can get away with arbitrarily complicated code as long as you avoid embedding K_3,3 and K_5 in your dependency graph.
squeaky-clean 9y ago
> while a circle with an even number of nodes needs only two, even though both models seem similarly complex. This is touched on in the article. The triangle is a complete graph, each vertice is connected to each other. A 2 colored circular graph would not be a complete graph. It would have a ring or fan-out shape. You could have graph with 3 vertices that is 2 colored, you just can't have each vertice be connected to each other one. I don't have great intuition for graphs but I'm pretty sure something like a square or larger cannot be both complete and planar. Or to bring it back to software, I think it's true that a small system where each piece can directly talk to each other piece is more complex than a large system where pieces only communicate with their neighbors.
- akud 9y ago
  > I don't have great intuition for graphs but I'm pretty sure something like a square or larger cannot be both complete and planar. A square can, (you put one node in the middle), but 5 and up can't be both complete and planar.
  - squeaky-clean 9y ago
    > A square can, (you put one node in the middle) Clever!
- tomsmeding 9y ago
  I was talking about a circle in which only neighbouring nodes are connected: +---+ / \ + + \ / +---+ For 6, for example. This thing is two-colourable, while one with 5 nodes is only three-colourable. That's the instability I was referring to.
adrianratnapala 9y ago
> here are only three nontrivial complexity levels (2, 3, 4) The four colour limit is only for planar graphs. Dependency graphs need not be planar. Also there is a very well understood connection between software complexity and graph colourings: register allocation. If you model variables as vertices, and place edges between variables that are required at the same time, then assigning locations to variables is a graph colouring. I think this might generalise: the number of graph colours tells you something about the maximum number of things you need to keep track of simultaneously in order to deal with one locality in the graph.

throwaway080383 9y ago

(2, 3, 4) only applies to planar graphs, which the graph of a code base need not be. E.g. if you have n classes which all pairwise talk to each other, you'll need n colors.

amelius 9y ago
Yes. He has a point with the circle though.

rbalicki 9y ago

This analogy has some strength, but one of the most obvious complaints is as follows. Having everything go through one central bus (e.g. `bus.setItem` and `bus.getItem`) requires only two colors, one for the bus and one for everything else. But of course, that just hides all of the complexity. Nonetheless, focusing on reducing complexity and simplifying dependency graphs is good, mmkay.

Someone 9y ago
You can even get it down to one color by writing a big ball of mud (https://en.m.wikipedia.org/wiki/Big_ball_of_mud https://en.m.wikipedia.org/wiki/Big_ball_of_mud)
ballenf 9y ago
The complexity inside an interface should also be considered -- how the components of the 'bus' interact with each other with one connection to the outside world. If the 'bus' is simple enough to need few colors, then great. Same goes for the sibling comment regarding a ball of mud. It makes the analysis more complex but you should consider every global variable as connected to every other global in constructing the graph. Balls of mud, in my thinking, then need nearly as many colors as they have globals since every component theoretically interacts with every other. And when I mixed all the water colors as a kid, I was always disappointed to get a muddy color.
adrianratnapala 9y ago
Its important to remember that complexity matters at all levels of abstraction and you don't improve things by merely moving it from the level you are looking to one you are ignoring. Simplifying your depgraph by writing on big ball of mud means pushing the complexity down. Instead of a complex module graph, you have a complex dependency graph between variables/functions/whatever in your mudball. Oversimplify your individual modules and you complexify your module graph, or even your production infrastructure (one-line microservices anyone?). Forced to choose, I would prefer a mudball to dependency hell. But really I would like the complexity to be intelligently and somewhat evenly distributed to each level.

deleted 9y ago

[deleted]

aphextron 9y ago

>But I'm unconvinced that this is a good measure of software complexity; for one, there are only three nontrivial complexity levels (2, 3, 4) But can we even reason beyond 4 levels? This point made a lot of sense to me. My intuition is that this comes down to our fundamental inability to generally solve quintics. There are also topological proofs to this which fit the author's point perfectly [0]. 4th degree is the limit of formal proof. [0] https://en.wikipedia.org/wiki/Topological_Galois_theory https://en.wikipedia.org/wiki/Topological_Galois_theory

pdpi 9y ago

> there are only three nontrivial complexity levels (2, 3, 4). That's only true if your dependency graph is planar. That said, the sentiment is spot on: you can get away with arbitrarily complicated code as long as you avoid embedding K_3,3 and K_5 in your dependency graph.

squeaky-clean 9y ago

> while a circle with an even number of nodes needs only two, even though both models seem similarly complex. This is touched on in the article. The triangle is a complete graph, each vertice is connected to each other. A 2 colored circular graph would not be a complete graph. It would have a ring or fan-out shape. You could have graph with 3 vertices that is 2 colored, you just can't have each vertice be connected to each other one. I don't have great intuition for graphs but I'm pretty sure something like a square or larger cannot be both complete and planar. Or to bring it back to software, I think it's true that a small system where each piece can directly talk to each other piece is more complex than a large system where pieces only communicate with their neighbors.

akud 9y ago
> I don't have great intuition for graphs but I'm pretty sure something like a square or larger cannot be both complete and planar. A square can, (you put one node in the middle), but 5 and up can't be both complete and planar.
- squeaky-clean 9y ago
  > A square can, (you put one node in the middle) Clever!
tomsmeding 9y ago
I was talking about a circle in which only neighbouring nodes are connected: +---+ / \ + + \ / +---+ For 6, for example. This thing is two-colourable, while one with 5 nodes is only three-colourable. That's the instability I was referring to.

adrianratnapala 9y ago

> here are only three nontrivial complexity levels (2, 3, 4) The four colour limit is only for planar graphs. Dependency graphs need not be planar. Also there is a very well understood connection between software complexity and graph colourings: register allocation. If you model variables as vertices, and place edges between variables that are required at the same time, then assigning locations to variables is a graph colouring. I think this might generalise: the number of graph colours tells you something about the maximum number of things you need to keep track of simultaneously in order to deal with one locality in the graph.