What's more important optimisations or debugging?

Optimising also adds in the possibiity of adding new bugs so its a stage to skip if you can. With very fast clock speeds now I no longer optimise unless I really need to.

Getting bugs out has got to be a top priority otherwise your customer wont come back !

are many, many

you are

since it is

algorithms,

general interest

Good compilers will not change a bubble sort into a quicksort. Optimization starts with describing what is wanted with good clear code. Good compiler optimization analyses the code presented and creates a solid implementation.

To weigh in on this thread set the compiler at the optimization level that the code is going to be shipped so the code that is debugged is the code shipped. There is nothing worse than debugging at one optimization level and shipping at another. The product that is shipped should be the one that is best understood and has had the most experience being used.

Walter Banks

-- Byte Craft Limited Tel. (519) 888-6911

email snipped-for-privacy@bytecraft.com

many, many

you are

since it is

algorithms,

general interest

A good implementation of a simple algorithm is often the right choice - bubblesort can be faster than quicksort for small numbers of elements, and is much easier to understand and get right in the code.

What I am arguing against is "optimising" your source code to the extent that it is no longer good code - if you need to do that, you've got the wrong algorithm (or wrong hardware). Writing sensible, efficient code is always a good thing - but if you need to go back and make lots of tweaks to your source code for better performance, then either you've written bad code in the first case, you have the wrong algorithm, or you have poor tools. For example, if you are at the level of changing a "for" loop into a "while (n--)" loop, or adding extra local pointer registers, then you are not helping (assuming, of course, that you have a reasonably effective optimising compiler).

QuickSort is not theoretically slower than all NlogN algorithms. It is theoretically faster than most, assuming a completely random distribution of the original data. But it has a worst case O(N^2) complexity, and it hits this worst case when the original data is already sorted. It can be modified to avoid this, if you are expecting to meet nearly sorted data. But if you are expecting to regularly meet nearly sorted data, then some other algorithms (including even bubblesort) can be much faster.

This is why sorting is so interesting in algorithm design - depending on the requirements, and the kind and size of data you will be sorting, there are many different algorithms.

There can easily be a factor of two between well-written code and badly written code, or between code compiled with a good optimising compiler and code compiled with a poorer compiler (or a good one with optimising turned off). Writing fast code is certainly part of writing high quality code - but I don't think you can, in general, take good quality code and "optimise" it to run twice as fast while still keeping it as good quality code.

I don't see that correlation at all. I've seen code that is long-winded, unclear, unmaintainable and bug-ridden. I've also seen code that is tight and compact, and is also unclear, unmaintainable and bug-ridden. I am in full support of the idea of spending extra time on the hard bits of the code, to get a better understanding and to write better code - and that this will often give faster code as well. But it's the speed of the code that is the bonus from writing better code with fewer bugs, not the other way round.

destined

Cranking the clock up with a slower implementation is not an option on many volume commercial products for two reasons

1) EMI Most products require EMI testing and reducing the clock speed is a factor that all other things being equal generally will reduce emissions. 2) Power consumption is a function of clock speed. A first order approximation power is a linear function of clock speed. With so many battery powered hand held products this is an important factor to be considered.

Optimization is not the issue as much as debugging at the optimization level that will be shipped so the final product is the product that was developed.

Something I see in Asia more than North America is project budgets for code size and execution cycles by function.

Walter Banks

-- Byte Craft Limited Tel. (519) 888-6911

email snipped-for-privacy@bytecraft.com

A lot of the PICs instructions are single cycle anyway. I have done a lot of projects where the PIC has to be the cheapest possible and has to mop up as much external hardware as possible i.e. UARTs. ADC etc Good PCB design should help with EMI. Given that the high clock is internal to the PIC I dont see that the problem should be so severe. Externals clocks running around the board is quite a different matter. Enclosure is important too to shield radiation both in and out.

Also most compilers are of good quality nowadays. It's always possible to find bugs of course (I've found at least one in every compiler I have used), but you need to throw millions of lines of code at it before you're guaranteed to find something. Also compiler bugs are not exclusively introduced by optimizations. In fact I know a compiler which had many more bugs when you turned optimizations off...

The idea of shipping with debugging off has been obsolete for quite a while - as Walter says, shipping the optimised code you tested is best. Most bugs are in the application rather than caused by the compiler. Of course bad programmers prefer to blame the compiler when a bug goes away when they change optimization level rather than fix their code...

Wilco

... snip ...

This is one of the points about mergesort. It is ALWAYS O(nlogn). In addition, it is always (properly coded) a stable sort. Neither applies to quicksort. Mergesort code can be very compact. For an example, see the demo applications in my hashlib package, at:

which is written in standard C and is completely portable. Released under GPL.

--
 
 
 
 
                        cbfalconer at maineline dot net

Let us no forget the aims for software development. It is to "Write a correct, robust, readable, documented program to perform the specified functions. The program should be written so that it can be modified, extended, or re-used in the future by the original author or others. It is good (and in some cases vital) that it demonstrate efficiency at run time in time and space, machine independence, ease of debugging, etc."

(paraphrased from "Software Fault Prevention by Language Choice: Why C is Not My Favorite Language" by Richard Fateman (UoC, Berkeley). Richard happens to like Lisp.

This is why the debug support would be higher up my list rather than optimisation. However, I also consider a decent development process that is able to debug the specification before you begin thinking about the code is a much better prospect all round.

--
********************************************************************
Paul E. Bennett ....................
Forth based HIDECS Consultancy .....
Mob: +44 (0)7811-639972
Tel: +44 (0)1235-811095
Going Forth Safely ..... EBA. www.electric-boat-association.org.uk..
********************************************************************

I meant the worst case complexity. People too often only look at the theoretical worst case rather than at the amortized average case which is what matters in practise. Similarly, the constant factor is often overlooked or being handwaved about, but again this is what actually matters in practise.

For similar reasons it's much better to use radix trees rather than balanced search trees. However everybody just codes the terribly complex and inefficient AVL or Red-Black stuff...

My standard implementation chooses the pivot from the middle, which works perfectly for partially sorted, sorted, reverse sorted inputs, and even the degenerate case of all elements identical. My point is that not all implementations are equal despite using the same basic algorithm...

Indeed. You could do partial insertion sort and only run quicksort if it didn't end up sorted.

Mergesort works quite well on linked lists but is very inefficient on arrays as it isn't an in-place algorithm. Quicksort needs far fewer data swaps, and that is the main reason it wins over mergesort or heapsort.

Wilco

... snip ...

Take a look at my implementation, as referenced before. No data is moved, only pointers.

--
 
 
 
 
                        cbfalconer at maineline dot net

This is not the case - it is perfectly possible to get true backwards stepping without hardware support, as UndoDB demonstrates.

- Julian [one of the developers of UndoDB].

--

There are two aspects to porting UndoDB - the OS, and the processor. At the moment, UndoDB only supports Linux/x86, but we hope to support other combinations in the future (see

The only major restriction is that the OS should have memory protection. There are ways of supporting non-protected OS's, but it would be somewhat harder to do.

- Julian [one of the developers of UndoDB]

--

Back-stepping cannot be done without hardware support or simulation of some sort. Either your product uses hardware support in some way, or it simply doesn't do full backwards debugging. I'm quite happy to believe that you can get somewhat beyond the simple call-stack view of gdb without more sophisticated hardware, but I am sceptical to your claims of back-stepping since you offer no explanation as to how it might work (at least, none that I can find).

The only hint I can see from your website is that you require Linux with a MMU - my guess is that you are making the stack and data segments read-only, trapping on writes and storing a log of these writes, before returning to the program. Combined this with traces on change-of-flow, and you can do a reasonable job of back-tracing - because you have a created a databus trace buffer. You won't get everything (changes to register data will be lost), and you have a hefty run-time overhead since every data write leads to a trap, but you would have a debug system that would be very useful in tracking down many types of bugs. If that is what you are doing, then you've got a good product, well worth the price you are asking - but not quite the magic you imply above.

Correct me if I'm wrong, of course - even though only a tiny proportion of embedded systems are x86 Linux, it's still a fascinating idea which is probably of interest to many people here.

This is comp.arch.embedded - we are often concerned with real-time behaviour and guarantees for time limits. So worst-case behaviour is sometimes critical. Certainly amortized time is often the important figure - and as you say, implementation (like careful choice of the pivot) can make a big difference to the chance of meeting the worst case, and therefore the amortized time.

And I agree that the constant factor is relevant - as can smaller O terms when the sizes are small (an algorithm may be described as O(NlogN) when the time taken is A*(NlogN) + B*N - the linear part will be important for small N and large B).

I think we both agree that the choosing the best algorithm for a particular problem involves much more than simply looking at the time complexity for large data sizes.

Just because it's not obvious how something works, doesn't mean it don't work :-)

We can argue forever here but, happily, we have an evaluation version of UndoDB available on our website, and it does exactly what I claim, so I'd encourage you to try it out.

I wasn't trying to imply it was magic. Though it's very hard to get right, and certainly the most difficult project I've ever been involved with.

However it doesn't work in the way you suggest. I don't really want to get into the details of how it works right now, but it certainly does involve some memory/time overheads.

- Julian [one of the developers of UndoDB]

--

If it were too obvious, then it would not be as interesting! But it is "obvious" that backstepping cannot work without simulation or hardware support, so I am both curious and sceptical. Perhaps x86 chips provide more hardware support than I thought (I don't know x86 devices in detail), in which case you *do* have sophisticated debugging hardware.

I don't do any native Linux debugging - by gdb usage is all cross-debugging. And anyway, my interest is not so much in seeing that UndoDB works, but knowing *how* it works. No doubt as others try it, information and reviews about how well it works will turn up across the web.

Memory and time overhead is of course an expected price to pay for the benefits of such a debugger.

According to Greg Law (on a few webpages found via Google),

"A reversible debugger effectively records everything that the debuggee program does, down to the finest detail: every memory access, every computation, every call to the operating system and every input it receives."

I don't think there is any way to do that using pure software except by simulation - you need debugging hardware support.

On the other hand, it is possible to get some sort of backwards stepping without anything more sophisticated than breakpoints (or using instrumentation functions in the compilation, much like profiling):

Basically, you take regular snapshots of the state of the program - say, every function call entry. If you want to go backwards in time, the debugger can reload the most recent snapshot, then use standard single stepping to move forward to the point you are looking at. When you are talking about debugging a deterministic program on a system with an MMU (the MMU ensures there is only a limited, known block of memory that the program could possibly change), this will work fine. In the context of embedded systems, this is not nearly enough to be considered backwards debugging, since it cannot handle asynchronous or external events.

mvh.,

David

I did, and it's a small and easy to understand implementation indeed (unlike some of the copying variants). Other sorts can avoid data swaps in a similar way. However when sorting pointers, you still need pointer swaps, and merge sort needs far more swaps than a good quicksort.

Wilco

Please qualify that with "in most cases". At the worst case mergesort is far faster than quicksort, since it is alway O(n log n). Also mergesort naturally handles lists.

--
 
 
 
 
                        cbfalconer at maineline dot net

Only if said practise by some stroke of luck happens not include real-time constraints. This would be the wrong newsgroup to refer to such circumstances as "in practise" without qualification. Actually, worst-case time is probably *more* important in our line of work than average time would be.

Brushing the worst case under a different corner of the same carpet doesn't really solve anything --- even if it's *very* big carpet.

Not really. Actual data swaps can be avoided the same way for all internal sorting algorithms, to the point where all algorithms use the same, perfect sequence of data moves (--> disjoint cycle decomposition of the permutation). Which is why standard theoretical analysis doesn't even bother looking at data moves, and instead qualifies algorithms by the number of comparisons only.