Review the share schema and consider the various issues of implementing it.
Prologue
skip
FlyWeight Pattern
The theory of
Sharing pattern is a structural design pattern that extracts and maintains the same component elements of complex objects separately. These same components, called shared components, are uniquely managed in a separate container, and complex objects only need to hold a reference to that unique instance, rather than having to create such identical elements repeatedly, thus drastically reducing memory footprint.
In the case of a word processor, each character has its own special properties that distinguish it from other characters: font style, background, border, alignment, and so on. If all characters in a document stored a separate copy of all its attributes, this would be a huge memory requirement. But given that a whole bunch of characters (say, 1000 characters) might all have the same “宋体, 9pt” attribute, all we really need to store is a single copy of the font style attribute for “宋体, 9pt”, and a single character only needs a pointer to that font style attribute. This is much less than copying 1000 font style attributes for 1000 characters.
There are many similar cases, such as the example in which each particle in the system (e.g. bullet, shrapnel, or enemy aircraft) has some of the same properties (e.g. color, contour, etc.) but occupies a large area with the same value.
The factory pattern
It is easy to imagine that we could manage our share objects in situ in a factory. When a customer requests a privilege object with a specific value, the factory retrieves the existence of the privilege from a dictionary and returns a reference to the element to the customer. If the attribute does not already exist, the factory creates it and returns the reference.
immutability
Traditionally, the share pattern requires that these same parts (the share, the same component) be immutable. But this is not an iron law.
One way to do this is to take a whole element as a whole, and we can change the whole element reference that the object holds.
For example, if we are changing the font style of a word in our word processor from “宋体, 9pt” to “boldface, 12pt”, we can change the reference point directly. That is, we provide an overall modification interface like character.apply_font_style(font_style& style).
Another approach could be to modify at a finer granularity, such as from “宋体, 9pt” to “宋体, 10pt,” but try to verify the reference to the new value from the factory when the change occurs. That is, we provide an interface like character.set_font_size(float pt), but remember to check the share factory (manager) to update internal references during its implementation.
C + + implementation
Example code to implement the traditional share pattern looks like this:
namespace hicc::dp::flyweight::basic { /** * flyweight Design Pattern * * Intent: Lets you fit more objects into the available amount of RAM by sharing * common parts of state between multiple objects, instead of keeping all of the * data in each object. */ struct shared_state { std::string brand_; std::string model_; std::string color_; shared_state(const std::string &brand, const std::string &model, const std::string &color) : brand_(brand) , model_(model) , color_(color) { } friend std::ostream &operator<<(std::ostream &os, const shared_state &ss) { return os << "[ " << ss.brand_ << " , " << ss.model_ << " , " << ss.color_ << " ]"; }}; struct unique_state { std::string owner_; std::string plates_; unique_state(const std::string &owner, const std::string &plates) : owner_(owner) , plates_(plates) { } friend std::ostream &operator<<(std::ostream &os, const unique_state &us) { return os << "[ " << us.owner_ << " , " << us.plates_ << " ]"; }}; /** * The flyweight stores a common portion of the state (also called intrinsic * state) that belongs to multiple real business entities. The flyweight accepts * the rest of the state (extrinsic state, unique for each entity) via its * method parameters. */ class flyweight { private: shared_state *shared_state_; public: flyweight(const shared_state *o) : shared_state_(new struct shared_state(*o)) { } flyweight(const flyweight &o) : shared_state_(new struct shared_state(*o.shared_state_)) { } ~flyweight() { delete shared_state_; } shared_state *state() const { return shared_state_; } void Operation(const unique_state &unique_state) const { std::cout << "flyweight: Displaying shared (" << *shared_state_ << ") and unique (" << unique_state << ") state.\n"; }}; /** * The flyweight Factory creates and manages the flyweight objects. It ensures * that flyweights are shared correctly. When the client requests a flyweight, * the factory either returns an existing instance or creates a new one, if it * doesn't exist yet. */ class flyweight_factory { std::unordered_map<std::string, flyweight> flyweights_; std::string key(const shared_state &ss) const { return ss.brand_ + "_" + ss.model_ + "_" + ss.color_; } public: flyweight_factory(std::initializer_list<shared_state> lists) { for (const shared_state &ss : lists) { this->flyweights_.insert(std::make_pair<std::string, flyweight>(this->key(ss), flyweight(&ss))); } } /** * Returns an existing flyweight with a given state or creates a new one. */ flyweight get(const shared_state &shared_state) { std::string key = this->key(shared_state); if (this->flyweights_.find(key) == this->flyweights_.end()) { std::cout << "flyweight_factory: Can't find a flyweight, creating new one.\n"; this->flyweights_.insert(std::make_pair(key, flyweight(&shared_state))); } else { std::cout << "flyweight_factory: Reusing existing flyweight.\n"; } return this->flyweights_.at(key); } void list() const { size_t count = this->flyweights_.size(); std::cout << "\nflyweight_factory: I have " << count << " flyweights:\n"; for (std::pair<std::string, flyweight> pair : this->flyweights_) { std::cout << pair.first << "\n"; }}}; / /... void AddCarToPoliceDatabase( flyweight_factory &ff, const std::string &plates, const std::string &owner, const std::string &brand, const std::string &model, const std::string &color) { std::cout << "\nClient: Adding a car to database.\n"; const flyweight &flyweight = ff.get({brand, model, color}); // The client code either stores or calculates extrinsic state and passes it // to the flyweight's methods. flyweight.Operation({owner, plates}); } } // namespace hicc::dp::flyweight::basic void test_flyweight_basic() { using namespace hicc::dp::flyweight::basic; flyweight_factory *factory = new flyweight_factory({ {"Chevrolet", "Camaro2018", "pink"}, {"Mercedes Benz", "C300", "black"}, {"Mercedes Benz", "C500", "red"}, {"BMW", "M5", "red"}, {"BMW", "X6", "white"} }); factory->list(); AddCarToPoliceDatabase(*factory, "CL234IR", "James Doe", "BMW", "M5", "red"); AddCarToPoliceDatabase(*factory, "CL234IR", "James Doe", "BMW", "X1", "red"); factory->list(); delete factory; }Copy the codeThe output looks like this:
--- BEGIN OF test_flyweight_basic ----------------------
flyweight_factory: I have 5 flyweights:
BMW_X6_white
Mercedes Benz_C500_red
Mercedes Benz_C300_black
BMW_M5_red
Chevrolet_Camaro2018_pink
Client: Adding a car to database.
flyweight_factory: Reusing existing flyweight.
flyweight: Displaying shared ([ BMW , M5 , red ]) and unique ([ James Doe , CL234IR ]) state.
Client: Adding a car to database.
flyweight_factory: Can't find a flyweight, creating new one.
flyweight: Displaying shared ([ BMW , X1 , red ]) and unique ([ James Doe , CL234IR ]) state.
flyweight_factory: I have 6 flyweights:
BMW_X1_red
Mercedes Benz_C300_black
BMW_X6_white
Mercedes Benz_C500_red
BMW_M5_red
Chevrolet_Camaro2018_pink
--- END OF test_flyweight_basic ----------------------
Copy the codeAs you can see, for a free element like [BMW, X1, Red], where the individual instance is large (tens, hundreds, or even tens of kilobytes) and the reference reference is no more than the size of a pointer (typically 64 bytes on 64-bit OS), the eventual memory savings are significant.
FlyWeight Pattern in metaprogramming
The example above, which is old style, requires a lot of use of smart Pointers and template syntax after C++11, while the better in situ construction ability after C++17 allows our code to be more meaningful.
flyweight_factory
One idea is that we think a generic meta-factory as common as possible might be beneficial for code writing. So we tried a free factory template like this:
namespace hicc::dp::flyweight::meta { template<typename shared_t = shared_state_impl, typename unique_t = unique_state_impl> class flyweight { std::shared_ptr<shared_t> shared_state_; public: flyweight(flyweight const &o) : shared_state_(std::move(o.shared_state_)) { } flyweight(shared_t const &o) : shared_state_(std::make_shared<shared_t>(o)) { } ~flyweight() {} auto state() const { return shared_state_; } auto &state() { return shared_state_; } void Operation(const unique_t &unique_state) const { std::cout << "flyweight: Displaying shared (" << *shared_state_ << ") and unique (" << unique_state << ") state.\n"; } friend std::ostream &operator<<(std::ostream &os, const flyweight &o) { return os << *o.shared_state_; }}; template<typename shared_t = shared_state_impl, typename unique_t = unique_state_impl, typename flyweight_t = flyweight<shared_t, unique_t>, typename hasher_t = std::hash<shared_t>> class flyweight_factory { public: flyweight_factory() {} explicit flyweight_factory(std::initializer_list<shared_t> args) { for (auto const &ss : args) { flyweights_.emplace(_hasher(ss), flyweight_t(ss)); } } flyweight_t get(shared_t const &shared_state) { auto key = _hasher(shared_state); if (this->flyweights_.find(key) == this->flyweights_.end()) { std::cout << "flyweight_factory: Can't find a flyweight, creating new one.\n"; this->flyweights_.emplace(key, flyweight_t(shared_state)); } else { std::cout << "flyweight_factory: Reusing existing flyweight.\n"; } return this->flyweights_.at(key); } void list() const { size_t count = this->flyweights_.size(); std::cout << "\nflyweight_factory: I have " << count << " flyweights:\n"; for (auto const &pair : this->flyweights_) { std::cout << pair.first << " => " << pair.second << "\n"; } } private: std::unordered_map<std::size_t, flyweight_t> flyweights_; hasher_t _hasher{}; }; } // namespace hicc::dp::flyweight::metaCopy the codeWe can then use the privilege factory directly as a derived class:
class vehicle : public flyweight_factory<shared_state_impl, unique_state_impl> { public: using flyweight_factory<shared_state_impl, unique_state_impl>::flyweight_factory; void AddCarToPoliceDatabase( const std::string &plates, const std::string &owner, const std::string &brand, const std::string &model, const std::string &color) { std::cout << "\nClient: Adding a car to database.\n"; auto const &flyweight = this->get({brand, model, color}); flyweight.Operation({owner, plates}); }};Copy the codeUsing flyweight_factory
::flyweight_factory; Is a new syntax since C++17 that copies all the constructors of a parent class to a derived class as is, so you don’t have to copy and paste code and change the class name.
In the vehicle template class we use the default flyweight
, but you can modify this in the flyweight_factory template argument to provide your own implementation of the privilege metaclass.
The test code
void test_flyweight_meta() {
using namespace hicc::dp::flyweight::meta;
auto factory = std::make_unique<vehicle>(
std::initializer_list<shared_state_impl>{
{"Chevrolet", "Camaro2018", "pink"},
{"Mercedes Benz", "C300", "black"},
{"Mercedes Benz", "C500", "red"},
{"BMW", "M5", "red"},
{"BMW", "X6", "white"}});
factory->list();
factory->AddCarToPoliceDatabase("CL234IR",
"James Doe",
"BMW",
"M5",
"red");
factory->AddCarToPoliceDatabase("CL234IR",
"James Doe",
"BMW",
"X1",
"red");
factory->list();
}
Copy the codeadditional
We used slightly different base classes shared_state_impl and unique_state_impl:
namespace hicc::dp::flyweight::meta { struct shared_state_impl { std::string brand_; std::string model_; std::string color_; shared_state_impl(const std::string &brand, const std::string &model, const std::string &color) : brand_(brand) , model_(model) , color_(color) { } shared_state_impl(shared_state_impl const &o) : brand_(o.brand_) , model_(o.model_) , color_(o.color_) { } friend std::ostream &operator<<(std::ostream &os, const shared_state_impl &ss) { return os << "[ " << ss.brand_ << " , " << ss.model_ << " , " << ss.color_ << " ]"; }}; struct unique_state_impl { std::string owner_; std::string plates_; unique_state_impl(const std::string &owner, const std::string &plates) : owner_(owner) , plates_(plates) { } friend std::ostream &operator<<(std::ostream &os, const unique_state_impl &us) { return os << "[ " << us.owner_ << " , " << us.plates_ << " ]"; }}; } // namespace hicc::dp::flyweight::meta namespace std { template<> struct hash<hicc::dp::flyweight::meta::shared_state_impl> { typedef hicc::dp::flyweight::meta::shared_state_impl argument_type; typedef std::size_t result_type; result_type operator()(argument_type const &s) const { result_type h1(std::hash<std::string>{}(s.brand_)); hash_combine(h1, s.model_, s.color_); return h1; }}; } // namespace stdCopy the codeThis is because we use STD ::hash technology in flyweight_factory to manage the key values of a share, so we must explicitly implement the STD :: Hash specialized version of shared_state_IMPl.
In this specialized version we make use of a special hash_combine function.
hash_combine
This is a very technical concept because it involves a magic number (MagicNum) 0x9e3779b9.
We provide a namesake extension in Hick-cxx/cmDR-cxx derived from Boost ::hash_combine:
namespace std { template<typename T, typename... Rest> inline void hash_combine(std::size_t &seed, T const &t, Rest &&... rest) { std::hash<T> hasher; seed ^= 0x9e3779b9 + (seed << 6) + (seed >> 2) + hasher(t); int i[] = {0, (hash_combine(seed, std::forward<Rest>(rest)), 0)... }; (void) (i); } template<typename T> inline void hash_combine(std::size_t &seed, T const &v) { std::hash<T> hasher; seed ^= 0x9e3779b9 + (seed << 6) + (seed >> 2) + hasher(v); } } // namespace stdCopy the codeIts job is to compute the hash value of a series of objects and combine them.
The simplest way to correctly combine a bunch of hash values is:
std::size_t h1 = std::hash<std::string>("hello");
std::size_t h2 = std::hash<std::string>("world");
std::size_t h = h1 | (h2 << 1);
Copy the codeBut there’s still a lot of discussion, and one of the best approaches (in C++) is a method derived from boost::hash_combine implementation code:
seed ^= hasher(v) + 0x9e3779b9 + (seed<<6) + (seed>>2);
Copy the codeThis is the best academic study known to date.
So who created the golden Ratio?A Hash Function for Hash Table Lookup 或 Hash Functions for Hash Table Lookup. Originally written by Bob Jenkins, originally published in DDJ journal 1997, the code was formed circa 1996. And this number, from the expression: \ frac {2 ^ {32}} {\ frac {1 + \ SQRT {5}} {2}} (
).
Epilogue
Well, it’s not all that great, but I did implement a vaguely generic flyweight_factory template class from C++17, so I’ll settle for it.