Optimizing compilers deduplicate strings and arrays

WalterBright | karma 71923 | avg karma 2.96 · 2022-09-23 19:55:16

The dmd D compiler goes even farther. Each string is given a name based on the hash of its contents. Then, the linker will coalesce all the strings in the program with the same contents into the one string.

vlovich123 | karma 10600 | avg karma 2.26 · 2022-09-23 20:04:27

That’s true for C/C++ for clang and GCC if you use -fdata-sections for compiling and linking. -function-sections does a similar thing for duplicate functions.

This doesn’t work across executable boundaries (ie shared libraries) for obvious reasons. Not sure if D’s approach makes that work.

reply

mmoskal | karma 631 | avg karma 3.02 · 2022-09-23 21:35:11

-fdata-sections can increase code size if you have lots of small global - the compiler doesn't know where they will be placed and has to generate pointer literals for all of them, in every function that use them (due to function sections). Without data sections it can generate one literal and then use relative addressing.

I've been hitting that in embedded code with tight size constraints.

reply

vlovich123 | karma 10600 | avg karma 2.26 · 2022-09-23 23:18:00

Doesn’t that all get removed if you LTO?

JonChesterfield | karma 5107 | avg karma 2.47 · 2022-09-23 20:09:44

Does D fold strings with a common suffix? I.e. "bar" to a pointer into "foobar"

WalterBright | karma 71923 | avg karma 2.96 · 2022-09-23 20:39:46

I've thought about doing it a few times, but it didn't seem there was much oil in that well.

JonChesterfield | karma 5107 | avg karma 2.47 · 2022-09-23 20:58:14

I vaguely remember it as a pattern in a dwarf string table but can't remember if the memory saving was worth the compile time. Thanks

nneonneo | karma 11759 | avg karma 9.12 · 2022-09-23 21:40:44

FWIW, GCC does implement this optimization; see https://godbolt.org/z/o81xa94v7 for an example. I've definitely run across real-world samples where it saved some bytes (at the expense of making reverse-engineering a bit more annoying!).

astrange | karma 14132 | avg karma 1.32 · 2022-09-23 22:38:51

It only happens if you check "compile to binary" there, so I think the linker is actually doing it.

User23 | karma 6892 | avg karma 1.23 · 2022-09-23 20:13:50

How does that work? “Foo” isn’t a prefix of “Foobar” because it’s actually “Foo\0” and “Foobar\0”.

JonChesterfield | karma 5107 | avg karma 2.47 · 2022-09-23 21:00:04

If the strings have a 0 after them suffixes are more likely to fold than prefixes. bar\0.

nneonneo | karma 11759 | avg karma 9.12 · 2022-09-23 21:38:49

`"dear friend"` is in fact a prefix of `"dear friend\0f"` - note the embedded null byte. However, I'm guessing GCC doesn't implement this optimization because it's uncommon for a string constant to contain an embedded null.

GCC does implement suffix deduplication, though: `"foobar"` and `"bar"` share the same storage. For example, in https://godbolt.org/z/o81xa94v7, `foobar` is at 0x402004 and `bar` is at 0x402007.

reply

User23 | karma 6892 | avg karma 1.23 · 2022-09-24 09:03:37

Yeah that’s a neat trick. SBCL does that with compiled code. It will use different entry points into a function based on the type checker. So checked and unchecked calls share a suffix of machine code.

kevin_thibedeau | karma 19088 | avg karma 2.16 · 2022-09-23 20:24:42

Surely this doesn't work without const since that would be breaking the expectation of unique objects. I suppose a sufficiently thorough optimizer can check if an array is modified or escapes via a pointer to disable the compaction.

nneonneo | karma 11759 | avg karma 9.12 · 2022-09-23 21:35:32

If an object is initialized with a constant, the constant itself can be located in read-only memory and copied to the object at runtime. The constant can then be deduplicated.

brrrrrm | karma 2032 | avg karma 4.19 · 2022-09-23 21:37:54

const pretty much does nothing to allow optimization in C/C++ :(

jcelerier | karma 10788 | avg karma 2.29 · 2022-09-23 21:47:07

It definitely does for globals

tsimionescu | karma 17553 | avg karma 2.17 · 2022-09-23 23:50:40

I think in general it does something for symbols visible outside the compilation unit (globals, public fields). Otherwise, the compiler usually has enough information to decide if something is actually a constant regardless of the const modifier.

heinrich5991 | karma 1879 | avg karma 3.46 · 2022-09-24 03:53:27

`const` only does something for (global, static, local) variable declarations. The rest is just guidance to for the programmer. It doesn't do anything on pointers, and I think it doesn't do anything on members, but not entirely sure on the last one.

chrisseaton | karma 36438 | avg karma 2.64 · 2022-09-24 02:12:32

> expectation of unique objects

Is that expectation granted by the language specification? Identity is often a problem with optimisations, but only if the specification guarantees it in the first place.

reply

leni536 | karma 3944 | avg karma 2.53 · 2022-09-24 08:54:31

In C++ string literals are const. In C they are non-const, but modifyng them is undefined behavior regardless.

kazinator | karma 30751 | avg karma 1.78 · 2022-09-23 22:10:50

Here is a Lisp compiler where (eq "foo" "foo") turns out false, in spite of there being deduplication:

  1> (compile-toplevel '(list "foo" "foo"))
  #<sys:vm-desc: 923d0b0>
  2> [*1]
  ("foo" "foo")
  3> (eq (car *2) (cadr *2))
  t
  4> (compile-toplevel (eq "foo" "foo"))
  #<sys:vm-desc: 9270bc0>
  5> [*4]
  nil

This is because when (eq "foo" "foo") is read, the objects are not the same. The compiler does constant folding on that expression before merging the literals. The expression folds down to nil:

  6> (disassemble *4)
  data:
  syms:
  code:
      0: 10000000 end nil
  instruction count:
      1
  #<sys:vm-desc: 9270bc0>

and that's that; there are no literals going into the compiled image, and so no deduplication of anything is possible.

kazinator | karma 30751 | avg karma 1.78 · 2022-09-24 02:29:46

Supplement: paradoxically, by reducing the optimization level, we can get the string literals to be preserved in that eq expression, and get deduplicated:

  1> (let ((*opt-level* 0))
       (compile-toplevel '(eq "foo" "foo")))
  #<sys:vm-desc: 9e48fd0>
  2> [*1]
  t
  3> (disassemble *1)
  data:
    0: "foo"
  syms:
      0: eq
  code:
      0: 20020002 gcall t2 0 d0 d0
      1: 04000000
      2: 00000400
      3: 10000002 end t2
  instruction count:
      2
  #<sys:vm-desc: 9e48fd0>

Now there is a call to eq in the compiled code (index 0 in the function symbol table). The string literal is deduplicated and lives in the data register d0, which appears as both arguments to the function. Register t2 receives the result of the call, and the end instruction indicates that register as the result.

kaba0 | karma 9701 | avg karma 1.18 · 2022-09-24 04:58:13

I don’t know CL, is there a separate way to check for object equality vs identity equality (as in java’s == vs equals)?

tmtvl | karma 1823 | avg karma 1.64 · 2022-09-24 05:59:40

There is equalp (http://www.lispworks.com/documentation/HyperSpec/Body/f_equa...). It's like Scheme's equal?.

ridiculous_fish | karma 6729 | avg karma 5.37 · 2022-09-24 00:44:16

Say your code has two strings "split pea" and "pea soup". In the binary file, you can overlap the suffix of the first with the prefix of the second to form "split pea soup": the "pea" is shared, and this reduces both memory usage and binary size.

"split pea soup" is called a superstring of "split pea" and "pea soup" because it contains them both. An optimal superstring packs strings as closely as possible, and its construction is a moderately well-studied problem. This is the best paper I found: https://www.sciencedirect.com/science/article/pii/0304397588...

After implementation I found that "optimal superstrings" compress poorly because the string ranges are unpredictable, and I later did some work to make the string ranges compress better even if the superstring gets longer.

The Hermes superstring optimization was time unwisely spent but is pretty cool anyways, and I don't know of any other work in this area. Check it out: https://github.com/facebook/hermes/blob/main/lib/BCGen/HBC/C...

reply

leni536 | karma 3944 | avg karma 2.53 · 2022-09-24 02:25:06

This can't work for "split pea" and "pea soup" in C, due to the zero terminator at the end of "split pea".

edit:

However this could work with C++ sring_views. I can imagine a library implementing this like:

   constexpr auto store = superstring<
      "split pea",
      "pea soup",
      "split pea soup"
   >;

where `get<i>(store)` gets you a corresponding string_view.

edit2: doh, I just skimmed your github link. I presume you implement just this.

reply

ggambetta | karma 6684 | avg karma 6.13 · 2022-09-24 03:40:13

> There is redundancy since the prefix “Good day professor” is the same in both cases.

The prefix "Good day professor J" is longer and also shared :)

reply

stabbles | karma 2467 | avg karma 3.87 · 2022-09-24 03:56:07

The optimization is under -O1 in gcc, and can be turned off with `-fno-merge-constants`.

However, if you use lld as a linker, strings are duplicated by default. To merge them, you need `gcc -O1 -Wl,-O3 -fuse-ld=lld`.

So, it is a combination of compiler and linker optimizations.

reply

mgraczyk | karma 6060 | avg karma 4.47 · 2022-09-24 12:17:07

For languages like C and C++, the idiomatic way to get the first optimization mentioned is to use formatting strings.

Instead of splitting these two calls into four:

    printf("Good day professor Jones");
    printf("Good day professor Jane");

-->

    printf("Good day professor ");
    printf("Jones");

    printf("Good day professor ");
    printf("Jane");

You should use formatting strings

    printf("Good day professor %s", "Jones");
    printf("Good day professor %s", "Jane");

You'll get the same interning optimization, although you may get an extra "malloc" in printf which two calls would avoid.