Matthew Dempsky has uploaded a new change for review.
https://gwt-review.googlesource.com/2460
Change subject: Reduce O(N^2) memory complexity to O(N)
......................................................................
Reduce O(N^2) memory complexity to O(N)
For long strings with lots of newlines, the current recursive
algorithm results in a bunch of nested call frames, each keeping a
large portion of the original string in memory. Switching to an
iterative algorithm avoids keeping more than one or two copies of the
input string alive in memory at a time.
Change-Id: I30301a58bad0244a41b08fb534c4cb18b90c9494
---
M user/src/com/google/gwt/user/rebind/ClassSourceFileComposer.java
1 file changed, 24 insertions(+), 22 deletions(-)
diff --git
a/user/src/com/google/gwt/user/rebind/ClassSourceFileComposer.java
b/user/src/com/google/gwt/user/rebind/ClassSourceFileComposer.java
index dd067fb..423713a 100644
--- a/user/src/com/google/gwt/user/rebind/ClassSourceFileComposer.java
+++ b/user/src/com/google/gwt/user/rebind/ClassSourceFileComposer.java
@@ -135,31 +135,33 @@
}
public void print(String s) {
- // If we just printed a newline, print an indent.
- //
- if (atStart) {
- for (int j = 0; j < indent; ++j) {
- printWriter.print(" ");
+ for (;;) {
+ // If we just printed a newline, print an indent.
+ if (atStart) {
+ for (int j = 0; j < indent; ++j) {
+ printWriter.print(" ");
+ }
+ if (inComment) {
+ printWriter.print(commentIndicator);
+ }
+ atStart = false;
}
- if (inComment) {
- printWriter.print(commentIndicator);
+
+ // Now find the next newline.
+ int i = s.indexOf("\n");
+
+ // If there's no newline or it's at the end of the string, just print
+ // and we're done.
+ if (i == -1 || i == s.length() - 1) {
+ printWriter.print(s);
+ return;
}
- atStart = false;
- }
- // Now print up to the end of the string or the next newline.
- //
- String rest = null;
- int i = s.indexOf("\n");
- if (i > -1 && i < s.length() - 1) {
- rest = s.substring(i + 1);
- s = s.substring(0, i + 1);
- }
- printWriter.print(s);
- // If rest is non-null, then s ended with a newline and we recurse.
- //
- if (rest != null) {
+
+ // Otherwise, print up to and including the newline, note that we
just
+ // printed a newline, and loop on the rest of the string.
+ printWriter.print(s.substring(0, i + 1));
+ s = s.substring(i + 1);
atStart = true;
- print(rest);
}
}
--
To view, visit https://gwt-review.googlesource.com/2460
To unsubscribe, visit https://gwt-review.googlesource.com/settings
Gerrit-MessageType: newchange
Gerrit-Change-Id: I30301a58bad0244a41b08fb534c4cb18b90c9494
Gerrit-PatchSet: 1
Gerrit-Project: gwt
Gerrit-Branch: master
Gerrit-Owner: Matthew Dempsky <[email protected]>
--
--
http://groups.google.com/group/Google-Web-Toolkit-Contributors
---
You received this message because you are subscribed to the Google Groups "Google Web Toolkit Contributors" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
For more options, visit https://groups.google.com/groups/opt_out.
