Re: [ C ] [ C++ ] Efficient Array Construction / Binary Payload Handling

[Richard Biener <richard dot guenther at gmail dot com>]

On Sun, Dec 1, 2019 at 7:47 PM JeanHeyd Meneide <phdofthehouse@gmail.com> wrote:
>
> Dear GCC Community,
>
>      I have a bit of a question. I recently fixed up and deployed 2
> separate implementations of a paper I am working on for C and C++
> Standardization called #embed (found here -
> https://thephd.github.io/vendor/future_cxx/papers/source/C%20-%20embed
> ).
>
>     I was trying to play with some of the semantics of implementing
> this in GCC, beyond just doing plain expansion into an brace-init-list
> of numbers. I noticed that that large payloads (firmware binary images
> used in resets, lossless music data, generated config data, etc.)
> takes quite a bit more memory and time to initialize and store in GCC;
> Clang has much the same problem too, using ~2 GiB memory to handle a
> 20 MiB array.
>
>     My current working knowledge is that it takes a very long time to
> parse, verify, and create a VECTOR_CST to use for array
> initialization. I am wondering if it might be a good idea for
> optimization purposes to introduce a new way of representing a blob of
> binary data.
>
>      I was able to get extremely fast speeds in a test implementation
> by making a special builtin called __builtin_array with keyword tag
> RID_BUILTIN_ARRAY. The preprocessor directive would expand to
> __builtin_array and one of its arguments was a string literal encoded
> as base64 representing the original resource's binary data (so it
> could survive re-preprocessing the file untouched). I would decode the
> string literal and then build a static array of tree type STRING_CST
> with the actual data.
>
>      It worked, but this approach required removing some type checks
> in digest_init just to be able to fake-up a proper initialization from
> a string literal. It also could not initialize data beyond `unsigned
> char`, as that is what I had pinned the array representation to upon
> creation of the STRING_CST.

Using a STRING_CST is an iteresting idea and probably works well
for most data.

>      I am new to this, and not really a compiler developer, so I was
> wonder if anyone had any tips, tricks, or other places I should look
> to learn something about better ways to do this or faster ways to
> handle what is essentially large binary payloads! I appreciate any
> feedback or thoughts tremendously.

I think most constraints come from designated initializer processing
and handling of symbolic constants that eventually generate relocations.
I've once played with patches in this area, noting that we "waste"
one INTEGER_CST counting the element number for each actual
data element.  For contiguous elements this could be elided.

Note we also have "special" CONSTRUCTOR fields like
RANGE_EXPR for repetitive data.

Since the large initializers are usually in static initializers
tied to variables another option is to replace the DECL_INITIAL
CONSTRUCTOR tree node with a new BINARY_BLOB
tree node containing a pointer to target encoded (compressed)
data.

Then the fastest alternative is to do as GCC did way back in the
past, emit the initializer to final assembly immediately and not
store it in memory (works only when designated initializer processing
isn't needed).  That removes the possibility of eliding the initializer
by constant folding or dead code removal of course.

For the programmer I'd advise to use separate objects for such data,
possibly compiling it with -O0.  With -O0 we could default to emitting
the data immediately then...

Richard.


> Sincerely Yours,
> JeanHeyd Meneide