| Age | Commit message (Collapse) | Author |
|---|
|
Since page size can be customized let's do a special validation check for
compact encoding. Right now it's redundant since page size is limited by
64k in alloc_string, but that may change in the future.
|
|
This allows us to add pi value to restore target support for PI nodes without
increasing the memory usage for other nodes.
Right now the PI node has a separate header that's used for allocated bit;
this allows us to reduce header bitcount in the future.
|
|
|
|
|
|
Split number/boolean filtering logic into two functions. This creates an
extra copy of a remove_if-like algorithm, but moves the type check out of
the loop and results in better organized filtering code.
Consolidate test-based dispatch into apply_predicate (which is now a member
function).
|
|
Calling memcpy(x, 0, 0) is technically undefined (although it should usually
be a no-op).
|
|
Calling memcpy(x, 0, 0) is technically undefined (although it should usually
be a no-op).
Fixes #20.
|
|
|
|
|
|
|
|
This lets us do fewer null pointer checks (making printing 2% faster with -O3)
and removes a lot of function calls (making printing 20% faster with -O0).
|
|
To get more benefits from constant predicate/filter optimization we rewrite
[position()=expr] predicates into [expr] for numeric expressions. Right now
the rewrite is only for entire expressions - it may be beneficial to split
complex expressions like [position()=constant and expr] into [constant][expr]
but that is more complicated.
last() does not depend on the node set contents so is "constant" as far as
our optimization is concerned so we can evaluate it once.
|
|
Numeric and boolean constant expressions in filters are different in that
to evaluate numeric expressions we need a sorted order, but to evaluate
boolean expressions we don't. The previously implemented optimization adds
an extra sorting step for constant boolean filters that will be more expensive
than redundant computations.
Since constant booleans are sort of an edge case, don't do this optimization.
This allows us to simplify apply_predicate_const to only handle numbers.
|
|
Now expression is always _right for filter/predicate nodes to make optimize()
simpler. Additionally we now use predicate metadata to make is_posinv_step()
faster.
This introduces a weak ordering dependency in rewrite rules to optimize() -
classification has to be performed before other optimizations.
|
|
If a filter/predicate expression is a constant, we don't need to evaluate it
for every nodeset element - we can evaluate it once and pick the right element
or keep/discard the entire collection.
If the expression is 1, we can early out on first node when evaluating the
node set - queries like following::item[1] are now significantly faster.
Additionally this change refactors filters/predicates to have additional
metadata describing the expression type in _test field that is filled during
optimization.
Note that predicate_constant selection right now is very simple (but captures
most common use cases except for maybe [last()]).
|
|
A page can fail to allocate during attribute creation; this case was not
previously handled.
git-svn-id: https://pugixml.googlecode.com/svn/trunk@1080 99668b35-9821-0410-8761-19e4c4f06640
|
|
When removing a node or attribute, we know that the parent has at least one
node/attribute so a null pointer check is redundant.
git-svn-id: https://pugixml.googlecode.com/svn/trunk@1078 99668b35-9821-0410-8761-19e4c4f06640
|
|
|
|
|
|
If the requested evaluation mode is not _all, we can use this mode for the
last predicate/filter expression and exit early.
git-svn-id: https://pugixml.googlecode.com/svn/trunk@1073 99668b35-9821-0410-8761-19e4c4f06640
|
|
Using pointers instead of node/attribute objects allows us to use knowledge
about the tree to guarantee that pointers are not null. This results in
less null checks (10-20% speedup with optimizations enabled) and less
function calls (5x speedup with optimizations disabled).
git-svn-id: https://pugixml.googlecode.com/svn/trunk@1072 99668b35-9821-0410-8761-19e4c4f06640
|
|
|
|
Some steps relied on step_push rejecting null inputs; this is no longer
the case. Additionally stepping now more rigorously filters null inputs.
git-svn-id: https://pugixml.googlecode.com/svn/trunk@1069 99668b35-9821-0410-8761-19e4c4f06640
|
|
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
|
|
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
|
|
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
|
|
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
|
|
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
|
|
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
|
|
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
|
|
|
|
Remove compact stats and tags, replace pointer hash with murmur3 32-bit
finalizer.
|
|
|
|
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
|
|
Insert is now unsafe - since we don't have a way to handle rehash()
failures transparently we need to reserve space beforehand. Reserve is now
called before every tree-mutating operations and it guarantees that we
can perform 16 arbitrary pointer mutations after that.
This fixes all test crashes with compact mode.
|
|
This helps streamline class dependencies and will make subsequent changes
smaller.
|
|
|
|
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
|
|
git-svn-id: https://pugixml.googlecode.com/svn/trunk@1055 99668b35-9821-0410-8761-19e4c4f06640
|
|
Parent pointers need to be able to reach everywhere within a page to
minimize shared parent pointer reuse unless it's absolutely necessary.
This reduces parent hash utilization on all test cases to <1%.
Rename compact_parent to compact_shared_parent.
|
|
We now no longer need the compact_alignment type so replace it with a
constant.
|
|
Split the implementation into a generic one with adjustable range and a
special implementation for parent (may need to use 2 bytes on that one
later).
Optimize compact_string and compact_pointer to use minimal amount of math
and move slow hash paths into no-inline functions so that compiler can
inline the fast-paths.
Merge compact_pointer_generic and compact_pointer_forward and optimize.
|
|
Also remove get() methods on pointer wrappers - this makes the surface
area smaller so we can create more of them easier.
|
|
To make this possible name and value in the node structure had to be
merged into one contents field. Not sure what to do with node_pi, since it
is the only type that required both.
|
|
The storage uses one hash table for fallbacks and simple difference
encoding for node and string pointers.
This is a work in progress implementation - while node pointers seem to
work properly, string encoding is inefficient and parent pointers could
use more tuning.
No performance or compatibility work has been done either.
|
|
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
|
|
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
|
|
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
|
|
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
|
|
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
|
