How to waste a lot of space without knowing
const char *foo = "foo";
This was recently mentioned on bugzilla, and the problem is usually underestimated, so I thought I would give some details about what is wrong with the code above.
The first common mistake here is to believe foo is a constant. It is a pointer to a constant. In practical ELF terms, this means the pointer lives in the .data section, and the string constant in .rodata. The following code defines a constant pointer to a constant:
const char * const foo = "foo";
The above code will put both the pointer and the string constant in .rodata. But keeping a constant pointer to a constant string is pointless. In the above examples, the string itself is 4 bytes (3 characters and a zero termination). On 32-bits architectures, a pointer is 4 bytes, so storing the pointer and the string takes 8 bytes. A 100% overhead. On 64-bits architectures, a pointer is 8 bytes, putting the total weight at 12 bytes, a 200% overhead.
The overhead is always the same size, though, so the longer the string, the smaller the overhead, relatively to the string size.
But there is another, not well known, hidden overhead: relocations. When loading a library in memory, its base address varies depending on how many other libraries were loaded beforehand, or depending on the use of address space layout randomization (ASLR). This also applies to programs built as position independent executables (PIE). For pointers embedded in the library or program image to point to the appropriate place, they need to be adjusted to the base address where the program or library is loaded. This process is called relocation.
The relocation process requires information which is stored in .rel.* or .rela.* ELF sections. Each pointer needs one relocation. The relocation overhead varies depending on the relocation type and the architecture. REL relocations use 2 words, and RELA relocations use 3 words, where a word is 4 bytes on 32-bits architectures and 8 bytes on 64-bits architectures.
On x86 and ARM, to mention the most popular 32-bits architectures nowadays, REL relocations are used, which makes a relocation weigh 8 bytes. This puts the pointer overhead for our example string to 12 bytes, or 300% of the string size.
On x86-64, RELA relocations are used, making a relocation weigh 24 bytes! This puts the pointer overhead for our example string to 32 bytes, or 800% of the string size!
Another hidden cost of using a pointer to a constant is that every time it is used in the code, there will be pointer dereference. A function as simple as
int bar() { return foo; }
weighs one instruction more when foo is defined const char *. On x86, that instruction weighs 2 bytes. On x86-64, 3 bytes. On ARM, 4 bytes (or 2 in Thumb). That weight can vary depending on the additional instructions required, but you get the idea: using a pointer to a constant also adds overhead to the code, both in time and space. Also, if the string is defined as a constant instead of being used as a literal in the code, chances are it's used several times, multiplying the number of such instructions. Update: Note that in the case of const char * const, the compiler will optimize these instruction and avoid reading the pointer, since it's never going to change.
The symbol for foo is also exported, making it available from other libraries or programs, which might not be required, but also adds its own overhead: an entry in the symbols table (5 words), an entry in the string table for the symbol name (strlen("foo") + 1) and an entry in the symbols hash chain table (4 bytes if only one type of hash table (sysv or GNU) is present, 8 if both are present), and possibly an entry in the symbols hash bucket table, depending on the other exported symbols (4 or 8 bytes, as chain table). It can also affect the size of the bloom filter table in the GNU symbol hash table.
So here we are, with a seemingly tiny 3 character string possibly taking 64 bytes or more! Now imagine what happens when you have an array of such tiny strings. This also doesn't only apply to strings, it applies to any kind of global pointer to constants.
In conclusion, using a definition like
const char *foo = "foo";
is almost never what you want. Instead, you want to use one of the following forms:
- For a string meant to be exported:
const char foo[] = "foo"; - For a string meant to be used in the same source file:
static const char foo[] = "foo"; - For a string meant to be used across several source files for the same library:
__attribute__((visibility("hidden"))) const char foo[] = "foo";
2012-02-18 09:17:21+0900
You can leave a response, or trackback from your own site.
2012-02-18 13:38:50+0900
Thanks for the writeup. I`m always interested in the inner workings of my OS ;-)
Do you have any estimates as to how present such problems are in the mozilla codebase?
How does this relate to GkAtoms which are used in place of literal strings?
2012-02-19 00:34:43+0900
Would be cool to have a tool to scan for pointless binary bloat like this. Shouldn’t be too hard.
2012-02-19 11:25:40+0900
Shoudn’t the compiler take care of this for us?
2012-02-19 16:44:03+0900
Fortunately, most compilers are clever enough (GCC surely is) to notice that your “static const char *foo” is never modified (it would require exporting &foo to the outside to do so, or a direct modification within the same compilation unit) and will treat it as a “static const char * const foo”.
2012-02-20 16:41:03+0900
I was taught (maybe incorrectly) that using:
(const char *foo = “foo”;) and (const char foo[] = “foo”;)
are the same thing. Obviously functionally they are equivalent, but how does declaring the string as an array save on the execution time and size? Can you provide some detail?
2012-02-21 04:01:54+0900
Great post! a few questions/comments.
What about literal strings declared in function scope?
void x() {
const char *foo = “foo”;
…
}
The compiler should have all the information it needs to do the right job there, right? I mean, the pointer itself is at worst a stack variable, and the literal is by definition not visible at all to anything outside the scope of this function. So can you confirm that const char* is good enough for literals declared in function scope?
Also, when you say that const char * const allows the compiler to optimize, are you referring specifically to the case of global variables on most modern OSes where there are read-only segments and attempting to write there would just crash? I ask because, for a const variable in function scope, the constness doesn’t tell the compiler much: one could const_cast a pointer to that variable, etc. So for local variables, I expect that there is little or no correlation at all between constness, and the ability for the compiler to optimize using the fact that it’s not changing.
2012-02-22 19:53:37+0900
Jim, they are not functionally equivalent. The former lets you do |foo = “bar”;| to change where the pointer is pointing, and the compiler has to allow for that. That’s especially so if the pointer is not marked static, because then the compiler can’t even look at the source file to see whether that is in fact the case.
2012-02-23 11:39:06+0900
Benoit, defining const char *foo in function scope is like defining static const char *foo at global scope. The compiler knows it can probably eliminate the pointer if it’s never changed, and optimize that away.
About const char * const, the language guarantees that the pointer is never going to change, independently of the actual data being read-only at runtime on modern OSes, so the compiler has a nice optimization opportunity if the symbol is not exported. Sure, you can shoot yourself in the foot by const_casting and changing the pointer (which will effectively crash at runtime), but then the compiler knows you are modifying the pointer and won’t optimize it away. Note this doesn’t need to be a const char * const local variable. There are other cases where the compiler won’t optimize the pointer away, but in general cases, it will.
2012-02-24 19:12:15+0900
I tried to change a single appearance of “const char *a=…” to “const char a[]=…” as you suggested, but the resulting file.o was larger. This contradicts your claim that the latter form is universally superior.
2012-02-24 23:01:26+0900
âš›: don’t look at the object file size. Loot at final, linked, stripped, binary size.
2012-03-07 12:52:37+0900
One precisation: what you write is correct for C, but not for C++.
const X y = z; at global scope is interpreted by C as:
extern const X y = z;
but by C++ as:
static const X y = z;
This has also the interesting consequence that a global const in an .h file (not explicitly marked extern) in C++ occupies space in all the translation units including it (and the linker is often not allowed to merge the occurrences).
2012-03-07 16:42:14+0900
The article talks all about |const char*| vs |const char* const|, but then at the end the recommendation is for |const char[]|, which wasn’t mentioned previously. Are you saying that |const char* const| is equivalent to |const char[]| and that either is recommended?
2016-05-08 17:56:51+0900
Thanks very much for the post! I am learning a lot today. I came here because I have a large table of short string to load into memory and my program is taking way (10 times) more memory than I thought. Here is a simple snippet to demonstrate it.
int i;
char **buffer = new char*[1000000];
for (i=0;i<1000000;i++) {
buffer[i] = (char *)malloc(1);
buffer[i][0] = '\0';
}
I use VS2008 to compile this, and it seems that these 1 byte char strings will take 64 bytes each on x64 and 48 bytes on Win32. I still cannot explain all the memory use.
2018-08-17 07:17:17+0900
Actually, it is the brand that everyone needs just for the calming the process to check whether it been able to load into the memory for the program, which is going to have it.
2018-09-08 20:38:43+0900
Very nice information is shared about coding. Usually, the coder doesn’t know and he wastes a lot of space. so it is very helpful