digitalmars.D - [OT] Keeping algorithm and optimisations separated
- renoX (12/12) Sep 09 2012 Hello,
- bearophile (27/33) Sep 09 2012 Maybe some programming language of the future will contain ways
- Nick Sabalausky (13/31) Sep 09 2012 That is very interesting. Sounds very domain-specific though, I wonder
- Guillaume Chatelet (34/49) Sep 09 2012 I was about to tell about Halide in D's forum : perfect timing :)
Hello, one common issue when you optimize code is that the code becomes difficult to read/maintain, but if you're trying to process images there may be hope: Halide is a DSL (currently embedded in C++) which keep the algorithm and the "optimization recipe"(schedule) separated AND the performance can be similar to hand-optimized C++ code. You can read more about Halide here: http://halide-lang.org/ Regards, renoX PS: I'm not related at all with the Halide's developers but I thought this is an interesting topic.
Sep 09 2012
"bearophile" <bearophileHUGS lycos.com> renoX:one common issue when you optimize code is that the code becomes difficult to read/maintain, but if you're trying to process images there may be hope: Halide is a DSL (currently embedded in C++) which keep the algorithm and the "optimization recipe"(schedule) separated AND the performance can be similar to hand-optimized C++ code.Maybe some programming language of the future will contain ways to specify code at various levels, like that. I think that's a quite important but unsolved problem of the endavour of designing languages. Today sometimes you see a complex function (or groups of related functions/methods) that is preceded by a comment that contains the pseudocode version of the algorithm implemented below. [I suggested the idea of docpicture, to insert small images in doctexts (similar to ddoc comments of D functions), to help explain algorithms implemented inside the following function. Later the idea was implemented by someone else: https://groups.google.com/forum/?hl=en&fromgroups=#!topic/comp.lan .python/ykGwWA0WKfc ] And one metric of progress in the history of computer language design is more and more content of the comments moved to code that a compiler/interpreter is able to understand (there are practical limits to this, this partially explains why today everybody isn't programming in Idris or ATS that support dependent types: sometimes saying some things to the compiler is not worth the effort). The idea of writing code in a high level and later specify a second or third layer of optimization on it, keeping the whole thing DRY (don't repeat yourself) seems an important progress for a future language. Bye, bearophile
Sep 09 2012
On Sun, 09 Sep 2012 19:36:56 +0200 "renoX" <renozyx gmail.com> wrote:Hello, one common issue when you optimize code is that the code becomes difficult to read/maintain, but if you're trying to process images there may be hope: Halide is a DSL (currently embedded in C++) which keep the algorithm and the "optimization recipe"(schedule) separated AND the performance can be similar to hand-optimized C++ code. You can read more about Halide here: http://halide-lang.org/ Regards, renoX PS: I'm not related at all with the Halide's developers but I thought this is an interesting topic.That is very interesting. Sounds very domain-specific though, I wonder how, or if, it could be generalized? Then again, on second thought, certain parts of the "schedule" part do seem pretty general. D would be a perfect language for this. It'd be cool to port it and demonstrate that an embedded language wouldn't be needed in D. It doesn't sound *too* far off from D ranges and std.parallelize. I think I'm gonna have to find a printer and kill a tree to actually read through that whitepaper, though. I don't understand why academic folk people still insist on putting electronic documents in paged *multi-column* form. PDF or not, it makes no sense, and only makes it awkward (at best) to read. This isn't 1970.
Sep 09 2012
On 09/09/12 19:36, renoX wrote:Hello, one common issue when you optimize code is that the code becomes difficult to read/maintain, but if you're trying to process images there may be hope: Halide is a DSL (currently embedded in C++) which keep the algorithm and the "optimization recipe"(schedule) separated AND the performance can be similar to hand-optimized C++ code. You can read more about Halide here: http://halide-lang.org/ Regards, renoX PS: I'm not related at all with the Halide's developers but I thought this is an interesting topic.I was about to tell about Halide in D's forum : perfect timing :) Halide has been announced just before siggraph 2012 (august). I think they really spotted the caveats of current Image Processing frameworks. But I'm unsure it can address all IP problems ( graph based images are out for instance ) and how the optimization part composes with the actual composition of functions. As bearophile told the automatic optimization problem is still quite open and it's not been tackled in this paper. So they decided to rely on the expert to then specify the optimization part in a dedicated language. They call this phase _the schedule_. The schedule language is very terse and allows experts to try a lot of different designs without rewriting the algorithm, quickly converging to an efficient solution for a particular hardware. The optimizations proposed by the framework ranges from 'compute once this subdomain and reuse' to 'inline everything'. The former is good when there is some redundant calculations ( as for spatial filters ), the later is better when it's just a pixel wise pipeline. Also because of bandwidth limitations it's often more interesting to trade computation against locality and better performance can be achieved by actually recomputing data. I do recommend anyone interested in image processing or data crunching to look at this project. For the moment they can process and let you optimize data pipelines up to four dimensions. The only issue is that optimal performance will be achieved only for a particular hardware (GPU and CPU schedules are completely different), there is no automatic optimization at runtime yet. But I'm sure the schedules produced by expert will soon lead to heuristics enabling self optimizing algorithms ( genetic algorithms anyone ? ) There is already a Python binding and I'm sure it'll be very easy to add a D one. The DSL basically builds an AST at runtime which is JIT compiled to machine code. -- Guillaume
Sep 09 2012