[
Date Prev][
Date Next][
Thread Prev][
Thread Next][
Date Index][
Thread Index]
[
List Home]
|
Re: [cdt-debug-dev] MIParser Change
|
>
> --=====================_109560890==_
> Content-Type: text/plain; charset="us-ascii"; format=flowed
>
>
> Hi,
>
> Assuming I correctly browsed the CDT/CVS repository, the following issues
> apply to the head as well.
>
Applied to the head with appropriate Changelog entries, thanks.
===================================================================
Index: ChangeLog
===================================================================
RCS file: /home/tools/org.eclipse.cdt.debug.mi.core/ChangeLog,v
retrieving revision 1.144
diff -u -r1.144 ChangeLog
--- ChangeLog 19 Jun 2003 03:39:27 -0000 1.144
+++ ChangeLog 25 Jun 2003 19:03:50 -0000
@@ -1,3 +1,22 @@
+2003-06-25 Alain Magloire
+
+ Patch from Chris Songer, excerpt from its email:
+ 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.
+
+ * src/org/eclipse/cdt/debug/mi/core/output/MIParser.java
+
2003-06-18 Alain Magloire
* src/org/eclipse/cdt/debug/mi/core/cdi/event/ChangedEvent.java:
Index: src/org/eclipse/cdt/debug/mi/core/output/MIParser.java
===================================================================
RCS file: /home/tools/org.eclipse.cdt.debug.mi.core/src/org/eclipse/cdt/debug/mi/core/output/MIParser.java,v
retrieving revision 1.11
diff -u -r1.11 MIParser.java
--- src/org/eclipse/cdt/debug/mi/core/output/MIParser.java 15 Aug 2002 18:38:59 -0000 1.11
+++ src/org/eclipse/cdt/debug/mi/core/output/MIParser.java 25 Jun 2003 19:03:50 -0000
@@ -121,7 +121,7 @@
if (token.charAt(0) == '^') {
token.deleteCharAt(0);
rr = processMIResultRecord(token, id);
- } else if(token.toString().startsWith(MIOutput.terminator)) {
+ } else if (token.toString().startsWith(MIOutput.terminator)) {
//break; // Do nothing.
} else {
MIOOBRecord band = processMIOOBRecord(token, id);
@@ -166,7 +166,7 @@
// Results are separated by commas.
if (buffer.length() > 0 && buffer.charAt(0) == ',') {
buffer.deleteCharAt(0);
- MIResult[] res = processMIResults(buffer);
+ MIResult[] res = processMIResults(new FSB(buffer));
rr.setMIResults(res);
}
return rr;
@@ -207,7 +207,7 @@
async.setAsyncClass(buffer.toString().trim());
buffer.setLength(0);
}
- MIResult[] res = processMIResults(buffer);
+ MIResult[] res = processMIResults(new FSB(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(buffer));
+ stream.setCString(translateCString(new FSB(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(StringBuffer buffer) {
+ private MIResult[] processMIResults(FSB buffer) {
List aList = new ArrayList();
MIResult result = processMIResult(buffer);
if (result != null) {
@@ -261,11 +261,10 @@
* Construct the MIResult. Characters will be consume/delete
* moving forward constructing the AST.
*/
- private MIResult processMIResult(StringBuffer buffer) {
+ private MIResult processMIResult(FSB buffer) {
MIResult result = new MIResult();
int equal;
- if (buffer.length() > 0 && Character.isLetter(buffer.charAt(0))
- && (equal = buffer.toString().indexOf('=')) != -1) {
+ if (buffer.length() > 0 && Character.isLetter(buffer.charAt(0)) && (equal = buffer.indexOf('=')) != -1) {
String variable = buffer.substring(0, equal);
result.setVariable(variable);
buffer.delete(0, equal + 1);
@@ -282,7 +281,7 @@
/**
* Find a MIValue implementation or return null.
*/
- private MIValue processMIValue(StringBuffer buffer) {
+ private MIValue processMIValue(FSB buffer) {
MIValue value = null;
if (buffer.length() > 0) {
if (buffer.charAt(0) == '{') {
@@ -306,7 +305,7 @@
* go to the closing '}' consuming/deleting all the characters.
* This is usually call by processMIvalue();
*/
- private MIValue processMITuple(StringBuffer buffer) {
+ private MIValue processMITuple(FSB buffer) {
MITuple tuple = new MITuple();
MIResult[] results = null;
// Catch closing '}'
@@ -327,7 +326,7 @@
* Assuming the leading '[' was deleted, find the closing
* ']' consuming/delete chars from the StringBuffer.
*/
- private MIValue processMIList(StringBuffer buffer) {
+ private MIValue processMIList(FSB buffer) {
MIList list = new MIList();
List valueList = new ArrayList();
List resultList = new ArrayList();
@@ -337,7 +336,7 @@
MIValue value = processMIValue(buffer);
if (value != null) {
valueList.add(value);
- } else {
+ } else {
MIResult result = processMIResult(buffer);
if (result != null) {
resultList.add(result);
@@ -350,8 +349,8 @@
if (buffer.length() > 0 && buffer.charAt(0) == ']') {
buffer.deleteCharAt(0);
}
- MIValue[] values = (MIValue[])valueList.toArray(new MIValue[valueList.size()]);
- MIResult[] res = (MIResult[])resultList.toArray(new MIResult[resultList.size()]);
+ MIValue[] values = (MIValue[]) valueList.toArray(new MIValue[valueList.size()]);
+ MIResult[] res = (MIResult[]) resultList.toArray(new MIResult[resultList.size()]);
list.setMIValues(values);
list.setMIResults(res);
return list;
@@ -365,7 +364,7 @@
* backslach escaping and return the string __without__ the enclosing double quotes
* The orignal StringBuffer will move forward.
*/
- private String translateCString(StringBuffer buffer) {
+ private String translateCString(FSB buffer) {
boolean escape = false;
boolean closingQuotes = false;
@@ -383,7 +382,7 @@
}
} else if (c == '"') {
if (escape) {
- sb.append(c);;
+ sb.append(c);
escape = false;
} else {
// Bail out.
@@ -399,5 +398,112 @@
}
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;
+ }
}
}
