Possible "hesitation" bug revealed using strcmp()

LeafLabs Garden » Support » Maple IDE Support

Possible "hesitation" bug revealed using strcmp()

(46 posts) (7 voices)

Started 5 years ago by StephenFromNYC
Latest reply from gbulmer

« Previous 1 234 Next »

gbulmer
Moderator

mbolivar -

I sincerely hope no offense was taken at my comment above about the understandability of the qsort type signature

No offence taken, and thank you for your consideration.
I agree that it's helpful practice to avoid assuming knowledge (ASS of U and ME?-), and I wish I was better at that.

I actually agree with you that the qsort comparison function signature does look daunting. That's partly why I dug around for a self-contained sort function; much easier to convince myself it was okay :-)

Posted 5 years ago #
mbolivar
LeafLabs

so as i'm sure you've seen, newlib qsort switches to insertion sort at the leaves (n < 7) and (i think) when the the array appears to be almost sorted (as determined by swap_cnt); however, in reading about shell sort, it seems that it's equivalent to insertion at small inputs, so no difference there.

there is a hand-coded TCO on lines 213-221, which i'll include inline since it's short:

if ((r = pb - pa) > es)
qsort(a, r / es, es, cmp);
if ((r = pd - pc) > es) {
/* Iterate rather than recurse to save stack space */
a = pn - r;
n = r / es;
goto loop;
}

so the second recursive call (which is of course in tail position) is manually optimized, as you suspected.

Posted 5 years ago #
mbolivar
LeafLabs
[a previous post deleted as it was a copy of yours]

gbulmer:

I had a look, and it does the TCO by hand:

if ((r = pd - pc) > es) {
/* Iterate rather than recurse to save stack space */
a = pn - r;
n = r / es;
goto loop;
}

I'm looking at it too; it's a cool implementation.

As I'm sure you've seen, it switches to insertion sort at the leaves (n < 7) and when the array appears to be almost sorted (swap_cnt == 0).

From what I've just read about shell sort, it is equivalent to insertion sort when the array is small, so there's no difference at the leaves. And of course insertion sort performs well on almost-sorted data, so the motivation for its use there is clear, but I found it curious that they wouldn't use shell sort in that case, given that the array could still potentially be large and that shell sort is considered better (unless there is some property I'm missing).

Here's some speculation as to why insertion might have been chosen, though:

The Wikipedia shell sort has this to say about implementation:
http://en.wikipedia.org/wiki/Shell_sort#Shell_sort_algorithm_in_pseudocode
```
inc <- round(n/2)
while inc > 0 do:
    for i = inc .. n − 1 do:
        temp <- a[i]
        j <- i
        while j >= inc and a[j − inc] > temp do:
            a[j] <- a[j − inc]
            j <- j − inc
        a[j] <- temp
    inc <- round(inc / 2.2)
```
The last line in particular is a definite deal-breaker on embedded hardware.
Posted 5 years ago #
mbolivar
LeafLabs

oh, and just a clarification on what i meant when i said

GCC does attempt to do tail call elimination, but that won't help here, since quicksort is not tail-recursive -- the presence of two recursive calls (on the left and right subarrays after the partition step) dooms us to needing the stack.

by "won't help", i meant that the stack size is asymptotically still logarithmic in the input length, since the first recursive call can't be eliminated. optimizing out the recursive call which _is_ in tail position will of course pare down the constant factors.

Posted 5 years ago #
mbolivar
LeafLabs

gbulmer: one last thing.

I think you'll find Shell sort is slightly better than insertion sort http://en.wikipedia.org/wiki/Shell_sort under most conditions. In experiments we did (in the 80's) on sorting 3D polygons within a rendering engine, it often beat quicksort. (I've tended to use it, and always been pleased with its performance. It seemed overkill for this problem.)

This is fascinating. If you have an implementation you'd like included in libmaple, I'm sure we'd be grateful.

Posted 5 years ago #
gbulmer
Moderator

If you have an implementation you'd like included in libmaple, I'm sure we'd be grateful.

That was several jobs ago ...
The battery backed "non-volatile" memory on my old IBM AT clone, gave up years ago, losing all the hard disk parameters, and rendering it useless :-(
The 5 1/4" floppy 'backups" are just as useless (that was my only machine with a 5 1/4" disk drive).

But, I think I might have the book that I copied from, somewhere :-)
(I remember it had a dark-ish green cover)

Paper, the only information back-up civilisation needs ;-)

Posted 5 years ago #
gbulmer
Moderator

oh, and just a clarification on what i meant when i said

GCC does attempt to do tail call elimination, but that won't help here, since quicksort is not tail-recursive -- the presence of two recursive calls (on the left and right subarrays after the partition step) dooms us to needing the stack.

by "won't help", i meant that the stack size is asymptotically still logarithmic in the input length, since the first recursive call can't be eliminated. optimizing out the recursive call which _is_ in tail position will of course pare down the constant factors.

Agreed; in the worst case, flattening the tail call to an iterative solution makes no difference to the stack size.

I am on thin ice here but, my vague recollection was that quicksort could choose which partition to recurse on, and which to iterate on. In many cases, the partitions are uneven, so recursing on the smaller partition, is a good strategy to reduce stack space requirements.

Posted 5 years ago #
snigelen
Member

Interesting discussion you have. Just a small comment on this

inc <- round(inc / 2.2)

The last line in particular is a definite deal-breaker on embedded hardware.

With integer arithmetic you can do the same thing as (I think)
inc <- (10*inc+5)/22

Posted 5 years ago #
poslathian
LeafLabs

In no particular order, here are some quick comments to the topics covered on this thread:

1) Auto-reset on terminal open:
One thought for reset control is to directly use DTR/RTS to control the reset, so that opening a terminal program will engage the autoreset. I think this is clearly the wrong thing. Surely you want to decouple opening a terminal window from program flow unless you program this in explicitly (via getDTR(), getRTS()). So, currently, the auto-reset works via pulling down DTR and then sending along some magic numbers (0x1EAF).

2) SerialUSB voodoo:
Ugh, such voodoo. I dont want to get anyones hopes of of full fixes in 0.0.7, its a very hard problem (but have cleaned up a lot of related bugs in 0.0.7). However, we had the pleasure of talking it over a lot recently - and with a lot of users and developers of other products at maker faire - and have finally settled on a long term fix. Its a hardware fix, and a feature add, and were psyched. In the meantime if SerialUSB is really killing you, (and I hate to do this) please use the UART's with an FTDI for now - but with confidence that this problem will not plague this platform forever ;)

3) The RAM/Flash contention. This IS a bootloader issue, the best we can do is a push changes into the bootloader git and if users want to use the serial-bootloader to upgrade then go for it! The issue is a throwback from before a permanent-bootloader mode didnt exist. What would happen is that botched code would get into flash, and everytime you restarted it would jump to bad flash code and crash. Meanwhile, bad ram code can be cleared with a power cycle, so everything was designed to heavily favor ram whenever there was a contention. Of course, with permanent bootloader this problem goes away, so we can do the "right thing" now.

I have nothing to say about sorting algs ;) (although incidentally, I wrote a really bad merge sort the other day for my THX note synth)

Posted 5 years ago #
gbulmer
Moderator

1) Auto-reset on terminal open:
One thought for reset control is to directly use DTR/RTS to control the reset, so that opening a terminal program will engage the autoreset. I think this is clearly the wrong thing.

I agree with you for general terminal program.
The issue was/is when reoppening the IDE's serial monitor on the Arduino, it auto-resets.
That is a very nice behaviour for new users, who can try their programs out very easily without losing any of their print output.
If that is implemented, I would like it to be an option that I can switch off.

Surely you want to decouple opening a terminal window from program flow unless you program this in explicitly (via getDTR(), getRTS()).

A completly agree. That's what I want, and I think is the most general purpose. One can press the rest button if one needs a Reset. I don't want opening a connection to the Maple to reset it. We had a horrible job to defeat that on older Arduino's when my chum Mark wrote a ICSP using the Arduino.

So, currently, the auto-reset works via pulling down DTR and then sending along some magic numbers (0x1EAF).

That sounds okay. I think I could (at a push) defeat that on a Mac, if I really needed to (using DTrace). BUt I assume it's an option with some of the terminal emulators.

Does puling down DTR stop the user program, or is it still running?
Is the reset only done when the magic number comes along too?
If the user program is a different kind of USB device, I assume none of this happens?

2) SerialUSB voodoo:
Ugh, such voodoo. I dont want to get anyones hopes of of full fixes in 0.0.7, its a very hard problem (but have cleaned up a lot of related bugs in 0.0.7). However, we had the pleasure of talking it over a lot recently - and with a lot of users and developers of other products at maker faire - and have finally settled on a long term fix. Its a hardware fix, and a feature add, and were psyched.

Is it more than using DTR for out-of-band signaling? What other issues am I missing?

So will this be practical for us to implement on existing boards?
When will the change get rolled into Maple boards?

Posted 5 years ago #
poslathian
LeafLabs

about auto-reset:
Hmm. We could add auto-reset on terminal open as selectable feature. I agree with you that it has its uses. Right now, *most* (and in the IDE this is enforced) terminals will only send data when DTR is high. Thus, by forcing DTR low and then sending data, you are doing something beyond the normal bounds of operation. We poll these bytes for 1EAF, if found we reset. This code is strictly part of the libmaple SerialUSB driver, so any nonstandard USB stack would not have this included. Since well behaving terminals should set DTR when writing, this magic number check is not really a performance hit nor easy to do by accident. DTR toggling does nothing by itself (no reset). getDTR(),getRTS() are already in libmaple!

SerialUSB fix:
Nope, not a DTR based fix. this is a hardware fix. Im leave it to everyone to guess what the change is going to be, but we arnt ready to announce hardware changes in Rev6 just yet. How will this affect current users? Not at all, the new hardware will be a separate board in the drop down menu. However, if you wish to use the new scheme, we *might* (if requested) offer very low cost adapter boards (0 profit) that will add the new hardware to old maples via the JTAG port, perhaps ugly - but it will make everything behave equivalently. The change should not affect the library at all, so all sketches etc remain unchanged. We have tried many many permutations of driving the USB to maintain correct operation across the various operating systems, and we think this is a low cost high value fix that makes neat new features possible to boot.

Posted 5 years ago #
perry
Administrator
here's what i do to make sure i din;t miss anything coming out of the serialusb:
```
setup() {
    while(!SerialUSB.available()
        ;
    SerialUSB.println("Hello!");
}
```
this will make the maple wait until a key is pressed in the serial monitor and then start spewing stuff out.
Posted 5 years ago #
poslathian
LeafLabs

I often do:

setup() {
pinMode(38,INPUT); // BUT button
while(!digitalRead(38));

// tap button to start (starts on DOWN)
}

Posted 5 years ago #
StephenFromNYC
Moderator

Hello,

I like both perry's software version and postlathian's hardware method. Both are useful, depending on the application (eg. physical access to the button).

Perry, I think you are missing a close parenthesis after "available()".

Is this the correct code?

setup() { while(!SerialUSB.available()) ; SerialUSB.println("Hello!"); }

Thanks!

Stephen from NYC

Posted 5 years ago #
poslathian
LeafLabs

yup you want that other paren ;)

Posted 5 years ago #

RSS feed for this topic

« Previous 1 234 Next »

Reply »

You must log in to post.