A tool that suggests optimized logic for a piece of code/module/function
in [General Programming]
|
Prev: A tool that suggests optimized logic for a piece of code/module/function
Next: How to ascertain the type of files being read
From: Jon Kirwan on 15 Jan 2010 17:18 On Fri, 15 Jan 2010 12:19:11 -0800 (PST), -jg wrote: >On Jan 16, 8:28�am, Jon Kirwan <j...(a)infinitefactors.org> wrote: >> >> Walter, they don't even do _that_ task well enough. >> >> Since this topic appears to suggest the idea of having a >> compiler do something I consider almost crazy-minded at this >> point in time..... > > Yes, the best reply to the original overall question, is a Pencil !!. Hehe. I can conceive (and accept) the idea that once good _human_ imagination has been applied, that these concepts can be more rigorously explored (along the lines found in Knuth's early 1970's 3-volume set) about their boundary conditions and application space and placed into a "dictionary of moves" (as in some chess programs) that a compiler can use, together with heuristics to adduce which of the many options to choose as a "fit." Yeah, I can imagine the idea. And perhaps some of the low hanging fruit there can be picked, too. Don't know. But cripes! Some time ago, I engaged in a very interesting process exploring various compilers' results upon compiling a very simple (we are talking maybe 10-12 lines of code here?) and well-known algorithm for calculating the GCD of two integers. The creative juices of several were applied, with the result of more than one excellent topological reformation that, had a compiler observed it, would have resulted in the automatic generation of object code very close to the best a human can do on their own. (Once the slight reorganization was found, merely using traditional optimizations that have been implemented, not just known about, for two decades and more.) I have no problem discussing viable ideas about moving well forward. But a journey of a thousand miles starts with a single step. I'd just like to see some serious discussion about some of these earlier steps and some actual implementation work exhibited. I'm not speaking from afar, from some distanced or uninvolved position. I'm willing to put in my own time here, to put money where my mouth is at. I'm NOT a practiced compiler writer, only having a few experiences of my own (a BASIC interpreter, with a library, and a toy c compiler without any of the library system.) But I'd be willing to, under the guidance of those more recently and broadly experienced, cooperate and supply time working on some ideas if it would help here. I'm seriously interested in meaningful compiler advances. There is so much that is yet to do that is right in front of us, though. I'd like to see success there before wasting so much breath on what appears right now to be pretty far out and even then relatively ad hoc besides. > However, there are some details, aside from the >'find a new algorithm'(?!) request that tools could be >expected to offer. > > Taking this: >[" It will be even more helpful if that tool >also provides the cycle counts, cache >usage, cache misses and lines of code >also. "] To add something else I'd like to have in a language above the level of assembly, since we are chatting, is the ability to specify that two different code edges on either side of a branch must execute in the exact same cycle count. In other words, that regardless of the condition, the entire block of code including the condition test must have one and only one execution time. I have application for this. But we may be simply discussing all this by starting from a bottom up approach, listing various "leaf ideas" we'd like to see -- hoping perhaps that, by induction, we may find an enclosing principle from that. I'd like to see a more theoretical approach taken, where specific approaches are _deduced_ readily by applying circumstances to theory. So here and regarding your suggestion about cache usage and cache misses, I'd refer to this: http://mitpress.mit.edu/catalog/item/default.asp?tid=5098&ttype=2 A 1985 dissertation. Although it was more focused on DRAM bank organization, among other things, I suspect that the theoretical ideas it presents could also be used to deduce some thoughts addressing a variety of cache optimizations, taking those specifics into account. > Lines of code should already be there, in a listing output, and also >in a debugger. Yeah. It's been done. It just isn't done enough for embedded work, I suppose. > Likewise, on a chip/ICE with HW breakpoints and sys timers, you could >expect a good system to be able to give time-of-flight on running >code, if you really need that. > The OP sees to expect all this in an EDITOR, which is miss-directed, >but it is possible in a full tool chain. I suppose so. I was addressing myself to the idea of swapping in a quick sort for a bubble sort and similar thrusts, though. On that point, there are some earlier steps to take first. Jon
From: David Brown on 16 Jan 2010 11:11 Andy wrote: > On Jan 14, 9:57 am, David Brown <da...(a)westcontrol.removethisbit.com> > wrote: >> I don't agree here (perhaps as a compiler writer you are thinking of >> "implementation" in terms of generated target code - then I'd agree). >> Kids use Logo to learn about programming concepts, and how to get the >> computer to do what you want it to do. They learn to write things like: >> >> TO SQUARE :size >> REPEAT 4 [ FD :size RT 90 ] >> END >> >> This is entirely about writing an imperative implementation of how you >> want the system to draw a square. >> >> Compare this to a sample program in a real functional programming >> language, Haskell: >> >> factorial 0 = 1 >> factorial n = n * factorial(n - 1) >> >> Here you tell the system what you want - you give a mathematical >> description of the results. You don't care how it gets them - maybe it >> uses recursion, maybe it uses iteration, maybe it builds up a cache of >> calculated values as it goes along. >> > > The LOGO interpreter/compiler is just as free to implement alternative > solutions to drawing a square as the Haskell compiler is of altering > the described recursive implementation of a factorial. Whether the > compiler is smart enough to do so has nothing to do with the language > being "procedural" or "functional". > It is certainly true that the compiler is free to implement alternative solutions in any language. However, the style of language has a great deal to say in how hard a task this is for the compiler writer. In particular, with a language that does not have states or allow side effects in functions, it is much easier for the compiler to have a complete view of what the function does - and thus it has a better chance of generating alternative implementations. You can think of compiling (or interpreting - it's the same thing in theory) as taking a high level source code down to a low level implementation in a series of steps. At each step down, the compiler can pick one of many implementations at the lower level. It can also re-arrange the code at the same level. Moving up a level from an implementation is a much harder task, and will rarely lead to a better result in the end - too much of the "overview" information is already lost, and there are too many implementation details that cannot be distinguished from requirements. Thus an ideal compiler has the best chance of generating the best code if the source is at a higher level, and if it is written in a language that gives a clearer and more mathematically precise specification. Of course, practical reality does not match directly with the theory. In particular, vastly more man-hours have been spent to write better compilers for C than for Haskell - the result being that you can compile C code to tighter target code than you can with Haskell code.
From: Jon Kirwan on 16 Jan 2010 17:01 On Sat, 16 Jan 2010 13:01:24 -0800 (PST), -jg <jim.granville(a)gmail.com> wrote: >On Jan 16, 11:18�pm, Walter Banks <wal...(a)bytecraft.com> wrote: > >> To illustrate this point. Your exact timing example is not a >> C compiler limitation but a language limitation. How do >> you describe exact timing all paths in a function in an >> unambiguous way in C? Exact timing is an application >> objective. > > Something like exact timing would be via local directives, and is >going to be very locally dependant. Oh, yes. On some machines (on one extreme, the modern x86 with branch detection logic, read-around-write data flows, registration stations, all manner of out-of-order execution, and multi-level caching), it would be a nightmare to achieve. On others, quite achievable in practice. The "requirement" would instead be a "goal" for the compiler language. Something like "register" is for a c variable -- a suggestion -- but perhaps with a little higher priority meant than 'register' means today. #pragma might be appropriate to bracket the code where all edges should perform in similar times, though I'm sure there will be problems to work out there, too. > It almost comes into "better reporting" Not just better reporting for the case I'm talking about. If you can't provide something that actually impacts the code generation but have very good reporting on what you get out of it, you will find yourself fighting the darned thing at every turn of the code trying to work out equal times. It's far better to provide the clues and hints a compiler can then use in generating code. > I remember we added a simple code-size report, for each code block, >so pgmrs could quickly compare different choices. Trivial to do, and >useful. > > We did think about reporting time, but that quickly degenerates as >you do not know what path combinations will actually occur, and it can >vary widely across >same core:different vendor. > So our solution here was always to verify on a scope, >and patch as needed. That covers all complexity levels. > > > On this 'exact timing' topic, I note the new Cortex M0 cores (NXP, >Nuvoton?), claims a fixed-int-response time, so they remove the >'current opcode' jitter. This was also discussed some years ago as a >feature option for a faster 8051 that never got to silicon. > It's a good thing to see devices that are moving 'less deterministic' >offer a way to be 'more deterministic' :) >[- and it side-steps all that SW work ] The ADSP-21xx provides rock-solid timing. If the only interrupt source is the timer, since that is in synch with the clock and doesn't need to be asynchronously latched and tested, then even the interrupt latency is _exactly_ known. Very sweet. I used that to advantage. Jon > >-jg
From: Jon Kirwan on 16 Jan 2010 22:08 On Sat, 16 Jan 2010 14:43:11 -0800 (PST), -jg <jim.granville(a)gmail.com> wrote: >On Jan 17, 11:01�am, Jon Kirwan <j...(a)infinitefactors.org> wrote: >> On Sat, 16 Jan 2010 13:01:24 -0800 (PST), -jg >> >> <jim.granvi...(a)gmail.com> wrote: >> >> > It almost comes into "better reporting" >> >> Not just better reporting for the case I'm talking about. �If >> you can't provide something that actually impacts the code >> generation but have very good reporting on what you get out >> of it, you will find yourself fighting the darned thing at >> every turn of the code trying to work out equal times. �It's >> far better to provide the clues and hints a compiler can then >> use in generating code. > > In the simplest cases, the difference between manually adding NOPs >and checking, or trawling the manual, setting a directive, and then >also checking the tool really DID do what you hoped, is negligible. > > In the more complex cases, the tools are almost certain to drop the >ball, so you'll also need to manually check. > > So that's why I favour 'better reporting' over 'granular smarts' >anytime, as the reporting is ALWAYS useful, and the smarts are only >case-by-case useful and with risky failure modes. >[aka The illusion of intelligence is dangerous] > > The rare times I've needed to do this, it was no sweat to just use a >pencil, and then do an operational check. Well, what can I say? I'd doing pretty much exactly this in the case where I needed it -- wrote it in assembly and counted instructions. However, I acknowledge that a compiler would do a reliable job of counting cycles. This is one of those good examples where it's better to let the compiler worry about the bookkeeping issues. Jon
From: Rainer Weikusat on 17 Jan 2010 06:32
Nick Keighley <nick_keighley_nospam(a)hotmail.com> writes: > On 13 Jan, 16:43, dj3va...(a)csclub.uwaterloo.ca.invalid wrote: >> In article <4b4def88$0$22938$e4fe5...(a)news.xs4all.nl>, >> [Jongware] <so...(a)no.spam.net> wrote: >> >Walter Banks wrote: > >> >> Defining goals at a much higher level than C opens the possibilities >> >> for automating algorithmic choices at the function level. >> >> >Aha -- wouldn't the logical end point be a programming language where >> >you type "word processor", save it as source, compile, and have a word >> >processor? >> >> Why bother to compile it? �Just have it interpret on-the-fly. >> That way you could even run it in interactive mode, and it's >> sufficiently high-level that even non-programmers could usefully use >> it. >> >> Unix people call this a "shell". > > I'm guessing you're trying to be funny/ironic. But in case you aren't, > Unix has dozens of stranglely incompatible Command Line Interfaces > that Unix people call "shells". None of them are word processors. UNIX(*) has a single type of 'interactive command processor/ simple scripting language' and its features are described by an IEEE standard. You observation that lots of different people and organizations have written application software for UNIX(*) and that this different applications differ is nevertheless correct. Pearls of wisdom ... |