Comment 1 Philipe Mulet 2003-03-22 04:41:05 EST

Did you use 2.0.2 to produce the thread dump ? In 2.1, we think we have 
improved the cycle detection significantly.

Also we would need exact steps to reproduce. What you are doing is close to 
what we do when developping Eclipse and we have not seen problems in 2.1 (in 
2.0.2 it was a performance issue).

Comment 2 Raj Mandayam 2003-03-24 04:30:42 EST

Hi Philippe,

Problem:

I import a lot of plugins to my Eclipse RC2 environment (problem occurs in 2.0.2
(Here it is even slower,as you have mentioned earlier) & RC1 as well)
After I do that. I delete two projects, connect to my CVS repository and select the 
same two projects and retrieve them from the repository (where I have the source). 
The dialog is popped up which, after retreiving the files, tries to update
classpaths.
This stage of the operation takes almost 10 minutes displaying "Updating". 

The thread stack trace reveals

Full thread dump Classic VM (J2RE 1.3.1 IBM Windows 32 build cn131-20020710,
native threads):
    "ModalContext" (TID:0x2FF9390, sys_thread_t:0x36D9F900, state:R, native
ID:0x3B8) prio=5
	at
org.eclipse.jdt.internal.core.JavaProject.updateAllCycleMarkers(JavaProject.java:2272)
	at
org.eclipse.jdt.internal.core.DeltaProcessor.updateClasspathMarkers(DeltaProcessor.java:1949)
	at
org.eclipse.jdt.internal.core.DeltaProcessor.resourceChanged(DeltaProcessor.java:1686)
	at
org.eclipse.core.internal.events.NotificationManager$1.run(NotificationManager.java:137)
	at
org.eclipse.core.internal.runtime.InternalPlatform.run(InternalPlatform.java(Compiled
Code))
	at org.eclipse.core.runtime.Platform.run(Platform.java(Compiled Code))
	at
org.eclipse.core.internal.events.NotificationManager.notify(NotificationManager.java:152)
	at
org.eclipse.core.internal.events.NotificationManager.broadcastChanges(NotificationManager.java:67)
	at
org.eclipse.core.internal.resources.Workspace.broadcastChanges(Workspace.java:161)
	at
org.eclipse.core.internal.resources.Workspace.endOperation(Workspace.java(Compiled
Code))
	at org.eclipse.core.internal.resources.Workspace.run(Workspace.java(Compiled Code))
	at
org.eclipse.ui.actions.WorkspaceModifyOperation.run(WorkspaceModifyOperation.java:79)
	at
org.eclipse.team.internal.ccvs.ui.repo.RepositoryManager.run(RepositoryManager.java:790)
	at org.eclipse.team.internal.ccvs.ui.actions.CVSAction$1.run(CVSAction.java:242)
	at
org.eclipse.jface.operation.ModalContext$ModalContextThread.run(ModalContext.java:95)

After essentially setting up a development environment to launch Eclipse, I
performed the same
steps as above from my Runtime Workbench and found that the operation was taking
an inordinate amount of time in

executing 
	at
org.eclipse.jdt.internal.core.JavaProject.updateAllCycleMarkers(JavaProject.java:2272)

This method is used to perform cycle detection when traversing classpaths of
each project in the workspace.

The following segment of the code 

		for (int i = 0; i < length; i++){
			JavaProject project = (JavaProject)projects[i];
			if (!cycleParticipants.contains(project)){
				visited.clear();
				project.updateCycleParticipants(null, visited, cycleParticipants,
workspaceRoot);
			}
		}


Here, for each project a cycle detection algorithm is run and the cycle
participants are stored in a HashSet "cycleParticipants"
The method project.updateCycleParticipants performs the core operation.

In the method updateCycleParticipants

	public void updateCycleParticipants(IClasspathEntry[] preferredClasspath,
ArrayList visited, HashSet cycleParticipants, IWorkspaceRoot workspaceRoot){
		visited.add(this);
		try {
			IClasspathEntry[] classpath = preferredClasspath == null ?
getResolvedClasspath(true) : preferredClasspath;
			for (int i = 0, length = classpath.length; i < length; i++) {
				IClasspathEntry entry = classpath[i];
				
				if (entry.getEntryKind() == IClasspathEntry.CPE_PROJECT){
					IPath entryPath = entry.getPath();
					IResource member = workspaceRoot.findMember(entryPath);
					if (member != null && member.getType() == IResource.PROJECT){
						JavaProject project = (JavaProject)JavaCore.create((IProject)member);
						int index = visited.indexOf(project);
						if (index == -1 && cycleParticipants.contains(project))
							index = visited.indexOf(this); // another loop in the cycle exists
						if (index >= 0) { // only consider direct participants inside the cycle
							for (int size = visited.size(); index < size; index++)
								cycleParticipants.add(visited.get(index)); 
						} else {
							project.updateCycleParticipants(null, visited, cycleParticipants,
workspaceRoot);
						}
					}
				}
			}
		} catch(JavaModelException e){
		}
		visited.remove(this);
	}


This method as seen maintains two objects a ArrayList named "visited" & the
HashSet "cycleParticipants". It's a recursive method and
what this method does is that it retrieves the classpath entries for the current
project and for each entry that is of type "PROJECT"
It checks to see if its on its "visited" list, If it is then it forms a cycle
and the method adds the project (classpath entry) to the list of cycleParticipants

As seen above these two methods since they are recursive they would encounter
the same project again and again, Note that some effort at optimizing
has been made by ensuring that if a project is already part of the
cycleParticipant then project.updateCycleParticipants(..) is not called.
But there is one problem that has been overlooked, projects whose classpath
entries have been already been visited can be marked as "doneTraversing" and
need not
be analyzed later when another project has this project as its classpath entry.  

To illustrate the problem,  if 

   A  --> B  ---> C --> D --> E-..>
          |             |
          |-------------

  If you are traversing the path  A->B->C->D->E. Once you have finished visiting
project "D" & its classpath entries (in this case "E")
  There is no need to visit the project "D" when traversing the path
A->B->D->E..>  because D has already been exhausted. 

Infact Since the code segment already checks, if cycleParticipants includes a
project, 
so if it doesn't include the project then
  we do not need to call project.updateCyc... 
     if the project has already been "doneTraversing". 

So we do not lose genuine cycle participants as well.
  

When I did that the it went a long way to reducing the amount of time this
method was taking. It took 10 seconds for the above case instead of minutes.

To do that, I added another HashSet named "doneTraversing". At the end of
project.updateCycleParticipants(..) when one has finished analyzing the current
project and
all of its classpath entries, this project can be added to "doneTraversing".
Therefore if we encounter the same project later in another classpath entry one
need not call
the project.updateCycleParticipants(..)

The following code is what I had to do 

	public static void updateAllCycleMarkers() throws JavaModelException {
		...
		
		HashSet doneTraversing = new HashSet;
		ArrayList visited = new ArrayList();

		for (int i = 0; i < length; i++){
			JavaProject project = (JavaProject)projects[i];
			if (!cycleParticipants.contains(project) && !doneTraversing.contains(project)){
				visited.clear();
				project.updateCycleParticipants(null, visited, cycleParticipants,
workspaceRoot, doneTraversing);
			}
		}
                doneTraversing.clear(); //flush out
		...
	}
		
&

	public void updateCycleParticipants(IClasspathEntry[] preferredClasspath,
ArrayList visited, HashSet cycleParticipants, IWorkspaceRoot workspaceRoot,
HashSet doneTraversing){
		visited.add(this);
		try {
			IClasspathEntry[] classpath = preferredClasspath == null ?
getResolvedClasspath(true) : preferredClasspath;
			for (int i = 0, length = classpath.length; i < length; i++) {
				IClasspathEntry entry = classpath[i];
				
				if (entry.getEntryKind() == IClasspathEntry.CPE_PROJECT){
					IPath entryPath = entry.getPath();
					IResource member = workspaceRoot.findMember(entryPath);
					if (member != null && member.getType() == IResource.PROJECT){
						JavaProject project = (JavaProject)JavaCore.create((IProject)member);
						int index = visited.indexOf(project);
						if (index == -1 && cycleParticipants.contains(project))
							index = visited.indexOf(this); // another loop in the cycle exists
						if (index >= 0) { // only consider direct participants inside the cycle
							for (int size = visited.size(); index < size; index++)
								cycleParticipants.add(visited.get(index)); 
						} else {
							if(!doneTraversing.contains(project))
								project.updateCycleParticipants(null, visited, cycleParticipants,
workspaceRoot);
						}
					}
				}
			}
		} catch(JavaModelException e){
		}
		visited.remove(this);

		doneTraversing.add(this);
	}

The above was happening because I had 180 projects in my workspace and almost
many of them have "org.eclipse.core.boot" & "org.eclipse.core.runtime"
"org..xerces" in their classpath
so the method ended up trying to detect cycles and ended up with 10 levels of
recursive calls for the method "updateCycleParticipants"

The above is just a rudimentary fix. I don't know if there is some drawback to
this approach or something Iam overlooking as I said I checked it with some
scenarios and it 
did not eliminate any genuine cycle participants.

Please let me know if the above is useful in fixing the problem.

Comment 3 Philipe Mulet 2003-03-24 08:44:59 EST

This feels like a good performance improvement. We should not only cache cycle 
participants (which is fairly rare in general).

Comment 4 Philipe Mulet 2003-03-25 07:00:32 EST

When building a WSAD workspace with *.nl1 circular plugin fragments (bug in 
PDE?), the fix proposal improves the speed considerably, however some of the 
cycle detection doesn't occur any longer. Need to investigate.

Comment 5 Philipe Mulet 2003-03-25 08:54:04 EST

Steps:
- import all plugins from WSAD (~760 binary projects) with cycle severity 
turned as warning
- observe that lots of cycle warnings got generated (due to *.nl1 projects)
- import Eclipse SDK to refresh existing projects
- observe that all cycle markers are gone, though those outside Eclipse 
projects should have persisted
- change some classpath to introduce a cycle, then all cycle markers reappear.

Need to find a smaller testcase.

Comment 6 Philipe Mulet 2003-03-31 04:32:08 EST

*** Bug 35859 has been marked as a duplicate of this bug. ***

Comment 7 Philipe Mulet 2003-04-09 07:03:35 EDT

Following cycle detection code seems to have the good performance 
characteristics, and not causing mentionned grief:

/**
 * Update cycle markers for all java projects
 */
public static void updateAllCycleMarkers() throws JavaModelException {
	
	JavaModelManager manager = JavaModelManager.getJavaModelManager();
	IJavaProject[] projects = manager.getJavaModel().getJavaProjects();
	IWorkspaceRoot workspaceRoot = ResourcesPlugin.getWorkspace().getRoot();

	HashSet cycleParticipants = new HashSet();
	HashSet alreadyTraversed = new HashSet();
	int length = projects.length;
	
	// compute cycle participants
	ArrayList prereqChain = new ArrayList();
	for (int i = 0; i < length; i++){
		JavaProject project = (JavaProject)projects[i];
		if (!alreadyTraversed.contains(project)){
			prereqChain.clear();
			project.updateCycleParticipants(null, prereqChain, 
cycleParticipants, workspaceRoot, alreadyTraversed);
		}
	}
	
	for (int i = 0; i < length; i++){
		JavaProject project = (JavaProject)projects[i];
		
		if (cycleParticipants.contains(project)){
			IMarker cycleMarker = project.getCycleMarker();
			String circularCPOption = project.getOption
(JavaCore.CORE_CIRCULAR_CLASSPATH, true);
			int circularCPSeverity = JavaCore.ERROR.equals
(circularCPOption) ? IMarker.SEVERITY_ERROR : IMarker.SEVERITY_WARNING;
			if (cycleMarker != null) {
				// update existing cycle marker if needed
				try {
					int existingSeverity = ((Integer)
cycleMarker.getAttribute(IMarker.SEVERITY)).intValue();
					if (existingSeverity != 
circularCPSeverity) {
						cycleMarker.setAttribute
(IMarker.SEVERITY, circularCPSeverity);
					}
				} catch (CoreException e) {
					throw new JavaModelException(e);
				}
			} else {
				// create new marker
				project.createClasspathProblemMarker(
					new JavaModelStatus
(IJavaModelStatusConstants.CLASSPATH_CYCLE, project)); 
			}
		} else {
			project.flushClasspathProblemMarkers(true, false);
		}			
	}
}

/**
 * If a cycle is detected, then cycleParticipants contains all the project 
involved in this cycle (directly and indirectly),
 * no cycle if the set is empty (and started empty)
 */
public void updateCycleParticipants(
		IClasspathEntry[] preferredClasspath, 
		ArrayList prereqChain, 
		HashSet cycleParticipants, 
		IWorkspaceRoot workspaceRoot,
		HashSet alreadyTraversed){
			
	prereqChain.add(this);
	try {
		IClasspathEntry[] classpath = preferredClasspath == null ? 
getResolvedClasspath(true) : preferredClasspath;
		for (int i = 0, length = classpath.length; i < length; i++) {
			IClasspathEntry entry = classpath[i];
			
			if (entry.getEntryKind() == IClasspathEntry.CPE_PROJECT)
{
				IPath entryPath = entry.getPath();
				IResource member = workspaceRoot.findMember
(entryPath);
				if (member != null && member.getType() == 
IResource.PROJECT){
					JavaProject project = (JavaProject)
JavaCore.create((IProject)member);
					int index = cycleParticipants.contains
(project) ? 0 : prereqChain.indexOf(project);
					if (index >= 0) { // refer to cycle, or 
in cycle itself
						for (int size = prereqChain.size
(); index < size; index++) {
							cycleParticipants.add
(prereqChain.get(index)); 
						}
					} else {
						if (!alreadyTraversed.contains
(project)) {
						
	project.updateCycleParticipants(null, prereqChain, cycleParticipants, 
workspaceRoot, alreadyTraversed);
						}
					}
				}
			}
		}
	} catch(JavaModelException e){
	}
	prereqChain.remove(this);
	alreadyTraversed.add(this);
}

Comment 8 Philipe Mulet 2003-04-09 07:06:23 EDT

Created attachment 4518 [details]
Proposed implementation as an attachment

Comment 9 Philipe Mulet 2003-04-09 08:51:28 EDT

Released slightly better version, which doesn't create handle, but rather 
accumulate paths.

Fixed. 

Will also backport to 2.1 maintenance stream, and post a patch on JDT/Core 
update area shortly (http://dev.eclipse.org/viewcvs/index.cgi/%7Echeckout%
7E/jdt-core-home/r2.1/main.html#updates).

Comment 10 Philipe Mulet 2003-04-09 09:09:10 EDT

Backported to 2.1 maintenance stream.

Comment 11 Philipe Mulet 2003-04-10 07:19:59 EDT

Also IJavaProject#hasClasspathCycle suffered from a similar performance issue.
Fixed by using the new updateCycleParticipants implementation instead.
Backported this extra fix too.

Comment 12 Jerome Lanneluc 2003-04-15 10:46:14 EDT

Fixed in 2.2 stream as well.

Comment 13 David Audel 2003-06-02 10:29:16 EDT

Verified.

Comment 14 David Audel 2003-06-10 10:23:24 EDT

Verified for 3.0M1.