Saxon

Legacy ID: #8329718 Legacy Poster: Vladimir Nesterovsky (vnesterovsky)

Sorry, I meant in net.sf.saxon.tree.NodeImpl

Legacy ID: #8330507 Legacy Poster: Michael Kay (mhkay)

I think the code is OK (or almost): the only nodes that have sequence number of -1 are nodes added using XQuery Update, and generate-id() is called only in XSLT. Perhaps you might hit problems if you did an XQuery update and then passed the resulting tree as input to XSLT... It looks as if generate-id() is moving into XQuery anyway, so it needs to be fixed. By the way, I've been thinking about your comment 25 on the previous page, of replacing the set of integers for a node in TinyTree (perhaps nodeKind, nameCode, typeCode and perhaps depth) with a reference to an object that can be shared for objects that have the same set of values for those integers. It clearly gives a space saving, though the experience of the CondensedTinyTree is that it will add significantly to tree building time. I'm thinking it might well make sense to combine it with the other features of the CondensedTinyTree to give an option for a tree with the trade-off "less space, more build time".

Legacy ID: #8334190 Legacy Poster: Vladimir Nesterovsky (vnesterovsky)

I've created another tree. Unlike composable tree, which does not store parent references, this one does not store children. It's called streamed tree, constructs nodes on the fly from PullProvider, and can be used for processing of a big input. To use it one needs to create an instance of DocumentInfo, which pulls data from XMLStreamReader, and to pass it as an input to a transformation: XMLInputFactory factory = XMLInputFactory.newInstance(); XMLStreamReader reader = factory.createXMLStreamReader(input); StaxBridge bridge = new StaxBridge(); bridge.setPipelineConfiguration(controller.makePipelineConfiguration()); bridge.setXMLStreamReader(reader); controller.transform(new DocumentImpl(bridge), output); Here is a short description http://www.nesterovsky-bros.com/weblog/2010/04/21/StreamedTree.aspx, and implementation http://www.nesterovsky-bros.com/download/saxon/streamedtree.zip

Legacy ID: #8335458 Legacy Poster: Bruno Feurer (bfeurer)

Hello Mr Kay, hello Mr Nesterovsky Since I haven't found the time to dig into the Saxon code very deep yet, I'm trying to follow your discussion from a maybe more abstract point of view... Can you please verify, comment some of my thoughts? Namepool Memory Model, QualifiedName objects / int-codes With QNames only being added and read, a memory model, simpler than the JVM one, is possible. The int-approach has a smaller memory foot-print and still offers the same access performance. In addition the Garbage Collector has less objects to worry about and the memory usage does not necessarily double, just because the application needs a 64bit JVM. Synchronization does not differ for both approaches, adds need to be synchronized either way. Maybe a double-check approach could help here: Lookup the name code unsynchronized, if missing, synchronize, look it up again, if still missing, add a new code. Since most likely adds will be less often, the more are added already, it should speed up lookups on average. The second lookup might even be optimized, searching only the most recent ones... Node Meta Data, Build-Time / Space Any builder needs to lookup, know the code for kind, type and name for the node to build. Then it would lookup the meta data set, matching all the codes. The kind code directs the search to one of 7 containers / direct references (no type and name for, lets say, comment nodes). Organized by the fingerprint of the name code (fingerprint to type => many to one) the meta data should be found pretty fast. Is this really that significant for the tree build-time in relation to the lookup time for the individual codes? Thanks, Bruno Feurer

Legacy ID: #8336823 Legacy Poster: Michael Kay (mhkay)

Bruno: thanks for your comments: (a) Namepool Memory Model, QualifiedName objects / int-codes With QNames only being added and read, a memory model, simpler than the JVM one, is possible. The int-approach has a smaller memory foot-print and still offers the same access performance. In addition the Garbage Collector has less objects to worry about and the memory usage does not necessarily double, just because the application needs a 64bit JVM. - Yes, matches my analysis. I think the approach suggested by Vladimir of using a pool of QName objects rather than integer codes might be viable, but doesn't offer any benefits over the current approach that would justify the huge disruption it would cause. The need to handle QName prefixes greatly complicates matters. (b) Synchronization does not differ for both approaches, adds need to be synchronized either way. Maybe a double-check approach could help here: - Correct. Saxon already in effect uses a double-check approach on paths where it matters. (c) Node Meta Data, Build-Time / Space Any builder needs to lookup, know the code for kind, type and name for the node to build. Then it would lookup the meta data set, matching all the codes. The kind code directs the search to one of 7 containers / direct references (no type and name for, lets say, comment nodes). ... Is this really that significant for the tree build-time in relation to the lookup time for the individual codes? The problem here is that there's a wide variety of scenarios to consider. There are some scenarios where a 30% reduction in memory usage would be very welcome; there are others where a 30% increase in tree-building time would be catastrophic (for some applications parsing and tree-building dominates the time for the query/transformation).

Legacy ID: #8337238 Legacy Poster: Vladimir Nesterovsky (vnesterovsky)

In my opinion pool of QualifiedName objects has its pros and cons. It seems it's as fast as NamePool during name allocation and name comparision; It's faster during streaming of xml. Consider: [code] NamePool: public String getLocalName(int nameCode) { if ((nameCode & USER_DEFINED_MASK) == 0) { return StandardNames.getLocalName(nameCode & FP_MASK); } NameEntry entry = getNameEntry(nameCode); if (entry == null) { unknownNameCode(nameCode); return null; } return entry.localName; } [/code] vs [code] QualifiedName: public final String getLocalName() { return localName; } [/code] On the other hand use of QualifiedName increases memory footprint on 64bit for the TinyTree. That's why I suggested node metadata, which is analog, in some sense, of schema element/attribure definition, so it can be factored out of storage. The main obstacle of such approach, I think, is a compatibility, as many APIs external to saxon depend on NamePool interface. Fortunately, even this could be addressed. One just needs to add a fast way to identify integer with QualifiedName. I've updated [url="http://www.nesterovsky-bros.com/download/saxon/QualifiedName.java.txt"]QualifiedName.java[/url] [url="http://www.nesterovsky-bros.com/download/saxon/NameCache.java.txt"]NameCache.java.txt[/url] and have introduced methods: int QualifiedName.getId(); QualifiedName NameCache.getQualifiedName(int id); which could do the work.

Legacy ID: #8338183 Legacy Poster: Bruno Feurer (bfeurer)

Michael, thanks for the verification! Vladimir, you are right, the access performance is not the same. Hmm, I don't really see right now, why the namecode in Saxon is a hash and what the NameEntry object is good for. But theoretically it should also be possible to model the different parts of the name into int[] arrays and use the index as the namecode. The int-NamePool would have a method something like this: public String getLocalName(int nameCode) { return localNames[nameCode & SOME_MASK]; } Ok, not a direct access, but pretty close ;) In allocation the int[] approach would benefit of not needing to allocate an object for every name, but only to grow the arrays every, lets say, 1000 names. Despite the all-optimizing HotspotVM, I guess, the JVM memory management rather sees a few large int[] blocks than thousands of QualifiedName objects. Somehow the GC has to check every object for being reachable every now and then. I still think, in an average application the resulting performance of both approaches should be similar in theory.

Legacy ID: #8404206 Legacy Poster: Bruno Feurer (bfeurer)

With the bad weather in Switzerland not allowing me to fly my hang glider, I also have been working on some new name pool implementations: http://livcos-dev.blogspot.com/2010/05/xml-namepool-2.html Has somebody some unit tests to run? or some bigger collection of "realistic" example qualified names? Maybe the "Saxon2" version has the potential to replace the current implementation in Saxon. I have successfully applied a patched version of Saxon in my project and have noticed an increase in overall performance of about 6% for some quick tests. Of course the name pool does not effect the performance of all the applications, but so far, I haven't found a significant downside in any aspect. Thanks for feedback and happy holidays (the weather forecast looks promising for the Swiss Hang Gliding Championship, yeha!), Bruno

Legacy ID: #8404286 Legacy Poster: Michael Kay (mhkay)

Bruno, thanks for the data on this. 6% looks attractive enough to be worth considering. However, the biggest performance problem with the current NamePool design is contention, and if I were to do any work in this area at all, then I would be looking for ways to reduce the contention problems experienced by people with high-throughput workloads. One idea for this is to use a thread-local cache of the NamePool (currently the ReceivingContentHandler uses a cache, which helps greatly during document building, but there are still many paths that make excessive calls on allocate(), most notably when using external tree models such as DOM.

Legacy ID: #8404310 Legacy Poster: Vladimir Nesterovsky (vnesterovsky)

Hello Bruno! Unfortunatelly every implementation your have provided so far is not thread safe. Sorry. Also, I've not studied you code in depth but on the surface I don't understand why QualifiedName objects should consume x10 memory comparing to Saxon's implementation.

Legacy ID: #8413677 Legacy Poster: Bruno Feurer (bfeurer)

Thanks for your feedback! Michael: Do you think the performance drop for not being able to compare fingerprints via bit-masks would be essential for Saxon? I have some ideas for the concurrency aspect, but I'd rather implement them only on one design. For it's simplicity I favor the StringArray implementation (with the only, small performance drawback at comparing fingerprints). Vladimir: I know, the concurrency aspect is not perfect yet ;) . Well, in terms of memory, the measurements are really rough and simple (Runtime.totalMemory - .freeMemory). It's purpose is to detect some hot spots, asking for an explanation and to see that no garbage collection is damaging the timing measurements. Some explanations: Saxon does not buffer Clark- and QName String (other than via String.intern()), a QualifiedName object, a map entry object and a key object use more memory than some integer indexes. Also I don't think, the memory usage is an issue here, since a system, handling 100'000 qualified names, should also be able to provide 20MB of additional memory. Are there really no unit test for the NamePool out there?

Legacy ID: #8413722 Legacy Poster: Michael Kay (mhkay)

Do you think the performance drop for not being able to compare fingerprints via bit-masks would be essential for Saxon? You mean, do I think the performance drop would be unacceptable, I suppose? Yes, I imagine it would: however, speculation about performance often turns out to be wrong. The only way to find out is by measurement. >Are there really no unit test for the NamePool out there? I have very few unit tests for internal interfaces; nearly all my testing is by running stylesheets and queries. This has the major advantage that you can change internal interfaces without having to rewrite large numbers of tests, something which I have found on other projects can be a major barrier to refactoring. Unfortunately though I also have no real tests that simulate high-throughput concurrent web-server workloads, which is something I would really want to do before replacing such a critical component of the system. I agree that memory for the NamePool isn't likely to be a significant issue. The objectives are (a) speed of comparison of names (b) speed of adding new names (c) minimizing contention.

Legacy ID: #8430035 Legacy Poster: Bruno Feurer (bfeurer)

Double-checking seems to make a difference in a simple multi-thread-allocation test: [url=http://livcos-dev.blogspot.com/2010/06/xml-namepool-3.html]http://livcos-dev.blogspot.com/2010/06/xml-namepool-3.html[/url]. Michael, maybe you want to try my patched version of Saxon 9.2.1.1 ([url=http://livcos.org/res/saxon9he_Saxon5.jar]http://livcos.org/res/saxon9he_Saxon5.jar[/url]) in your high-throughput scenarios? I would be interested in the results! What do you think about the "pre-allocation" approach? My initial implementation in Cosmos4 did not show a noticeable improvement, but in theory, in an intensive concurrent-allocation scenario, it should be able to play its purpose.

Legacy ID: #8430898 Legacy Poster: Michael Kay (mhkay)

Double-checking seems to make a difference Of course, and Saxon in effect uses double-checking extensively. The general approach is (a) use getFingerprint() when a name is expected to be already present in the pool, (b) otherwise use allocate() (which is synchronised), but (c) on paths where there are many allocate() calls, either use a local cache of names and check this first, or call getFingerprint before calling allocate(). Looking at your code, however, you seem to use unsynchronized references to an array which is occasionally reorganized when it gets too large. That is surely broken.

Legacy ID: #8432381 Legacy Poster: Bruno Feurer (bfeurer)

I don't see the advantage in moving the double-checking out of the NamePool into the calling code. Handling the double-checking within the NamePool at least lets us reuse the hash code and simplifies the calling context. Local caches, like in the ReceivingContentHandler, represent only the stable part of the the name pool and would become obsolete. Ah, they also help to avoid reparsing the raw name. Btw, an additional interface (or the interpretation of the rawname as only the prefix) would be nice here. It would spare the client to need to build the qnames and Saxon to parse it again for the prefix, but the SAX interface is standard, I know. I see, you have taken this topic to the blog. A good idea, thank you!