NO

Author Topic: Speed Optimization: buggy or am I terribly missing something?  (Read 2210 times)

Offline Werner

  • Member
  • *
  • Posts: 20
Speed Optimization: buggy or am I terribly missing something?
« on: September 30, 2020, 02:31:30 PM »
The following code which implements a simple insertion sort,
yields, when built with Pelles C for Windows V10.00.6,
a) in debug mode:                                                correct results
b) in release mode without any optimization:        correct results
c) in release mode with any speed optimization: *INcorrect* results      
d) in release mode with any size optimization:     correct results

Code: [Select]
int main(void)
{
int a_arr[] = {5, 2, 1};

int i;
int j;
int n;
int temp;

n = sizeof(a_arr) / sizeof(a_arr[0]);

puts("Before sorting");
for (i = 0; i < n; ++i)
printf("%i   ", a_arr[i]);
putchar('\n');

/*
insertion sort
compare each element to the right (i) with all elements to the left (j)
*/
for (i = 1; i < n; ++i) // start outer loop with second array element to sort
for (j = 0; j < i; ++j) // inner loop always starts with the first of the already sorted array elements
{
if (a_arr[j] > a_arr[i]) // if already sorted element to the left is greater than the element to sort, ...
{
temp = a_arr[i]; // ... save element to sort, ...
memmove(&a_arr[j + 1], &a_arr[j], (i - j) * sizeof(int)); // ... shift all already sorted greater elements 1 postion to the right, ...
a_arr[j] = temp; // ... insert element to sort to the left of the shifted elements, and ...
break; // ... start over with next element to sort
}
}

puts("After sorting");
for (i = 0; i < n; ++i)
printf("%i   ", a_arr[i]);
putchar('\n');
}

Offline John Z

  • Member
  • *
  • Posts: 790
Re: Speed Optimization: buggy or am I terribly missing something?
« Reply #1 on: October 01, 2020, 03:11:48 PM »
You might try using volatile for a_arr[] variable and see if that fixes it.

John Z

Offline Werner

  • Member
  • *
  • Posts: 20
Re: Speed Optimization: buggy or am I terribly missing something?
« Reply #2 on: October 01, 2020, 05:18:15 PM »
Thanks a lot for your advice, John Z. I already tried this and it does work.

But to me, is seems to be a mere workaround. "volatile" is intended for different uses. I'd prefer a better working optimizer.

But then again, it doesn't count for much. The code serves only to demonstarte an algorithm. So I could just turn off optimizing at all. I only thought, my observations might be useful.

Offline John Z

  • Member
  • *
  • Posts: 790
Re: Speed Optimization: buggy or am I terribly missing something?
« Reply #3 on: October 02, 2020, 12:19:55 AM »
Hi Werner,

I could only suggest that because Pelle has identified some issues in the optimizer, based on other similar bug reports, and this has resolved (worked around) the problem for other users.   I believe Pelle is looking into the optimizer algorithms involved for possible improvements in future versions.

Welcome to the forum!

 Regards,
John Z

Offline frankie

  • Global Moderator
  • Member
  • *****
  • Posts: 2096
Re: Speed Optimization: buggy or am I terribly missing something?
« Reply #4 on: October 02, 2020, 09:34:27 AM »
The code serves only to demonstarte an algorithm. So I could just turn off optimizing at all. I only thought, my observations might be useful.
Thanks Werner.
We need as many as possible samples for a better debugging.
Welcome on the forum!
It is better to be hated for what you are than to be loved for what you are not. - Andre Gide

Offline Pelle

  • Administrator
  • Member
  • *****
  • Posts: 2266
    • http://www.smorgasbordet.com
Re: Speed Optimization: buggy or am I terribly missing something?
« Reply #5 on: October 04, 2020, 03:13:05 PM »
It's a bug (somewhere in the alias analyzer). It seems you can work around it, for now, by changing:
Code: [Select]
temp = a_arr[i];  // ... save element to sort, ...into:
Code: [Select]
volatile int temp = a_arr[i];  // ... save element to sort, ...
/Pelle

Offline Werner

  • Member
  • *
  • Posts: 20
Re: Speed Optimization: buggy or am I terribly missing something?
« Reply #6 on: October 05, 2020, 12:58:40 PM »
Thank you very much for your advice!

Offline TimoVJL

  • Global Moderator
  • Member
  • *****
  • Posts: 2091
Re: Speed Optimization: buggy or am I terribly missing something?
« Reply #7 on: October 06, 2020, 08:41:45 PM »
Optimizations are difficult.
I have a some  code, where also msvc fails, so none is perfect.
I can't publish my code, as it is private for a one company.
May the source be with you