From 334e70455b7f8a4607fe99dc12710d48169113a6 Mon Sep 17 00:00:00 2001 From: est31 Date: Sat, 4 Apr 2015 01:33:34 +0200 Subject: Crafting speedup This greatly increases crafting performance, especially in worlds with many mods. Approved by @kwolekr. Introduces a hash-type-layered fall-through mechanism, where every layer specifies one hash algorithm, and the "deeper the fall", the more collisions to expect for the algorithm. One Craft definition only resides at one layer, which improves speed for lower layers (and a complete fail), due to most craft definitions residing at high layers. Due to the fall-through design, the undocumented behaviour that later craft recipes override older ones had to be weaked up a bit, but craft recipes with the same hash and layer will still override. --- src/craftdef.cpp | 338 +++++++++++++++++++++++++++++++++++++++++++------------ 1 file changed, 263 insertions(+), 75 deletions(-) (limited to 'src/craftdef.cpp') diff --git a/src/craftdef.cpp b/src/craftdef.cpp index bca16a4c6..749490f62 100644 --- a/src/craftdef.cpp +++ b/src/craftdef.cpp @@ -27,10 +27,48 @@ with this program; if not, write to the Free Software Foundation, Inc., #include "gamedef.h" #include "inventory.h" #include "util/serialize.h" +#include "util/string.h" #include "util/numeric.h" #include "strfnd.h" #include "exceptions.h" +inline bool isGroupRecipeStr(const std::string &rec_name) +{ + return str_starts_with(rec_name, std::string("group:")); +} + +inline u64 getHashForString(const std::string &recipe_str) +{ + /*errorstream << "Hashing craft string \"" << recipe_str << "\"";*/ + return murmur_hash_64_ua(recipe_str.data(), recipe_str.length(), 0xdeadbeef); +} + +static u64 getHashForGrid(CraftHashType type, const std::vector &grid_names) +{ + switch (type) { + case CRAFT_HASH_TYPE_ITEM_NAMES: { + std::ostringstream os; + bool is_first = true; + for (size_t i = 0; i < grid_names.size(); i++) { + if (grid_names[i] != "") { + os << (is_first ? "" : "\n") << grid_names[i]; + is_first = false; + } + } + return getHashForString(os.str()); + } case CRAFT_HASH_TYPE_COUNT: { + u64 cnt = 0; + for (size_t i = 0; i < grid_names.size(); i++) + if (grid_names[i] != "") + cnt++; + return cnt; + } case CRAFT_HASH_TYPE_UNHASHED: + return 0; + } + // invalid CraftHashType + assert(false); +} + // Check if input matches recipe // Takes recipe groups into account static bool inputItemMatchesRecipe(const std::string &inp_name, @@ -41,7 +79,7 @@ static bool inputItemMatchesRecipe(const std::string &inp_name, return true; // Group - if(rec_name.substr(0,6) == "group:" && idef->isKnown(inp_name)){ + if (isGroupRecipeStr(rec_name) && idef->isKnown(inp_name)) { const struct ItemDefinition &def = idef->get(inp_name); Strfnd f(rec_name.substr(6)); bool all_groups_match = true; @@ -405,8 +443,13 @@ bool CraftDefinitionShaped::check(const CraftInput &input, IGameDef *gamedef) co if(!craftGetBounds(inp_names, inp_width, inp_min_x, inp_max_x, inp_min_y, inp_max_y)) return false; // it was empty + std::vector rec_names; + if (hash_inited) + rec_names = recipe_names; + else + rec_names = craftGetItemNames(recipe, gamedef); + // Get recipe item matrix - std::vector rec_names = craftGetItemNames(recipe, gamedef); unsigned int rec_width = width; if(rec_width == 0) return false; @@ -462,6 +505,43 @@ void CraftDefinitionShaped::decrementInput(CraftInput &input, IGameDef *gamedef) craftDecrementOrReplaceInput(input, replacements, gamedef); } +CraftHashType CraftDefinitionShaped::getHashType() const +{ + assert(hash_inited); //pre-condition + bool has_group = false; + for (size_t i = 0; i < recipe_names.size(); i++) { + if (isGroupRecipeStr(recipe_names[i])) { + has_group = true; + break; + } + } + if (has_group) + return CRAFT_HASH_TYPE_COUNT; + else + return CRAFT_HASH_TYPE_ITEM_NAMES; +} + +u64 CraftDefinitionShaped::getHash(CraftHashType type) const +{ + assert(hash_inited); //pre-condition + if ((type == CRAFT_HASH_TYPE_ITEM_NAMES) || (type == CRAFT_HASH_TYPE_COUNT)) { + std::vector rec_names = recipe_names; + std::sort(rec_names.begin(), rec_names.end()); + return getHashForGrid(type, rec_names); + } else { + //illegal hash type for this CraftDefinition (pre-condition) + assert(false); + } +} + +void CraftDefinitionShaped::initHash(IGameDef *gamedef) +{ + if (hash_inited) + return; + hash_inited = true; + recipe_names = craftGetItemNames(recipe, gamedef); +} + std::string CraftDefinitionShaped::dump() const { std::ostringstream os(std::ios::binary); @@ -526,12 +606,18 @@ bool CraftDefinitionShapeless::check(const CraftInput &input, IGameDef *gamedef) return false; } - // Try with all permutations of the recipe - std::vector recipe_copy = craftGetItemNames(recipe, gamedef); - // Start from the lexicographically first permutation (=sorted) - std::sort(recipe_copy.begin(), recipe_copy.end()); - //while(std::prev_permutation(recipe_copy.begin(), recipe_copy.end())){} - do{ + std::vector recipe_copy; + if (hash_inited) + recipe_copy = recipe_names; + else { + recipe_copy = craftGetItemNames(recipe, gamedef); + std::sort(recipe_copy.begin(), recipe_copy.end()); + } + + // Try with all permutations of the recipe, + // start from the lexicographically first permutation (=sorted), + // recipe_names is pre-sorted + do { // If all items match, the recipe matches bool all_match = true; //dstream<<"Testing recipe (output="<::const_iterator + for (std::vector::const_iterator i = input.items.begin(); - i != input.items.end(); i++) - { - if(!i->empty()) - { + i != input.items.end(); i++) { + if (!i->empty()) { all_empty = false; break; } } - if(all_empty) + if (all_empty) return false; - // Walk crafting definitions from back to front, so that later - // definitions can override earlier ones. - for(std::vector::const_reverse_iterator - i = m_craft_definitions.rbegin(); - i != m_craft_definitions.rend(); i++) - { - CraftDefinition *def = *i; + std::vector input_names; + input_names = craftGetItemNames(input.items, gamedef); + std::sort(input_names.begin(), input_names.end()); - /*infostream<<"Checking "<dump()<check(input, gamedef)) - { + /*errorstream << "Checking type " << type << " with hash " << hash << std::endl;*/ + + // We'd like to do "const [...] hash_collisions = m_craft_defs[type][hash];" + // but that doesn't compile for some reason. This does. + std::map >::const_iterator + col_iter = (m_craft_defs[type]).find(hash); + + if (col_iter == (m_craft_defs[type]).end()) + continue; + + const std::vector &hash_collisions = col_iter->second; + // Walk crafting definitions from back to front, so that later + // definitions can override earlier ones. + for (std::vector::const_reverse_iterator + i = hash_collisions.rbegin(); + i != hash_collisions.rend(); i++) { + CraftDefinition *def = *i; + + /*errorstream << "Checking " << input.dump() << std::endl + << " against " << def->dump() << std::endl;*/ + + if (def->check(input, gamedef)) { // Get output, then decrement input (if requested) output = def->getOutput(input, gamedef); - if(decrementInput) + if (decrementInput) def->decrementInput(input, gamedef); + /*errorstream << "Check RETURNS TRUE" << std::endl;*/ return true; } } - catch(SerializationError &e) - { - errorstream<<"getCraftResult: ERROR: " - <<"Serialization error in recipe " - <dump()<::const_iterator - i = m_craft_definitions.begin(); - i != m_craft_definitions.end(); i++) - { - os<<(*i)->dump()<<"\n"; + os << "Crafting definitions:\n"; + for (int type = 0; type <= craft_hash_type_max; type++) { + for (std::map >::const_iterator + i = (m_craft_defs[type]).begin(); + i != (m_craft_defs[type]).end(); i++) { + for (std::vector::const_iterator + ii = i->second.begin(); ii != i->second.end(); ii++) { + os << "type " << type << " hash " << i->first << (*ii)->dump() << "\n"; + } + } } return os.str(); } @@ -973,7 +1168,7 @@ public: { verbosestream<<"registerCraft: registering craft definition: " <dump()<::iterator - i = m_craft_definitions.begin(); - i != m_craft_definitions.end(); i++){ - delete *i; + for (int type = 0; type <= craft_hash_type_max; type++) { + for (std::map >::iterator + i = m_craft_defs[type].begin(); + i != m_craft_defs[type].end(); i++) { + for (std::vector::iterator + ii = i->second.begin(); ii != i->second.end(); ii++) { + delete *ii; + } + i->second.clear(); + } + m_craft_defs[type].clear(); } - m_craft_definitions.clear(); m_output_craft_definitions.clear(); } - virtual void serialize(std::ostream &os) const + virtual void initHashes(IGameDef *gamedef) { - writeU8(os, 0); // version - u16 count = m_craft_definitions.size(); - writeU16(os, count); - for(std::vector::const_iterator - i = m_craft_definitions.begin(); - i != m_craft_definitions.end(); i++){ + // Move the CraftDefs from the unhashed layer into layers higher up. + for (std::vector::iterator + i = (m_craft_defs[(int) CRAFT_HASH_TYPE_UNHASHED][0]).begin(); + i != (m_craft_defs[(int) CRAFT_HASH_TYPE_UNHASHED][0]).end(); i++) { CraftDefinition *def = *i; - // Serialize wrapped in a string - std::ostringstream tmp_os(std::ios::binary); - def->serialize(tmp_os); - os<initHash(gamedef); + CraftHashType type = def->getHashType(); + u64 hash = def->getHash(type); + + // Enter the definition + m_craft_defs[type][hash].push_back(def); } + m_craft_defs[(int) CRAFT_HASH_TYPE_UNHASHED][0].clear(); } private: - std::vector m_craft_definitions; + //TODO: change both maps to unordered_map when c++11 can be used + std::vector > > m_craft_defs; std::map > m_output_craft_definitions; }; -- cgit v1.2.3