Hacker News Reader

Comment by timeforcomputer | Hacker News Reader

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?

View on HN

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

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!

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.

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.

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.

Or graphically, this sounds like the spring paradox: https://www.youtube.com/watch?v=Cg73j3QYRJc

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).

> Now, let's say you split the function in two parts and you find their minimums independently. Optimal substructure tells us that if you just merge these two, you'll get the minimum version of the whole function.

Optimal substructure doesn't tell us this. I don't know whether or not this problem has optimal substructure, but even if it did, it still wouldn't tell us this.

Optimal substructure means it is possible to construct an optimal solution from optimal solutions to its subproblems; it doesn't mean that optimal solutions to arbitrary pair of subproblems (that compose to form the complete problem) can be used to form an optimal solution, which is what I understood the quoted section of the article to be saying.

Thanks, it looks like I had forgotten how dynamic programming works, e.g. constructing from possibly all subproblem solutions rather than just some way of breaking into some disjoint union. In this case I guess for code optimization a "subproblem" needs to be defined. I'm not sure if just breaking the code into chunks works as I was imagining. Maybe optimal substructure applies to some graph-like model of computation but not the naive assumption I made on how this would work.

> 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?

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)

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!

Reply on news.ycombinator.com