Why is the built-in es code from initial.es so big?

[jpco]

(Note: This is all using gcc on my 64-bit Linux laptop.)

If I compile es at HEAD (but with the treededup() call commented out, since it's a fine optimization but it messes with the math), using -Os, and then I strip it, the resulting binary is 245328 bytes in size. If I delete all of the definitions in initial.es and do the same thing, the es binary ends up at 130640 bytes. That comes out to a difference of 114688 bytes, or 112kiB, of binary image purely due to the contents of initial.es. Doesn't that seem way too large?

Looking deeper, there are two major parts to initial.c: the declaration of the "nodes" - all the lists and strings and trees and such that make up the value of the variables, and then the defs variable which actually defines the variables which use these trees. The other components in the file don't vary with the size of initial.es, so they shouldn't be accounted for in the size difference.

For the first part, I see

; cat initial.c | awk '/^static const/ {print $3}' | grep -v 'struct' | sort | uniq -c
    251 char
     76 Closure
    113 List
    112 Term
    355 Tree_p
    773 Tree_pp
    528 Tree_s

From some more awk-hackery, those 251 char (really char[]) declarations are collectively around 2070 bytes based on the length of the strings.

The other data types have sizes (based on sizeof() on my machine):

Closure	16
List	16
Term	16
Tree_p	16
Tree_pp	24
Tree_s	16

The counts and sizes of these types all add up to 37496 bytes. Adding in the strings estimate gives us 39566 bytes. That's all the "nodes".

The defs variable is an 88-element array where each element is two pointers (16 bytes) in size. That's 1408 bytes, so adding that to the total makes 40974 bytes.

Honestly, 40974 bytes still feels like a lot, but it's directly based on the representation of these structures in memory, so shrinking that would require rethinking the memory layout of Trees and Lists, and that's a pretty tall order. (Actually, I notice the NodeKinds in those Tree structures are using a total of 13248 bytes. That seems like relatively low-hanging fruit.)

The much weirder thing I notice is that after a strip, initial.o is 48704 bytes on my machine. That seems like a basically reasonable size for a file holding 40974 bytes of data. But then where the heck are the other ~70k bytes coming from in the final es binary? In a binary that's 240k total, that mysterious 70k alone makes up like 30% of the entire image!

[jpco]

Most of the size difference in the binaries comprises the .rela.dyn (difference of 62592) and .data.rel.ro (difference of 45064) sections. I suspect the .data.rel.ro stuff is the data we actually care about (see iant's description of relro here https://www.airs.com/blog/archives/189), and the .rela.dyn content is the bulk of my "mystery overhead" (see discussion of .rela here https://blog.k3170makan.com/2018/10/introduction-to-elf-format-part-vi_18.html).

So my suspicion (and I am very much not an expert here) is that we're serializing initial.es as a large set of separate symbols each pointing to small rather small bits of data (generally just a couple pointers each), which all live in the .data.rel.ro section, and which for whatever reason all need to be relocated during program startup. The metadata to perform these relocations is stored in the form of per-symbol data structures in the .rela.dyn section -- and those relocation data structures are actually larger than the little structs they apply to! (See https://dram.page/p/relative-relocs-explained/ -- "The RELA format is grossly inefficient space-wise at representing relocations.")

So I believe there are more-or-less two options here:

1. Change the linking story such that this data as-is doesn't need relocation, or its relocation representation is far more efficient
2. Change the code-generation logic in dump.c so that it doesn't require thousands of independent symbols to represent these data structures, replacing the current state with one big array (or a few big arrays) with elements that refer to the addresses of the other elements in the array.

I think the better choice would be (2); it's more fool-proof to variations in the building/linking infrastructure, all the pointer arithmetic should be relatively simple to perform, and there's plenty of room for algorithmic inefficiency in dump.c.

[jpco]

As an experiment in the short term, you can try adding -z pack-relative-relocs to your LDFLAGS (This causes the linker to use the new, more-efficient RELR relocation representation rather than the older inefficient RELA representation). Doing that on my machine with es built with -Os, at HEAD (but with the treededup() optimization removed) produces a 175768-byte es, compared to 245328 without the flag. That's a ~28% reduction in binary size, due to a single linker flag! I believe the gains are fairly consistent no matter what other optimizations are going on, so they remain with treededup(), and building with -O2 or -O3.

[jpco]

As an aside - thinking about it while making coffee this morning, there are a few possible data-structure-shrinking things that could be tried. These data-structure optimizations would have the effect of shrinking the memory usage and binary size of the shell.

Embedding Terms directly in Lists would shrink the overall size of Lists by 1/4 (from Term *+char *+Closure *+List * to just char *+Closure *+List *), and save on GC'ing a whole lot of separate objects. Then, making Term into a union with a single-bit discriminant packed into the pointer, similar to how FORWARDED works in gc.c, could then take each List down to two pointers in size -- a 50% reduction from the original.

Then there's the NodeKinds of Trees. There are 19 possible values of NodeKind which means 5 bits are needed to represent them. If we could pack those bits into the u[0] of each Tree, we could reduce the size of Trees by between 1/3 and 1/2 (hard to estimate exactly since some Trees point to one child and some to two).

Since Trees are generally quite a bit more numerous than Lists, that optimization would be a bigger win, but the changes to Lists would be simpler, since in general the structure of Terms is well-encapsulated already (note how term.h defines the actual members of Term while Tree is just out in the open in es.h). The List changes would also have the benefit of less pointer following and fewer objects for the GC to manage.

Something else to look at (and now we're just talking about memory-use optimizations, not binary-size optimizations) are the Tag *s in gc.c, which currently use an entire word to discriminate between just a few different kinds of Tag (plus one bit for FORWARDED). Since these are used for every single GC'd object, shrinking them down would pay off, but I'm having a hard time picturing ways to do that at the moment.

Not to mention, the GC by design adds a 100% memory overhead on top of everything already mentioned. :) I've thought about trying alternative schemes but haven't started really messing around with that yet. There are other interesting experiments to be done here too, like CoW-friendliness (see the discussion of this from a few years back in the Ruby space, the problem statement is extremely relevant for a shell), and this might actually dovetail very nicely with more efficient Tag *s (if the tags are maintained separately from their objects, they could be packed more efficiently without the interference of the pointer-aligned structs they refer to).

I guess this is all to say, there are a lot of potential wins to be had!

[jpco]

I've learned more about this.

This is due to PIE; linking with -no-pie prevents the bulky relocation symbols from being required. That said, in the interest of being friendly to what most OSes/distros want these days, let's prefer not to use -no-pie.

I also spent some time making changes to try to fix this.

First, I refactored dump.c such that the initial.c it produces is made up of eight large-ish arrays of data, instead of the thousands of little individual structs. Like this:

static const Tree_s trees_s[169] = {
    { nPrim, { { (char *) &chars[10] } } },
    { nWord, { { (char *) &chars[127] } } },
/* ... */

That makes everything a bit tidier, and it does make it a bit easier to systematically deduplicate symbols in a nice way. With better deduplication, I was able to squeeze out a whole 4 kiB of binary space compared to the treededup() optimization. That's sure not significant enough to justify working on this, lol. Unfortunately, this also doesn't avoid the relocation data. At first I was confused by that, but then it was pointed out to me that each of these pointers (like &chars[10]) where each bit of data is referring to each other bit of data also need to be rewritten during relocation, and that's the source of the extra data.

The next part, then, is rewriting these data structures so that instead of using pointers, they refer to each other via array offsets (or array offsets + some array ID, in the case of the Tree_p^('' p)s). Like so:

static const Tree_s trees_s[169] = {
    { nPrim, { { 10 } } },
    { nWord, { { 127 } } },
/* ... */

Here's where the challenge appears. In order to avoid having to do a lot of extra junk elsewhere in the binary, it would be ideal to maintain the behavior that you can just cast a (for example) Tree_s * to a Tree * and have everything work. So the scheme I came up with was that the initial.c data structures would look something like

typdef struct { NodeKind k; union { int i; char *s; } u[1]; } Tree_s;
typdef struct { NodeKind k; union { int i; char *p; } u[1]; } Tree_p;
typdef struct { NodeKind k; union { int i; char *p; } u[2]; } Tree_pp;

and then on startup we scan through all of the initial data and convert the int-ish unions to their pointer-ish equivalents, which the rest of the shell would use none the wiser. (Basically, we'd do relocation manually!) The downside of this is that it makes us take all this data which was previously defined as const and therefore in .rodata and instead define it as non-const and therefore in .data. I still don't have a great idea of the implications of this, but my worry is that it potentially harms some degree of memory-sharing the kernel does on read-only pages and can't do on writeable pages; in that case, this change could increase the memory usage of the shell for each process running in an amount that would easily overwhelm the savings we'd get in the binary.

So at this point I'm not entirely confident it's the "right thing" to pursue this "in-code" solution.

Edit: I have now spoken to my colleague who is very knowledgeable about this stuff. There should be no resource-usage implications of making const variables un-const.