[
Date Prev][
Date Next][
Thread Prev][
Thread Next][
Date Index][
Thread Index]
[
List Home]
|
[cdt-debug-dev] MIParser Change
|
Hi,
Assuming I correctly browsed the CDT/CVS repository, the following issues
apply to the head as well.
The MIParser is O(N^2) time in the length of a line returned from GDB.
While not an issue for OOB messages, this can be quite an issue for array
retrieval from the target and other potentially long messages. It's N^2
because it relies on StringBuffer.deleteCharAt( 0 ) and
StringBuffer.delete( 0, X ). These operations appear to do a copy of the
remaining data in the Sun Java library rather than bumping some index.
The following diffs are code that we are using on 1.0.1 to correct this
issue. It's relatively new, so there may be some bugs but has certainly
performed just fine in our initial regressions. Because of that I'm not
sending it in as a patch, more an FYI really. The basic change is exactly
what you'd expect: these diffs make MIParser use a new type of string
buffer that's quite efficient at deleting from the head of the array.
Now our issue has to do with GDB performance in array retrieval. It's quite
slow.
Thanks!
-Chris
songer@xxxxxxxxxxxxx
director of platform engineering
voice: 408 327 7341 fax: 408 986 8919
diff -r -u xide/org.eclipse.cdt.debug.mi.core/src/org/eclipse/cdt/debug/mi/core/output/MIParser.java xide_compare/org.eclipse.cdt.debug.mi.core/src/org/eclipse/cdt/debug/mi/core/output/MIParser.java
--- xide/org.eclipse.cdt.debug.mi.core/src/org/eclipse/cdt/debug/mi/core/output/MIParser.java Tue Jun 24 16:10:22 2003
+++ xide_compare/org.eclipse.cdt.debug.mi.core/src/org/eclipse/cdt/debug/mi/core/output/MIParser.java Sat Feb 1 12:54:44 2003
@@ -166,7 +166,7 @@
// Results are separated by commas.
if (buffer.length() > 0 && buffer.charAt(0) == ',') {
buffer.deleteCharAt(0);
- MIResult[] res = processMIResults(new FSB(buffer));
+ MIResult[] res = processMIResults(buffer);
rr.setMIResults(res);
}
return rr;
@@ -207,7 +207,7 @@
async.setAsyncClass(buffer.toString().trim());
buffer.setLength(0);
}
- MIResult[] res = processMIResults(new FSB(buffer));
+ MIResult[] res = processMIResults(buffer);
async.setMIResults(res);
oob = async;
} else if (c == '~' || c == '@' || c == '&') {
@@ -231,7 +231,7 @@
if (buffer.length() > 0 && buffer.charAt(0) == '"') {
buffer.deleteCharAt(0);
}
- stream.setCString(translateCString(new FSB(buffer)));
+ stream.setCString(translateCString(buffer));
oob = stream;
}
return oob;
@@ -241,7 +241,7 @@
* Assuming that the usual leading comma was consumed.
* Extract the MI Result comma seperated responses.
*/
- private MIResult[] processMIResults(FSB buffer) {
+ private MIResult[] processMIResults(StringBuffer buffer) {
List aList = new ArrayList();
MIResult result = processMIResult(buffer);
if (result != null) {
@@ -261,11 +261,11 @@
* Construct the MIResult. Characters will be consume/delete
* moving forward constructing the AST.
*/
- private MIResult processMIResult(FSB buffer) {
+ private MIResult processMIResult(StringBuffer buffer) {
MIResult result = new MIResult();
int equal;
if (buffer.length() > 0 && Character.isLetter(buffer.charAt(0))
- && (equal = buffer.indexOf('=')) != -1) {
+ && (equal = buffer.toString().indexOf('=')) != -1) {
String variable = buffer.substring(0, equal);
result.setVariable(variable);
buffer.delete(0, equal + 1);
@@ -282,7 +282,7 @@
/**
* Find a MIValue implementation or return null.
*/
- private MIValue processMIValue(FSB buffer) {
+ private MIValue processMIValue(StringBuffer buffer) {
MIValue value = null;
if (buffer.length() > 0) {
if (buffer.charAt(0) == '{') {
@@ -306,7 +306,7 @@
* go to the closing '}' consuming/deleting all the characters.
* This is usually call by processMIvalue();
*/
- private MIValue processMITuple(FSB buffer) {
+ private MIValue processMITuple(StringBuffer buffer) {
MITuple tuple = new MITuple();
MIResult[] results = null;
// Catch closing '}'
@@ -327,7 +327,7 @@
* Assuming the leading '[' was deleted, find the closing
* ']' consuming/delete chars from the StringBuffer.
*/
- private MIValue processMIList(FSB buffer) {
+ private MIValue processMIList(StringBuffer buffer) {
MIList list = new MIList();
List valueList = new ArrayList();
List resultList = new ArrayList();
@@ -365,7 +365,7 @@
* backslach escaping and return the string __without__ the enclosing double quotes
* The orignal StringBuffer will move forward.
*/
- private String translateCString(FSB buffer) {
+ private String translateCString(StringBuffer buffer) {
boolean escape = false;
boolean closingQuotes = false;
@@ -400,134 +400,4 @@
buffer.delete(0, index);
return sb.toString();
}
-
- /**
- * Fast String Buffer class. MIParser does a lot
- * of deleting off the front of a string, that's clearly
- * an order N operation for StringBuffer which makes
- * the MIParser an order N^2 operation. There are "issues"
- * with this for large arrays. Use of FSB rather than String
- * Buffer makes MIParser N rather than N^2 because FSB can
- * delete from the front in constant time.
- */
- public class FSB
- {
- StringBuffer buf;
- int pos;
- boolean shared;
-
- public FSB( StringBuffer buf )
- {
- this.buf = buf;
- pos = 0;
- shared = false;
- }
-
- public FSB( FSB fbuf )
- {
- pos = fbuf.pos;
- buf = fbuf.buf;
- shared = true;
- }
-
- public int length()
- {
- int res = buf.length() - pos;
- if( res < 0 )
- return 0;
-
- return res;
- }
-
- public char charAt( int index )
- {
- return buf.charAt(index + pos);
- }
-
- private void resolveCopy( )
- {
- if( shared )
- {
- buf = new StringBuffer( buf.toString() );
- shared = false;
- }
- }
-
- public FSB deleteCharAt( int index )
- {
- if( index == 0 )
- {
- pos++;
- }
- else
- {
- resolveCopy();
- buf = buf.deleteCharAt(pos + index);
- }
-
- return this;
- }
-
- public FSB delete( int start, int end )
- {
- if( start == 0 )
- {
- pos = pos + end - start;
- }
- else
- {
- resolveCopy();
- buf.delete(start + pos, end + pos);
- }
-
- return this;
- }
-
- public void setLength( int a )
- {
- if( a == 0 )
- pos = buf.length();
- else
- {
- // panic! fortunately we don't do this.
- }
- }
-
- public String substring( int start, int end )
- {
- return buf.substring( start + pos, end + pos );
- }
-
- public String toString()
- {
- return buf.substring( pos, buf.length());
- }
-
- int indexOf( char c )
- {
- int len = buf.length();
- for( int i = pos ; i < len ; i++ )
- {
- if( buf.charAt(i) == c )
- return i - pos;
- }
-
- return -1;
- }
-
- boolean startsWith( String s )
- {
- int len = Math.min( s.length(), length());
- if( len < s.length() )
- return false;
-
- for( int i = 0 ; i < len ; i++ )
- {
- if(s.charAt( i ) != buf.charAt( pos + i ))
- return false;
- }
-
- return true;
- }
- }
}
