5 ms·

Why does optimal substructure work for code size? Couldn't you take a compiled non-minimal function and break each instruction into a function call (with some a

Why does optimal substructure work for code size? Couldn't you take a compiled non-minimal function and break each instruction into a function call (with some assumptions about the ISA maybe), then assuming each single-instruction function is minimal by itself, infer the entirety is minimal, contradicting?

Joker_vD 2y ago
> break each instruction into a function call With values falling into just the right registers magically? > each single-instruction function So the RET is also implicit? Well, in this case taking a non-minimal function and replacing its body with function calls to single-instruction functions would indeed reduce (or leave the same) the code size because some instructions are probably repeated, and now this duplication will be removed. What's the contradiction?
- timeforcomputer 2y ago
  In the article he says "Now, let's say you split the function in two parts and you find their minimums independently", so I am trying to think of what that means. I was thinking something like splitting "func() { ins1; ins2; }" into "ins1func() { ins1; } ins2func() { ins2; } func() { ins1func(); ins2func() }", but I agree this is an unwieldy/unrealistic example, all the register context would need to be passed in, stack memory addressing etc., and this changes instruction counts non-trivially. So I guess I don't need to think too much of the functionness of splitting up a code-block, I suppose this example contradiction would also apply and more cleanly if just thinking of the compiler considering blocks of code individually e.g. in a greedy algorithm. (Actually reading the intro again I think I overcomplicated this and he actually does mean just splitting into code blocks. My mistake)
baziotis 2y ago
Ok, I see a nice discussion going here. I may have disproved myself here and save ourselves some effort. First, just to be sure what we're talking about: If split the function in two and compile the two parts to minimum sizes, combining them gives you the global minimum. So, we're not starting from assembly programs. Now, you can compile a loop to a single instruction: https://godbolt.org/z/6E38dx8jr https://godbolt.org/z/6E38dx8jr And, if you split the loop and compile parts of it, you will most certainly not get this single instruction. So, I'm sorry! It seems I have proved myself wrong. I'll try to find some time to revisit this. I hope this helps!
- timeforcomputer 2y ago
  Yes I was surprised at that sentence because I think (considering theoretical properties of code size are the same as instruction count) that the main initial reason compiler optimization is non-trivial is because these kinds of global optimizations are possible, like your loop example. Also I am really enjoying your article, still reading it with wikipedia open on the side haha.
  - baziotis 2y ago
    Nice to hear that! I hope nothing else is questionable. And thanks for pointing it out! I guess the moral of the story is don't do "proofs" in your head after 3am.
- denotational 2y ago
  The definition of optimal substructure in the article isn’t quite right. A problem can have optimal substructure even if merging two optimal solutions to two sub-problems that compose to form the complete problem does not provide an optimal solution to the complete problem. This happens when there is more than one way of splitting the complete problem into two sub-problems. For example, the shortest path problem on a DAG has optimal substructure, but if you pick two subproblems by splitting the path at an intermediate node that does not lie on the shortest path, then you will not find an optimal solution by combining these. When this happens, one needs to optimise over all the possible ways of splitting into sub-problems. This is the basis of dynamic programming.
  - manwe150 2y ago
    Or graphically, this sounds like the spring paradox: https://www.youtube.com/watch?v=Cg73j3QYRJc https://www.youtube.com/watch?v=Cg73j3QYRJc
  - baziotis 2y ago
    Sure, but the article doesn't define optimal substructure, nor does it give a general statement about it. It just talks about a specific implication that _would be_ true if code size had optimal substructure as I thought (but based on my comment above, it seems I proved myself wrong).
timeforcomputer 2y ago
I just realised in the above comment I was making a mistake in an analogy to shortest path optimal substructure. In shortest path, starting with an optimal solution, "subproblems" have optimal solutions. This is not true starting from a non-optimal path, although length-1 subpaths are optimal. But still not sure of a particular way to phrase optimal substructure for code size. Sorry for the confusion!

Joker_vD 2y ago

> break each instruction into a function call With values falling into just the right registers magically? > each single-instruction function So the RET is also implicit? Well, in this case taking a non-minimal function and replacing its body with function calls to single-instruction functions would indeed reduce (or leave the same) the code size because some instructions are probably repeated, and now this duplication will be removed. What's the contradiction?

timeforcomputer 2y ago
In the article he says "Now, let's say you split the function in two parts and you find their minimums independently", so I am trying to think of what that means. I was thinking something like splitting "func() { ins1; ins2; }" into "ins1func() { ins1; } ins2func() { ins2; } func() { ins1func(); ins2func() }", but I agree this is an unwieldy/unrealistic example, all the register context would need to be passed in, stack memory addressing etc., and this changes instruction counts non-trivially. So I guess I don't need to think too much of the functionness of splitting up a code-block, I suppose this example contradiction would also apply and more cleanly if just thinking of the compiler considering blocks of code individually e.g. in a greedy algorithm. (Actually reading the intro again I think I overcomplicated this and he actually does mean just splitting into code blocks. My mistake)

baziotis 2y ago

Ok, I see a nice discussion going here. I may have disproved myself here and save ourselves some effort. First, just to be sure what we're talking about: If split the function in two and compile the two parts to minimum sizes, combining them gives you the global minimum. So, we're not starting from assembly programs. Now, you can compile a loop to a single instruction: https://godbolt.org/z/6E38dx8jr https://godbolt.org/z/6E38dx8jr And, if you split the loop and compile parts of it, you will most certainly not get this single instruction. So, I'm sorry! It seems I have proved myself wrong. I'll try to find some time to revisit this. I hope this helps!

timeforcomputer 2y ago
Yes I was surprised at that sentence because I think (considering theoretical properties of code size are the same as instruction count) that the main initial reason compiler optimization is non-trivial is because these kinds of global optimizations are possible, like your loop example. Also I am really enjoying your article, still reading it with wikipedia open on the side haha.
- baziotis 2y ago
  Nice to hear that! I hope nothing else is questionable. And thanks for pointing it out! I guess the moral of the story is don't do "proofs" in your head after 3am.
denotational 2y ago
The definition of optimal substructure in the article isn’t quite right. A problem can have optimal substructure even if merging two optimal solutions to two sub-problems that compose to form the complete problem does not provide an optimal solution to the complete problem. This happens when there is more than one way of splitting the complete problem into two sub-problems. For example, the shortest path problem on a DAG has optimal substructure, but if you pick two subproblems by splitting the path at an intermediate node that does not lie on the shortest path, then you will not find an optimal solution by combining these. When this happens, one needs to optimise over all the possible ways of splitting into sub-problems. This is the basis of dynamic programming.
- manwe150 2y ago
  Or graphically, this sounds like the spring paradox: https://www.youtube.com/watch?v=Cg73j3QYRJc https://www.youtube.com/watch?v=Cg73j3QYRJc
- baziotis 2y ago
  Sure, but the article doesn't define optimal substructure, nor does it give a general statement about it. It just talks about a specific implication that _would be_ true if code size had optimal substructure as I thought (but based on my comment above, it seems I proved myself wrong).

timeforcomputer 2y ago

I just realised in the above comment I was making a mistake in an analogy to shortest path optimal substructure. In shortest path, starting with an optimal solution, "subproblems" have optimal solutions. This is not true starting from a non-optimal path, although length-1 subpaths are optimal. But still not sure of a particular way to phrase optimal substructure for code size. Sorry for the confusion!