From b905f4b8aa74d2178ae80f2f5d5323a649d63229 Mon Sep 17 00:00:00 2001 From: Tim Moore Date: Thu, 5 Nov 2009 09:06:18 +0100 Subject: [PATCH] Property system optimizations Profiling startup with the new effects code exposed some performance gotchas. The objective is to reduce allocation of std::string temporaries, especially when looking up node path names. Also, I changed some paths to initialize strings with strings instead of char *; this causes less allocation, at least with glibc. Also, eliminate the old version of find_node and its helper functions by writing the template version of find_node_aux to handle an explicit index parameter. Also, add const char[] as an internal property type This doesn't actually add a new type to the property system, but allows using character arrays as arguments to certain templates. --- simgear/props/props.cxx | 388 ++++++++++++++++++++----------------- simgear/props/props.hxx | 41 ++-- simgear/props/props_io.cxx | 11 +- 3 files changed, 241 insertions(+), 199 deletions(-) diff --git a/simgear/props/props.cxx b/simgear/props/props.cxx index 0bc56dcd..15cfabe0 100644 --- a/simgear/props/props.cxx +++ b/simgear/props/props.cxx @@ -19,6 +19,11 @@ #include #include +#include +#include +#include +#include + #include #if PROPS_STANDALONE @@ -78,49 +83,36 @@ public: // Local path normalization code. //////////////////////////////////////////////////////////////////////// -/** - * A component in a path. - */ -struct PathComponent -{ - string name; - int index; -}; - /** * Parse the name for a path component. * * Name: [_a-zA-Z][-._a-zA-Z0-9]* */ -static inline const string -parse_name (const string &path, int &i) + +template +inline Range +parse_name (const Range &path) { - string name = ""; - int max = path.size(); + typename Range::iterator i = path.begin(); + typename Range::iterator max = path.end(); - if (path[i] == '.') { + if (*i == '.') { i++; - if (i < max && path[i] == '.') { + if (i != path.end() && *i == '.') { i++; - name = ".."; - } else { - name = "."; } - if (i < max && path[i] != '/') - throw string("illegal character after " + name); - } - - else if (isalpha(path[i]) || path[i] == '_') { - name += path[i]; + if (i != max && *i != '/') + throw string("illegal character after . or .."); + } else if (isalpha(*i) || *i == '_') { i++; // The rules inside a name are a little // less restrictive. - while (i < max) { - if (isalpha(path[i]) || isdigit(path[i]) || path[i] == '_' || - path[i] == '-' || path[i] == '.') { - name += path[i]; - } else if (path[i] == '[' || path[i] == '/') { + while (i != max) { + if (isalpha(*i) || isdigit(*i) || *i == '_' || + *i == '-' || *i == '.') { + // name += path[i]; + } else if (*i == '[' || *i == '/') { break; } else { throw string("name may contain only ._- and alphanumeric characters"); @@ -130,90 +122,24 @@ parse_name (const string &path, int &i) } else { - if (name.size() == 0) + if (path.begin() == i) throw string("name must begin with alpha or '_'"); } - - return name; + return Range(path.begin(), i); } - -/** - * Parse the optional integer index for a path component. - * - * Index: "[" [0-9]+ "]" - */ -static inline int -parse_index (const string &path, int &i) +// Validate the name of a single node +inline bool validateName(const string& name) { - int index = 0; - - if (path[i] != '[') - return 0; - else - i++; - - for (int max = path.size(); i < max; i++) { - if (isdigit(path[i])) { - index = (index * 10) + (path[i] - '0'); - } else if (path[i] == ']') { - i++; - return index; - } else { - break; - } - } - - throw string("unterminated index (looking for ']')"); -} - - -/** - * Parse a single path component. - * - * Component: Name Index? - */ -static inline PathComponent -parse_component (const string &path, int &i) -{ - PathComponent component; - component.name = parse_name(path, i); - if (component.name[0] != '.') - component.index = parse_index(path, i); - else - component.index = -1; - return component; -} - - -/** - * Parse a path into its components. - */ -static void -parse_path (const string &path, vector &components) -{ - int pos = 0; - int max = path.size(); - - // Check for initial '/' - if (path[pos] == '/') { - PathComponent root; - root.name = ""; - root.index = -1; - components.push_back(root); - pos++; - while (pos < max && path[pos] == '/') - pos++; - } - - while (pos < max) { - components.push_back(parse_component(path, pos)); - while (pos < max && path[pos] == '/') - pos++; - } + using namespace boost; + if (name.empty()) + return false; + if (!isalpha(name[0]) && name[0] != '_') + return false; + return all(make_iterator_range(name.begin(), name.end()), + is_alnum() || is_any_of("_-.")); } - //////////////////////////////////////////////////////////////////////// // Other static utility functions. @@ -242,16 +168,18 @@ compare_strings (const char * s1, const char * s2) /** * Locate a child node by name and index. */ +template static int -find_child (const char * name, int index, const PropertyList& nodes) +find_child (Itr begin, Itr end, int index, const PropertyList& nodes) { int nNodes = nodes.size(); + boost::iterator_range name(begin, end); for (int i = 0; i < nNodes; i++) { SGPropertyNode * node = nodes[i]; // searching for a mathing index is a lot less time consuming than // comparing two strings so do that first. - if (node->getIndex() == index && compare_strings(node->getName(), name)) + if (node->getIndex() == index && boost::equals(node->getName(), name)) return i; } return -1; @@ -277,55 +205,137 @@ find_last_child (const char * name, const PropertyList& nodes) return index; } - -/** - * Locate another node, given a relative path. - */ -static SGPropertyNode * -find_node (SGPropertyNode * current, - const vector &components, - int position, - bool create) +template +inline SGPropertyNode* +SGPropertyNode::getExistingChild (Itr begin, Itr end, int index, bool create) { - // Run off the end of the list - if (current == 0) { - return 0; - } - - // Success! This is the one we want. - else if (position >= (int)components.size()) { - return (current->getAttribute(SGPropertyNode::REMOVED) ? 0 : current); + int pos = find_child(begin, end, index, _children); + if (pos >= 0) { + return _children[pos]; + } else if (create) { + SGPropertyNode_ptr node; + pos = find_child(begin, end, index, _removedChildren); + if (pos >= 0) { + PropertyList::iterator it = _removedChildren.begin(); + it += pos; + node = _removedChildren[pos]; + _removedChildren.erase(it); + node->setAttribute(REMOVED, false); + _children.push_back(node); + fireChildAdded(node); + return node; + } } + return 0; +} + +template +SGPropertyNode * +SGPropertyNode::getChildImpl (Itr begin, Itr end, int index, bool create) +{ + SGPropertyNode* node = getExistingChild(begin, end, index, create); - // Empty component means root. - else if (components[position].name == "") { - return find_node(current->getRootNode(), components, position + 1, create); - } + if (node) { + return node; + } else if (create) { + node = new SGPropertyNode(begin, end, index, this); + _children.push_back(node); + fireChildAdded(node); + return node; + } else { + return 0; + } +} - // . means current directory - else if (components[position].name == ".") { - return find_node(current, components, position + 1, create); +template +SGPropertyNode* +find_node_aux(SGPropertyNode * current, SplitItr& itr, bool create, + int last_index) +{ + typedef typename SplitItr::value_type Range; + // Run off the end of the list + if (current == 0) { + return 0; } - // .. means parent directory - else if (components[position].name == "..") { + // Success! This is the one we want. + if (itr.eof()) + return current; + Range token = *itr; + // Empty name at this point is empty, not root. + if (token.empty()) + return find_node_aux(current, ++itr, create, last_index); + Range name = parse_name(token); + if (equals(name, ".")) + return find_node_aux(current, ++itr, create, last_index); + if (equals(name, "..")) { SGPropertyNode * parent = current->getParent(); if (parent == 0) throw string("attempt to move past root with '..'"); - else - return find_node(parent, components, position + 1, create); - } - - // Otherwise, a child name - else { - SGPropertyNode * child = - current->getChild(components[position].name.c_str(), - components[position].index, - create); - return find_node(child, components, position + 1, create); + return find_node_aux(parent, ++itr, create, last_index); + } + int index = -1; + if (last_index >= 0) { + // If we are at the last token and last_index is valid, use + // last_index as the index value + bool lastTok = true; + while (!(++itr).eof()) { + if (!itr->empty()) { + lastTok = false; + break; + } + } + if (lastTok) + index = last_index; + } else { + ++itr; + } + + if (index < 0) { + index = 0; + if (name.end() != token.end()) { + if (*name.end() == '[') { + typename Range::iterator i = name.end() + 1, end = token.end(); + for (;i != end; ++i) { + if (isdigit(*i)) { + index = (index * 10) + (*i - '0'); + } else { + break; + } + } + if (i == token.end() || *i != ']') + throw string("unterminated index (looking for ']')"); + } else { + throw string("illegal characters in token: ") + + string(name.begin(), name.end()); + } + } } + return find_node_aux(current->getChildImpl(name.begin(), name.end(), + index, create), itr, create, + last_index); } +// Internal function for parsing property paths. last_index provides +// and index value for the last node name token, if supplied. +template +SGPropertyNode* +find_node (SGPropertyNode * current, + const Range& path, + bool create, + int last_index = -1) +{ + using namespace boost; + typedef split_iterator::type> + PathSplitIterator; + + PathSplitIterator itr + = make_split_iterator(path, first_finder("/", is_equal())); + if (*path.begin() == '/') + return find_node_aux(current->getRootNode(), itr, create, last_index); + else + return find_node_aux(current, itr, create, last_index); +} //////////////////////////////////////////////////////////////////////// @@ -695,10 +705,12 @@ SGPropertyNode::SGPropertyNode (const SGPropertyNode &node) /** * Convenience constructor. */ -SGPropertyNode::SGPropertyNode (const char * name, +template +SGPropertyNode::SGPropertyNode (Itr begin, Itr end, int index, SGPropertyNode * parent) : _index(index), + _name(begin, end), _parent(parent), _path_cache(0), _type(props::NONE), @@ -706,14 +718,29 @@ SGPropertyNode::SGPropertyNode (const char * name, _attr(READ|WRITE), _listeners(0) { - int i = 0; _local_val.string_val = 0; _value.val = 0; - _name = parse_name(name, i); - if (i != int(strlen(name)) || name[0] == '.') - throw string("plain name expected instead of '") + name + '\''; + if (!validateName(_name)) + throw string("plain name expected instead of '") + _name + '\''; } +SGPropertyNode::SGPropertyNode (const string& name, + int index, + SGPropertyNode * parent) + : _index(index), + _name(name), + _parent(parent), + _path_cache(0), + _type(props::NONE), + _tied(false), + _attr(READ|WRITE), + _listeners(0) +{ + _local_val.string_val = 0; + _value.val = 0; + if (!validateName(name)) + throw string("plain name expected instead of '") + _name + '\''; +} /** * Destructor. @@ -801,7 +828,7 @@ SGPropertyNode::addChild (const char * name) int pos = find_last_child(name, _children)+1; SGPropertyNode_ptr node; - node = new SGPropertyNode(name, pos, this); + node = new SGPropertyNode(name, name + strlen(name), pos, this); _children.push_back(node); fireChildAdded(node); return node; @@ -837,40 +864,38 @@ SGPropertyNode::getChild (int position) const /** * Get a non-const child by name and index, creating if necessary. */ + SGPropertyNode * SGPropertyNode::getChild (const char * name, int index, bool create) { - int pos = find_child(name, index, _children); - if (pos >= 0) { - return _children[pos]; - } else if (create) { - SGPropertyNode_ptr node; - pos = find_child(name, index, _removedChildren); - if (pos >= 0) { - PropertyList::iterator it = _removedChildren.begin(); - it += pos; - node = _removedChildren[pos]; - _removedChildren.erase(it); - node->setAttribute(REMOVED, false); - } else { + return getChildImpl(name, name + strlen(name), index, create); +} + +SGPropertyNode * +SGPropertyNode::SGPropertyNode::getChild (const string& name, int index, + bool create) +{ + SGPropertyNode* node = getExistingChild(name.begin(), name.end(), index, + create); + if (node) { + return node; + } else if (create) { node = new SGPropertyNode(name, index, this); + _children.push_back(node); + fireChildAdded(node); + return node; + } else { + return 0; } - _children.push_back(node); - fireChildAdded(node); - return node; - } else { - return 0; - } } - /** * Get a const child by name and index. */ const SGPropertyNode * SGPropertyNode::getChild (const char * name, int index) const { - int pos = find_child(name, index, _children); + int pos = find_child(name, name + strlen(name), index, _children); if (pos >= 0) return _children[pos]; else @@ -945,7 +970,7 @@ SGPropertyNode_ptr SGPropertyNode::removeChild (const char * name, int index, bool keep) { SGPropertyNode_ptr ret; - int pos = find_child(name, index, _children); + int pos = find_child(name, name + strlen(name), index, _children); if (pos >= 0) ret = removeChild(pos, keep); return ret; @@ -1710,14 +1735,16 @@ SGPropertyNode::getRootNode () const SGPropertyNode * SGPropertyNode::getNode (const char * relative_path, bool create) { + using namespace boost; if (_path_cache == 0) _path_cache = new hash_table; SGPropertyNode * result = _path_cache->get(relative_path); if (result == 0) { - vector components; - parse_path(relative_path, components); - result = find_node(this, components, 0, create); + result = find_node(this, + make_iterator_range(relative_path, relative_path + + strlen(relative_path)), + create); if (result != 0) _path_cache->put(relative_path, result); } @@ -1728,11 +1755,10 @@ SGPropertyNode::getNode (const char * relative_path, bool create) SGPropertyNode * SGPropertyNode::getNode (const char * relative_path, int index, bool create) { - vector components; - parse_path(relative_path, components); - if (components.size() > 0) - components.back().index = index; - return find_node(this, components, 0, create); + using namespace boost; + return find_node(this, make_iterator_range(relative_path, relative_path + + strlen(relative_path)), + create, index); } const SGPropertyNode * diff --git a/simgear/props/props.hxx b/simgear/props/props.hxx index dc987134..ee2e6b6f 100644 --- a/simgear/props/props.hxx +++ b/simgear/props/props.hxx @@ -161,6 +161,7 @@ DEFINTERNALPROP(long, LONG); DEFINTERNALPROP(float, FLOAT); DEFINTERNALPROP(double, DOUBLE); DEFINTERNALPROP(const char *, STRING); +DEFINTERNALPROP(const char[], STRING); #undef DEFINTERNALPROP template<> @@ -804,6 +805,11 @@ public: */ const char * getName () const { return _name.c_str(); } + /** + * Get the node's simple name as a string. + */ + const std::string& getNameString () const { return _name; } + /** * Get the node's pretty display name, with subscript when needed. */ @@ -875,17 +881,10 @@ public: /** * Get a child node by name and index. */ - SGPropertyNode * getChild (const char * name, int index = 0, - bool create = false); - - /** - * Get a child node by name and index. - */ + SGPropertyNode * getChild (const char* name, int index = 0, + bool create = false); SGPropertyNode * getChild (const std::string& name, int index = 0, - bool create = false) - { return getChild(name.c_str(), index, create); } - - + bool create = false); /** * Get a const child node by name and index. */ @@ -1223,6 +1222,12 @@ public: bool setValue(const T& val, typename boost::disable_if_c::Internal> ::type* dummy = 0); + + template + bool setValue(const char (&val)[N]) + { + return setValue(&val[0]); + } /** * Print the value of the property to a stream. @@ -1604,8 +1609,9 @@ protected: /** * Protected constructor for making new nodes on demand. */ - SGPropertyNode (const char * name, int index, SGPropertyNode * parent); - + SGPropertyNode (const std::string& name, int index, SGPropertyNode * parent); + template + SGPropertyNode (Itr begin, Itr end, int index, SGPropertyNode * parent); private: @@ -1743,7 +1749,16 @@ private: unsigned int _data_length; bucket ** _data; }; - + // Pass name as a pair of iterators + template + SGPropertyNode * getChildImpl (Itr begin, Itr end, int index = 0, bool create = false); + // very internal method + template + SGPropertyNode* getExistingChild (Itr begin, Itr end, int index, bool create); + // very internal path parsing function + template + friend SGPropertyNode* find_node_aux(SGPropertyNode * current, SplitItr& itr, + bool create, int last_index); }; // Convenience functions for use in templates diff --git a/simgear/props/props_io.cxx b/simgear/props/props_io.cxx index 232e3c2c..622ef367 100644 --- a/simgear/props/props_io.cxx +++ b/simgear/props/props_io.cxx @@ -187,16 +187,17 @@ PropsVisitor::startElement (const char * name, const XMLAttributes &atts) // Get the index. attval = atts.getValue("n"); int index = 0; + string strName(name); if (attval != 0) { index = atoi(attval); - st.counters[name] = SG_MAX2(st.counters[name], index+1); + st.counters[strName] = SG_MAX2(st.counters[strName], index+1); } else { - index = st.counters[name]; - st.counters[name]++; + index = st.counters[strName]; + st.counters[strName]++; } // Got the index, so grab the node. - SGPropertyNode * node = st.node->getChild(name, index, true); + SGPropertyNode * node = st.node->getChild(strName, index, true); if (!node->getAttribute(SGPropertyNode::WRITE)) { SG_LOG(SG_INPUT, SG_ALERT, "Not overwriting write-protected property " << node->getPath(true)); @@ -678,7 +679,7 @@ copyProperties (const SGPropertyNode *in, SGPropertyNode *out) int nChildren = in->nChildren(); for (int i = 0; i < nChildren; i++) { const SGPropertyNode * in_child = in->getChild(i); - SGPropertyNode * out_child = out->getChild(in_child->getName(), + SGPropertyNode * out_child = out->getChild(in_child->getNameString(), in_child->getIndex(), true); if (!copyProperties(in_child, out_child)) -- 2.39.5