Some Eclipse Foundation services are deprecated, or will be soon. Please ensure you've read this important communication.

Bug 332289

Summary:	ParsetreeUtil.getOffset is too slow
Product:	[Modeling] TMF	Reporter:	Mark Christiaens <mark.g.j.christiaens>
Component:	Xtext	Assignee:	Project Inbox <tmf.xtext-inbox>
Status:	CLOSED WORKSFORME	QA Contact:
Severity:	enhancement
Priority:	P3	CC:	mark.g.j.christiaens, sebastian.zarnekow
Version:	1.0.1	Flags:	sebastian.zarnekow: indigo+
Target Milestone:	M5
Hardware:	PC
OS:	Linux
Whiteboard:

Description Mark Christiaens

2010-12-10 05:35:22 EST

Build Identifier: I20100608-0911

Opening a big VHDL-file (2> MB) is very slow.  The file is already part of my project so it's just opening that's costly.  I'm using an Intel(R) Core(TM) i5 CPU 750 @ 2.67GHz and it takes 22 seconds. 

The profiler indicates that ParsetreeUtil.getOffset is using a lot of CPU cycles.  The causes are threefold:

1) Iterating over a list by using an index (O(n^2) time)
2) Too much casting
3) Recursively visiting the parse tree within a recursive loop (I guess that's also (O(n^2)).

Reproducible: Always

Comment 1 Mark Christiaens

2010-12-10 05:36:54 EST

I have a patch that reduces opening time from 22 seconds to 14 seconds:

	/**
	 * @param abstractNode
	 * @return
	 */
	public static int getOffset(AbstractNode abstractNode) {
		if (abstractNode instanceof LeafNode) {
			LeafNode leafNode = (LeafNode) abstractNode;
			return leafNode.getTotalOffset();
		} else {
			BooleanHolder hasLeafNodes = new BooleanHolder(false);
			CompositeNode compNode = (CompositeNode) abstractNode;
			return getOffset(compNode, hasLeafNodes);
		}
	}

	private static int getOffset(CompositeNode node, BooleanHolder hasLeafNodes) {
		for (AbstractNode child : node.getChildren()) {
			if (child instanceof CompositeNode) {
				CompositeNode childNode = (CompositeNode) child;
				BooleanHolder childrenHaveLeafNodes = new BooleanHolder(false);
				
				int offset = getOffset(childNode, childrenHaveLeafNodes);
				
				if (childrenHaveLeafNodes.isVal()) {
					hasLeafNodes.setVal(true);
					return offset;
				}
			} else {
				LeafNode leafNode = (LeafNode) child;
				hasLeafNodes.setVal(true);

				if (!leafNode.isHidden())
					return leafNode.getTotalOffset();
			}
		}

		return node.getTotalOffset();
	}

Comment 2 Mark Christiaens

2010-12-10 05:38:52 EST

A quick question.  I can't use injection (I think) for this patch.  Should I build my own Xtext version then or is there a better way?

Comment 3 Sebastian Zarnekow

2010-12-10 05:43:59 EST

(In reply to comment #2)
> A quick question.  I can't use injection (I think) for this patch.  Should I
> build my own Xtext version then or is there a better way?

I'm not aware of a better way.

Some remarks:

1) Iterating over a list by using an index (O(n^2) time)
As the lists are RandomAccessLists, using an index is effectivly O(1). In fact, it should be slightly faster for really deep recursion since there is no need to instantiate an iterator.

2) Too much casting
3) Recursively visiting the parse tree within a recursive loop (I guess that's
also (O(n^2)).

This should be the main problem.

Please note that the class ParsetreeUtil does no longer exist in Xtext 2.0 since we rewrote the node model.

Comment 4 Mark Christiaens

2010-12-10 05:45:15 EST

Forgot to mention a little helper class:


private final static class BooleanHolder {
		private boolean val;
		
		public BooleanHolder (boolean val)
		{
			this.val = val; 
		}

		public boolean isVal() {
			return val;
		}

		public void setVal(boolean val) {
			this.val = val;
		}
	}

Comment 5 Sebastian Zarnekow

2011-01-30 09:17:44 EST

This should be obsolete with the new node model. Please reopen if the problem persists.

Comment 6 Karsten Thoms

2017-09-19 16:54:45 EDT

Closing all bugs that were set to RESOLVED before Neon.0

Comment 7 Karsten Thoms

2017-09-19 17:05:35 EDT

Closing all bugs that were set to RESOLVED before Neon.0