Compiler: Problem of using qsort() on the ARM processer

Peter010

Other Parts Discussed in Thread: AWR1642, SYSBIOS

Tool/software: TI C/C++ Compiler

Hello everyone

I am using the ARM core on the AWR1642, the compiler version is v16.9.1.LTS. I want to sort an array structure as showing below, however, when I run the code, it gives the error. It seems like the qsort want to access to an invalid area. Can you tell me what is the wrong?

Thanks

Xining

#include <stdio.h>
#include <stdlib.h>
#include <time.h>


typedef struct {
    float price;
    float test;
    int id;
} order;
order list[10];
int i = 0;

int compare (const void * a, const void * b)
{

  order *orderA = (order *)a;
  order *orderB = (order *)b;

  return ( (orderA->price > orderB->price) ? 1:-1 );
}

int main ()
{
    srand((unsigned int)time(NULL));

    printf("Before sorting\n");
    for(i=0; i<10; i++){
        list[i].price = (float)rand()/(float)(RAND_MAX) * 10;
        list[i].test = rand()%10;
        list[i].id = i;
        printf ("Order id = %d Price = %f Test = %f\n",list[i].id, list[i].price, list[i].test);
    }
    printf("AFTER sorting\n");
    int n;
    qsort (list, 6, sizeof(order), compare);
    for (n=0; n<10; n++)
         printf ("Order id = %d Price = %f Test = %f\n",list[n].id, list[n].price, list[n].test);
    return 0;
}

The output is:

Before sorting
Order id = 0 Price = 6.347239 Test = 8.000000
Order id = 1 Price = 1.647694 Test = 3.000000
Order id = 2 Price = 5.049898 Test = 5.000000
Order id = 3 Price = 8.674276 Test = 4.000000
Order id = 4 Price = 4.470962 Test = 0.000000
Order id = 5 Price = 6.625263 Test = 6.000000
Order id = 6 Price = 3.482467 Test = 9.000000
Order id = 7 Price = 6.930449 Test = 9.000000
Order id = 8 Price = 5.341044 Test = 6.000000
Order id = 9 Price = 5.465560 Test = 2.000000
AFTER sorting
Exception occurred in ThreadType_Main.
Main handle: 0x0.
Main stack base: 0x8019a40.
Main stack size: 0x1000.
R0 = 0x08040000 R8 = 0x080199fc
R1 = 0x080199e4 R9 = 0x08040000
R2 = 0x0000000c R10 = 0x00008710
R3 = 0x00008710 R11 = 0x00000003
R4 = 0x00000005 R12 = 0x08040000
R5 = 0x00003330 SP(R13) = 0x0801a9e8
R6 = 0x0000000c LR(R14) = 0x000068c3
R7 = 0x00000006 PC(R15) = 0x00008738
PSR = 0x000c01df
DFSR = 0x0000000d IFSR = 0x00000000
DFAR = 0x08040000 IFAR = 0x00000000
ti.sysbios.family.arm.exc.Exception: line 205: E_dataAbort: pc = 0x00008738, lr = 0x000068c3.
xdc.runtime.Error.raise: terminating execution

over 8 years ago

0 Keith Barkley over 8 years ago

Guru 42335 points

Put a printf() (or a breakpoint!) inside compare to see if the crash happens before, during or after the compare - or indeed after several of them.

(Any reason to only sort 6 of them?)

0 Peter010 over 8 years ago in reply to Keith Barkley

Genius 4165 points

Thanks for your reply.

After adding code line <printf("\nCompare successful.");> inside compare function, the program runs without crashing. But the sorting result is wrong. The output is showing as below.

Keith Barkley said:
(Any reason to only sort 6 of them?)

In my application, I cannot decide how many items would be registered each time. So, in this time there are 6 items, next time would be 7 or 5. ( the number of items depends on the input). The program i pasted here is just an illustration, which is used to show the issue I encountered in my real application.

Before sorting
Order id = 0 Price = 8.997162 Test = 5.000000
Order id = 1 Price = 1.835383 Test = 7.000000
Order id = 2 Price = 6.288339 Test = 0.000000
Order id = 3 Price = 8.461562 Test = 0.000000
Order id = 4 Price = 9.874569 Test = 6.000000
Order id = 5 Price = 4.933012 Test = 9.000000
Order id = 6 Price = 3.842585 Test = 6.000000
Order id = 7 Price = 0.871914 Test = 2.000000
Order id = 8 Price = 1.196631 Test = 9.000000
Order id = 9 Price = 0.255745 Test = 2.000000
AFTER sorting

Compare successful.
Compare successful.
Compare successful.
.

Compare successful.
Compare successful.
Compare successful

Order id = 31725 Price = 0.000000 Test = 0.000000
Order id = 134328860 Price = 0.000000 Test = 0.000000
Order id = -1 Price = 0.000000 Test = 0.000000
Order id = -1 Price = 0.000000 Test = 0.000000
Order id = 134323356 Price = 0.000000 Test = 0.000000
Order id = 46 Price = 0.000000 Test = 0.000000
Order id = 46 Price = 0.000000 Test = nan
Order id = 0 Price = 0.000000 Test = 0.000000
Order id = 0 Price = 0.000000 Test = nan
Order id = 29463 Price = 0.000000 Test = 0.000000

0 Keith Barkley over 8 years ago in reply to Peter010

Guru 42335 points

This sounds like a stack issue. Can you increase the stack?

print sizeof(order) and see if it makes sense.

You can also print the addresses of each element, and make sure the pointers you get in the compare() are the right ones.

0 Peter010 over 8 years ago in reply to Keith Barkley

Genius 4165 points

I double the stack size (4K). It does not help.

In my previous test, there are 262 times comparison. However, there are only 6 elements to be sorted. Don't you think the number of comparison is too large for this size of array?

Xining Yu

0 Archaeologist over 8 years ago

TI__Guru* 84285 points

Your comparison function returns the wrong values. It must return 0 if two elements compare equal:

  return ( (orderA->price > orderB->price) ? 1 : 
           (orderA->price < orderB->price) ? -1 : 0);

0 Peter010 over 8 years ago in reply to Archaeologist

Genius 4165 points

First, your answer sloves my issue. Thanks for your help.

Second, as you can see that in my post, there are no element has same value. Why the program goes wrong?

Third, why the qsort() function runs well with my "return method" on other C programming software?

Thanks
Xining

0 Keith Barkley over 8 years ago in reply to Peter010

Guru 42335 points

Yes, it should be about nlog2(n). I googled it, I did not want to drag out Sedgewick. 8^). It looks to me like you are clobbering memory and the keys are changing every time which confuses quicksort. For example, if you have provided a wrong value for the size of the elements, which is why I said to check the value of sizeof(order).

The other scary thing is that you are clobbering way more than 6 elements. Who knows how much memory qsort() is messing up.

It really looks like a qsort() bug, though that is hard to believe. The only error in your code is that the compare function cannot return 0.

0 Peter010 over 8 years ago in reply to Keith Barkley

Genius 4165 points

Yes, you are right there is a bug as mentioned by TI employee. I check the size of element. It gives the correct value. In this case it is 12. After correcting this bug, the code works. I also raised other questions to TI employee as you can see.

Thanks for your help.
Xining

0 Archaeologist over 8 years ago in reply to Peter010

TI__Guru* 84285 points

Different toolchains implement qsort with slight differences. This is OK as long as the function gets the job done. In particular, it seems the TI implementation tries to compare elements to themselves. I don't want to look too closely at the failure mode, but the function seems to get confused and go into an infinite loop. I suspect that the values aren't actually corrupted, but that printf's ability to correctly show them is corrupted because we ran out of stack.

0 Keith Barkley over 8 years ago in reply to Peter010

Guru 42335 points

Yes, but you have the bug, not TI, as I pointed out.

0 Peter010 over 8 years ago in reply to Keith Barkley

Genius 4165 points

That is true.

0 Keith Barkley over 8 years ago in reply to Peter010

Guru 42335 points

Just to beat a dead horse, Sedgewick states that quicksort is not stable and fragile. I think you have found that an incorrect compare function can cause big problems. I actually spotted the error in the compare function when I first read the OP, but like you did not think that it would make the algorithm blow up.

Code Composer Studio™︎

Code Composer Studio forum

Compiler: Problem of using qsort() on the ARM processer