This is part of the "Your New Mental Model For constexpr" talk by Jason Turner, copyright 2021. It'll make less sense on its own without the intro which is not here.
Note: all helper functions are static to prevent them from mudying up the assembly output after they have been inlined.
#include <algorithm>
#include <array>
#include <cstdint>
#include <span>
#include <string_view>
#include <utility>
#include <cstring>
[[nodiscard]] static char charToPETSCII2(char c) noexcept {
if (c >= 'a' && c <= 'z') {
return c - 'a' + 1;
}
if (c >= 'A' && c <= 'Z') {
return c - 'A' + 65;
}
if (c == '@') {
return 0;
}
if (c == '_') {
return 100;
}
return c;
}
template <std::size_t Size>
[[nodiscard]] static auto PETSCII2(const char (&value)[Size]) noexcept {
std::array<char, Size - 1> result{};
std::transform(std::begin(value), std::prev(std::end(value)),
std::begin(result), charToPETSCII2);
return result;
}
template <typename Contained, std::size_t MaxLines = 10> struct FixedVector {
std::array<Contained, MaxLines> data;
std::size_t count{0};
constexpr auto size() const noexcept { return count; }
constexpr auto &push_back(Contained &&item) noexcept {
data[count++] = std::move(item);
return data[count - 1];
}
constexpr auto &push_back(const Contained &item) noexcept {
data[count++] = item;
return data[count - 1];
}
[[nodiscard]] constexpr auto begin() noexcept { return std::begin(data); }
[[nodiscard]] constexpr auto end() noexcept {
return std::next(begin(), count);
}
[[nodiscard]] constexpr auto begin() const noexcept {
return std::begin(data);
}
[[nodiscard]] constexpr auto end() const noexcept {
return std::next(begin(), count);
}
};
static constexpr std::size_t MaxLines = 10;
using SplitLines = FixedVector<std::string_view, MaxLines>;
using CenteredLines =
FixedVector<std::pair<std::string_view, std::size_t>, MaxLines>;
[[nodiscard]] static CenteredLines center_lines(const SplitLines &lines,
std::size_t line_length) {
CenteredLines results;
for (const auto &line : lines) {
results.push_back({line, (line_length - line.size()) / 2});
}
return results;
}
[[nodiscard]] static std::size_t
vertical_center_offset(const CenteredLines &lines, std::size_t display_height) {
return (display_height - lines.size()) / 2;
}
[[nodiscard]] static SplitLines
split_line(std::string_view string, const std::size_t line_length) noexcept {
SplitLines lines;
auto begin = string.begin();
const auto end = string.end();
while (begin != end) {
auto word_end = [end](auto start) {
while (start != end && *start != ' ') {
++start;
}
return start;
};
auto eat_spaces = [end](auto start) {
while (start != end && *start == ' ') {
++start;
}
return start;
};
begin = eat_spaces(begin);
auto next_word = word_end(begin);
while (next_word != end) {
auto next_begin = eat_spaces(next_word);
if (next_begin == end) {
break;
}
auto possible_next = word_end(next_begin);
if (std::cmp_less_equal(std::distance(begin, possible_next),
line_length)) {
next_word = possible_next;
if (possible_next == end) {
break;
}
} else {
break;
}
}
lines.push_back(std::string_view(begin, next_word));
begin = next_word;
}
return lines;
}
struct Size {
std::size_t width;
std::size_t height;
};
struct Point {
std::size_t x;
std::size_t y;
};
static void centered_line_drawer(std::string_view line, Size screen_size, const auto &draw) {
const auto split = split_line(line, screen_size.width);
const auto centered = center_lines(split, screen_size.width);
const auto y_start = vertical_center_offset(centered, screen_size.height);
for (std::size_t y = y_start; const auto &line : centered) {
draw(Point{line.second, y}, line.first);
++y;
}
}
void draw(Point, std::string_view);
void do_work() {
// we want to take this string and center it on the screen (40x25),
// split to appropriate line lengths, with each line centered and the whole
// block centered on the screen
// can we make `str` constexpr? That is, is the conversion known at compile time?
const auto str = PETSCII2("Hello world, let's write a long string that needs to be split up. After it's split, we can draw it!");
centered_line_drawer(std::string_view{str.begin(), str.end()}, {40, 25}, draw);
}https://compiler-explorer.com/z/M1n1xjnTz
/* snip */
[[nodiscard]] constexpr static char charToPETSCII2(char c) noexcept {
if (c >= 'a' && c <= 'z') {
return c - 'a' + 1;
}
if (c >= 'A' && c <= 'Z') {
return c - 'A' + 65;
}
if (c == '@') {
return 0;
}
if (c == '_') {
return 100;
}
return c;
}
template <std::size_t Size>
[[nodiscard]] constexpr static auto
PETSCII2(const char (&value)[Size]) noexcept {
std::array<char, Size - 1> result{};
std::transform(std::begin(value), std::prev(std::end(value)),
std::begin(result), charToPETSCII2);
return result;
}
void draw(Point, std::string_view);
/* snip */
void do_work() {
constexpr static auto str =
PETSCII2("Hello world, let's write a long string that needs to be split "
"up. After it's split, we can draw it!");
centered_line_drawer(std::string_view{str.begin(), str.end()}, {40, 25},
draw);
}https://compiler-explorer.com/z/1ceP34Tnb
/* snip */
// auto return type deduction to return a lambda
static auto centered_line_drawer(std::string_view line, Size screen_size) {
// all params captured
return [=](const auto &draw) {
const auto split = split_line(line, screen_size.width);
const auto centered = center_lines(split, screen_size.width);
const auto y_start = vertical_center_offset(centered, screen_size.height);
for (std::size_t y = y_start; const auto &line : centered) {
draw(Point{line.second, y}, line.first);
++y;
}
};
}
// intentionally unimplemented so we can see the results in CE
void draw(Point, std::string_view);
void do_work() {
constexpr static auto str =
PETSCII2("Hello world, let's write a long string that needs to be split "
"up. After it's split, we can draw it!");
// now we return a lambda that is reusable that will draw this
// given block of text whenever it is called.
const auto drawer =
centered_line_drawer(std::string_view{str.begin(), str.end()}, {40, 25});
drawer(draw);
}https://compiler-explorer.com/z/ExEvcGT14
Units of work
- Convert ASCII to PETSCII
- Split 1 string into several lines
- Center those lines
- Center paragraph
- Draw paragraph
We have gone from 0% of the work being done at compile time (optimizations excluded) to 20% done at compile time.
- Convert ASCII to PETSCII - Compile Time
- Split 1 string into several lines
- Center those lines
- Center paragraph
- Draw paragraph
Currently, the lambda returned by centered_line_drawer does no up-front work, but we can change that. To start, we need to make the lambda returned also constexpr. This is easy to accomplish because the function isn't doing anything other than creating a lambda.
/* snip */
// Just made it constexpr
constexpr static auto centered_line_drawer(std::string_view line, Size screen_size) {
return [=](const auto &draw) {
const auto split = split_line(line, screen_size.width);
const auto centered = center_lines(split, screen_size.width);
const auto y_start = vertical_center_offset(centered, screen_size.height);
for (std::size_t y = y_start; const auto &line : centered) {
draw(Point{line.second, y}, line.first);
++y;
}
};
}
void draw(Point, std::string_view);
void do_work() {
constexpr static auto str =
PETSCII2("Hello world, let's write a long string that needs to be split "
"up. After it's split, we can draw it!");
constexpr static auto drawer =
centered_line_drawer(std::string_view{str.begin(), str.end()}, {40, 25});
drawer(draw);
}https://compiler-explorer.com/z/9369565T3
/* snip */
// This is the key for the "moving along the continuum"
// idea
constexpr static auto centered_line_drawer(std::string_view line, Size screen_size) {
// now "split_line" is run at compile-time
const auto split = split_line(line, screen_size.width);
return [=](const auto &draw) {
const auto centered = center_lines(split, screen_size.width);
const auto y_start = vertical_center_offset(centered, screen_size.height);
for (std::size_t y = y_start; const auto &line : centered) {
draw(Point{line.second, y}, line.first);
++y;
}
};
}
void draw(Point, std::string_view);
void do_work() {
constexpr static auto str =
PETSCII2("Hello world, let's write a long string that needs to be split "
"up. After it's split, we can draw it!");
constexpr static auto drawer =
centered_line_drawer(std::string_view{str.begin(), str.end()}, {40, 25});
drawer(draw);
}https://compiler-explorer.com/z/rMK5r8r8x
- Convert ASCII to PETSCII - Compile Time
- Split 1 string into several lines - Compile Time
- Center those lines
- Center paragraph
- Draw paragraph
40% done at compile-time
/* snip */
// one more step to constexpr
constexpr static auto centered_line_drawer(std::string_view line, Size screen_size) {
const auto split = split_line(line, screen_size.width);
const auto centered = center_lines(split, screen_size.width);
return [=](const auto &draw) {
const auto y_start = vertical_center_offset(centered, screen_size.height);
for (std::size_t y = y_start; const auto &line : centered) {
draw(Point{line.second, y}, line.first);
++y;
}
};
}
void draw(Point, std::string_view);
void do_work() {
constexpr static auto str =
PETSCII2("Hello world, let's write a long string that needs to be split "
"up. After it's split, we can draw it!");
constexpr static auto drawer =
centered_line_drawer(std::string_view{str.begin(), str.end()}, {40, 25});
drawer(draw);
}https://compiler-explorer.com/z/YzsMoh3Gb
- Convert ASCII to PETSCII - Compile Time
- Split 1 string into several lines - Compile Time
- Center those lines - Compile Time
- Center paragraph
- Draw paragraph
60% done at compile-time
/* snip */
// now everything is calculated at compile time
constexpr static auto centered_line_drawer(std::string_view line, Size screen_size) {
const auto split = split_line(line, screen_size.width);
const auto centered = center_lines(split, screen_size.width);
const auto y_start = vertical_center_offset(centered, screen_size.height);
return [=](const auto &draw) {
for (std::size_t y = y_start; const auto &line : centered) {
draw(Point{line.second, y}, line.first);
++y;
}
};
}
void draw(Point, std::string_view);
void do_work() {
constexpr static auto str =
PETSCII2("Hello world, let's write a long string that needs to be split "
"up. After it's split, we can draw it!");
constexpr static auto drawer =
centered_line_drawer(std::string_view{str.begin(), str.end()}, {40, 25});
drawer(draw);
}https://compiler-explorer.com/z/68of8s5Gd
- Convert ASCII to PETSCII - Compile Time
- Split 1 string into several lines - Compile Time
- Center those lines - Compile Time
- Center paragraph - Compile Time
- Draw paragraph
80% done at compile-time
... Simply requires making a compile-time allocated buffer to store the resulting screen image.
/* snip */
constexpr auto centered_line_drawer(std::string_view line, Size screen_size) {
return [=](const auto &draw) {
const auto split = split_line(line, screen_size.width);
const auto centered = center_lines(split, screen_size.width);
const auto y_start = vertical_center_offset(centered, screen_size.height);
for (std::size_t y = y_start; const auto &line : centered) {
draw(Point{line.second, y}, line.first);
++y;
}
};
}
template <typename T>
constexpr std::array<char, 40 * 25> run_worker(const T &worker) {
std::array<char, 40 * 25> results{};
auto draw = [&](Point p, std::string_view data) {
const std::size_t start = p.y * 40 + p.x;
std::copy(data.begin(), data.end(), std::next(results.begin(), start));
};
worker(draw);
return results;
}
static void blit(const std::array<char, 40 * 25> &data) {
std::copy(data.begin(), data.end(), reinterpret_cast<char *>(0x0400));
}
void do_work() {
void draw(Point, std::string_view);
static constexpr auto str =
PETSCII2("Hello world, let's write a long string that needs to be split "
"up. After it's split, we can draw it!");
static constexpr auto worker =
centered_line_drawer(std::string_view{str.begin(), str.end()}, {40, 25});
static constexpr auto data = run_worker(worker);
// now all we do is blit at runtime to the display
blit(data);
}https://compiler-explorer.com/z/YhjKqah5E
- Convert ASCII to PETSCII - Compile Time
- Split 1 string into several lines - Compile Time
- Center those lines - Compile Time
- Center paragraph - Compile Time
- Draw paragraph - Compile Time
100% done at compile-time, with only a memcpy required at runtime.
...is to give you a new way of thinking about constexpr and reconsider what things can be moved and what techniques can be used when moving work from runtime to compile-time.
... this "save and continue" technique for using lambdas can have many other applications for pre-calculating values you need more than once!
You could run a series of instructions up to a certain point, then at runtime copy the compile-time generated state of the system and continue calculates at runtime.
/* snip */
static void blit(const std::array<char, 40 * 25> &data) {
std::copy(data.begin(), data.end(), reinterpret_cast<char *>(0x0400));
}
constexpr auto rotate_left(const std::array<char, 40 * 25> &data) {
auto result = data;
for (std::size_t row = 0; row < 25; ++row) {
auto begin = std::next(std::begin(result), 40 * row);
// #thatsarotate
std::rotate(begin, std::next(begin), std::next(begin, 40));
}
return result;
}
void do_work() {
void draw(Point, std::string_view);
static constexpr auto str =
PETSCII2("Hello world, let's write a long string that needs to be split "
"up. After it's split, we can draw it!");
static constexpr auto worker =
centered_line_drawer(std::string_view{str.begin(), str.end()}, {40, 25});
static constexpr auto data = run_worker(worker);
// take compile-time generated data and run it through a runtime processor
blit(rotate_left(data));
}https://compiler-explorer.com/z/bae84d7Tb
- What can you move to compile time?
- Where can you end up on this continuum?
- What might you gain from generating some portion at compile time, then copying and modifying that data at runtime?
Also note that you can move these things behind a compilation firewall if you want to.
// hpp file:
const std::array<std::uint8_t, 40*25> &get_screen();
// cpp file:
const std::array<std::uint8_t, 40*25> &get_screen()
{
static constexpr auto str =
PETSCII2("Hello world, let's write a long string that needs to be split "
"up. After it's split, we can draw it!");
static constexpr auto worker =
centered_line_drawer(std::string_view{str.begin(), str.end()}, {40, 25});
static constexpr auto data = run_worker(worker);
return data;
}
// another cpp file:
void do_work() {
// Now you only pay for the data constexpr code in one place,
// and get all of the runtime advantages!
blit(rotate_left(get_screen()));
}