diff --git a/org.eclipse.search.tests/src/org/eclipse/search/core/tests/TestSearchResult.java b/org.eclipse.search.tests/src/org/eclipse/search/core/tests/TestSearchResult.java
index 3e88db4..a2e4b11 100644
--- a/org.eclipse.search.tests/src/org/eclipse/search/core/tests/TestSearchResult.java
+++ b/org.eclipse.search.tests/src/org/eclipse/search/core/tests/TestSearchResult.java
@@ -102,23 +102,6 @@
 	}
 
 	@Test
-	public void testAddMatchOrderPreserving() {
-		ISearchQuery query= new NullQuery();
-		AbstractTextSearchResult result= (AbstractTextSearchResult) query.getSearchResult();
-
-		String object= "object"; //$NON-NLS-1$
-
-		Match match1= new Match(object, 1, 0);
-		result.addMatch(match1);
-		assertEquals(result.getMatchCount(), 1);
-		Match match2= new Match(object, 1, 0);
-		result.addMatch(match2);
-		Match[] matches= result.getMatches(object);
-		assertTrue("matches[0]", matches[0] == match1);
-		assertTrue("matches[1]", matches[1] == match2);
-	}
-
-	@Test
 	public void testAddMatches() {
 		ISearchQuery query= new NullQuery();
 		AbstractTextSearchResult result= (AbstractTextSearchResult) query.getSearchResult();
diff --git a/org.eclipse.search/META-INF/MANIFEST.MF b/org.eclipse.search/META-INF/MANIFEST.MF
index 97d1b0a..e3699b9 100644
--- a/org.eclipse.search/META-INF/MANIFEST.MF
+++ b/org.eclipse.search/META-INF/MANIFEST.MF
@@ -2,7 +2,7 @@
 Bundle-ManifestVersion: 2
 Bundle-Name: %pluginName
 Bundle-SymbolicName: org.eclipse.search; singleton:=true
-Bundle-Version: 3.13.400.qualifier
+Bundle-Version: 3.14.0.qualifier
 Bundle-Activator: org.eclipse.search.internal.ui.SearchPlugin
 Bundle-ActivationPolicy: lazy
 Bundle-Vendor: %providerName
diff --git a/org.eclipse.search/new search/org/eclipse/search/ui/text/AbstractTextSearchResult.java b/org.eclipse.search/new search/org/eclipse/search/ui/text/AbstractTextSearchResult.java
index c013321..02f660d 100644
--- a/org.eclipse.search/new search/org/eclipse/search/ui/text/AbstractTextSearchResult.java
+++ b/org.eclipse.search/new search/org/eclipse/search/ui/text/AbstractTextSearchResult.java
@@ -14,12 +14,16 @@
 package org.eclipse.search.ui.text;
 
 import java.util.ArrayList;
+import java.util.Arrays;
 import java.util.Collection;
-import java.util.HashMap;
+import java.util.Collections;
+import java.util.Enumeration;
 import java.util.HashSet;
 import java.util.Iterator;
 import java.util.List;
-import java.util.Map;
+import java.util.Set;
+import java.util.concurrent.ConcurrentHashMap;
+import java.util.concurrent.ConcurrentMap;
 
 import org.eclipse.search.ui.ISearchResult;
 import org.eclipse.search.ui.ISearchResultListener;
@@ -36,7 +40,7 @@
 
 	private static final Match[] EMPTY_ARRAY= new Match[0];
 
-	private final Map<Object, List<Match>> fElementsToMatches;
+	private final ConcurrentMap<Object, Set<Match>> fElementsToMatches;
 	private final List<ISearchResultListener> fListeners;
 	private final MatchEvent fMatchEvent;
 
@@ -46,7 +50,7 @@
 	 * Constructs a new <code>AbstractTextSearchResult</code>
 	 */
 	protected AbstractTextSearchResult() {
-		fElementsToMatches= new HashMap<>();
+		fElementsToMatches= new ConcurrentHashMap<>();
 		fListeners= new ArrayList<>();
 		fMatchEvent= new MatchEvent(this);
 
@@ -55,19 +59,47 @@
 
 	/**
 	 * Returns an array with all matches reported against the given element.
-	 * Note that all matches of the given element are returned. The filter state of the matches is not relevant.
+	 * Note that all matches of the given element are returned. The filter state
+	 * of the matches is not relevant. The matches are reported sorted per
+	 * offset and length. The order may be important for example stepping
+	 * between matches (see bug 58417). For calculating just a match count the
+	 * order is not needed and the faster {@link #getMatchSet(Object)} should be used instead.
+	 * The order of reported matches found (with equal offset and length) is not preserved
+	 * (Does not make sense	during parallel search).
 	 *
-	 * @param element the element to report matches for
+	 * @param element
+	 *            the element to report matches for
 	 * @return all matches reported for this element
 	 * @see Match#getElement()
 	 */
 	public Match[] getMatches(Object element) {
-		synchronized (fElementsToMatches) {
-			List<Match> matches= fElementsToMatches.get(element);
-			if (matches != null)
-				return matches.toArray(new Match[matches.size()]);
-			return EMPTY_ARRAY;
+		Set<Match> matches = fElementsToMatches.get(element);
+		if (matches != null) {
+			Match[] sortingCopy = matches.toArray(new Match[matches.size()]);
+			Arrays.sort(sortingCopy, AbstractTextSearchResult::compare);
+			return sortingCopy;
 		}
+		return EMPTY_ARRAY;
+	}
+
+	/**
+	 * Returns an Enumeration of all matches reported against the given element.
+	 * Note that all matches of the given element are returned. The filter state
+	 * of the matches is not relevant. Like {@link #getMatches(Object)} but
+	 * unordered result.
+	 *
+	 * @param element
+	 *            the element to report matches for
+	 * @return all matches reported for this element
+	 * @since 3.14
+	 * @see AbstractTextSearchResult#getMatches(Object)
+	 */
+	public Enumeration<Match> getMatchSet(Object element) {
+		Set<Match> matches = fElementsToMatches.get(element);
+		if (matches != null) {
+			return Collections.enumeration(matches);
+		}
+		return Collections.emptyEnumeration();
 	}
 
 	/**
@@ -80,11 +112,7 @@
 	 * @param match the match to add
 	 */
 	public void addMatch(Match match) {
-		boolean hasAdded= false;
-		synchronized (fElementsToMatches) {
-			hasAdded= doAddMatch(match);
-		}
-		if (hasAdded)
+		if (didAddMatch(match))
 			fireChange(getSearchResultEvent(match, MatchEvent.ADDED));
 	}
 
@@ -98,10 +126,9 @@
 	 */
 	public void addMatches(Match[] matches) {
 		Collection<Match> reallyAdded= new ArrayList<>();
-		synchronized (fElementsToMatches) {
-			for (Match match : matches) {
-				if (doAddMatch(match))
-					reallyAdded.add(match);
+		for (Match match : matches) {
+			if (didAddMatch(match)) {
+				reallyAdded.add(match);
 			}
 		}
 		if (!reallyAdded.isEmpty())
@@ -121,46 +148,12 @@
 		return fMatchEvent;
 	}
 
-	private boolean doAddMatch(Match match) {
+	private boolean didAddMatch(Match match) {
 		updateFilterState(match);
-
-		List<Match> matches= fElementsToMatches.get(match.getElement());
-		if (matches == null) {
-			matches= new ArrayList<>();
-			fElementsToMatches.put(match.getElement(), matches);
-			matches.add(match);
-			return true;
-		}
-		if (!matches.contains(match)) {
-			insertSorted(matches, match);
-			return true;
-		}
-		return false;
+		return fElementsToMatches.computeIfAbsent(match.getElement(), k -> ConcurrentHashMap.newKeySet()).add(match);
 	}
 
-	private static void insertSorted(List<Match> matches, Match match) {
-		int insertIndex= getInsertIndex(matches, match);
-		matches.add(insertIndex, match);
-	}
-
-	private static int getInsertIndex(List<Match> matches, Match match) {
-		int count= matches.size();
-		int min = 0;
-		int max = count - 1;
-		while (min <= max) {
-			int mid = (min + max) / 2;
-			Match data = matches.get(mid);
-			int compare = compare(match, data);
-			if (compare > 0)
-				max = mid - 1;
-			else
-				min = mid + 1;
-		}
-		return min;
-	}
-
-
-	private static int compare(Match match1, Match match2) {
+	private static int compare(Match match2, Match match1) {
 		int diff= match2.getOffset()-match1.getOffset();
 		if (diff != 0)
 			return diff;
@@ -174,9 +167,7 @@
 	 * </p>
 	 */
 	public void removeAll() {
-		synchronized (fElementsToMatches) {
-			doRemoveAll();
-		}
+		doRemoveAll();
 		fireChange(new RemoveAllEvent(this));
 	}
 	private void doRemoveAll() {
@@ -192,11 +183,7 @@
 	 * @param match the match to remove
 	 */
 	public void removeMatch(Match match) {
-		boolean existed= false;
-		synchronized (fElementsToMatches) {
-			existed= doRemoveMatch(match);
-		}
-		if (existed)
+		if (didRemoveMatch(match))
 			fireChange(getSearchResultEvent(match, MatchEvent.REMOVED));
 	}
 
@@ -211,26 +198,25 @@
 	 */
 	public void removeMatches(Match[] matches) {
 		Collection<Match> existing= new ArrayList<>();
-		synchronized (fElementsToMatches) {
-			for (Match match : matches) {
-				if (doRemoveMatch(match))
-					existing.add(match); // no duplicate matches at this point
-			}
+		for (Match match : matches) {
+			if (didRemoveMatch(match))
+				existing.add(match); // no duplicate matches at this point
 		}
 		if (!existing.isEmpty())
 			fireChange(getSearchResultEvent(existing, MatchEvent.REMOVED));
 	}
 
 
-	private boolean doRemoveMatch(Match match) {
-		boolean existed= false;
-		List<Match> matches= fElementsToMatches.get(match.getElement());
-		if (matches != null) {
-			existed= matches.remove(match);
-			if (matches.isEmpty())
-				fElementsToMatches.remove(match.getElement());
-		}
-		return existed;
+	private boolean didRemoveMatch(Match match) {
+		boolean[] existed = new boolean[1];
+		fElementsToMatches.computeIfPresent(match.getElement(), (f, matches) -> {
+			existed[0] = matches.remove(match);
+			if (matches.isEmpty()) {
+				return null; // remove
+			}
+			return matches;
+		});
+		return existed[0];
 	}
 
 	@Override
@@ -309,12 +295,9 @@
 	 * @return total number of matches
 	 */
 	public int getMatchCount() {
-		int count= 0;
-		synchronized (fElementsToMatches) {
-			for (List<Match> element : fElementsToMatches.values()) {
-				if (element != null)
-					count+= element.size();
-			}
+		int count = 0;
+		for (Set<Match> element : fElementsToMatches.values()) {
+			count += element.size();
 		}
 		return count;
 	}
@@ -328,7 +311,7 @@
 	 * @return the number of matches reported against the element
 	 */
 	public int getMatchCount(Object element) {
-		List<Match> matches= fElementsToMatches.get(element);
+		Set<Match> matches = fElementsToMatches.get(element);
 		if (matches != null)
 			return matches.size();
 		return 0;
@@ -342,9 +325,7 @@
 	 * @return the set of elements in this search result
 	 */
 	public Object[] getElements() {
-		synchronized (fElementsToMatches) {
-			return fElementsToMatches.keySet().toArray();
-		}
+		return fElementsToMatches.keySet().toArray();
 	}
 
 	/**
diff --git a/org.eclipse.search/search/org/eclipse/search/internal/ui/text/FileTreeContentProvider.java b/org.eclipse.search/search/org/eclipse/search/internal/ui/text/FileTreeContentProvider.java
index e976f89..f0703db 100644
--- a/org.eclipse.search/search/org/eclipse/search/internal/ui/text/FileTreeContentProvider.java
+++ b/org.eclipse.search/search/org/eclipse/search/internal/ui/text/FileTreeContentProvider.java
@@ -166,7 +166,7 @@
 	private boolean hasMatches(Object element) {
 		if (element instanceof LineElement) {
 			LineElement lineElement= (LineElement) element;
-			return lineElement.getNumberOfMatches(fResult) > 0;
+			return lineElement.hasMatches(fResult);
 		}
 		return fResult.getMatchCount(element) > 0;
 	}
@@ -208,8 +208,8 @@
 					// change events to line elements are reported in text
 					// search
 					LineElement lineElement = (LineElement) updatedElement;
-					int nMatches = lineElement.getNumberOfMatches(fResult);
-					if (nMatches > 0) {
+					boolean hasMatches = lineElement.hasMatches(fResult);
+					if (hasMatches) {
 						if (singleElement && hasChild(lineElement.getParent(), lineElement)) {
 							fTreeViewer.update(new Object[] { lineElement, lineElement.getParent() }, null);
 						} else {
diff --git a/org.eclipse.search/search/org/eclipse/search/internal/ui/text/LineElement.java b/org.eclipse.search/search/org/eclipse/search/internal/ui/text/LineElement.java
index be7b807..7e86cd5 100644
--- a/org.eclipse.search/search/org/eclipse/search/internal/ui/text/LineElement.java
+++ b/org.eclipse.search/search/org/eclipse/search/internal/ui/text/LineElement.java
@@ -15,6 +15,7 @@
 package org.eclipse.search.internal.ui.text;
 
 import java.util.ArrayList;
+import java.util.Enumeration;
 
 import org.eclipse.core.resources.IResource;
 
@@ -66,9 +67,9 @@
 
 	public FileMatch[] getMatches(AbstractTextSearchResult result) {
 		ArrayList<FileMatch> res= new ArrayList<>();
-		Match[] matches= result.getMatches(fParent);
-		for (Match match : matches) {
-			FileMatch curr= (FileMatch) match;
+		Enumeration<Match> matches = result.getMatchSet(fParent);
+		while (matches.hasMoreElements()) {
+			FileMatch curr = (FileMatch) matches.nextElement();
 			if (curr.getLineElement() == this) {
 				res.add(curr);
 			}
@@ -78,9 +79,9 @@
 
 	public int getNumberOfMatches(AbstractTextSearchResult result) {
 		int count= 0;
-		Match[] matches= result.getMatches(fParent);
-		for (Match match : matches) {
-			FileMatch curr= (FileMatch) match;
+		Enumeration<Match> matches = result.getMatchSet(fParent);
+		while (matches.hasMoreElements()) {
+			FileMatch curr = (FileMatch) matches.nextElement();
 			if (curr.getLineElement() == this) {
 				count++;
 			}
@@ -88,5 +89,14 @@
 		return count;
 	}
 
-
+	public boolean hasMatches(AbstractTextSearchResult result) {
+		Enumeration<Match> matches = result.getMatchSet(fParent);
+		while (matches.hasMoreElements()) {
+			FileMatch curr = (FileMatch) matches.nextElement();
+			if (curr.getLineElement() == this) {
+				return true;
+			}
+		}
+		return false;
+	}
 }