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: David Brown on 13 Jan 2010 11:09 Lorenzo Villari wrote: > On Tue, 12 Jan 2010 23:44:08 +0100 > David Brown <david.brown(a)hesbynett.removethisbit.no> wrote: > >> Thirdly, rather than having a compiler try to guess what algorithm >> you are trying to implement, it would be better to have more >> algorithms implemented in the libraries and preferably the language >> itself in a way that is natural for the programmer. For example, if >> the language has support for real arrays with functions such as >> sorting, the programmer can work with an array and let the compiler >> figure out the best way to implement it. >> > > 1) Coding a custom algorithm is not natural to the programmer? Coding efficient sort algorithms (since this is the example mentioned) is not natural to most programmers. "Low-level" algorithms for data structures, data manipulation and calculations is not something that many programmers are good at - it requires a more mathematical background to do well. Application algorithms are a different matter, of course. > 2) What's a "real" array? > I mean something more than syntactic sugar for a pointer and a block of memory (which is C's concept of arrays). Some languages have direct support for higher level data structures such as arrays which know their size and have useful methods, dictionaries, tress, etc. My point is, when the language and compiler support these sorts of structures, the compiler has a better chance to generate good code than when all it has is low-level pointer access, and it has to guess what you are doing with the array. >> With C, the programmer will >> either write their own bubble sort, or call qsort - with all its >> overheads. > > Which overhead? > The overhead of calling the comparison function indirectly through a pointer, and using run-time widths. Have you ever looked at the source code for a typical standard C library qsort() routine? As with many "generic" functions in C, it is far less efficient than if you right a dedicated quicksort function with known sizes and comparison functions. >> This is why programs written in interpreted languages >> such as Python can often be faster than compiled C code for code >> working with complex data structures, hash tables, sorting, list >> manipulation, etc., Of course the C code /could/ be faster - but >> people don't write optimal algorithms in most code. With the >> libraries and language support in Python, you get very good >> algorithms for free. >> > > If you can stand the formatting of python... ouch! It's the same case Python formatting is a matter of taste. At least there you are forced to work to a reasonably standard formatting - C gives people freedom to write the most hideous code (though it also lets you write quite nice code). > of custom code vs standard code, or custom C container vs STL C++ > container. One asks himself\herself why the c++ people agreed to have a > standard way of doing this and the C counterpart won't never agree... > C++ templates let you write something like a generic qsort() function that will generate good target code.
From: Hans-Bernhard Bröker on 13 Jan 2010 18:32 [X-post was rather excessive --- snipped] Rich Webb wrote: > What he's looking for is not compiler optimizations but optimization of > the underlying algorithm. Those two are not necessarily as different from each other as you make them out to be. Nothing stops a compiler from completely reorganizing a given function, as long as it's written in such a way that all effects to the outside are tightly scoped. I.e. a compiler is already allowed to detected a piece of code performs a sort and just call qsort() instead.
From: David Brown on 14 Jan 2010 03:07 Hans-Bernhard Br�ker wrote: > [X-post was rather excessive --- snipped] > > Rich Webb wrote: >> What he's looking for is not compiler optimizations but optimization of >> the underlying algorithm. > > Those two are not necessarily as different from each other as you make > them out to be. Nothing stops a compiler from completely reorganizing a > given function, as long as it's written in such a way that all effects > to the outside are tightly scoped. I.e. a compiler is already allowed > to detected a piece of code performs a sort and just call qsort() instead. > Nothing stops the compiler from doing this sort of thing in /theory/. But /practice/ is a different matter. It is not often that the compiler can find out what code (of a size large enough to be called an "algorithm") actually does - and it has to be sure that any replacements do at least as "good" a job. That means, in the words of the Wine project, bug-for-bug compatibility. It's no easy job, especially with C where you often can't (or don't, even if you /can/) properly express what you want the code to do, but merely how you want it to do it.
From: Phil Carmody on 14 Jan 2010 05:16 Obeying f/u - probably not gonna read any replies (came from c.l.c) Rainer Weikusat <rweikusat(a)mssgmbh.com> writes: > [***] A well implemented bubblesort will outperform any more advanced > algorithm easily if the number of elements to sort is sufficiently > small. I will assert just as boldly that a well-implemented insertion sort[*] will out-perform bubblesort in that situation. Phil [* I'll also assert it's easier to implement insertion sort well, as it's a simpler and more intuitive algorithm than bubblesort.] -- Any true emperor never needs to wear clothes. -- Devany on r.a.s.f1
From: Hans-Bernhard Bröker on 14 Jan 2010 17:26
David Brown wrote: > Nothing stops the compiler from doing this sort of thing in /theory/. > But /practice/ is a different matter. The same thing applies to the original question. If a compiler's full-blown optimizer, given practically infinite time to ponder the problem, can't get that analysis job done, then no other tool can, and certainly not while just looking over the programmers' shoulders as they type. |