Initialize huge uint8_t array statically with reasonable compilation time

Asked 28/12, 2015 at 11:25 Answered 28/12, 2015 at 14:1

I would like to statically initialize huge (megabytes) uint8_t array.

At the beginning I tried this:

constexpr uint8_t arr[HUGE_SIZE] = { 0, 255, ... };

Unfortunatelly, compilation time of above is very long (no optimization - around 30 seconds, optimizations on - above hour).

I found out that compilation time can be reduced to negligible (in both optimization off and on cases) if we use c style string initialization:

constexpr uint8_t arr[HUGE_SIZE + 1] = "\x00\xFF\x...";

Is this good approach in C++? Should I use some string literal to make types of both sides of above assignment equal?

Eldwun answered 28/12, 2015 at 11:25 Comment(23)

Do you really need such a big array? Maybe you should think about the algorithm. – Lubricious 28/12, 2015 at 11:26

@Eldwun What is the array for, and do you actually need an array filled with memory at compile time? – Fullbodied 28/12, 2015 at 11:28

I am surprised, that optimizations make a difference in the first case. Can somebody explain that? – Stamin 28/12, 2015 at 11:28

@Ctx: Probably because the compiler generates code to filll the array, which is dumped in some special function - this function then becomes enormous, and at least gcc and clang [more specifically llvm] do not like large functions due to some O(N^x) complexity. – Syncopation 28/12, 2015 at 11:32

Is constexpr always static or is it more likely to be optimized away than just using static? Will the compile time with constexpr vary compared to the compile time of static? – Chatwin 28/12, 2015 at 11:33

@cad: yes, I need to store precomputed values – Eldwun 28/12, 2015 at 11:37

What version of what compiler is giving you this hour+ compile-time? – Spermatid 28/12, 2015 at 11:38

@Poriferous: this array stands for static dictionary (to be precise dictionary data); it would be great to don't load it from a file and don't keep it in free store, just have it in some compiled object – Eldwun 28/12, 2015 at 11:40

What toolchain are you using? – Coiffeur 28/12, 2015 at 11:42

@ilent2: when I wrote static, I meant initialized during compilation, not running; I guess compilation time does not vary when switching from constexpr to static, if you want, I can do a test today – Eldwun 28/12, 2015 at 11:42

Note that it is possible to embed an arbitrary binary file in an object file (see many posts on this website), if your compiler can't be convinced to finish in a reasonable time. – Spermatid 28/12, 2015 at 11:43

@MarcGlisse: I am using standard compiler provided in Command Line Tools for the newest version of XCode. I'll let you know precise version number in couple of hours (I don't have access for that machine in this moment) – Eldwun 28/12, 2015 at 11:46

@FUZxxl: stackoverflow did not let me to notify you with MarcGlisse, please take a look at comment addressed to him – Eldwun 28/12, 2015 at 11:47

XCode uses LLVM, so large function is definitely a problem. – Syncopation 28/12, 2015 at 11:47

@Eldwun The assembler included by XCode supports the syntax I mention as far as I know. – Coiffeur 28/12, 2015 at 11:49

Marking it as constrexpr suggests to the compiler "try to replace uses of this inline with the according value", which causes quite some compile overhead. How about using plain "const" instead? – Fadden 28/12, 2015 at 11:49

@UlrichEckhardt If you can back this up with facts, consider writing an answer. – Coiffeur 28/12, 2015 at 11:52

@UlrichEckhardt: as far as I remember, I tried const too but it did not fixed compilation time issue. – Eldwun 28/12, 2015 at 11:54

Just to make it more explicit: Why did you mark this as constexpr at all? Do you understand the difference between const and constexpr? Did you actually put this into a header file? How often is that header file included? That said, please extract a minimal example that at least answers the above questions. Also, please clarify what HUGE_SIZE really is. – Fadden 28/12, 2015 at 11:59

@UlrichEckhardt: I used constexpr just to have a guarantee that compiler won't produce code of initialization of this array in runtime. Will const give that same guarantee? This code is placed in a source file, not a header. The lowest size of HUGE_SIZE where I observed long compilation time was around 200 000 (I did not tested lower values). – Eldwun 28/12, 2015 at 12:18

I didn't manage to reproduce the huge compile-time difference between -O0 and -O3 with a file that has just the array (and a trivial function that returns the address of the array, so it is not eliminated). – Spermatid 28/12, 2015 at 13:46

@Eldwun Is the array a global variable? Or is it local? If it's local, is it automatic or static? – Coiffeur 28/12, 2015 at 14:26

constexpr does not apply to C. Suggest deleting tag. – Unswear 28/12, 2015 at 15:58

If the array is really large, consider using a utility to directly generate an object file from the array. For example, with the GNU assembler you can do something like this:

    .section .rodata # or .data, as needed
    .globl arr
arr:
    .incbin "arr.bin" # assuming arr.bin is a file that contains the data
    .size arr,.-arr

Then assemble this file with the GNU assembler and link it to your program. To use this data elsewhere in your program, just declare it as extern "C":

extern "C" const uint8_t arr[];

Coiffeur answered 28/12, 2015 at 11:44 Comment(7)

That would be a solution. Won't C++ programmers' world be unhappy with this approach? (-; – Eldwun 28/12, 2015 at 11:50

@Eldwun Well, with this solution you are operating outside of the realm of the C++ programming language. This applies to any other approach, too, though. In a portable open source application, I would take care to add a solution for Windows, too. – Coiffeur 28/12, 2015 at 11:51

You're right. I am wondering if embedding it in cpp file (like I did in question) gives some guarantees, that are lost in case of your approach. For instance endianness could be corrupted when developping for various devices (so we are required to provide version of arr.bin for big-endian and little-endian), am I right? – Eldwun 28/12, 2015 at 12:13

@Eldwun Endianness does not matter if you use uint8_t for your element type—a single byte has no endianess. The .incbin directive literally dumps the file named after it into the object file without changing anything. Endianess is not affected. – Coiffeur 28/12, 2015 at 12:19

Why not use plain C for this? – Ellersick 28/12, 2015 at 13:59

@Ellersick If OPs C++ compiler is horribly slow with this in C++, it's likely that it's just as slow with plain C. – Coiffeur 28/12, 2015 at 14:25

@FUZxxl: not even likely, worth a try anyway. – Ellersick 28/12, 2015 at 16:20

Found that compile time for large arrays does improve a bit if the array is broken down into smaller chunks. Yet the string approach is still significantly faster. With such a scheme, the true array could union this array of arrays.

Posting the below as an example of how to test OP's problem without explicitly coding million byte source files. As this is not much of an answer but a resource for investigation, marking this community wiki.

#include <iostream>
using namespace std;

#include <cstdint>

#define METHOD 5

#if METHOD == 1
// 1 byte blocks 28 secs
#define ZZ16 65, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255,
#define ZZ256 ZZ16  ZZ16  ZZ16  ZZ16  ZZ16  ZZ16  ZZ16  ZZ16  ZZ16  ZZ16  ZZ16  ZZ16  ZZ16  ZZ16  ZZ16  ZZ16
#define ZZ4K  ZZ256 ZZ256 ZZ256 ZZ256 ZZ256 ZZ256 ZZ256 ZZ256 ZZ256 ZZ256 ZZ256 ZZ256 ZZ256 ZZ256 ZZ256 ZZ256
#define ARR constexpr uint8_t arr[]
#define COUT cout << arr << endl

#elif METHOD == 2
// 16 byte blocks 16 secs
#define ZZ16 {66, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255},
#define ZZ256 ZZ16  ZZ16  ZZ16  ZZ16  ZZ16  ZZ16  ZZ16  ZZ16  ZZ16  ZZ16  ZZ16  ZZ16  ZZ16  ZZ16  ZZ16  ZZ16
#define ZZ4K  ZZ256 ZZ256 ZZ256 ZZ256 ZZ256 ZZ256 ZZ256 ZZ256 ZZ256 ZZ256 ZZ256 ZZ256 ZZ256 ZZ256 ZZ256 ZZ256
#define ARR constexpr uint8_t arr[][16]
#define COUT cout << arr[0] << endl

#elif METHOD == 3
// 256 byte blocks 16 secs
#define ZZ16 67, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255,
#define ZZ256 {ZZ16  ZZ16  ZZ16  ZZ16  ZZ16  ZZ16  ZZ16  ZZ16  ZZ16  ZZ16  ZZ16  ZZ16  ZZ16  ZZ16  ZZ16  ZZ16},
#define ZZ4K  ZZ256 ZZ256 ZZ256 ZZ256 ZZ256 ZZ256 ZZ256 ZZ256 ZZ256 ZZ256 ZZ256 ZZ256 ZZ256 ZZ256 ZZ256 ZZ256
#define ARR constexpr uint8_t arr[][256]
#define COUT cout << arr[0] << endl

#elif METHOD == 4
// 4K byte blocks 13 secs
#define ZZ16 68, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255, 0, 255,
#define ZZ256 ZZ16  ZZ16  ZZ16  ZZ16  ZZ16  ZZ16  ZZ16  ZZ16  ZZ16  ZZ16  ZZ16  ZZ16  ZZ16  ZZ16  ZZ16  ZZ16
#define ZZ4K  {ZZ256 ZZ256 ZZ256 ZZ256 ZZ256 ZZ256 ZZ256 ZZ256 ZZ256 ZZ256 ZZ256 ZZ256 ZZ256 ZZ256 ZZ256 ZZ256},
#define ARR constexpr uint8_t arr[][4096]
#define COUT cout << arr[0] << endl

#elif METHOD == 5
// String 4 sec
#define ZZ16 "\x45\xFF\x00\xFF\x00\xFF\x00\xFF\x00\xFF\x00\xFF\x00\xFF\x00\xFF"
#define ZZ256 ZZ16  ZZ16  ZZ16  ZZ16  ZZ16  ZZ16  ZZ16  ZZ16  ZZ16  ZZ16  ZZ16  ZZ16  ZZ16  ZZ16  ZZ16  ZZ16
#define ZZ4K  ZZ256 ZZ256 ZZ256 ZZ256 ZZ256 ZZ256 ZZ256 ZZ256 ZZ256 ZZ256 ZZ256 ZZ256 ZZ256 ZZ256 ZZ256 ZZ256
#define ARR constexpr uint8_t arr[]
#define COUT cout << arr << endl
#endif

#define ZZ64K ZZ4K  ZZ4K  ZZ4K  ZZ4K  ZZ4K  ZZ4K  ZZ4K  ZZ4K  ZZ4K  ZZ4K  ZZ4K  ZZ4K  ZZ4K  ZZ4K  ZZ4K  ZZ4K
#define ZZ1M  ZZ64K ZZ64K ZZ64K ZZ64K ZZ64K ZZ64K ZZ64K ZZ64K ZZ64K ZZ64K ZZ64K ZZ64K ZZ64K ZZ64K ZZ64K ZZ64K
#define ZZ16M ZZ1M  ZZ1M  ZZ1M  ZZ1M  ZZ1M  ZZ1M  ZZ1M  ZZ1M  ZZ1M  ZZ1M  ZZ1M  ZZ1M  ZZ1M  ZZ1M  ZZ1M  ZZ1M

// 3 million bytes
ARR = {
    ZZ1M ZZ1M ZZ1M
};

int main() {
  cout << "!!!Hello World!!!" << endl;
  COUT;
  cout << sizeof(arr) << endl;
  return 0;
}

Unswear answered 28/12, 2015 at 11:25 Comment(0)

Are you intending to recompile the file in which the array is defined very often? If not, you could put the definition of the array into a separate .cpp file with a forward declaration in a .h file. Thus you'll face compilation overhead only when the array changes.

Judicious answered 28/12, 2015 at 11:48 Comment(1)

During developing process array could change even once per day, so losing hour or more to compile it is not a case. Anyway thanks for answer. (-: – Eldwun 28/12, 2015 at 12:20

Move the array definition to a separate C file and compile it as such. C++ can refer to external global data from C object modules.

If gcc takes too long to compile it, use tcc .

Ellersick answered 28/12, 2015 at 14:1 Comment(1)

constexpr uint8_t arr[HUGE_SIZE] = { 0, 255, ... }; does not compile in C. If you are suggesting different code, perhaps posting to clarify your answer. – Unswear 28/12, 2015 at 16:1

Hot tags

Godot Unity Godot Help Programming Godot 4.X GUI GDScript 3D 2D Physics CSharp Godot 3.X VR XR Projects C++

Recommended topics

Hot tags