From 757c4943401d6a1922954cdac6ab8a901c8cbb51 Mon Sep 17 00:00:00 2001 From: Arseny Kapoulkine Date: Sun, 1 Jun 2014 19:12:36 +0000 Subject: Improve XPath allocator performance When allocating new pages, make sure that the page has at least 1/4 of the base page size free. This makes sure that we can do small allocations after big allocations (i.e. huge node lists) without doing a heap alloc. This is important because XPath stack code always reclaims extra pages after evaluating sub-expressions, so allocating a small chunk of memory and then rolling the state back is a common case (filtering a node list using a predicate usually does this). A better solution involves smarter allocation rollback strategy, but the implemented solution is simple and practical. git-svn-id: https://pugixml.googlecode.com/svn/trunk@999 99668b35-9821-0410-8761-19e4c4f06640 --- src/pugixml.cpp | 16 +++++++++++----- tests/test_xpath.cpp | 4 ++-- 2 files changed, 13 insertions(+), 7 deletions(-) diff --git a/src/pugixml.cpp b/src/pugixml.cpp index 754f92f..085d4e3 100644 --- a/src/pugixml.cpp +++ b/src/pugixml.cpp @@ -6069,6 +6069,7 @@ PUGI__NS_BEGIN struct xpath_memory_block { xpath_memory_block* next; + size_t capacity; char data[ #ifdef PUGIXML_MEMORY_XPATH_PAGE_SIZE @@ -6098,12 +6099,10 @@ PUGI__NS_BEGIN void* allocate_nothrow(size_t size) { - const size_t block_capacity = sizeof(_root->data); - // align size so that we're able to store pointers in subsequent blocks size = (size + sizeof(void*) - 1) & ~(sizeof(void*) - 1); - if (_root_size + size <= block_capacity) + if (_root_size + size <= _root->capacity) { void* buf = _root->data + _root_size; _root_size += size; @@ -6111,13 +6110,18 @@ PUGI__NS_BEGIN } else { - size_t block_data_size = (size > block_capacity) ? size : block_capacity; - size_t block_size = block_data_size + offsetof(xpath_memory_block, data); + // make sure we have at least 1/4th of the page free after allocation to satisfy subsequent allocation requests + size_t block_capacity_base = sizeof(_root->data); + size_t block_capacity_req = size + block_capacity_base / 4; + size_t block_capacity = (block_capacity_base > block_capacity_req) ? block_capacity_base : block_capacity_req; + + size_t block_size = block_capacity + offsetof(xpath_memory_block, data); xpath_memory_block* block = static_cast(xml_memory::allocate(block_size)); if (!block) return 0; block->next = _root; + block->capacity = block_capacity; _root = block; _root_size = size; @@ -6258,6 +6262,7 @@ PUGI__NS_BEGIN xpath_stack_data(): result(blocks + 0), temp(blocks + 1) { blocks[0].next = blocks[1].next = 0; + blocks[0].capacity = blocks[1].capacity = sizeof(blocks[0].data); stack.result = &result; stack.temp = &temp; @@ -9990,6 +9995,7 @@ PUGI__NS_BEGIN xpath_query_impl(): root(0), alloc(&block) { block.next = 0; + block.capacity = sizeof(block.data); } xpath_ast_node* root; diff --git a/tests/test_xpath.cpp b/tests/test_xpath.cpp index 7f74578..f9ae858 100644 --- a/tests/test_xpath.cpp +++ b/tests/test_xpath.cpp @@ -328,7 +328,7 @@ TEST(xpath_large_node_set) TEST(xpath_out_of_memory_evaluate_concat) { - test_runner::_memory_fail_threshold = 4096 * 2 * sizeof(char_t) + 4096 * 2; + test_runner::_memory_fail_threshold = 4196 * sizeof(char_t) + 4096 * 2; std::basic_string query = STR("concat(\"a\", \""); @@ -354,7 +354,7 @@ TEST(xpath_out_of_memory_evaluate_concat) TEST(xpath_out_of_memory_evaluate_substring) { - test_runner::_memory_fail_threshold = 4096 * 2 * sizeof(char_t) + 4096 * 2; + test_runner::_memory_fail_threshold = 4196 * sizeof(char_t) + 4096 * 2; std::basic_string query = STR("substring(\""); -- cgit v1.2.3