Re: Switching to XML

Peter Eisentraut <peter_e@gmx.net> writes:
> Tom Lane wrote:
>> Since jade does not go into this kind of spiral when producing html
>> output from the same sources, I suggest that it's not jade's fault,
>> but rather crummy coding in the sgml-to-tex conversion scripts it's
>> using.

> Right.  I fixed that, so now it takes about 15 minutes to build the
> whole thing.

Actually, I just finished fixing what seems to be the underlying problem
in jade: it's got a spectacularly bad implementation of linked lists.
In PG-code terms, if the list is built by successive lappends(), then
both lfirst() and lnext() take O(N) time for an N-element list, thus
iterating through the list in the usual way is O(N^2) ... and not even
with a reasonably small multiplier, because it stresses the hell out of
memory allocation and garbage collection while it's at it.  (Which may
well mean that it's really more like O(N^3), since the garbage collector
will iterate over every allocated object every so often.)

With the patch it takes me about 5 minutes to do the jade step of the
PDF build, using this morning's SGML sources.  (I don't know how to set
the TeX configuration to get the pdfjadetex steps to go through, so I
dunno about total time.)

However, I have no idea what it'll take to get this patch propagated
into the copies people actually use, so your fix sounds good for the
short term.

            regards, tom lane

diff -cr openjade-1.3.2.orig/style/ELObj.cxx openjade-1.3.2/style/ELObj.cxx
*** openjade-1.3.2.orig/style/ELObj.cxx    Fri Jan 11 10:48:38 2002
--- openjade-1.3.2/style/ELObj.cxx    Sat Dec  9 21:58:36 2006
***************
*** 1044,1049 ****
--- 1044,1054 ----
    return new (interp) ReverseNodeListObj(this);
  }

+ NodeListObj *NodeListObj::nodeListAppend(NodeListObj *newTail, Interpreter &interp)
+ {
+   return new (interp) HeadNodeListObj(this, newTail, interp);
+ }
+
  long NodeListObj::nodeListLength(EvalContext &context, Interpreter &interp)
  {
    NodeListObj *nl = this;
***************
*** 1217,1236 ****

  NodeListObj *PairNodeListObj::nodeListRest(EvalContext &context, Interpreter &interp)
  {
!   if (!head_ || !head_->nodeListFirst(context, interp))
      return tail_->nodeListRest(context, interp);
    NodeListObj *tem = head_->nodeListRest(context, interp);
    ELObjDynamicRoot protect(interp, tem);
!   return new (interp) PairNodeListObj(tem, tail_);
  }

  NodeListObj *PairNodeListObj::nodeListChunkRest(EvalContext &context, Interpreter &interp, bool &chunk)
  {
!   if (!head_ || !head_->nodeListFirst(context, interp))
      return tail_->nodeListChunkRest(context, interp, chunk);
    NodeListObj *tem = head_->nodeListChunkRest(context, interp, chunk);
    ELObjDynamicRoot protect(interp, tem);
!   return new (interp) PairNodeListObj(tem, tail_);
  }

  void PairNodeListObj::traceSubObjects(Collector &c) const
--- 1222,1260 ----

  NodeListObj *PairNodeListObj::nodeListRest(EvalContext &context, Interpreter &interp)
  {
!   if (!head_)
!     return tail_->nodeListRest(context, interp);
!   if (!head_->nodeListFirst(context, interp)) {
!     head_ = 0;
      return tail_->nodeListRest(context, interp);
+   }
    NodeListObj *tem = head_->nodeListRest(context, interp);
    ELObjDynamicRoot protect(interp, tem);
!   if (!tem || !tem->nodeListFirst(context, interp))
!     return tail_;
!   return tem->nodeListAppend(tail_, interp);
  }

  NodeListObj *PairNodeListObj::nodeListChunkRest(EvalContext &context, Interpreter &interp, bool &chunk)
  {
!   if (!head_)
!     return tail_->nodeListChunkRest(context, interp, chunk);
!   if (!head_->nodeListFirst(context, interp)) {
!     head_ = 0;
      return tail_->nodeListChunkRest(context, interp, chunk);
+   }
    NodeListObj *tem = head_->nodeListChunkRest(context, interp, chunk);
    ELObjDynamicRoot protect(interp, tem);
!   if (!tem || !tem->nodeListFirst(context, interp))
!     return tail_;
!   return tem->nodeListAppend(tail_, interp);
! }
!
! NodeListObj *PairNodeListObj::nodeListAppend(NodeListObj *newTail, Interpreter &interp)
! {
!   NodeListObj *tem = new (interp) PairNodeListObj(tail_, newTail);
!   ELObjDynamicRoot protect(interp, tem);
!   return new (interp) PairNodeListObj(head_, tem);
  }

  void PairNodeListObj::traceSubObjects(Collector &c) const
***************
*** 1239,1244 ****
--- 1263,1384 ----
    c.trace(tail_);
  }

+ CellNodeListObj::CellNodeListObj(NodeListObj *head)
+ : head_(head), next_(0)
+ {
+   hasSubObjects_ = 1;
+ }
+
+ NodePtr CellNodeListObj::nodeListFirst(EvalContext &context, Interpreter &interp)
+ {
+   if (head_) {
+     NodePtr nd(head_->nodeListFirst(context, interp));
+     if (nd)
+       return nd;
+     head_ = 0;
+   }
+   if (next_)
+     return next_->nodeListFirst(context, interp);
+   return NodePtr();
+ }
+
+ NodeListObj *CellNodeListObj::nodeListRest(EvalContext &context, Interpreter &interp)
+ {
+   if (!head_) {
+     if (next_)
+       return next_->nodeListRest(context, interp);
+     return interp.makeEmptyNodeList();
+   }
+   if (!head_->nodeListFirst(context, interp)) {
+     head_ = 0;
+     if (next_)
+       return next_->nodeListRest(context, interp);
+     return interp.makeEmptyNodeList();
+   }
+   NodeListObj *tem = head_->nodeListRest(context, interp);
+   ELObjDynamicRoot protect(interp, tem);
+   if (!tem || !tem->nodeListFirst(context, interp)) {
+     if (next_)
+       return next_;
+     return interp.makeEmptyNodeList();
+   }
+   if (next_)
+     return tem->nodeListAppend(next_, interp);
+   return tem;
+ }
+
+ NodeListObj *CellNodeListObj::nodeListChunkRest(EvalContext &context, Interpreter &interp, bool &chunk)
+ {
+   if (!head_) {
+     if (next_)
+       return next_->nodeListChunkRest(context, interp, chunk);
+     chunk = 0;
+     return interp.makeEmptyNodeList();
+   }
+   if (!head_->nodeListFirst(context, interp)) {
+     head_ = 0;
+     if (next_)
+       return next_->nodeListChunkRest(context, interp, chunk);
+     chunk = 0;
+     return interp.makeEmptyNodeList();
+   }
+   NodeListObj *tem = head_->nodeListChunkRest(context, interp, chunk);
+   ELObjDynamicRoot protect(interp, tem);
+   if (!tem || !tem->nodeListFirst(context, interp)) {
+     if (next_)
+       return next_;
+     return interp.makeEmptyNodeList();
+   }
+   if (next_)
+     return tem->nodeListAppend(next_, interp);
+   return tem;
+ }
+
+ void CellNodeListObj::traceSubObjects(Collector &c) const
+ {
+   c.trace(head_);
+   c.trace(next_);
+ }
+
+ HeadNodeListObj::HeadNodeListObj(NodeListObj *first, NodeListObj *second, Interpreter &interp)
+ : first_(0), last_(0)
+ {
+   hasSubObjects_ = 1;
+   ELObjDynamicRoot protect(interp, this);
+   first_ = new (interp) CellNodeListObj(first);
+   last_ = new (interp) CellNodeListObj(second);
+   first_->next_ = last_;
+ }
+
+ NodePtr HeadNodeListObj::nodeListFirst(EvalContext &context, Interpreter &interp)
+ {
+   return first_->nodeListFirst(context, interp);
+ }
+
+ NodeListObj *HeadNodeListObj::nodeListRest(EvalContext &context, Interpreter &interp)
+ {
+   return first_->nodeListRest(context, interp);
+ }
+
+ NodeListObj *HeadNodeListObj::nodeListChunkRest(EvalContext &context, Interpreter &interp, bool &chunk)
+ {
+   return first_->nodeListChunkRest(context, interp, chunk);
+ }
+
+ NodeListObj *HeadNodeListObj::nodeListAppend(NodeListObj *newTail, Interpreter &interp)
+ {
+   CellNodeListObj *tem = new (interp) CellNodeListObj(newTail);
+   last_->next_ = tem;
+   last_ = tem;
+   return this;
+ }
+
+ void HeadNodeListObj::traceSubObjects(Collector &c) const
+ {
+   c.trace(first_);
+   // first_ will recurse to the rest
+ }
+
  ReverseNodeListObj::ReverseNodeListObj(NodeListObj *nl)
  : nl_(nl), reversed_(0)
  {
diff -cr openjade-1.3.2.orig/style/ELObj.h openjade-1.3.2/style/ELObj.h
*** openjade-1.3.2.orig/style/ELObj.h    Fri Jan 11 10:48:38 2002
--- openjade-1.3.2/style/ELObj.h    Sat Dec  9 20:14:23 2006
***************
*** 426,431 ****
--- 426,432 ----
    virtual NodeListObj *nodeListChunkRest(EvalContext &, Interpreter &, bool &chunk);
    virtual NodePtr nodeListRef(long, EvalContext &, Interpreter &);
    virtual NodeListObj *nodeListReverse(EvalContext &, Interpreter &);
+   virtual NodeListObj *nodeListAppend(NodeListObj *, Interpreter &);
    virtual long nodeListLength(EvalContext &, Interpreter &);
    virtual bool suppressError();
  };
***************
*** 493,504 ****
--- 494,533 ----
    NodePtr nodeListFirst(EvalContext &, Interpreter &);
    NodeListObj *nodeListRest(EvalContext &, Interpreter &);
    NodeListObj *nodeListChunkRest(EvalContext &, Interpreter &, bool &);
+   NodeListObj *nodeListAppend(NodeListObj *, Interpreter &);
    void traceSubObjects(Collector &) const;
  private:
    NodeListObj *head_; // may be null
    NodeListObj *tail_;
  };

+ class CellNodeListObj : public NodeListObj {
+ public:
+   CellNodeListObj(NodeListObj *);
+   NodePtr nodeListFirst(EvalContext &, Interpreter &);
+   NodeListObj *nodeListRest(EvalContext &, Interpreter &);
+   NodeListObj *nodeListChunkRest(EvalContext &, Interpreter &, bool &);
+   void traceSubObjects(Collector &) const;
+ private:
+   NodeListObj *head_; // may be null
+   CellNodeListObj *next_; // may be null
+   friend class HeadNodeListObj; // needs access to next_ link
+ };
+
+ class HeadNodeListObj : public NodeListObj {
+ public:
+   HeadNodeListObj(NodeListObj *, NodeListObj *, Interpreter &);
+   NodePtr nodeListFirst(EvalContext &, Interpreter &);
+   NodeListObj *nodeListRest(EvalContext &, Interpreter &);
+   NodeListObj *nodeListChunkRest(EvalContext &, Interpreter &, bool &);
+   NodeListObj *nodeListAppend(NodeListObj *, Interpreter &);
+   void traceSubObjects(Collector &) const;
+ private:
+   // there are always at least two cells in the list, hence first_ != last_
+   CellNodeListObj *first_;
+   CellNodeListObj *last_;
+ };
+
  inline
  bool ELObj::equal(ELObj &obj1, ELObj &obj2)
  {
diff -cr openjade-1.3.2.orig/style/primitive.cxx openjade-1.3.2/style/primitive.cxx
*** openjade-1.3.2.orig/style/primitive.cxx    Wed Mar 13 07:21:22 2002
--- openjade-1.3.2/style/primitive.cxx    Sat Dec  9 21:48:01 2006
***************
*** 3846,3870 ****

  DEFPRIMITIVE(NodeList, argc, argv, context, interp, loc)
  {
!   if (argc == 0)
      return interp.makeEmptyNodeList();
!   int i = argc - 1;
!   NodeListObj *nl = argv[i]->asNodeList();
    if (!nl)
      return argError(interp, loc,
!             InterpreterMessages::notANodeList, i, argv[i]);
!   if (i > 0) {
!     ELObjDynamicRoot protect(interp, nl);
!     for (;;) {
!       i--;
        NodeListObj *tem = argv[i]->asNodeList();
        if (!tem)
!         return argError(interp, loc,
!                     InterpreterMessages::notANodeList, i, argv[i]);
!       nl = new (interp) PairNodeListObj(tem, nl);
!       if (i == 0)
!     break;
!       protect = nl;
      }
    }
    return nl;
--- 3846,3868 ----

  DEFPRIMITIVE(NodeList, argc, argv, context, interp, loc)
  {
!   if (argc <= 0)
      return interp.makeEmptyNodeList();
!   NodeListObj *nl = argv[0]->asNodeList();
    if (!nl)
      return argError(interp, loc,
!             InterpreterMessages::notANodeList, 0, argv[0]);
!   if (argc > 1) {
!     ELObjDynamicRoot protect(interp);
!     ELObjDynamicRoot protect2(interp);
!     for (int i = 1; i < argc; i++) {
!       protect = nl;
        NodeListObj *tem = argv[i]->asNodeList();
        if (!tem)
!     return argError(interp, loc,
!             InterpreterMessages::notANodeList, i, argv[i]);
!       protect2 = tem;
!       nl = nl->nodeListAppend(tem, interp);
      }
    }
    return nl;