You are viewing a plain text version of this content. The canonical link for it is here.
Posted to java-dev@axis.apache.org by Glen Daniels <gd...@macromedia.com> on 2002/08/18 16:54:58 UTC
RE: cvs commit: xml-axis/java/src/org/apache/axis/utils DOM2Write
r.java NSStack.java axisNLS.properties
So much for them Java collection classes being efficient, eh? :)
What kind of improvements are you seeing after changes like these, Sam?
--Glen
> -----Original Message-----
> From: rubys@apache.org [mailto:rubys@apache.org]
> Sent: Sunday, August 18, 2002 10:00 AM
> To: xml-axis-cvs@apache.org
> Subject: cvs commit: xml-axis/java/src/org/apache/axis/utils
> DOM2Writer.java NSStack.java axisNLS.properties
>
>
> rubys 2002/08/18 06:59:29
>
> Modified: java/src/org/apache/axis/encoding
> DeserializationContextImpl.java
> SerializationContextImpl.java
> java/src/org/apache/axis/utils DOM2Writer.java
> NSStack.java
> axisNLS.properties
> Log:
> Rewrite NSStack for performance.
>
> Revision Changes Path
> 1.46 +1 -1
> xml-axis/java/src/org/apache/axis/encoding/DeserializationCont
> extImpl.java
>
> Index: DeserializationContextImpl.java
> ===================================================================
> RCS file:
> /home/cvs/xml-axis/java/src/org/apache/axis/encoding/Deseriali
> zationContextImpl.java,v
> retrieving revision 1.45
> retrieving revision 1.46
> diff -u -r1.45 -r1.46
> --- DeserializationContextImpl.java 16 Aug 2002 17:04:55
> -0000 1.45
> +++ DeserializationContextImpl.java 18 Aug 2002 13:59:29
> -0000 1.46
> @@ -282,7 +282,7 @@
> **/
> public ArrayList getCurrentNSMappings()
> {
> - return (ArrayList)namespaces.peek().clone();
> + return namespaces.cloneFrame();
> }
>
> /**
>
>
>
> 1.57 +2 -4
> xml-axis/java/src/org/apache/axis/encoding/SerializationContex
> tImpl.java
>
> Index: SerializationContextImpl.java
> ===================================================================
> RCS file:
> /home/cvs/xml-axis/java/src/org/apache/axis/encoding/Serializa
> tionContextImpl.java,v
> retrieving revision 1.56
> retrieving revision 1.57
> diff -u -r1.56 -r1.57
> --- SerializationContextImpl.java 16 Aug 2002 17:37:02
> -0000 1.56
> +++ SerializationContextImpl.java 18 Aug 2002 13:59:29
> -0000 1.57
> @@ -902,9 +902,7 @@
> }
> }
>
> - ArrayList currentMappings = nsStack.peek();
> - for (int i = 0; i < currentMappings.size(); i++) {
> - Mapping map = (Mapping)currentMappings.get(i);
> + for (Mapping map=nsStack.topOfFrame(); map!=null;
> map=nsStack.next()) {
> StringBuffer sb = new StringBuffer("xmlns");
> if (!map.getPrefix().equals("")) {
> sb.append(":");
> @@ -941,7 +939,7 @@
> }
>
> nsStack.pop();
> - nsStack.peek().clear();
> + nsStack.clearFrame();
>
> if (writingStartTag) {
> writer.write("/>");
>
>
>
> 1.13 +6 -7
> xml-axis/java/src/org/apache/axis/utils/DOM2Writer.java
>
> Index: DOM2Writer.java
> ===================================================================
> RCS file:
> /home/cvs/xml-axis/java/src/org/apache/axis/utils/DOM2Writer.java,v
> retrieving revision 1.12
> retrieving revision 1.13
> diff -u -r1.12 -r1.13
> --- DOM2Writer.java 12 Aug 2002 22:52:14 -0000 1.12
> +++ DOM2Writer.java 18 Aug 2002 13:59:29 -0000 1.13
> @@ -103,11 +103,7 @@
> public static void serializeAsXML(Node node, Writer writer,
> boolean omitXMLDecl)
> {
> - PrintWriter out = new PrintWriter(writer);
> - if (!omitXMLDecl)
> - out.println("<?xml version=\"1.0\"
> encoding=\"UTF-8\"?>");
> - print(node, null, out, false, 0);
> - out.flush();
> + serializeAsXML(node, writer, omitXMLDecl, false);
> }
>
> /**
> @@ -120,7 +116,8 @@
> PrintWriter out = new PrintWriter(writer);
> if (!omitXMLDecl)
> out.println("<?xml version=\"1.0\"
> encoding=\"UTF-8\"?>");
> - print(node, null, out, pretty, 0);
> + NSStack namespaceStack = new NSStack();
> + print(node, namespaceStack, out, pretty, 0);
> out.flush();
> }
>
> @@ -157,7 +154,7 @@
>
> case Node.ELEMENT_NODE :
> {
> - namespaceStack = new NSStack(namespaceStack);
> + namespaceStack.push();
>
> if (pretty) {
> for (int i = 0; i < indent; i++)
> @@ -261,6 +258,8 @@
> if (pretty)
> out.print(JavaUtils.LS);
> }
> +
> + namespaceStack.pop();
> break;
> }
>
>
>
>
> 1.27 +131 -147
> xml-axis/java/src/org/apache/axis/utils/NSStack.java
>
> Index: NSStack.java
> ===================================================================
> RCS file:
> /home/cvs/xml-axis/java/src/org/apache/axis/utils/NSStack.java,v
> retrieving revision 1.26
> retrieving revision 1.27
> diff -u -r1.26 -r1.27
> --- NSStack.java 12 Aug 2002 22:52:13 -0000 1.26
> +++ NSStack.java 18 Aug 2002 13:59:29 -0000 1.27
> @@ -63,116 +63,138 @@
> import java.util.Iterator;
>
> /**
> + * The abstraction this class provides is a push down
> stack of variable
> + * length frames of prefix to namespace mappings. Used
> for keeping track
> + * of what namespaces are active at any given point as an
> XML document is
> + * traversed or produced.
> + *
> + * From a performance point of view, this data will both
> be modified frequently
> + * (at a minimum, there will be one push and pop per XML
> element processed),
> + * and scanned frequently (many of the "good" mappings
> will be at the bottom
> + * of the stack). The one saving grace is that the
> expected maximum
> + * cardinalities of the number of frames and the number of
> total mappings
> + * is only in the dozens, representing the nesting depth
> of an XML document
> + * and the number of active namespaces at any point in the
> processing.
> + *
> + * Accordingly, this stack is implemented as a single
> array, will null
> + * values used to indicate frame boundaries.
> + *
> * @author: James Snell
> * @author Glen Daniels (gdaniels@macromedia.com)
> + * @author Sam Ruby (rubys@us.ibm.com)
> */
> public class NSStack {
> protected static Log log =
> LogFactory.getLog(NSStack.class.getName());
>
> - private static final ArrayList EMPTY = new ArrayList();
> -
> - private Stack stack = new Stack();
> -
> - private NSStack parent = null;
> -
> - public NSStack() {}
> -
> - public NSStack(ArrayList table) {
> - push(table);
> - }
> -
> - public NSStack(NSStack parent) {
> - this.parent = parent;
> + private Mapping[] stack;
> + private int top = 0;
> + private int iterator = 0;
> +
> + public NSStack() {
> + stack = new Mapping[32];
> + stack[0] = null;
> }
>
> + /**
> + * Create a new frame at the top of the stack.
> + */
> public void push() {
> - if (stack == null) stack = new Stack();
> -
> - if (log.isTraceEnabled())
> - log.trace("NSPush (" + stack.size() + ")");
> + top ++;
>
> - stack.push(EMPTY);
> - }
> -
> - public void push(ArrayList table) {
> - if (stack == null) stack = new Stack();
> + if (top >= stack.length) {
> + Mapping newstack[] = new Mapping[stack.length*2];
> + System.arraycopy (stack, 0, newstack, 0, stack.length);
> + stack = newstack;
> + }
>
> if (log.isTraceEnabled())
> - log.trace("NSPush (" + stack.size() + ")");
> + log.trace("NSPush (" + stack.length + ")");
>
> - if (table.size() == 0)
> - stack.push(EMPTY);
> - else
> - stack.push(table);
> - }
> -
> - public ArrayList peek() {
> - if (stack.isEmpty())
> - if (parent != null)
> - return parent.peek();
> - else
> - return EMPTY;
> -
> -
> - return (ArrayList)stack.peek();
> + stack[top] = null;
> }
>
> - public ArrayList pop() {
> - if (stack.isEmpty()) {
> + /**
> + * Remove the top frame from the stack.
> + */
> + public void pop() {
> + while (stack[top] != null) top--;
> +
> + if (top == 0) {
> if (log.isTraceEnabled())
> log.trace("NSPop (" +
> JavaUtils.getMessage("empty00") + ")");
>
> - if (parent != null)
> - return parent.pop();
> -
> - return null;
> + return;
> }
>
> + top--;
> +
> if (log.isTraceEnabled()){
> - ArrayList t = (ArrayList)stack.pop();
> - log.trace("NSPop (" + stack.size() + ")");
> - return t;
> - } else {
> - return (ArrayList)stack.pop();
> + log.trace("NSPop (" + stack.length + ")");
> }
> }
>
> - public void add(String namespaceURI, String prefix) {
> - if (stack.isEmpty()) push();
> - ArrayList table = peek();
> - if (table == EMPTY) {
> - table = new ArrayList();
> - stack.pop();
> - stack.push(table);
> - }
> - // Replace duplicate prefixes (last wins - this
> could also fault)
> - for (Iterator i = table.iterator(); i.hasNext();) {
> - Mapping mapping = (Mapping)i.next();
> - if (mapping.getPrefix().equals(prefix)) {
> - mapping.setNamespaceURI(namespaceURI);
> - return;
> - }
> + /**
> + * Return a copy of the current frame.
> + */
> + public ArrayList cloneFrame() {
> + ArrayList clone = new ArrayList();
> +
> + topOfFrame();
> +
> + while (iterator <= top) clone.add(stack[iterator++]);
> +
> + return clone;
> + }
> +
> + /**
> + * Remove all mappings from the current frame.
> + */
> + public void clearFrame() {
> + while (stack[top] != null) top--;
> + }
> +
> + /**
> + * Reset the embedded iterator in this class to the
> top of the current
> + * (i.e., last) frame. Note that this is not
> threadsafe, nor does it
> + * provide multiple iterators, so don't use this
> recursively. Nor
> + * should you modify the stack while iterating over it.
> + */
> + public Mapping topOfFrame() {
> + iterator = top;
> + while (stack[iterator] != null) iterator--;
> + iterator++;
> + return next();
> + }
> +
> + /**
> + * Return the next namespace mapping in the top frame.
> + */
> + public Mapping next() {
> + if (iterator > top) {
> + return null;
> + } else {
> + return stack[iterator++];
> }
> - table.add(new Mapping(namespaceURI, prefix));
> }
> -
> +
> /**
> - * remove a namespace from the topmost table on the stack
> + * Add a mapping for a namespaceURI to the specified
> prefix to the top
> + * frame in the stack. If the prefix is already
> mapped in that frame,
> + * remap it to the (possibly different) namespaceURI.
> */
> - /*
> - public void remove(String namespaceURI) {
> - if (stack.isEmpty()) return;
> - ArrayList current = peek();
> - for (int i = 0; i < current.size(); i++) {
> - Mapping map = (Mapping)current.get(i);
> - if (map.getNamespaceURI().equals(namespaceURI)) {
> - current.removeElementAt(i);
> - return; // ???
> + public void add(String namespaceURI, String prefix) {
> + // Replace duplicate prefixes (last wins - this
> could also fault)
> + for (int cursor=top; stack[cursor]!=null; cursor--) {
> + if (stack[cursor].getPrefix().equals(prefix)) {
> + stack[cursor].setNamespaceURI(namespaceURI);
> + return;
> }
> }
> +
> + push();
> + stack[top] = new Mapping(namespaceURI, prefix);
> }
> - */
>
> /**
> * Return an active prefix for the given namespaceURI.
> NOTE : This
> @@ -193,99 +215,61 @@
> if ((namespaceURI == null) || (namespaceURI.equals("")))
> return null;
>
> - if (!stack.isEmpty()) {
> - for (int n = stack.size() - 1; n >= 0; n--) {
> - ArrayList t = (ArrayList)stack.get(n);
> -
> - for (int i = 0; i < t.size(); i++) {
> - Mapping map = (Mapping)t.get(i);
> - if
> (map.getNamespaceURI().equals(namespaceURI)) {
> - String possiblePrefix = map.getPrefix();
> - if
> (getNamespaceURI(possiblePrefix).equals(namespaceURI) &&
> - (!noDefault ||
> !"".equals(possiblePrefix)))
> - return possiblePrefix;
> - }
> - }
> + for (int cursor=top; cursor>0; cursor--) {
> + Mapping map = stack[cursor];
> + if (map == null) continue;
> +
> + if (map.getNamespaceURI().equals(namespaceURI)) {
> + String possiblePrefix = map.getPrefix();
> + if
> (getNamespaceURI(possiblePrefix).equals(namespaceURI) &&
> + (!noDefault || !"".equals(possiblePrefix)))
> + return possiblePrefix;
> }
> }
>
> - if (parent != null)
> - return parent.getPrefix(namespaceURI);
> return null;
> }
>
> + /**
> + * Return an active prefix for the given namespaceURI,
> including
> + * the default prefix ("").
> + */
> public String getPrefix(String namespaceURI) {
> return getPrefix(namespaceURI, false);
> }
>
> + /**
> + * Given a prefix, return the associated namespace (if any).
> + */
> public String getNamespaceURI(String prefix) {
> if (prefix == null)
> prefix = "";
> +
> + for (int cursor=top; cursor>0; cursor--) {
> + Mapping map = stack[cursor];
> + if (map == null) continue;
>
> - if (!stack.isEmpty()) {
> - for (int n = stack.size() - 1; n >= 0; n--) {
> - ArrayList t = (ArrayList)stack.get(n);
> -
> - for (int i = 0; i < t.size(); i++) {
> - Mapping map = (Mapping)t.get(i);
> - if (map.getPrefix().equals(prefix))
> - return map.getNamespaceURI();
> - }
> - }
> + if (map.getPrefix().equals(prefix))
> + return map.getNamespaceURI();
> }
>
> - if (parent != null)
> - return parent.getNamespaceURI(prefix);
> -
> - if (log.isTraceEnabled()){
> - log.trace("--" +
> JavaUtils.getMessage("noPrefix00", "" + this, prefix));
> - dump("--");
> - log.trace("--" + JavaUtils.getMessage("end00"));
> - }
> -
> return null;
> }
>
> - public boolean isDeclared(String namespaceURI) {
> - if (!stack.isEmpty()) {
> - for (int n = stack.size() - 1; n >= 0; n--) {
> - ArrayList t = (ArrayList)stack.get(n);
> - if ((t != null) && (t != EMPTY)) {
> - for (int i = 0; i < t.size(); i++) {
> - if (((Mapping)t.get(i)).getNamespaceURI().
> - equals(namespaceURI))
> - return true;
> - }
> - }
> - }
> - }
> -
> - if (parent != null)
> - return parent.isDeclared(namespaceURI);
> -
> - return false;
> - }
> -
> + /**
> + * Produce a trace dump of the entire stack, starting
> from the top and
> + * including frame markers.
> + */
> public void dump(String dumpPrefix)
> {
> - Enumeration e = stack.elements();
> - while (e.hasMoreElements()) {
> - ArrayList list = (ArrayList)e.nextElement();
> -
> - if (list == null) {
> - log.trace(dumpPrefix +
> JavaUtils.getMessage("nullTable00"));
> - continue;
> - }
> + for (int cursor=top; cursor>0; cursor--) {
> + Mapping map = stack[cursor];
>
> - for (int i = 0; i < list.size(); i++) {
> - Mapping map = (Mapping)list.get(i);
> + if (map == null) {
> + log.trace(dumpPrefix +
> JavaUtils.getMessage("stackFrame00"));
> + } else {
> log.trace(dumpPrefix +
> map.getNamespaceURI() + " -> " + map.getPrefix());
> }
> - }
> -
> - if (parent != null) {
> - log.trace(dumpPrefix + "--" +
> JavaUtils.getMessage("parent00"));
> - parent.dump(dumpPrefix + "--");
> }
> }
> }
>
>
>
> 1.46 +1 -1
> xml-axis/java/src/org/apache/axis/utils/axisNLS.properties
>
> Index: axisNLS.properties
> ===================================================================
> RCS file:
> /home/cvs/xml-axis/java/src/org/apache/axis/utils/axisNLS.properties,v
> retrieving revision 1.45
> retrieving revision 1.46
> diff -u -r1.45 -r1.46
> --- axisNLS.properties 16 Aug 2002 20:07:55 -0000 1.45
> +++ axisNLS.properties 18 Aug 2002 13:59:29 -0000 1.46
> @@ -460,7 +460,6 @@
> nullProvider00=Null provider type passed to WSDDProvider!
>
> nullResponse00=Null response message!
> -nullTable00=null table??
> oddDigits00=Odd number of digits in hex string
> ok00=OK
>
> @@ -574,6 +573,7 @@
> start00={0} starting up on port {1}.
> startElem00=Start element {0}
> startPrefix00=Start prefix mapping ''{0}'' -> ''{1}''
> +stackFrame00=Stack frame marker
> test00=...
> test01=.{0}.
> test02={0}, {1}.
>
>
>
>
Re: cvs commit: xml-axis/java/src/org/apache/axis/utils DOM2Write
r.java NSStack.java axisNLS.properties
Posted by Sam Ruby <ru...@apache.org>.
Glen Daniels wrote:
> So much for them Java collection classes being efficient, eh? :)
Stack is synchronized.
My theory is that ArrayList is relatively efficient when amortized over
a number of requests, but our usage pattern was often to create an
ArrayList, add a single element to it, and then throw them both away.
If you take a look at the resulting code, you will see that it is not
noticably more complex than using the collection classes. Arguably, it
is a bit less complex in many of the methods.
It also now has comments. ;-)
> What kind of improvements are you seeing after changes like these, Sam?
I'm not running the test... but reportedly NSStack usage is relatively
low on small (one element) payloads, but grows exponentially on larger
payloads. Before this change, in a 100 element payload, NSStack usage
grew to over 11% of the *ENTIRE* path length of a request (including
webSphere, the parser, etc). Mostly in the serialization side.
- Sam Ruby