On May 7th I'll have a discussion with Federica Frabetti, the author of the amazing book: Software Theory: A Cultural and Philosophical Study. Federica is an Associate Professor in Digital Media at the University of Roehampton, and a former software engineer. The book will be the focus of our discussion. In it, Federica draws upon the work of (underrated) figures like Bernard Stiegler, Jacques Derrida, and Timothy Clark, to enable a new cultural and political understanding of software.
William has almost no talks or interviews online. I thought this would be a one-time opportunity for anyone interested in these topics to pose questions to William directly! So, if you have a question for William, please send it to me using THIS FORM: https://docs.google.com/forms/d/e/1FAIpQLScu0u_nW3S94CfrEGza...! Also, feel free to forward it to anyone you think would be interested.
You should include your name, and link to channel in the form's self description. I accidentally followed the link blindly, and had no context.
Anyone following the link directly without viewing comments or knowing your hn username will be confused. I suspect your intended audience is larger than: people who already know you and your content well.
Thanks for the comment and I'm sorry for the late response. HackerNews is bad in that you get no notifications. I agree and I updated the form, although I suspect no one will see it now :-)
4 short essays:
- On the value of a non-thesis CS master's in a top school in the US
- Descartes' conception of infinity
- Unified theories as a type of compression
- Two interpretations of the rise of authoritarian regimes
Hey folks, author here. I'm really happy the article has gotten such attention. I hope it's good attention and that you folks learned something! Unfortunately, though, it's _very_ hard to keep track of all the comments in HackerNews. So, if you have a comment you'd like me to reply to and I haven't, please either use the Reddit post: https://www.reddit.com/r/Compilers/comments/1hapetl/common_m...
Indeed, I'm a 4-th year CS PhD at UIUC. Yes, the environment is great and it's surprising how non-antagonistic it is for a top school. About the social environment, that's exactly how you put it: let's not talk about it haha.
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.
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!
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.
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.
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.
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.
I don't know that much about ThinLTO but ThinLTO just works on summaries instead of the full code right? It still seems the linker is the one who reads these summaries (doc: https://clang.llvm.org/docs/ThinLTO.html).
You can send me your questions for Federica using THIS FORM: https://docs.google.com/forms/d/e/1FAIpQLSe3B8mnk7jS6yNLDj1L...