Work at SourceForge, help us to make it a better place! We have an immediate need for a Support Technician in our San Francisco or Denver office.

Close

Custom tree model

2010-03-27
2012-10-08
<< < 1 2 (Page 2 of 2)
  • I think you have a typo in net.sf.saxon.sreamedtree.NodeImpl.generateId():

    public void generateId(FastStringBuffer buffer) {
    long seq = getSequenceNumber();
    if (seq == -1L) {
    getPhysicalRoot().generateId(buffer);
    buffer.append(NODE_LETTER);
    buffer.append(Long.toString(seq));
    } else {
    parent.generateId(buffer);
    buffer.append(NODE_LETTER);
    buffer.append(Integer.toString(index));
    }
    }

    If node has no a sequence number (-1) then result will always be the same.
    This is masked, however, with method overrides, but still one is able to
    construct a tree
    with two text nodes with identical generateid() values.

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

     
  • Michael Kay
    Michael Kay
    2010-04-19

    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".

     
  • 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

     
  • Bruno Feurer
    Bruno Feurer
    2010-04-21

    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

     
  • Michael Kay
    Michael Kay
    2010-04-22

    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).

     
  • 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:

    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;
     }
    

    vs

    QualifiedName:
      public final String getLocalName()
      {
        return localName; 
      }
    

    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
    QualifiedName.java
    NameCache.java.txt

    and have introduced methods:
    int QualifiedName.getId();
    QualifiedName NameCache.getQualifiedName(int id);

    which could do the work.

     
  • Bruno Feurer
    Bruno Feurer
    2010-04-22

    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;
    }

    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.

     
  • Bruno Feurer
    Bruno Feurer
    2010-05-20

    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

     
  • Michael Kay
    Michael Kay
    2010-05-20

    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.

     
  • 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.

     
  • Bruno Feurer
    Bruno Feurer
    2010-05-25

    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?

     
  • Michael Kay
    Michael Kay
    2010-05-25

    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.

     
  • Bruno Feurer
    Bruno Feurer
    2010-06-01

    Double-checking seems to make a difference in a simple multi-thread-allocation
    test: http://livcos-dev.blogspot.com/2010/06/xml-namepool-3.html.

    Michael, maybe you want to try my patched version of Saxon 9.2.1.1 (http://li
    vcos.org/res/saxon9he_Saxon5.jar
    )
    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.

     
  • Michael Kay
    Michael Kay
    2010-06-01

    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.

     
  • Bruno Feurer
    Bruno Feurer
    2010-06-02

    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!

     
<< < 1 2 (Page 2 of 2)