4 ms·

That seems interesting in theory but I have a hard time imagining what it would look like in practice. In my experience micro-optimizing C code looks like what

by simias 8y ago

That seems interesting in theory but I have a hard time imagining what it would look like in practice. In my experience micro-optimizing C code looks like what you describe: when you write your algorithm you have a pretty clear idea about what the machine code should look like. You compile it and check the assembly output to see if the compiler understood what you were going for. If it doesn't look like what you were expecting you need to make sure that the compiler didn't manage to actually generate better code than you exepected (because it might know things about the underlying architecture that you don't) and if it turns out that it's genuinely sub-optimal then you refactor your code a bit until you manage to get the compiler to do what you want. It can be a frustrating process. Now we do have a few language constructs to help us here, although sometimes it's not enough. We have inline, restrict, register as well, although that one is not really used a lot in practice in my experience (at least not for its original purpose). We have compiler extensions for computed GOTOs, alignment constraints etc... In this context what would "an interactive program-manipulation system" look like? Personally I think we could use more standardized constraints in languages like C to be able to annotate code in a way that could be useful to optimizer, such as tagging "cold" code, having control of the prefetcher and being able to write SIMD code without using intrinsics (a very complex problem admittedly). Standardizing computed gotos would be nice as well. Beyond that, in my experience a big problem with modern architectures is that it's very much non-trivial to figure out what's the fastest way to implement an algorithm. You have to consider which CPU model you're using, the cache architecture, RAM speed ... Second-guessing the compiler is pretty hard if you don't have a lot of experience optimizing for a particular architecture.

tonyg 8y ago
> That seems interesting in theory but I have a hard time imagining what it would look like in practice. This is one of the properties that makes an idea a worthy research direction.
pjmlp 8y ago
Only to be taken under our feet the moment the code gets compiled by another compiler, or updated version of the same one.
theoh 8y ago
It seems pretty clear that Knuth was not talking about instruction-level optimization, but about those activities/features that came to be known as metaprogramming, reflection, refactoring etc. I imagine he was thinking about human-directed program transformations that are almost language and machine-independent, implicitly high-level, whole-program stuff, rather than aimed at writing "idiomatic" fast machine code. So I guess not the kind of optimization you have in mind. What sounds more applicable for your use case would be profile-directed optimization, maybe based on mutating an initial fragment of assembler in ways that preserve its semantics but might improve performance. Like https://en.wikipedia.org/wiki/Superoptimization https://en.wikipedia.org/wiki/Superoptimization. But unless you wanted to create an instruction set that included reflection as a feature, this would most conveniently be written in another language. Edit: I should clarify, obviously self-modifying code written in assembler is in some sense reflective, but it's hard work.
naasking 8y ago
> Beyond that, in my experience a big problem with modern architectures is that it's very much non-trivial to figure out what's the fastest way to implement an algorithm. You have to consider which CPU model you're using, the cache architecture, RAM speed Indeed, we need better abstractions, like cache-oblivious data structures.

by simias 8y ago

tonyg 8y ago

> That seems interesting in theory but I have a hard time imagining what it would look like in practice. This is one of the properties that makes an idea a worthy research direction.

pjmlp 8y ago

Only to be taken under our feet the moment the code gets compiled by another compiler, or updated version of the same one.

theoh 8y ago

It seems pretty clear that Knuth was not talking about instruction-level optimization, but about those activities/features that came to be known as metaprogramming, reflection, refactoring etc. I imagine he was thinking about human-directed program transformations that are almost language and machine-independent, implicitly high-level, whole-program stuff, rather than aimed at writing "idiomatic" fast machine code. So I guess not the kind of optimization you have in mind. What sounds more applicable for your use case would be profile-directed optimization, maybe based on mutating an initial fragment of assembler in ways that preserve its semantics but might improve performance. Like https://en.wikipedia.org/wiki/Superoptimization https://en.wikipedia.org/wiki/Superoptimization. But unless you wanted to create an instruction set that included reflection as a feature, this would most conveniently be written in another language. Edit: I should clarify, obviously self-modifying code written in assembler is in some sense reflective, but it's hard work.

naasking 8y ago

> Beyond that, in my experience a big problem with modern architectures is that it's very much non-trivial to figure out what's the fastest way to implement an algorithm. You have to consider which CPU model you're using, the cache architecture, RAM speed Indeed, we need better abstractions, like cache-oblivious data structures.