What's more important optimisations or debugging?

Wilco Dijkstra wrote:
> "CBFalconer" <cbfalconer@yahoo.com> wrote:
>> David Brown wrote:
>>
... snip ...
> 
>>> 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.
>>
>> 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.
> 
> 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.

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

-- 
 <http://www.cs.auckland.ac.nz/~pgut001/pubs/vista_cost.txt>
 <http://www.securityfocus.com/columnists/423>
 <http://www.aaxnet.com/editor/edit043.html>
 <http://kadaitcha.cx/vista/dogsbreakfast/index.html>
                        cbfalconer at maineline dot net



-- 
Posted via a free Usenet account from http://www.teranews.com

On 31 May, 12:13, David Brown <d...@westcontrol.removethisbit.com>
wrote:
> Colin Paul Gloster wrote:

> > Has anyone experience or impressions of debuggers which allow stepping
> > backwards in time through program flow, such as apparently provided
> > for desktops/workstations byUndoDB(
> > WWW.Undo-Software.com
> > ) and Java (Virtual Machine?) debuggers? If so, for which processors
> > and with which tools? I imagine it would be possible to pay Undo
> > Limited to port a version of its debugger which would be compatible
> > with any of the targets supported by the GNU DeBugger GDB asUndoDBis
> > a wrapper for GDB.
>
> > Curious,
> > Colin Paul Gloster
>
> Many debuggers can let you look back in time to some extent, by looking
> at the call stack - this will let you see what called your current
> function, and the state of local variables in the caller function (and
> its callers, and so on).  But to get true backwards stepping, you need
> very sophisticated trace buffers.  Some processors, combined with
> expensive hardware debuggers, can give you limited traces (such as
> indications of program flow), but a full trace requires capturing the
> databus and all internal data flows.  It's easy to do in a simulation,
> and possible to do in a full hardware emulator, but impossible with
> modern jtag-type debugging.

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].

--
http://undo-software.com/

On 31 May, 10:34, Colin Paul Gloster <Colin_Paul_Glos...@ACM.org>
wrote:
> Innews:1180571919.025883.219930@i13g2000prf.googlegroups.com
> timestamped 30 May 2007 17:38:39 -0700, Ryan H <rhapg...@gmail.com>
> posted:
>      "On May 31, 9:21 am, BubbaGump <BubbaGump@localhost> wrote:
>
>      > I don't understand the question.  Debugging features in a development
>      > tool or extra debugging information in executable code?
>
>      The question refers to debugging features in a toolsuite. [..]
>
>      [..]"
>
> Has anyone experience or impressions of debuggers which allow stepping
> backwards in time through program flow, such as apparently provided
> for desktops/workstations byUndoDB(
> WWW.Undo-Software.com
> ) and Java (Virtual Machine?) debuggers? If so, for which processors
> and with which tools? I imagine it would be possible to pay Undo
> Limited to port a version of its debugger which would be compatible
> with any of the targets supported by the GNU DeBugger GDB asUndoDBis
> a wrapper for GDB.

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 http://undo-software.com/undodb_roadmap.html).
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]

--
http://undo-software.com/

google.co.uk@op59.net wrote:
> On 31 May, 12:13, David Brown <d...@westcontrol.removethisbit.com>
> wrote:
>> Colin Paul Gloster wrote:
> 
>>> Has anyone experience or impressions of debuggers which allow stepping
>>> backwards in time through program flow, such as apparently provided
>>> for desktops/workstations byUndoDB(
>>> WWW.Undo-Software.com
>>> ) and Java (Virtual Machine?) debuggers? If so, for which processors
>>> and with which tools? I imagine it would be possible to pay Undo
>>> Limited to port a version of its debugger which would be compatible
>>> with any of the targets supported by the GNU DeBugger GDB asUndoDBis
>>> a wrapper for GDB.
>>> Curious,
>>> Colin Paul Gloster
>> Many debuggers can let you look back in time to some extent, by looking
>> at the call stack - this will let you see what called your current
>> function, and the state of local variables in the caller function (and
>> its callers, and so on).  But to get true backwards stepping, you need
>> very sophisticated trace buffers.  Some processors, combined with
>> expensive hardware debuggers, can give you limited traces (such as
>> indications of program flow), but a full trace requires capturing the
>> databus and all internal data flows.  It's easy to do in a simulation,
>> and possible to do in a full hardware emulator, but impossible with
>> modern jtag-type debugging.
> 
> This is not the case - it is perfectly possible to get true backwards
> stepping without
> hardware support, as UndoDB demonstrates.
> 

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.

Wilco Dijkstra wrote:
> "CBFalconer" <cbfalconer@yahoo.com> wrote in message news:4668771B.913E42A5@yahoo.com...
>> David Brown wrote:
>> ... snip ...
>>> QuickSort is not theoretically slower than all NlogN algorithms.
> 
> 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.
> 

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.

> 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...
> 
>>> 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.
> 
> 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...
> 
>>> But if you are expecting to
>>> regularly meet nearly sorted data, then some other algorithms
>>> (including even bubblesort) can be much faster.
> 
> Indeed. You could do partial insertion sort and only run quicksort if
> it didn't end up sorted.
> 
>>> 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.
>> 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.
> 
> 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 
> 
> 

On 8 Jun, 08:35, David Brown <d...@westcontrol.removethisbit.com>
wrote:
> google.co...@op59.net wrote:

> > This is not the case - it is perfectly possible to get true backwards
> > stepping without
> > hardware support, asUndoDBdemonstrates.
>
> 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).

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.

>
> 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.

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.

>
> 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.

- Julian [one of the developers of UndoDB]

--
http://undo-software.com/

google.co.uk@op59.net wrote:
> On 8 Jun, 08:35, David Brown <d...@westcontrol.removethisbit.com>
> wrote:
>> google.co...@op59.net wrote:
> 
>>> This is not the case - it is perfectly possible to get true backwards
>>> stepping without
>>> hardware support, asUndoDBdemonstrates.
>> 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).
> 
> Just because it's not obvious how something works, doesn't mean it
> don't work :-)

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.

> 
> 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 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.

>> 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.
> 
> 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.

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):
http://lizard.sourceforge.net/explain.html

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


> 
>> 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.
> 
> - Julian [one of the developers of UndoDB]
> 
> --
> http://undo-software.com/
> 

"CBFalconer" <cbfalconer@yahoo.com> wrote in message news:4668B4F9.E4FC387F@yahoo.com...
> Wilco Dijkstra wrote:
>> "CBFalconer" <cbfalconer@yahoo.com> wrote:
>>> David Brown wrote:
>>>
> ... snip ...
>>
>>>> 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.
>>>
>>> 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.
>>
>> 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.
>
> Take a look at my implementation, as referenced before.  No data is
> moved, only pointers.

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 

Wilco Dijkstra wrote:
> "CBFalconer" <cbfalconer@yahoo.com> wrote:
>> Wilco Dijkstra wrote:
>>> "CBFalconer" <cbfalconer@yahoo.com> wrote:
>>>> David Brown wrote:
>>>>
>> ... snip ...
>>>
>>>>> 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.
>>>>
>>>> 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.
>>>
>>> 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.
>>
>> Take a look at my implementation, as referenced before.  No data is
>> moved, only pointers.
> 
> 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.

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.

-- 
 <http://www.cs.auckland.ac.nz/~pgut001/pubs/vista_cost.txt>
 <http://www.securityfocus.com/columnists/423>
 <http://www.aaxnet.com/editor/edit043.html>
 <http://kadaitcha.cx/vista/dogsbreakfast/index.html>
                        cbfalconer at maineline dot net



-- 
Posted via a free Usenet account from http://www.teranews.com

Wilco Dijkstra wrote:

> 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. 

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.

> 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.

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

> 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.

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.