Lightning Talk: Memoizing Constexpr Programs - Chris Philip - CppCon 2021

https://www.youtube.com/watch?v=wFRlUNSMK8s

Transcrição

[00:10]

00:10 all right my name is chris i work at google i'm going to be talking about memoizing constant expert programs today so since c plus modern version c 14 at least

[00:22]

00:22 um you can just add this nice contextual qualifier to your fibonacci function and then you can you know run call this function at compile time or at run time and it'll give you a value either way

[00:35]

00:35 problem is uh and yeah when you run a compile time it just kind of puts that constant in the binary so you can just use it for free at run time

[00:48]

00:48 the nice things about this is you get to move some computations from runtime to compile time and you can use functions for doing compile time only stuff

[01:00]

01:00 so cna and you know choosing template parameters so for example you could make an array

[01:08]

01:08 whose size is the fibonacci of some other number i don't know why you'd want that but you could totally do it and then for certain template meta programming strategies like boost hana

[01:18]

01:18 type c doing that with context for functions lets you use more function style syntax compared to traditional template meta programming

[01:28]

01:28 unfortunately compile time evaluation is not very fast for example if you call fibonacci of 35 with this trivial recursive implementation it's about 20 times

[01:38]

01:38 slower to compile than it is to just evaluate that recursion at runtime and it gets worse if you try and call fibonacci of 36 it doesn't even compile because

[01:50]

01:50 the compiler decides that you're probably just never going to terminate so we're just going to shut you off early you can pass this flag to increase that limit

[01:59]

01:59 but that's not really a very good solution because you know if i add 45 to this we're just going to get more problems so one common solution uh that i'm sure

[02:10]

02:10 everyone who did a fibonacci program in college uh learned about is memoization so can we memoize our concepts for function uh unfortunately the traditional usage

[02:21]

02:21 or way to memoize would be to use like a map or something fortunately we can't use those types at compile time and then additionally things like uh standard map

[02:31]

02:31 don't generally support uh higher level type manipulation such as a boost hana type c so we can't put multiple different kinds of types in our map

[02:42]

02:42 good news though we can memoize our constexpr functions the way we do that is by making a variable template constexpr global variable template and then all this is going to do is

[02:54]

02:54 going to dispatch to our function and then our function recurses by kind of invoking our variable template instead of directly recursing through

[03:06]

03:06 the function so this is pretty cool we get about 50 times better compile time performance

[03:16]

03:16 for fibonacci 35 compared to without memoization um and then even those intermediate variable templates um are actually

[03:27]

03:27 optimized out of the final binary so it's not going to increase your binary size and it actually you know completely solves that problem of computation limit

[03:37]

03:37 uh because it provides a very fixed limit on the number of computations that's going to be run at compile time instead of potentially growing continuously

[03:46]

03:46 unfortunately there are a couple of downsides these template arguments are compile time only so that means that you can't actually

[03:54]

03:54 use this context for function at runtime and compile time and it's gonna be a little bit more increased complexity because we're not just writing uh traditional functions

[04:04]

04:04 anymore we have to have this indirection in our dispatch but we use this uh in a library i wrote called haversack that does a lot of template meta

[04:14]

04:14 programming um and it allows our production code to actually compile uh and then i have a godbolt link here um that shows this actual this code actually working and compiling

[04:25]

04:25 um thank you very much [Applause] you

Real world usage - https://qithub.com/google/hotels-template-library/tree/master/haversack - https:/godbolt.org/z/soPb5TvKa