[Mono-devel-list] StringBuilder patch
Paolo Molaro
lupus at ximian.com
Tue Jan 13 08:02:28 EST 2004
On 01/12/04 Piers Haken wrote:
> > > + if (_length < (_str.Length / 2))
> >
> > Use a shift directly here, instead of the division, so we
> > don't have to bother optimizing it.
>
> 'GCC -O3' doesn't do this? You gotta be kidding me! (the JIT <i>can</i>
> shift this, right?)
Yes, the jit can do it.
> BTW: speaking of JIT optimizations, here's a few questions:
>
> - who's up for guessing the best x86 asm for this:
> int foo (int i) { return (i == 0) ? 3 : 7; }
> <hint> no branches </hint>
This code could be represented as branchless in IL code, too:
ldarg.0
ldc.i4.0
ceq
ldc.i4.0
ceq
ldc.i4.4 // or ldc.i4.2 shl
mul
ldc.i4.3
add
A simple burg rule can change the mul+add into a lea.
We should also probably add a cneq opcode to the mini IR, so that
we can simplify part of the code at an higher level.
> - how common is this construct?
It's not very likely that you'll be able to use the complex lea for for
this, but the patterns happens about 130 times in
mscorlib/System/System.dll/mcs.exe (see list at the end of the mail).
> - how easy would it be to implement support for this kind of optimization in
> the current JIT framework.
It's not hard to implement. In the peephole pass, when a cond branch is
found, you can look at the true and false basic blocks.
One should look like:
iconst %reg // or storei4_membase_imm
and the other:
iconst %reg // or storei4_membase_imm
br
If the regs are the same or if the base+offset values are the same and
the branch points to the bb following the first basic block, you found
the pattern. Then you need to find out the relation between the two
const values and apply a lea, a shift+add or whatever may be needed.
Any hacker willing to try it? A benchmark could be:
class T {
static int foo (int i) {
return i == 0? 3: 7;
}
static int Main (string[] args) {
int a = 0;
for (int i = 0; i < 100000000; ++i) {
a = foo (i);
}
return a;
}
}
Somewhat amusingly, mono with optimizations runs this test faster
than the MS runtime already (version 1.0: can't quote numbers because of
the stupid eula).
The only possible subtle issue that comes to mind is this: right now we
do the peephole pass right before emitting the native code for each
single basic block, but the maximum length of the native code of a basic
block has been already calculated. This is not an issue since the
current peephole opts always reduce code size, but it may not be the
case for this kind of optimization. So care must be taken, or the
peephole pass must be done at a different time.
lupus
--
-----------------------------------------------------------------
lupus at debian.org debian/rules
lupus at ximian.com Monkeys do it better
pattern found at I_0052 in Boolean:CompareTo, values: 0/-1
pattern found at I_0006 in Boolean:GetHashCode, values: 1/0
pattern found at I_0053 in Decimal:Parse, values: 1/0
pattern found at I_0007 in Array:compare, values: 0/-1
pattern found at I_05d9 in MiniParser:Parse, values: 515/7
pattern found at I_0001 in Convert:ToByte, values: 1/0
pattern found at I_0001 in Convert:ToDecimal, values: 1/0
pattern found at I_0001 in Convert:ToDouble, values: 1/0
pattern found at I_0001 in Convert:ToInt16, values: 1/0
pattern found at I_0001 in Convert:ToInt32, values: 1/0
pattern found at I_0001 in Convert:ToInt64, values: 1/0
pattern found at I_0001 in Convert:ToSByte, values: 1/0
pattern found at I_0001 in Convert:ToSingle, values: 1/0
pattern found at I_0001 in Convert:ToUInt16, values: 1/0
pattern found at I_0001 in Convert:ToUInt32, values: 1/0
pattern found at I_0001 in Convert:ToUInt64, values: 1/0
pattern found at I_04e6 in DateTime:_DoParse, values: 2000/1900
pattern found at I_01b9 in DateTime:_ToString, values: 1/2
pattern found at I_01e1 in DateTime:_ToString, values: 1/2
pattern found at I_0209 in DateTime:_ToString, values: 1/2
pattern found at I_0231 in DateTime:_ToString, values: 1/2
pattern found at I_0402 in DateTime:_ToString, values: 1/2
pattern found at I_0512 in DateTime:_ToString, values: 3/4
pattern found at I_01c0 in IntegerFormatter:FormatExponential, values: 69/101
pattern found at I_01cf in IntegerFormatter:FormatExponential, values: 69/101
pattern found at I_0174 in IntegerFormatter:FormatExponential, values: 69/101
pattern found at I_0175 in IntegerFormatter:FormatExponential, values: 69/101
pattern found at I_01f8 in IntegerFormatter:FormatGeneral, values: 69/101
pattern found at I_020c in IntegerFormatter:FormatGeneral, values: 69/101
pattern found at I_018c in IntegerFormatter:FormatGeneral, values: 69/101
pattern found at I_018e in IntegerFormatter:FormatGeneral, values: 69/101
pattern found at I_0022 in IntegerFormatter:FormatCustom, values: 1/0
pattern found at I_0020 in IntegerFormatter:FormatCustom, values: 1/0
pattern found at I_0020 in IntegerFormatter:FormatCustom, values: 1/0
pattern found at I_0022 in IntegerFormatter:FormatCustom, values: 1/0
pattern found at I_0015 in IntegerFormatter:FormatCustom, values: 0/1
pattern found at I_0016 in IntegerFormatter:FormatCustom, values: 0/1
pattern found at I_0015 in IntegerFormatter:FormatCustom, values: 0/1
pattern found at I_0016 in IntegerFormatter:FormatCustom, values: 0/1
pattern found at I_0210 in FormatParse:AddToken, values: 1/0
pattern found at I_01a2 in FormatParse:getNextToken, values: 1/2
pattern found at I_0041 in Math:IEEERemainder, values: 0/0
pattern found at I_001f in Math:Sign, values: 0/-1
pattern found at I_0031 in Math:Sign, values: 0/-1
pattern found at I_0029 in Math:Sign, values: 0/-1
pattern found at I_000b in Math:Sign, values: 0/-1
pattern found at I_000d in Math:Sign, values: 0/-1
pattern found at I_000d in Math:Sign, values: 0/-1
pattern found at I_000b in Math:Sign, values: 0/-1
pattern found at I_0037 in Calendar:ToFourDigitYear, values: 0/-100
pattern found at I_0066 in CCGregorianCalendar:fixed_from_dmy, values: -1/-2
pattern found at I_0009 in CCJulianCalendar:is_leap_year, values: 0/3
pattern found at I_0057 in CCJulianCalendar:fixed_from_dmy, values: -1/-2
pattern found at I_0006 in CCHebrewCalendar:last_month_of_year, values: 13/12
pattern found at I_0012 in CCHebrewCalendar:my_from_fixed, values: 7/1
pattern found at I_0016 in HebrewCalendar:M_Month, values: 6/7
pattern found at I_0023 in BinaryWriter:Write, values: 1/0
pattern found at I_0005 in FileStream:.ctor, values: 2/3
pattern found at I_0072 in StreamReader:Initialize, values: 1/0
pattern found at I_008d in StreamReader:Initialize, values: 0/2
pattern found at I_00ca in StringReader:ReadLine, values: 2/1
pattern found at I_0002 in UnicodeEncoding:.ctor, values: 1201/1200
pattern found at I_02b1 in UTF7Encoding:InternalGetChars, values: 0/16777216
pattern found at I_02c4 in UTF7Encoding:InternalGetChars, values: 33554432/0
pattern found at I_002b in BitVector32:ToString, values: 48/49
pattern found at I_0007 in ListDictionary:Contains, values: 1/0
pattern found at I_0045 in ListEntryEnumerator:MoveNext, values: 1/0
pattern found at I_0045 in ListEntryCollectionEnumerator:MoveNext, values: 1/0
pattern found at I_001c in _KeysEnumerator:MoveNext, values: 1/0
pattern found at I_0067 in ChunkStream:ReadBody, values: 2/1
pattern found at I_0006 in DnsPermissionAttribute:CreatePermission, values: 1/0
pattern found at I_02ca in IPv6Address:Parse, values: 6/8
pattern found at I_0394 in IPv6Address:Parse, values: 5/7
pattern found at I_03fb in IPv6Address:Parse, values: 6/8
pattern found at I_0006 in SocketPermission:Copy, values: 1/0
pattern found at I_0058 in Socket:CheckProtocolSupport, values: -1/0
pattern found at I_0084 in WebConnection:Connect, values: 15/1
pattern found at I_0006 in WebPermission:Copy, values: 1/0
pattern found at I_0052 in Match:NextMatch, values: -1/1
pattern found at I_00db in Parser:ParseGroup, values: 3/1
pattern found at I_00fd in Parser:ParseGroup, values: 7/5
pattern found at I_011f in Parser:ParseGroup, values: 2/1
pattern found at I_01e8 in Parser:ParseCharacterClass, values: 9/4
pattern found at I_0205 in Parser:ParseCharacterClass, values: 8/3
pattern found at I_0221 in Parser:ParseCharacterClass, values: 10/5
pattern found at I_0253 in Parser:ParseCharacterClass, values: 9/4
pattern found at I_0270 in Parser:ParseCharacterClass, values: 8/3
pattern found at I_028c in Parser:ParseCharacterClass, values: 10/5
pattern found at I_0168 in Parser:ParseSpecial, values: 9/4
pattern found at I_0182 in Parser:ParseSpecial, values: 8/3
pattern found at I_019b in Parser:ParseSpecial, values: 10/5
pattern found at I_01c7 in Parser:ParseSpecial, values: 9/4
pattern found at I_01e1 in Parser:ParseSpecial, values: 8/3
pattern found at I_01fa in Parser:ParseSpecial, values: 10/5
pattern found at I_020e in DTMXPathDocumentBuilder:Read, values: 6/4
pattern found at I_0001 in XPathNavigator:SelectAncestors, values: 1/0
pattern found at I_0023 in XPathNavigator:SelectAncestors, values: 1/0
pattern found at I_0001 in XPathNavigator:SelectDescendants, values: 5/4
pattern found at I_0023 in XPathNavigator:SelectDescendants, values: 5/4
pattern found at I_0040 in DTMXPathNavigator:ComparePosition, values: 1/0
pattern found at I_0089 in DTMXPathNavigator:ComparePosition, values: 1/0
pattern found at I_00d4 in DTMXPathNavigator:ComparePosition, values: 1/0
pattern found at I_00e9 in DTMXPathNavigator:ComparePosition, values: 0/2
pattern found at I_0180 in XslOutput:Fill, values: 1/2
pattern found at I_0003 in XsltCompiledContext:FindBestMethod, values: 48/16
pattern found at I_005b in DTDValidatingReader:ResolveEntity, values: 2/1
pattern found at I_0023 in DTDValidatingReader:get_NodeType, values: 13/3
pattern found at I_0086 in XmlNodeReader:ResolveEntity, values: 2/1
pattern found at I_0131 in XmlTextReader:ReadText, values: 14/13
pattern found at I_0076 in XmlTextReader:ReadWhitespace, values: 14/13
pattern found at I_0009 in XPathNumberComparer:.ctor, values: 1/-1
pattern found at I_0010 in XPathTextComparer:.ctor, values: -1/1
pattern found at I_0024 in XPathTextComparer:.ctor, values: 1/-1
pattern found at I_0007 in ExprBoolean:EvaluateNumber, values: 1/0
pattern found at I_0028 in ExtensionFunctionWrapper:Function, values: 0/1
pattern found at I_0194 in ExtensionFunctionWrapper:Function, values: 1/0
pattern found at I_0088 in ReflectedExtensionFunction:Function, values: 8/12
pattern found at I_004b in XmlSchemaComplexType:GetContentType, values: 2/1
pattern found at I_0068 in XmlSchemaExporter:AddSchemaElement, values: 1/0
pattern found at I_019c in Tokenizer:handle_preprocessing_directive, values: 8/0
pattern found at I_025b in Event:Define, values: 16/0
pattern found at I_0021 in Delegate:.ctor, values: 8/4
pattern found at I_001e in Enum:.ctor, values: 8/4
pattern found at I_0018 in FieldExpr:Report_AssignToReadonly, values: 191/198
pattern found at I_0039 in Invocation:BetterFunction, values: 1/0
pattern found at I_0420 in ArrayCreation:MakeByteBlob, values: 1/0
pattern found at I_0042 in IteratorHandler:ComputeConstructorTypes, values: 0/1
pattern found at I_0006 in Parameters:ComputeParameterTypes, values: 1/0
pattern found at I_0006 in Parameters:ComputeAndDefineParameterTypes, values: 1/0
pattern found at I_0054 in PendingImplementation:GetPendingImplementations, values: 1/0
pattern found at I_0008 in PendingImplementation:ImplementMethod, values: 1/2
pattern found at I_000d in PendingImplementation:ImplementIndexer, values: 1/2
pattern found at I_01d2 in Switch:EmitObjectInteger, values: 1/0
pattern found at I_0002 in TypeManager:SpecialContainerLookup, values: 8/4
More information about the Mono-devel-list
mailing list