C/C++: Optimization of Pointers to String Constants

C/C++: Optimization of pointers to string constants

It's an extremely easy optimization, probably so much so that most compiler writers don't even consider it much of an optimization at all. Setting the optimization flag to the lowest level doesn't mean "Be completely naive," after all.

Compilers will vary in how aggressive they are at merging duplicate string literals. They might limit themselves to a single subroutine — put those four declarations in different functions instead of a single function, and you might see different results. Others might do an entire compilation unit. Others might rely on the linker to do further merging among multiple compilation units.

You can't rely on this behavior, unless your particular compiler's documentation says you can. The language itself makes no demands in this regard. I'd be wary about relying on it in my own code, even if portability weren't a concern, because behavior is liable to change even between different versions of a single vendor's compiler.

const char compiler optimization

This kind of optimization is called string interning.

GCC sets the -fmerge-constants flag by default:

Attempt to merge identical constants (string constants and floating-point constants) across compilation units.

This option is the default for optimized compilation if the assembler and linker support it. Use -fno-merge-constants to inhibit this behavior.

Enabled at levels -O, -O2, -O3, -Os.

Let's make an executable with a 3rd file named f.c to reference the strings:

#include <stdio.h>

// For proposition#1
extern const char foo1[], foo2[];

// For proposition#2
//extern const char *foo1, *foo2;

int main(void) {

  printf("%s\n", foo1);
  printf("%s\n", foo2);

  return 0;
}

When you define the following respectively in f1.c and f2.c (proposition#1):

const char foo1[] = "SAME_VALUE";

const char foo2[] = "SAME_VALUE";

This results in 2 different memory spaces into which the string "SAME_VALUE" is stored. So, the string is duplicated:

$ gcc f.c f1.c f2.c
$ objdump -D a.out
[...]
0000000000001060 <main>:
    1060:   f3 0f 1e fa             endbr64 
    1064:   48 83 ec 08             sub    $0x8,%rsp
    1068:   48 8d 3d 99 0f 00 00    lea    0xf99(%rip),%rdi <-- foo1@2008
    106f:   e8 dc ff ff ff          callq  1050 <puts@plt>
    1074:   48 8d 3d 9d 0f 00 00    lea    0xf9d(%rip),%rdi <-- foo2@2018
    107b:   e8 d0 ff ff ff          callq  1050 <puts@plt>
[...]
0000000000002008 <foo1>:
    2008:   53        'S'  <-- 1 string @ 2008
    2009:   41        'A'
    200a:   4d        'M' 
    200b:   45 5f     'E' '_'
    200d:   56        'V'
    200e:   41        'A'
    200f:   4c 55     'L' 'U'
    2011:   45        'E'
    ...

0000000000002018 <foo2>:
    2018:   53        'S'  <-- Another string @ 2018
    2019:   41        'A' 
    201a:   4d        'M' 
    201b:   45 5f     'E' '_'
    201d:   56        'V'
    201e:   41        'A'
    201f:   4c 55     'L' 'U' 
    2021:   45        'E'

But if you define the following respectively in f1.c and f2.c (proposition#2):

const char *foo1 = "SAME_VALUE";

const char *foo2 = "SAME_VALUE";

You define two pointers which will point on the same string. In this case, "SAME_VALUE" will likely not be duplicated. In the following raw disassembly, the string is at address 2004 and both foo1 and foo2 point to it:

$ gcc f.c f1.c f2.c
$ objdump -D a.out
[...]
    2004:   53        'S'    <-- 1 string @ 2004
    2005:   41        'A'
    2006:   4d        'M'
    2007:   45 5f     'E' '_'
    2009:   56        'V'
    200a:   41        'A'
    200b:   4c 55     'L' 'U'
    200d:   45        'E'
[...]
0000000000001060 <main>:
    1060:   f3 0f 1e fa             endbr64 
    1064:   48 83 ec 08             sub    $0x8,%rsp
    1068:   48 8b 3d a1 2f 00 00    mov    0x2fa1(%rip),%rdi <-- 106f+2fa1=foo1@4010 
    106f:   e8 dc ff ff ff          callq  1050 <puts@plt>
    1074:   48 8b 3d 9d 2f 00 00    mov    0x2f9d(%rip),%rdi <-- 107b+2f9d=foo2@4018 
[...]
0000000000004010 <foo1>:
    4010:   04 20         <-- foo1 = @2004
[...]
0000000000004018 <foo2>:
    4018:   04 20         <-- foo2 = @2004

To avoid the duplication with proposition#1, GCC provides -fmerge-all-constants:

Attempt to merge identical constants and identical variables.

This option implies -fmerge-constants. In addition to -fmerge-constants this considers e.g. even constant initialized arrays or initialized constant variables with integral or floating-point types. Languages like C or C++ require each variable, including multiple instances of the same variable in recursive calls, to have distinct locations, so using this option results in non-conforming behavior.

Let's rebuild proposition#1 with this flag. We can see that foo2 is optimized out, only foo1 is kept and referenced:

$ gcc -fmerge-all-constants f.c f1.c f2.c
$ objdump -D a.out
[...]
0000000000001149 <main>:
    1149:   f3 0f 1e fa             endbr64 
    114d:   55                      push   %rbp
    114e:   48 89 e5                mov    %rsp,%rbp
    1151:   48 8d 3d b0 0e 00 00    lea    0xeb0(%rip),%rdi <-- 1158(RIP) + eb0 = 2008 <foo1>
    1158:   e8 f3 fe ff ff          callq  1050 <puts@plt>
    115d:   48 8d 3d a4 0e 00 00    lea    0xea4(%rip),%rdi <-- 1164(RIP) + ea4 = 2008 <foo1>
    1164:   e8 e7 fe ff ff          callq  1050 <puts@plt>
    1169:   b8 00 00 00 00          mov    $0x0,%eax
[...]
0000000000002008 <foo1>:
    2008:   53    'S' <--- foo2 optimized out, only foo1 defined
    2009:   41    'A'
    200a:   4d    'M'
    200b:   45 5f 'E' '_'
    200d:   56    'V'
    200e:   41    'A'
    200f:   4c 55 'L' 'U'
    2011:   45    'E'

Addresses of two char pointers to different string literals are same

Whether two different string literals with same content is placed in the same memory location or different memory locations is implementation-dependent.

You should always treat p and p1 as two different pointers (even though they have the same content) as they may or may not point to the same address. You shouldn't rely on compiler optimizations.

C11 Standard, 6.4.5, String literals, semantics

It is unspecified whether these arrays are distinct provided their
elements have the appropriate values. If the program attempts to
modify such an array, the behavior is undefined.

---

The format for printing must be %p:

  printf("%p %p", (void*)p, (void*)p1);

See this answer for why.

C: make, pass and access const array of pointers to const strings

Doesn't directly answer your question, but why not try this:

typedef enum {
    RESET_CMD,
    CONFIG_CND
} cmd_id;

const char *commands[2] = {
    "\r\nReset",
    "\r\nConfig"
};

And than use it like this:

commands[RESET_CMD]

EDIT

I'll rewrite your clarification to match this method:

typedef enum {
    RESET_CMD,
    CONFIG_CND,
    START_CMD,
    END_CMD
} cmd_id;

const char *commands[4] = {
    "\r\nReset",
    "\r\nConfig",
    "\r\nStart",
    "\r\nEnd"
};

const cmd_id group0[1] = {
    RESET_CMD
};

const cmd_id group1[2] = {
    RESET_CMD,
    START_CMD
};

const cmd_id group2[3] = {
    RESET_CMD,
    START_CMD,
    END_CMD
};

void doStuffToCharacter(unsigned char the_char){
    // ....
}

void doStuffToGroup(const cmd_id group[], unsigned char num_cmds){
    for (unsigned char s=0; s < num_cmds; s++) {
        unsigned char idx = 0;
        while (commands[group[s]][idx]) {
            doStuffToCharacter(commands[group[s]][idx++]);
        }
    }
}

void main (void){
    doStuff(group0, 1);
    doStuff(group1, 2);
    doStuff(group2, 3);
}

C optimisation of string literals

It's called "string pooling". It's optional in Microsoft Compilers, but not in GCC. If you switch off string pooling in MSVC, then the "same" strings in the different arrays would be duplicated, and have different memory addresses, and so would take up an extra (unnecessary) 50 or so bytes of your static data.

EDIT: gcc prior to v 4.0 had an option, -fwritable-strings which disabled string pooling. The effect of this option was twofold: It allowed string literals to be overwritten, and disabled string pooling. So, in your code, setting this flag would allow the somewhat dangerous code

/* Overwrite the first string in a, so that it reads 'xne'.  Does not */ 
/* affect the instances of the string "one" in b or d */
*a[0] = 'x';

Where are string constants stored by GCC and from where these pointers are mapped?

In both cases the compiler emits the actual bytes of the string "hello" just once, in the .rodata section of the program (rodata stands for read only data).

They are actually mapped directly from the executable file into memory, somewhat similar to the code section. That's why they are far apart from the dynamically allocated ones.

Then:

char *p = "hello";

Simply initializes p to the address of this (read-only) data.
And obviously:

char *q = "hello";

Gets the very same address. This is called string pooling and is an optional popular optimization of the compiler.

But when you write:

char p[] = "hello";

It will probably generate something like this:

char p[6];
memcpy(p, "hello", 6);

Being the "hello" actually the address of the read-only pooled string.

The call to memcpy is for illustration purposes only. It may very well to the copy inline, instead than with a function call.

If later you do:

char q[] = "hello";

It will define another array and another memcpy(). So same data, but different addresses.

But where these array variables will reside? Well, that depends.

• If they are local, non static, variables: in the stack.
• If they are global variables: then they will be in the .data section of the executable, and they will be saved there with the correct characters already in there, so no memcpy is needed in run time. Which is nice, because that memcpy would have to be executed before main.
• If they are local static variables: exactly the same than with global variables. They both together are called variables of static duration or something like that.

About the documentation links, sorry, I don't know of any.

But who needs documentation if you can do the experiments yourself? For that the best tool around is objdump, it can disassemble the program, dump the data sections and much more!

I hope this answer your questions...

Is declaring a string literal with a pointer more memory efficient than declaring constant array?

In the first case the data for the string is stored in the executable file, and it's stored in memory once the program is loaded. So yes it is "allocated twice" but in very different storage mediums (disk and memory).

However, the same is true for the second case as well. The string literal needs to be stored once in the executable file on disk, and once in memory when the program is running.

The difference is an implementation detail, namely that in the first case the string in memory is stored either on the stack or in some global modifiable data memory segment. In the second case the string is usually stored together with the code.

So if you only have one instance of the string in the first case, there is no difference in "memory efficiency".

What kind of optimization does const offer in C/C++?

^Source

Case 1:

When you declare a const in your program,

int const x = 2;

Compiler can optimize away this const by not providing storage for this variable; instead it can be added to the symbol table. So a subsequent read just needs indirection into the symbol table rather than instructions to fetch value from memory.

Note: If you do something like:

const int x = 1;
const int* y = &x;

Then this would force compiler to allocate space for x. So, that degree of optimization is not possible for this case.

In terms of function parameters const means that parameter is not modified in the function. As far as I know, there's no substantial performance gain for using const; rather it's a means to ensure correctness.

---

Case 2:

"Does declaring the parameter and/or the return value as const help the compiler to generate more optimal code?"

const Y& f( const X& x )
{
    // ... do something with x and find a Y object ...
    return someY;
}

What could the compiler do better? Could it avoid a copy of the parameter or the return value?

No, as argument is already passed by reference.

Could it put a copy of x or someY into read-only memory?

No, as both x and someY live outside its scope and come from and/or are given to the outside world. Even if someY is dynamically allocated on the fly within f() itself, it and its ownership are given up to the caller.

What about possible optimizations of code that appears inside the body of f()? Because of the const, could the compiler somehow improve the code it generates for the body of f()?

Even when you call a const member function, the compiler can't assume that the bits of object x or object someY won't be changed. Further, there are additional problems (unless the compiler performs global optimization): The compiler also may not know for sure that no other code might have a non-const reference that aliases the same object as x and/or someY, and whether any such non-const references to the same object might get used incidentally during the execution of f(); and the compiler may not even know whether the real objects, to which x and someY are merely references, were actually declared const in the first place.

---

Case 3:

void f( const Z z )
{
    // ...
}

Will there be any optimization in this?

Yes because the compiler knows that z truly is a const object, it could perform some useful optimizations even without global analysis. For example, if the body of f() contains a call like g( &z ), the compiler can be sure that the non-mutable parts of z do not change during the call to g().

Comparing two char* and two char[ ] strings in C

In the first case, as you defined two arrays, the compiler allocated two separate storage for them, so a and b are not equal.

But, for the second case, as you initialized two pointers with the same string literal, the compiler found them the same string, and point the two pointers into the same address which is the start address of that string literal ("bar").
However, as @David said, this is not happened necessarily, and in some situation, removing some optimization, or based on some compiler, x and y might not be the same.

---

Related Topics