6

As an experiment, I just put together some code to generate a std::array<uint32_t, 256> at compile time. The table contents themselves are a fairly typical CRC lookup table - about the only new thing is the use of constexpr functions to calculate the entries as opposed to putting an autogenerated magic table directly in the source code.

Anyway, this exercise got me curious: would there be any practical limitations on the amount of computation a compiler would be willing to do to evaluate a constexpr function or variable definition at compile time? e.g. something like gcc's -ftemplate-depth parameter creating practical limits on the amount of template metaprogramming evaluation. (I also wonder if there might be practical limitations on the length of a parameter pack - which would limit the size of a compile-time std::array created using a std::integer_sequence intermediate object.)

ildjarn
  • 62,044
  • 9
  • 127
  • 211
Daniel Schepler
  • 3,043
  • 14
  • 20
  • If I recall xorrectly, yes there is a limit, but it is supposed to be orders of magnitude bigger than the recursive instantiation limit. – MikeMB Jun 27 '16 at 19:51

1 Answers1

4

Recommendations for such can be found in [implimits] ¶2:

(2.35)   —   Recursive constexpr function invocations [512]

(2.36)   —   Full-expressions evaluated within a core constant expression [1 048 576]

GCC and Clang allow adjustment via -fconstexpr-depth (which is the flag you were looking for).

Constant expression evaluation practically runs in a sandbox, because undefined behavior must be preempted by the implementation. With that in mind, I don't see why the implementation couldn't use the entire resources of the host machine. Then again, I wouldn't recommend writing programs whose compilation requires gigabytes of memory or other unreasonable resources...

Community
  • 1
  • 1
Columbo
  • 60,038
  • 8
  • 155
  • 203
  • OK, would "Template arguments in a template declaration [1 024]" also count lengths of parameter packs? (I'm guessing yes, otherwise you could only run into that limit with extremely badly written C++ code.) If so, that would mean that building a `std::array` lookup table to process two bytes at a time would probably not be practical. – Daniel Schepler Jun 27 '16 at 22:02
  • @DanielSchepler I don't understand. – Columbo Jun 27 '16 at 22:14
  • In the end, the table is created by a function `template constexpr std::array crc_table_impl(uint32_t crc_poly, std::integer_sequence) { return { crc_table_entry(crc_poly, I)... }; }` being passed an `integer_sequence` containing 0 through 255. So, if I tried to do the same thing with `uint16_t` there would be an intermediate template with 65537 arguments. – Daniel Schepler Jun 27 '16 at 22:21
  • @DanielSchepler Yeah, that's a weird plan. Why not just use a loop? – Columbo Jun 27 '16 at 22:23
  • As far as I can tell, the only valid way to initialize a `std::array` of an integral type within a `constexpr` function is to give all the elements from the beginning. If I try using the default constructor gcc errors out with: `uninitialized variable ‘result’ in ‘constexpr’ function` (then going on to explain that the default constructor doesn't initialize the array). – Daniel Schepler Jun 27 '16 at 22:30
  • I suppose if I used a class wrapper around `uint32_t` to make the default constructor initialize to 0 then the loop method could potentially work. – Daniel Schepler Jun 27 '16 at 22:47
  • After more experimentation, it looks like with a class wrapper around `uint32_t`, and using C++17, the loop-based version would work. (C++17 is where non-const `std::array::operator[]` is updated to `constexpr` - and even g++ 6.1.0 hasn't incorporated that update so I had to make a local copy of the `` header and put it in myself - not the safest thing to do, though.) – Daniel Schepler Jun 27 '16 at 23:54
  • @DanielSchepler: no, the template pack length doesn't count as depth in general, unless reading the list of parameters requires it that way. See for instance Yakk's comments to my answer in this question from long ago. http://stackoverflow.com/questions/32235855/switch-statement-variadic-template-expansion/32235928#32235928 Often times its easy to make an algorithm that manages a parameter pack of length `n` using depth `n`, but if you are clever sometimes the depth can be only `log n`. If you use constexpr stuff instead of templates for actual iteration then you circumvent the issue I think – Chris Beck Jun 28 '16 at 03:20
  • @DanielSchepler `{}` is a valid initializer, as `array` is an aggregate (so each element will itself be initialized with `{}`, i.e. value-initialized). You don't need a wrapper. – Columbo Jun 28 '16 at 11:09
  • @Columbo OK thanks, `std::array result = {};` does work. That does still leave the issue that assigning to the array in a constexpr function requires C++17 features not yet in any of my available compilers. – Daniel Schepler Jun 28 '16 at 17:16
  • @DanielSchepler Why not use a bog-standard array? – Columbo Jun 28 '16 at 17:37
  • @Columbo According to gcc, a function is not allowed to return a language-level array: from `using table = uint32_t[256]; constexpr table my_arr() { ... }` I get `error: ‘my_arr’ declared as function returning an array`. – Daniel Schepler Jun 28 '16 at 17:59