NO

Author Topic: Constant pointers effects on optimization  (Read 5125 times)

Offline PaoloC13

  • Member
  • *
  • Posts: 44
Constant pointers effects on optimization
« on: April 10, 2016, 08:06:58 PM »
Hello, I've a simple question: The declaration of a pointer specified as constant, in a form such as this:

Code: [Select]
const char * Find(const char *restrict psrc, const char *const cpsReplace, /*...*/)
{
...
const char *psReplace = cpsReplace; // Take a readable copy of cpsReplace.
...
while (*psReplace != '\0')
*psNew++ = *psReplace++; // Copy the replacement.

psReplace = cpsReplace; // Reset the psReplace pointer.
...
return psNew;
}

will help the compiler to generate optimized code, or it is only for a safer development?

Thanks...

Offline PaoloC13

  • Member
  • *
  • Posts: 44
Re: Constant pointers effects on optimization
« Reply #1 on: April 11, 2016, 01:06:44 AM »
Oh, I forgot: the pointer in question is one that is declared as  const char *const cpsReplace  in the parameter list.

Offline frankie

  • Global Moderator
  • Member
  • *****
  • Posts: 2096
Re: Constant pointers effects on optimization
« Reply #2 on: April 11, 2016, 11:34:22 AM »
Hello,
declaring  that a pointer is constant, and that that even the object pointed to is constant, just instructs the compiler that not the pointer, nor the object can be changed by the generated code.
Maybe you can get some optimizations from values supposed to not change during their scope, but this is not the main aim of the const qualifier.
As a case of study consider that the const qualifier specify that the value will not be changed in the actual code context, but doesn't imply that it can be done from outside. I.e. a declaration as:
Code: [Select]
volatile const char * volatile const pep = NULL;
Is perfectly legal. The compiler will not allow you any assignment to the poinnter, nor to the pointed object (try), but will know that those values can be changed outside of code flow context.

What has been really developed to enahnce the optimization is the keyword restrict. It was introduced in C99 and instructs the compiler that a pointer will never be aliased during its whole scope:
Quote
It says that for the lifetime of the pointer, only the pointer itself or a value directly derived from it (such as pointer + 1) will be used to access the object to which it points
(wikiipedia)
« Last Edit: April 11, 2016, 01:28:09 PM by frankie »
It is better to be hated for what you are than to be loved for what you are not. - Andre Gide

Offline PaoloC13

  • Member
  • *
  • Posts: 44
Re: Constant pointers effects on optimization
« Reply #3 on: April 11, 2016, 11:29:05 PM »
Hello, thanks for the answer.
With regard to restricted pointers, a few days ago I've got a headache trying to figure out how to use the restrict qualifier without causing drawbacks in my program. Apparently, the issue can't be summed up in a few simple rules, at least for me.

Unfortunately I only found a few guides on the restric pointers matter, and they seemed to me a bit dark, not quite grasped.

Offline frankie

  • Global Moderator
  • Member
  • *****
  • Posts: 2096
Re: Constant pointers effects on optimization
« Reply #4 on: April 12, 2016, 06:02:50 PM »
The restrict qualifier indicates that objects that can be reached by a pointer will be accessed only with that pointer, not any other.
This allow the compiler to assume that not only pointers value, but even objects accessed by it can be reused, or optimized, in other part of code.
Consider:
Code: [Select]
void foo(int n, int * restrict p, int * restrict q)
{
    while(n-- > 0)
        p[n] = q[n];         // apparently what is modified by p is not modified by q so it's ok.
        p[n*2] = q[n];     // The compiler can reuse object accessed by q[n];
}

Now see these 2 calls:
Code: [Select]
    ....
    int array[100];
    foo(10, array+20, array);    //This is OK because even 2*n=2*10=20 will not address the same objects
    foo(10, array+10, array);    //This is NOT_OK because even 2*n=2*10=20 will address the same objects
As you can see from code above the assumption made by compiler will fail in the second case and the result will be UB (undefined behavior).
See this for a wide description, and this for pointer aliasing.
It is better to be hated for what you are than to be loved for what you are not. - Andre Gide

Offline PaoloC13

  • Member
  • *
  • Posts: 44
Re: Constant pointers effects on optimization
« Reply #5 on: April 13, 2016, 05:54:26 AM »

Thanks frankie,
Ok, now I start to get my ideas in more order, and my notes too.
if I understood correctly, a restrict "contract" is valid to these conditions:

Only for the lifetime of the restricted pointer, that is: during the execution of the block in which the pointer is declared.

Only if the chunk of memory accessible through the restricted pointer (directly or indirectly) has changed. Then, all access to that chunk of memory (read and write) must occur exclusively through the restricted pointer.

...and a first gold rule:
Working on pointers indirectly, the address accessible from a restricted pointer must not overlap the address accessible from another pointer.


Now, I would like to submit a code example.

Code: [Select]
const char * F(const char * pcStr)
{
...

char *restrict rps = (char*)g_psBuffer; // Take a copy of gpsNew for writing.

while (n--)
*rps++ = *pcStr++;
...

return g_psBuffer;
}

I declare a restrict pointer as a copy of a poiter that is never used after the restrict declaration, except for the use as return value. May be legal? ...or needs to create a nested block?

Offline frankie

  • Global Moderator
  • Member
  • *****
  • Posts: 2096
Re: Constant pointers effects on optimization
« Reply #6 on: April 13, 2016, 04:50:40 PM »
It should be legal, even if not strictly compliant.
What really matters is that the two pointers are not used together to access same objects.
It is better to be hated for what you are than to be loved for what you are not. - Andre Gide

Offline PaoloC13

  • Member
  • *
  • Posts: 44
Re: Constant pointers effects on optimization
« Reply #7 on: April 15, 2016, 12:38:15 PM »
anyway, it seems the declaration has no effect (at least in this case) on the executable code.
I compiled the following:

Code: [Select]
#include <stdio.h>

static const char sBuffer[512];

const char * Copy(const char * pcStr)
{
char *restrict rps = (char*)sBuffer; // Take a copy of sBuffer for writing.

while (*pcStr)
*rps++ = *pcStr++;

*rps++ = '\0';

return sBuffer;
}

int main(int argc, char *argv[])
{
const char * ps = Copy("This is a string!\n");
printf(ps);

    return 0;
}

Then I re-built the same code by declaring the pointer without the restrict qualifier.
By disassembling the two generated executables, is that they are identical.

Offline frankie

  • Global Moderator
  • Member
  • *****
  • Posts: 2096
Re: Constant pointers effects on optimization
« Reply #8 on: April 15, 2016, 12:46:31 PM »
To be honest on that code I don't see any optimization that can be made. It is a simple copy.
It is better to be hated for what you are than to be loved for what you are not. - Andre Gide

Offline PaoloC13

  • Member
  • *
  • Posts: 44
Re: Constant pointers effects on optimization
« Reply #9 on: April 18, 2016, 10:57:23 PM »
I don't know how to evaluate whether a code is optimizable by the compiler, but I tested another version (should be a version of the strcpy function):

Code: [Select]
#include <stdio.h>

const char * Copy(const char *restrict pRet, const char *restric pSrc)
{
char *pr = (char*)pRet;

while (*pr++ = *pSrc++)
*pr = '\0';

return pRet;
}

int main(int argc, char *argv[])
{
static char sBuffer[64];
Copy(sBuffer, "This is a string!\n");
printf(sBuffer);

    return 0;
}

...and here came a small optimization:

push rax
add [r8], r8b
xchg fs:[rax+rax], al
xchg [rax+0x5712], ecx

instead of (without restrict):

push rax
add [r8], r8b
xchg fs:[rax+rax], al
db 0xc5
mov [rdx], dl
push rdi
« Last Edit: April 18, 2016, 11:03:14 PM by PaoloC13 »

Offline TimoVJL

  • Global Moderator
  • Member
  • *****
  • Posts: 2091
Re: Constant pointers effects on optimization
« Reply #10 on: April 19, 2016, 08:56:34 AM »
No difference:
Code: [Select]
Copy
40001020h - 4000103Eh = 1Fh
[40001020] mov rax,rcx
[40001023] mov rcx,rax
[40001026] jmp 000000014000102B
[40001028] mov byte ptr [rcx],0
[4000102B] mov r8b,byte ptr [rdx]
[4000102E] mov byte ptr [rcx],r8b
[40001031] add rdx,1
[40001035] add rcx,1
[40001039] test r8b,r8b
[4000103C] jne 0000000140001028
[4000103E] ret

CopyR
40001000h - 4000101Eh = 1Fh
[40001000] mov rax,rcx
[40001003] mov rcx,rax
[40001006] jmp 000000014000100B
[40001008] mov byte ptr [rcx],0
[4000100B] mov r8b,byte ptr [rdx]
[4000100E] mov byte ptr [rcx],r8b
[40001011] add rdx,1
[40001015] add rcx,1
[40001019] test r8b,r8b
[4000101C] jne 0000000140001008
[4000101E] ret
This Add-In was used.
« Last Edit: April 19, 2016, 08:59:56 AM by TimoVJL »
May the source be with you

Offline frankie

  • Global Moderator
  • Member
  • *****
  • Posts: 2096
Re: Constant pointers effects on optimization
« Reply #11 on: April 19, 2016, 09:24:48 AM »
Paolo Where you got that code? It is evidently not coming from your copy function.
As Timo showed the code has no difference because the use of pointers is linear.
Maybe your source  is not exactly what you intended. Could you try this:
Code: [Select]
const char * Copy(const char *restrict pRet, const char *restric pSrc)
{
    char *pr = (char*)pRet;
    while (*pr++ = *pSrc++)
        ;          //this limit the while loop to assign (copy) chars up to the ending '\0'
    *pr = '\0';    //Now you terminate destination string only one time
    return pRet;
}
Look the difference now. I think that the assembly now is closer to what you expected, but there is still no matter for stronger optimizations.
« Last Edit: April 19, 2016, 09:27:20 AM by frankie »
It is better to be hated for what you are than to be loved for what you are not. - Andre Gide

Offline PaoloC13

  • Member
  • *
  • Posts: 44
Re: Constant pointers effects on optimization
« Reply #12 on: April 19, 2016, 06:18:47 PM »
Evidently, the assembly is from a portion of code that has nothing to do with the function, since the difference is located at [00000080].

Yes, what I intended to do is exacly:     while (*pr++ = *pSrc++);
It was a mistake due to distraction.
However, now (with the fix) I do not find differences in the generated executables.
« Last Edit: April 20, 2016, 12:41:12 AM by PaoloC13 »