💣 #2 - Manually Destroying a Map For Space, and Fun!
💣 😈
Happy middle of the month, everyone! If you are reading this, this meant that you have survived this far, and we're heckin' proud of you! This half-month's newsletter is going to be dedicated to std::unordered_map: or, specifically, how we saved some space on some critical devices by getting creative with how we share things!
But first..
CoSy!
A huge, big W E L C O M E to everyone who has signed up about CoSy! As with the last newsletter, here's an update of where we are:
- We are reaching out for sponsors and connecting with a lot of organizations! If you'd like to sponsor us, send an e-mail to cosy@soasis.org! We have a little two-page primer you can have, and can talk to your organization more directly if you like!
- We have contacted 6 Live Caption companies, who are getting back to us with quotes so we can make sure we support Hard of Hearing folks.
- We have a pretty good idea of what platforms we will stream on. More on that in the next Newsletter!
- We are offering trainings at the Conference! We have had immense interest in folks signing up to teach. If you're interested please send an e-mail to inquiries@soasis.org!
- We are working on STICKERS! (And a cute mascot, too!) Stay tuned for more on that.
We're excited at the progress we're making! So far, everything looks to be shaping up nicely. And now, let's get ready to...
💥 Explode an unordered_map, manually!
The coding portion of this is about a technique a few people helped us put together. Essentially, the problem is there was code that needed to loop through a map and invoke a function that changed both the key and the value of a std::unordered_map, which is C++'s standard associative container (typically called a "dictionary" in Python and C#). The code looked like this:
int super_cool_computation(
important_t* necessary,
const good_t& params)
{
using key_t = manual_destroy_key;
using value_t = manual_destroy_key;
std::unordered_map<key_t, value_t> my_map;
// ...
// used here to do some super cool stuff
// ...
for (auto& key_value_pair : my_map) {
key_t& key = key_value_pair.first;
value_t& value = key_value_pair.second;
key.clean_up_resource(necessary, params);
value.clean_up_resource(necessary, params);
}
// my_map destroys normally after return
return 0;
}
Unfortunately, there's 2 problems with this!
It Doesn't Compile!
This line:
key_t& key = key_value_pair.first;
Is illegal. key_value_pair.first is a const-qualified object! So, we can't get a normal reference type manual_destroy_key&, we need to get a constant reference type const manual_destroy_key&. Unfortunately, clean_up_resource(...) modifies things, so we can't call it if we const-qualify key!
We could use const_cast to get rid of the const-ness of the key_value_pair.first:
// ...
for (auto& key_value_pair : my_map) {
key_t& key =
const_cast<key_t&>(key_value_pair.first);
// ...
}
// ...
This works, but...
It's effectively a lie!
The key in map types in C++ are created and stored as const. Casting it away means that, while unlikely, some day the optimizer could do things to that value not expecting us to mutate it. This eventually opens us up to Undefined Behavior (😱)!
Making clean_up_resource into a const method and then marking some members mutable might work, but it's essentially just moving the problem inside the clean_up_resource call.
It turns out, there's some C++17 methods for getting both the key and value out of a map in their non-const forms. It's called...
extract(iterator)!
If our goal is to iterate over a map and call a function to mutate the keys and values, extract is the go-to way to do it. So, using that, we can achieve a standards-compliant way of cleaning out a map and cleaning up BOTH the keys and values like so:
int super_cool_computation(
important_t* necessary,
const good_t& params)
{
using key_t = manual_destroy_key;
using value_t = manual_destroy_key;
std::unordered_map<key_t, value_t> my_map;
// ...
// used here to do some super cool stuff
// ...
auto first_iterator = my_map.cbegin();
auto last_iterator = my_map.cend();
while (first_iterator != last_iterator) {
// save an iterator to what we want to extract
auto saved_iterator = first_iterator;
// move the iterator, once every loop!
++first_iterator;
// extract it!
auto extracted_node =
my_map.extracted(saved_iterator);
key_t& key = extracted_node.key();
value_t& value = extracted_node.mapped();
key.clean_up_resource(necessary, params);
value.clean_up_resource(necessary, params);
// let the node fall off!
}
// my_map is all empty!
return 0;
}
The extract method returns a special node type, which has both the key and value. When we let the node type expire by reaching the end of the for loop's scope, it deletes the type and nothing gets inserted back into the map. This means you can effectively extract, but never replace!
Want to keep it instead of getting rid of it?
If you want to modify the key and also return it back to the origin, you can always call my_map.insert(std::move(extracted_node));. We don't do that here because we just wanted to clean out my_map!
This is useful when you can't store the necessary parameters inside the key and value classes. For example, a process was inserting hundreds of thousands of keys into one of the maps previously, and we had to duplicate necessary, params as members on every single key and value! This meant we were shedding tons of bytes - plus padding - and needing to allocate way more space than was necessary. Since the necessary parameters were identical for all keys and values, it made sense to pull them out and then manually clean up the type instead.
And, that's it! Congratulations, you made it to the end of one of the longer newsletters! The ones in the future will be shorter, and the next one may even contain a bit of a musical surprise, from us! 🎶
— Shepherd's Oasis 💙