summaryrefslogtreecommitdiff
path: root/src
AgeCommit message (Collapse)Author
2014-10-20XPath: Introduce _first/_any set evaluation modesArseny Kapoulkine
Sometimes when evaluating the node set we don't need the entire set and only need the first element in docorder or any element. In the absence of iterator support we can still use this information to short-circuit traversals. This does not have any effect on straightforward node collection queries, but frequently improves performance of complex queries with predicates etc. XMark benchmark gets 15x faster with some queries enjoying 100x speedup on 10 Mb dataset due to a significant complexity improvement. git-svn-id: https://pugixml.googlecode.com/svn/trunk@1067 99668b35-9821-0410-8761-19e4c4f06640
2014-10-19XPath: Rename xml_node::select_single_node to ::select_nodeArseny Kapoulkine
select_node is shorter and mistyping nodes as node or vice versa should not lead to any issues since return types are substantially different. select_single_node method still works and will be deprecated with an attribute and removed at some point. git-svn-id: https://pugixml.googlecode.com/svn/trunk@1065 99668b35-9821-0410-8761-19e4c4f06640
2014-10-19XPath: Introduce xpath_query::evaluate_nodeArseny Kapoulkine
This method is equivalent to xml_node::select_single_node. This makes select_single_node faster in certain cases by avoiding an allocation and - more importantly - paves the way for future step optimizations. git-svn-id: https://pugixml.googlecode.com/svn/trunk@1064 99668b35-9821-0410-8761-19e4c4f06640
2014-10-18XPath: Extend the descendant-or-self optimizationArseny Kapoulkine
Use descendant-or-self::node() transformation for self, descendant and descendant-or-self axis. Self axis should be semi-frequent; descendant axes should not really be used with // but if they ever are the complexity of the step becomes quadratic so it's better to optimize this if possible. git-svn-id: https://pugixml.googlecode.com/svn/trunk@1063 99668b35-9821-0410-8761-19e4c4f06640
2014-10-16XPath: Optimize attribute axis lookupArseny Kapoulkine
When looking for an attribute by name, finding the first attribute means we can stop looking since attribute names are unique. This makes some queries faster by 40%. Another very common pattern in XPath queries is finding an attribute with a specified value using a predicate (@name = 'value'). While we perform an optimal amount of traversal in that case, there is a substantial overhead with evaluating the nodes, saving and restoring the stack state, pushing the attribute node into a set, etc. Detecting this pattern allows us to use optimized code, resulting in up to 2x speedup for some queries. git-svn-id: https://pugixml.googlecode.com/svn/trunk@1061 99668b35-9821-0410-8761-19e4c4f06640
2014-10-15XPath: Fix optimization bug with //name[last()]Arseny Kapoulkine
The actual condition for the optimization is invariance from context list -- this includes both position() and last(). Instead of splitting the posinv concept just include last() into non-posinv expressions - this requires sorting for boolean predicates that depend on last() and do not depend on position(). These cases should be very rare. git-svn-id: https://pugixml.googlecode.com/svn/trunk@1060 99668b35-9821-0410-8761-19e4c4f06640
2014-10-14Adjust comment output to avoid malformed documents.Arseny Kapoulkine
Comment value can not contain the string "--" or end with "-". Since comments do not support escaping, we're handling this by adding an extra space after the first "-". A string of "-" thus turns into "- - - ...". git-svn-id: https://pugixml.googlecode.com/svn/trunk@1058 99668b35-9821-0410-8761-19e4c4f06640
2014-10-11Swap insert_attribute_* implementationsArseny Kapoulkine
Make sure their order is consistent with the order of declaration in header file. git-svn-id: https://pugixml.googlecode.com/svn/trunk@1057 99668b35-9821-0410-8761-19e4c4f06640
2014-10-11Refactor node/attribute tree operationsArseny Kapoulkine
All ad-hoc attribute operations are now implemented as explicit low-level functions, and xml_node just uses them. Additionally extract commonly used is_attribute_of and move detaching of node from append_node to remove_node - append_node now only works on detached nodes (small increase in parsing performance). git-svn-id: https://pugixml.googlecode.com/svn/trunk@1056 99668b35-9821-0410-8761-19e4c4f06640
2014-10-10Fix Borland C++ compilation errors/warningsArseny Kapoulkine
git-svn-id: https://pugixml.googlecode.com/svn/trunk@1055 99668b35-9821-0410-8761-19e4c4f06640
2014-10-05XPath: Store string length inside string objectArseny Kapoulkine
When xpath_string is heap-allocated we always know the length of the string at some point - it is now stored in the object. This reduces redundant string length calculations and makes string_value() much faster in case it has to concatenate strings. git-svn-id: https://pugixml.googlecode.com/svn/trunk@1053 99668b35-9821-0410-8761-19e4c4f06640
2014-10-05XPath: Implement optimized translate()Arseny Kapoulkine
translate() with constant arguments now uses a 128-byte table and a table lookup instead of searching characters in the source string. The table is generated during query optimization. git-svn-id: https://pugixml.googlecode.com/svn/trunk@1052 99668b35-9821-0410-8761-19e4c4f06640
2014-10-05Optimize XPath document order comparatorArseny Kapoulkine
Node ancestor search now terminates early if ancestor is found before the document root (only happens if nodes were at the same depth). Sibling search now steps synchronously for left and right nodes to avoid worst-case performance when we go in the wrong direction and have to scan a big list (this comes at the cost of average performance since in the best case we do 2x more operations). Node comparison is now done using node pointers to elide some null comparisons since the structure of the search guarantees that they are handled properly. All of the above results in ~2x faster document order comparison on complex documents. git-svn-id: https://pugixml.googlecode.com/svn/trunk@1050 99668b35-9821-0410-8761-19e4c4f06640
2014-10-05Optimize XPath sorting for sorted sequencesArseny Kapoulkine
XPath evaluation frequently produces sequences that are sorted but are not tagged as such (area for improvement...). Doing a linear scan before sorting is cheap and results in tremendous speedup for already sorted sequences (especially if document_buffer_order optimization does not apply). git-svn-id: https://pugixml.googlecode.com/svn/trunk@1049 99668b35-9821-0410-8761-19e4c4f06640
2014-10-04Optimize unrolled scanning for MSVCArseny Kapoulkine
While gcc and clang can eliminate dependency on s in the inner loop of PUGI__SCANWHILE_UNROLL, MSVC emits a series of register increments. Rewriting the code to explicitly remove the dependency keeps similar codegen on gcc/clang but improves codegen on MSVC for a 10% performance boost. Also use unrolled scanning in text_output_escaped (2% faster). git-svn-id: https://pugixml.googlecode.com/svn/trunk@1048 99668b35-9821-0410-8761-19e4c4f06640
2014-10-03Fix whitespace indentationArseny Kapoulkine
git-svn-id: https://pugixml.googlecode.com/svn/trunk@1047 99668b35-9821-0410-8761-19e4c4f06640
2014-10-03Reorganize xml_memory_page structureArseny Kapoulkine
The page no longer contains 'data' field to use sizeof everywhere instead of offsetof/sizeof inconsistency (that is required because some compilers don't recognize offsetof as compile-time constant). The page no longer contains 'memory' field that is now encoded as an offset byte before the page - this allows us to save one pointer from the static page in the document to keep the size the same as in v1.2 (binary compatibility). git-svn-id: https://pugixml.googlecode.com/svn/trunk@1046 99668b35-9821-0410-8761-19e4c4f06640
2014-10-03Remove document buffer order flag from document nodeArseny Kapoulkine
Use the same flag that is used for marking name/value in nodes/attributes as shared. This reduces document structure size and makes some amount of sense (although admittedly is a bit of a hack). We need to bring document _memory size back down to 192 bytes and this is the first step. git-svn-id: https://pugixml.googlecode.com/svn/trunk@1045 99668b35-9821-0410-8761-19e4c4f06640
2014-10-03Optimize node_copy_tree by switching to pointersArseny Kapoulkine
xml_node objects carry an overhead since they perform NULL checks - in case of copying a hierarchy we know that we only traverse valid nodes so we don't need to do this. This makes copyless copy 16% faster. git-svn-id: https://pugixml.googlecode.com/svn/trunk@1043 99668b35-9821-0410-8761-19e4c4f06640
2014-10-03Refactor accessing node type into a macroArseny Kapoulkine
git-svn-id: https://pugixml.googlecode.com/svn/trunk@1042 99668b35-9821-0410-8761-19e4c4f06640
2014-10-02Fix copy behavior when out-of-memoryArseny Kapoulkine
Also remove accidentally committed pragma pack :-/ git-svn-id: https://pugixml.googlecode.com/svn/trunk@1041 99668b35-9821-0410-8761-19e4c4f06640
2014-10-02Remove redundant condition from text_output_indentArseny Kapoulkine
git-svn-id: https://pugixml.googlecode.com/svn/trunk@1037 99668b35-9821-0410-8761-19e4c4f06640
2014-10-01Use append_new_node in node_copy_treeArseny Kapoulkine
This bypasses the allow_insert check (which is redundant for copying since we're mirroring an existing node structure that must be valid) and does not cause an extra allocation for new declaration nodes. Overall results in 15% faster copying, git-svn-id: https://pugixml.googlecode.com/svn/trunk@1036 99668b35-9821-0410-8761-19e4c4f06640
2014-10-01Disable document_order optimization after move/append_buffer.Arseny Kapoulkine
Moving nodes results in node order being different from order of allocated names/values; since move is O(1) we can't mark the moved nodes in a subtree so we have to disable the optimization for the entire document. Similarly, if a node is composed of multiple buffers, comparing nodes in different buffers does not result in meaningful order. Since we value correctness over performance, mark the entire document in these cases to disable sorting optimization. git-svn-id: https://pugixml.googlecode.com/svn/trunk@1034 99668b35-9821-0410-8761-19e4c4f06640
2014-10-01Implement copyless copyArseny Kapoulkine
Now copying nodes or attributes does not copy names/values if the source strings are in a document buffer. As a result, several nodes can now share the same string in document buffer - to support this we 'taint' both source and destination with a special 'shared' bit. Tainting disables offset_debug() and fast-path document order comparison; it also prevents strcpy_insitu from reusing the document buffer memory for the copied node. The downsides include slower XPath queries in some (rare) cases and slightly higher memory consumption in some (rare) cases. XPath queries can execute slower if a lot of old nodes were copied to new nodes *and* a query only touches old nodes (so it used to benefit a lot from fast comparison path) *and* a query produces unsorted node sets that need to be sorted later (both are relatively rare). Higher memory consumption is possible if a lot of nodes were copied and all nodes (both new and old) have their contents modified 'in place' -- previously we could modify the old node in place and the new node required one allocation on copy, and now both nodes have to have their data allocated during modification. This should also be rare. On the bright side, in a lot of cases copying of string data can be avoided - this makes the copy much faster and the document now occupies less memory. For example, some uses of append_buffer are now actually slower compared to building up a document by copying a template from the same document and modifying the copy slightly. In one of the internal benchmarks copying is now 4x faster (the difference can be more dramatic with more string contents and less markup). git-svn-id: https://pugixml.googlecode.com/svn/trunk@1032 99668b35-9821-0410-8761-19e4c4f06640
2014-10-01Add header bit for 'name or value is shared' flagArseny Kapoulkine
This is required to make it possible to use a pointer to one of the buffers with the document data in nodes but keep offset_debug and (more importantly) XPath document order comparison optimization working. The change increases memory page alignment to 64 bytes (so requires +32 bytes for every page allocation, which should not be a problem - even with non-default 4k pages this is <1% extra cost, with default 32k pages the overhead is 0.1%) git-svn-id: https://pugixml.googlecode.com/svn/trunk@1031 99668b35-9821-0410-8761-19e4c4f06640
2014-09-28Remove redundant reference indirection for internal functions.Arseny Kapoulkine
Since xml_node/attribute are pointer wrappers it's cheaper to pass them by value. This makes XPath evaluation 4% faster and node printing 2% faster. git-svn-id: https://pugixml.googlecode.com/svn/trunk@1029 99668b35-9821-0410-8761-19e4c4f06640
2014-09-28Implement non-recursive node copyingArseny Kapoulkine
This makes node copying 6% faster, prevents it from ever running out of stack space and makes the profiling results more actionable for profilers that can't merge information from recursive calls. git-svn-id: https://pugixml.googlecode.com/svn/trunk@1027 99668b35-9821-0410-8761-19e4c4f06640
2014-09-25Internal refactoring: rename xml_buffered_writer::write overloadsArseny Kapoulkine
Renames write to write_string and write_buffer to make it easier to distinguish between them in profiling runs and commit messages... git-svn-id: https://pugixml.googlecode.com/svn/trunk@1025 99668b35-9821-0410-8761-19e4c4f06640
2014-09-25Optimize xml_buffered_writer::write(char_t...)Arseny Kapoulkine
Make it easier for the compiler to generate good code by loading bufsize into a local once and returning new offset from flush(). This results in 7% performance gain. git-svn-id: https://pugixml.googlecode.com/svn/trunk@1024 99668b35-9821-0410-8761-19e4c4f06640
2014-09-24Optimize xml_buffered_writer::write(const char_t*)Arseny Kapoulkine
Instead of computing the length and doing memcpy we now copy the head of the string into the buffer (like strcpy) and then use memcpy for tail if necessary. This results in 10-15% speedup for writing typical documents with a mix of short and long strings. git-svn-id: https://pugixml.googlecode.com/svn/trunk@1023 99668b35-9821-0410-8761-19e4c4f06640
2014-09-23XPath: Optimize //name queries when possibleArseny Kapoulkine
//name means /descendant-or-self::node()/child::name, but we frequently can replace it with /descendant::name. This means we do not have to build up a temporary node set with all descendants that can lead to 3x speedups. git-svn-id: https://pugixml.googlecode.com/svn/trunk@1021 99668b35-9821-0410-8761-19e4c4f06640
2014-09-22Optimize and refactor node output implementation a bit (+5% perf gain)Arseny Kapoulkine
git-svn-id: https://pugixml.googlecode.com/svn/trunk@1019 99668b35-9821-0410-8761-19e4c4f06640
2014-09-21Optimize text_output_indentArseny Kapoulkine
We now precompute indent length and have a fast path for lengths 0..4 that avoids calling memcpy in a tight loop. This makes node output 20-30% faster if indentation is enabled. git-svn-id: https://pugixml.googlecode.com/svn/trunk@1018 99668b35-9821-0410-8761-19e4c4f06640
2014-09-21Implement non-recursive node outputArseny Kapoulkine
This makes node output 3% faster, prevents it from ever running out of stack space and makes the profiling results more actionable for profilers that can't merge information from recursive calls. git-svn-id: https://pugixml.googlecode.com/svn/trunk@1014 99668b35-9821-0410-8761-19e4c4f06640
2014-09-15Fix VC 14 warningsArseny Kapoulkine
Fixes C4458: declaration of 'var' hides class member git-svn-id: https://pugixml.googlecode.com/svn/trunk@1011 99668b35-9821-0410-8761-19e4c4f06640
2014-08-26Unroll performance-critical loops 4xArseny Kapoulkine
Use a special macro that unrolls the loop body and uses static branch prediction to improve code generation. This increases performance across all data sets from benchmark; clang x64 is 10%-40% faster, clang x86 is 5%-20% faster, msvc is 5%-10% faster. git-svn-id: https://pugixml.googlecode.com/svn/trunk@1008 99668b35-9821-0410-8761-19e4c4f06640
2014-08-25Use PUGI__SCANWHILE for strconv utilitiesArseny Kapoulkine
This makes it easier to optimize strconv. For consistency move all definitions of parser-internal macros to one place. git-svn-id: https://pugixml.googlecode.com/svn/trunk@1007 99668b35-9821-0410-8761-19e4c4f06640
2014-08-25Rename ENDSWITH to PUGI__ENDSWITHArseny Kapoulkine
Also add it to #undef list at the end to avoid conflicts git-svn-id: https://pugixml.googlecode.com/svn/trunk@1006 99668b35-9821-0410-8761-19e4c4f06640
2014-08-11Move attribute name setup after pointer setup to handle exceptions betterArseny Kapoulkine
git-svn-id: https://pugixml.googlecode.com/svn/trunk@1005 99668b35-9821-0410-8761-19e4c4f06640
2014-08-10Implement node moving functions.Arseny Kapoulkine
The operations itself are O(1) since they just rearrange pointers. However, the validation step is O(logN) due to a sanity check to prevent recursive trees. git-svn-id: https://pugixml.googlecode.com/svn/trunk@1002 99668b35-9821-0410-8761-19e4c4f06640
2014-08-10Refactor low-level node manipulation routines into separate functions.Arseny Kapoulkine
This should make moving implementation easier. git-svn-id: https://pugixml.googlecode.com/svn/trunk@1001 99668b35-9821-0410-8761-19e4c4f06640
2014-06-01Improve XPath allocator performanceArseny Kapoulkine
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
2014-05-04Add xpath_node_set::iterator that is the same as const_iterator.Arseny Kapoulkine
Exposing true mutable iterators allows the user to violate sorting order contract. However, some generic algorithms (i.e. Boost ForEach) require iterator methods to be present. git-svn-id: https://pugixml.googlecode.com/svn/trunk@998 99668b35-9821-0410-8761-19e4c4f06640
2014-02-25Revert automatic support for header-only mode since it creates problems with ↵Arseny Kapoulkine
qmake. Qmake treats all files that are #include-d as header files, even if the #include is guarded by an #ifdef. It looks like the only solution that allows for transparent header-only support based on preprocessor define involves moving the actual source into a separate header file and including this file in pugixml.cpp. Let's not do it yet. git-svn-id: https://pugixml.googlecode.com/svn/trunk@990 99668b35-9821-0410-8761-19e4c4f06640
2014-02-25Add parse_trim_pcdata parse option.Arseny Kapoulkine
git-svn-id: https://pugixml.googlecode.com/svn/trunk@987 99668b35-9821-0410-8761-19e4c4f06640
2014-02-23Fix gap collapsing during PCDATA parsing for fragment mode.Arseny Kapoulkine
git-svn-id: https://pugixml.googlecode.com/svn/trunk@985 99668b35-9821-0410-8761-19e4c4f06640
2014-02-12Fix compilation warning for toolsets where wchar_t == char.Arseny Kapoulkine
git-svn-id: https://pugixml.googlecode.com/svn/trunk@983 99668b35-9821-0410-8761-19e4c4f06640
2014-02-11Implement document fragment parsing.Arseny Kapoulkine
Introduce a notable behavior change in default parsing mode: documents without a document element node are now considered invalid. This is technically a breaking change, however the amount of documents it affects is very small, all parsed data still persists, and lack of this check results in very confusing behavior in a number of cases. In order to be able to parse documents without an element node, a fragment parsing flag is introduced. Parsing a buffer in fragment mode treats the buffer as a fragment of a valid XML. As a consequence, top-level PCDATA is added to the tree; additionally, there are no restrictions on the number of nodes -- so documents without a document element are considered valid. Due to the way parsing works internally, load_buffer_inplace occasionally can not preserve the document contents if it's parsed in a fragment mode. While unfortunate, this problem is fundamental; since the use case is relatively obscure, hopefully documenting this shortcoming will be enough. git-svn-id: https://pugixml.googlecode.com/svn/trunk@980 99668b35-9821-0410-8761-19e4c4f06640
2014-02-10Use a null-terminated buffer for parsing as often as possible.Arseny Kapoulkine
Parsing used to work on a non null-terminated buffer, inserting a fake null terminator to increase performance. This makes it impossible to implement fragment parsing that preserves PCDATA contents (as witnessed by some tests for boundary conditions that actually depended on this behavior). Since almost all uses result in us allocating an internal buffer anyway, the new policy is to make sure all buffers that are allocated by pugixml are null-terminated - the only exception now is external calls to load_buffer_inplace that don't trigger encoding conversion. git-svn-id: https://pugixml.googlecode.com/svn/trunk@977 99668b35-9821-0410-8761-19e4c4f06640