From 4a90b861d9b84edc879bc024f7e9bbf12be6c9a5 Mon Sep 17 00:00:00 2001 From: "arseny.kapoulkine" Date: Mon, 10 May 2010 14:58:28 +0000 Subject: Minor allocation refactoring and optimization git-svn-id: http://pugixml.googlecode.com/svn/trunk@404 99668b35-9821-0410-8761-19e4c4f06640 --- src/pugixml.cpp | 245 ++++++++++++++++++++++++++++++-------------------------- 1 file changed, 133 insertions(+), 112 deletions(-) (limited to 'src') diff --git a/src/pugixml.cpp b/src/pugixml.cpp index 73b5271..d14016f 100644 --- a/src/pugixml.cpp +++ b/src/pugixml.cpp @@ -55,6 +55,16 @@ using std::memcpy; typedef size_t uintptr_t; #endif +// Inlining controls +#if defined(_MSC_VER) && _MSC_VER >= 1300 +# define PUGIXML_NO_INLINE __declspec(noinline) +#elif defined(__GNUC__) +# define PUGIXML_NO_INLINE __attribute__((noinline)) +#else +# define PUGIXML_NO_INLINE +#endif + +// Simple static assertion #define STATIC_ASSERT(cond) { static const char condition_failed[(cond) ? 1 : -1] = {0}; (void)condition_failed[0]; } // Memory allocation @@ -243,13 +253,24 @@ namespace pugi struct xml_allocator { - xml_allocator(xml_memory_page* root): _root(root) + xml_allocator(xml_memory_page* root): _root(root), _busy_size(root ? root->busy_size : 0) + { + } + + ~xml_allocator() { + if (_root) _root->busy_size = _busy_size; } xml_memory_page* allocate_page(size_t data_size) { - size_t size = sizeof(xml_memory_page) + data_size; // $$$ slightly incorrect + #ifdef __GNUC__ + // To avoid offsetof warning (xml_memory_page is not POD) + xml_memory_page* dummy_page = 0; + size_t size = ((size_t)(uintptr_t)&dummy_page->data) + data_size; + #else + size_t size = offsetof(xml_memory_page, data) + data_size; + #endif // allocate block with some alignment, leaving memory for worst-case padding void* memory = global_allocate(size + xml_memory_page_alignment); @@ -271,26 +292,25 @@ namespace pugi global_deallocate(page->memory); } - void* allocate_memory_oob(size_t size, xml_memory_page*& out_page) + PUGIXML_NO_INLINE void* allocate_memory_oob(size_t size, xml_memory_page*& out_page) { const size_t large_allocation_threshold = xml_memory_page_size / 4; - xml_memory_page* page; + xml_memory_page* page = allocate_page(size <= large_allocation_threshold ? xml_memory_page_size : size); if (size <= large_allocation_threshold) { - page = allocate_page(xml_memory_page_size); + _root->busy_size = _busy_size; // insert page at the end of linked list page->prev = _root; _root->next = page; _root = page; + + _busy_size = size; } else { - // standalone page - page = allocate_page(size); - // insert page before the end of linked list assert(_root->prev); @@ -310,11 +330,11 @@ namespace pugi void* allocate_memory(size_t size, xml_memory_page*& out_page) { - if (_root->busy_size + size > xml_memory_page_size) return allocate_memory_oob(size, out_page); + if (_busy_size + size > xml_memory_page_size) return allocate_memory_oob(size, out_page); - void* buf = _root->data + _root->busy_size; + void* buf = _root->data + _busy_size; - _root->busy_size += size; + _busy_size += size; out_page = _root; @@ -326,6 +346,8 @@ namespace pugi assert(ptr >= page->data && ptr < page->data + xml_memory_page_size); (void)!ptr; + if (page == _root) page->busy_size = _busy_size; + page->freed_size += size; assert(page->freed_size <= page->busy_size); @@ -337,6 +359,7 @@ namespace pugi // top page freed, just reset sizes page->busy_size = page->freed_size = 0; + _busy_size = 0; } else { @@ -353,10 +376,6 @@ namespace pugi } } - xml_document_struct* allocate_document(); - xml_node_struct* allocate_node(xml_node_type type); - xml_attribute_struct* allocate_attribute(); - char_t* allocate_string(size_t length) { // get actual size, rounded up to pointer alignment boundary @@ -385,6 +404,7 @@ namespace pugi } xml_memory_page* _root; + size_t _busy_size; }; /// A 'name=value' XML attribute structure. @@ -395,14 +415,6 @@ namespace pugi { } - void destroy(xml_allocator& alloc) - { - if (header & xml_memory_page_name_allocated_mask) alloc.deallocate_string(name); - if (header & xml_memory_page_value_allocated_mask) alloc.deallocate_string(value); - - alloc.deallocate_memory(this, sizeof(xml_attribute_struct), reinterpret_cast(header & xml_memory_page_pointer_mask)); - } - uintptr_t header; char_t* name; ///< Pointer to attribute name. @@ -421,68 +433,6 @@ namespace pugi { } - void destroy(xml_allocator& alloc) - { - destroy(alloc, sizeof(xml_node_struct)); - } - - void destroy(xml_allocator& alloc, size_t size) - { - if (header & xml_memory_page_name_allocated_mask) alloc.deallocate_string(name); - if (header & xml_memory_page_value_allocated_mask) alloc.deallocate_string(value); - - for (xml_attribute_struct* attr = first_attribute; attr; ) - { - xml_attribute_struct* next = attr->next_attribute; - - attr->destroy(alloc); - - attr = next; - } - - for (xml_node_struct* node = first_child; node; ) - { - xml_node_struct* next = node->next_sibling; - - node->destroy(alloc); - - node = next; - } - - alloc.deallocate_memory(this, size, reinterpret_cast(header & xml_memory_page_pointer_mask)); - } - - xml_node_struct* append_node(xml_allocator& alloc, xml_node_type type = node_element) - { - xml_node_struct* child = alloc.allocate_node(type); - child->parent = this; - - if (last_child) - { - last_child->next_sibling = child; - child->prev_sibling = last_child; - last_child = child; - } - else first_child = last_child = child; - - return child; - } - - xml_attribute_struct* append_attribute(xml_allocator& alloc) - { - xml_attribute_struct* a = alloc.allocate_attribute(); - - if (last_attribute) - { - last_attribute->next_attribute = a; - a->prev_attribute = last_attribute; - last_attribute = a; - } - else first_attribute = last_attribute = a; - - return a; - } - uintptr_t header; xml_node_struct* parent; ///< Pointer to parent @@ -509,29 +459,104 @@ namespace pugi xml_allocator allocator; const char_t* buffer; }; +} + +// Low-level DOM operations +namespace +{ + using namespace pugi; - xml_document_struct* xml_allocator::allocate_document() + inline xml_attribute_struct* allocate_attribute(xml_allocator& alloc) { xml_memory_page* page; - void* memory = allocate_memory(sizeof(xml_document_struct), page); + void* memory = alloc.allocate_memory(sizeof(xml_attribute_struct), page); - return new (memory) xml_document_struct(page); + return new (memory) xml_attribute_struct(page); } - xml_node_struct* xml_allocator::allocate_node(xml_node_type type) + inline xml_node_struct* allocate_node(xml_allocator& alloc, xml_node_type type) { xml_memory_page* page; - void* memory = allocate_memory(sizeof(xml_node_struct), page); + void* memory = alloc.allocate_memory(sizeof(xml_node_struct), page); return new (memory) xml_node_struct(page, type); } - xml_attribute_struct* xml_allocator::allocate_attribute() + inline xml_document_struct* allocate_document(xml_allocator& alloc) { xml_memory_page* page; - void* memory = allocate_memory(sizeof(xml_attribute_struct), page); + void* memory = alloc.allocate_memory(sizeof(xml_document_struct), page); - return new (memory) xml_attribute_struct(page); + return new (memory) xml_document_struct(page); + } + + inline void destroy_attribute(xml_attribute_struct* a, xml_allocator& alloc) + { + uintptr_t header = a->header; + + if (header & xml_memory_page_name_allocated_mask) alloc.deallocate_string(a->name); + if (header & xml_memory_page_value_allocated_mask) alloc.deallocate_string(a->value); + + alloc.deallocate_memory(a, sizeof(xml_attribute_struct), reinterpret_cast(header & xml_memory_page_pointer_mask)); + } + + inline void destroy_node(xml_node_struct* n, xml_allocator& alloc) + { + uintptr_t header = n->header; + + if (header & xml_memory_page_name_allocated_mask) alloc.deallocate_string(n->name); + if (header & xml_memory_page_value_allocated_mask) alloc.deallocate_string(n->value); + + for (xml_attribute_struct* attr = n->first_attribute; attr; ) + { + xml_attribute_struct* next = attr->next_attribute; + + destroy_attribute(attr, alloc); + + attr = next; + } + + for (xml_node_struct* child = n->first_child; child; ) + { + xml_node_struct* next = child->next_sibling; + + destroy_node(child, alloc); + + child = next; + } + + alloc.deallocate_memory(n, sizeof(xml_node_struct), reinterpret_cast(header & xml_memory_page_pointer_mask)); + } + + PUGIXML_NO_INLINE xml_node_struct* append_node(xml_node_struct* node, xml_allocator& alloc, xml_node_type type = node_element) + { + xml_node_struct* child = allocate_node(alloc, type); + child->parent = node; + + if (node->last_child) + { + node->last_child->next_sibling = child; + child->prev_sibling = node->last_child; + node->last_child = child; + } + else node->first_child = node->last_child = child; + + return child; + } + + PUGIXML_NO_INLINE xml_attribute_struct* append_attribute_ll(xml_node_struct* node, xml_allocator& alloc) + { + xml_attribute_struct* a = allocate_attribute(alloc); + + if (node->last_attribute) + { + node->last_attribute->next_attribute = a; + a->prev_attribute = node->last_attribute; + node->last_attribute = a; + } + else node->first_attribute = node->last_attribute = a; + + return a; } } @@ -1683,12 +1708,12 @@ namespace struct xml_parser { - xml_allocator& alloc; + xml_allocator alloc; // Parser utilities. #define SKIPWS() { while (is_chartype(*s, ct_space)) ++s; } #define OPTSET(OPT) ( optmsk & OPT ) - #define PUSHNODE(TYPE) { cursor = cursor->append_node(alloc,TYPE); } + #define PUSHNODE(TYPE) { cursor = append_node(cursor, alloc, TYPE); } #define POPNODE() { cursor = cursor->parent; } #define SCANFOR(X) { while (*s != 0 && !(X)) ++s; } #define SCANWHILE(X) { while ((X)) ++s; } @@ -1696,7 +1721,7 @@ namespace #define THROW_ERROR(err, m) return make_parse_result(err, m - buffer_start, __LINE__) #define CHECK_ERROR(err, m) { if (*s == 0) THROW_ERROR(err, m); } - xml_parser(xml_allocator& alloc): alloc(alloc) + xml_parser(const xml_allocator& alloc): alloc(alloc) { } @@ -2005,7 +2030,7 @@ namespace if (is_chartype(*s, ct_start_symbol)) // <... #... { - xml_attribute_struct* a = cursor->append_attribute(alloc); // Make space for this attribute. + xml_attribute_struct* a = append_attribute_ll(cursor, alloc); // Make space for this attribute. a->name = s; // Save the offset. SCANWHILE(is_chartype(*s, ct_symbol)); // Scan for a terminator. @@ -2207,8 +2232,8 @@ namespace // perform actual parsing xml_parse_result result = parser.parse(buffer, xmldoc, optmsk, endch); - // fixup page live_sizes $$$ - // for (xml_memory_page* page = alloc._root; page; page = page->prev) page->live_size = page->busy_size; + // update allocator state + alloc = parser.alloc; // since we removed last character, we have to handle the only possible false positive if (result && endch == '<') @@ -2221,10 +2246,6 @@ namespace return result; } - - private: - xml_parser(const xml_parser&); - const xml_parser& operator=(const xml_parser&); }; // Output facilities @@ -3435,7 +3456,7 @@ namespace pugi { if (type() != node_element && type() != node_declaration) return xml_attribute(); - xml_attribute a(_root->append_attribute(get_allocator())); + xml_attribute a(append_attribute_ll(_root, get_allocator())); a.set_name(name); return a; @@ -3452,7 +3473,7 @@ namespace pugi if (cur != _root->first_attribute) return xml_attribute(); - xml_attribute a(get_allocator().allocate_attribute()); + xml_attribute a(allocate_attribute(get_allocator())); a.set_name(name); if (attr._attr->prev_attribute) @@ -3478,7 +3499,7 @@ namespace pugi if (cur != _root->first_attribute) return xml_attribute(); - xml_attribute a(get_allocator().allocate_attribute()); + xml_attribute a(allocate_attribute(get_allocator())); a.set_name(name); if (attr._attr->next_attribute) @@ -3527,7 +3548,7 @@ namespace pugi { if ((this->type() != node_element && this->type() != node_document) || type == node_document || type == node_null) return xml_node(); - return xml_node(_root->append_node(get_allocator(), type)); + return xml_node(append_node(_root, get_allocator(), type)); } xml_node xml_node::insert_child_before(xml_node_type type, const xml_node& node) @@ -3535,7 +3556,7 @@ namespace pugi if ((this->type() != node_element && this->type() != node_document) || type == node_document || type == node_null) return xml_node(); if (node.parent() != *this) return xml_node(); - xml_node n(get_allocator().allocate_node(type)); + xml_node n(allocate_node(get_allocator(), type)); n._root->parent = _root; if (node._root->prev_sibling) @@ -3555,7 +3576,7 @@ namespace pugi if ((this->type() != node_element && this->type() != node_document) || type == node_document || type == node_null) return xml_node(); if (node.parent() != *this) return xml_node(); - xml_node n(get_allocator().allocate_node(type)); + xml_node n(allocate_node(get_allocator(), type)); n._root->parent = _root; if (node._root->next_sibling) @@ -3619,7 +3640,7 @@ namespace pugi if (a._attr->prev_attribute) a._attr->prev_attribute->next_attribute = a._attr->next_attribute; else _root->first_attribute = a._attr->next_attribute; - a._attr->destroy(get_allocator()); + destroy_attribute(a._attr, get_allocator()); } void xml_node::remove_child(const char_t* name) @@ -3637,7 +3658,7 @@ namespace pugi if (n._root->prev_sibling) n._root->prev_sibling->next_sibling = n._root->next_sibling; else _root->first_child = n._root->next_sibling; - n._root->destroy(get_allocator()); + destroy_node(n._root, get_allocator()); } xml_node xml_node::find_child_by_attribute(const char_t* name, const char_t* attr_name, const char_t* attr_value) const @@ -4071,7 +4092,7 @@ namespace pugi // allocate new root xml_allocator alloc(_memory.next ? _memory.next : &_memory); - _root = alloc.allocate_document(); + _root = allocate_document(alloc); // setup allocator xml_allocator& a = static_cast(_root)->allocator; -- cgit v1.2.3