313
edits
Mozilla 2/Strings/Static Analysis: Difference between revisions
Jump to navigation
Jump to search
Mozilla 2/Strings/Static Analysis (view source)
Revision as of 04:04, 28 February 2008
, 28 February 2008analysis notes
(gc strings backgroudn) |
(analysis notes) |
||
| Line 52: | Line 52: | ||
Another interesting application of HeapString is as a builder for string values that are to be stored in ImmutableStrings: the buffer can be passed (instead of copied) from a HeapString to a new ImmutableString as long as the HeapString's buffer pointer is set to null at the same time. | Another interesting application of HeapString is as a builder for string values that are to be stored in ImmutableStrings: the buffer can be passed (instead of copied) from a HeapString to a new ImmutableString as long as the HeapString's buffer pointer is set to null at the same time. | ||
''' | '''Dumbest Rewriting.''' Here I describe the dumb way to rewrite FF to use immutable strings. It probably wouldn't perform well, but it should work, providing a baseline for more elaborate rewritings. | ||
First, all heap strings and all string parameters become ImmutableString. Then, any points in the code where an ImmutableString is mutated are changed to use update operators. For example: | |||
immString.Append("foo") | |||
becomes something like | |||
immString = immString.Concat("foo") | |||
The Concat method of the new version should return a new ImmutableString with the result. The assignment operator then sets immString to point to the buffer of the new string. The old buffer is dropped on the floor, to be recovered later by GC. (In this version, the ImmutableStrings aren't really immutable, they just have immutable string buffers. But if you think of an ImmutableString instance as being a handle to an immutable string, sort of like a String pointer in Java, then it is immutable after all.) | |||
nsAutoStrings will stay the way they are (called AutoStackStrings in the terminology above). | |||
The main reason this rewriting is dumb is that when there is a sequence of mutation operations in the existing code (esp. in a loop), the dumb version does a corresponding sequence of string allocations, which is much more expensive than the current code's mutable strings. | |||
'''Second Dumbest Rewriting.''' The logical improvement to the dumbest rewriting is to try to use mutable strings when there is a sequence of mutation operations. Thus, where the current code has nsAString, we allow ourselves the choice of using ImmutableString or AutoStackString. We would ''like'' to use AutoStackString as much as possible, because it's cheap, but we have to be sure to use ImmutableString when necessary. Here is my type-inference-based idea: | |||
* Current nsAutoString stays (becomes AutoStackString). | |||
* Current strings on the heap (i.e., members of GCable classes or contained in hashtables/arrays) '''must''' become ImmutableString. | |||
* Strings not on the heap that have mutators called on them '''must''' become AutoStackString. | |||
* Other strings (mainly parameters) can be either Immutable or AutoStack. | |||
Now, we are left with 2 problems: | |||
Problem 1: heap strings are Immutable, but might have mutator methods called on them. We can always revert to the dumbest solution, but we'd like to do better. So, if any method makes more than one mutator call to a heap string, we'll rewrite the method to copy the string to a mutable HeapString at the beginning, and back to the heap string at the end. So: | |||
while (b) { | |||
mString.Append(stuff); | |||
} | |||
becomes | |||
HeapString temp(mString); // must copy--could be shared | |||
while (b) { | |||
temp.Append(stuff); | |||
} | |||
mString.Take(copy); // no copy--mString steals buffer | |||
Problem 2: the more interesting problem of selecting Immutable or AutoStack when we have the choice. To do this, we create a type variable for each string where we have the choice, and then set up a constraint system. Whenever there is an "assignment" between strings "a := b" (e.g., parameter passing), we place a constraint "a >= b". We then define "Immutable >= AutoStack" and find the least solution to the system (i.e., the one with the most AutoStacks). | |||
I need to think about that a little more. As described, the solution will always be "everything AutoStack", except where things have to be immutable. In that case, there needs to be inserted an AutoStack->Immutable conversion at the last moment. That seems OK in principle, but I'll have to look at some examples and see how it plays out in real code. | |||
There are also more optimizations that can be applied, such as using HeapString when the result will go to the heap, to save the copy from the stack. | |||