Greg Young [MVP]

Glad to be here Brendan. Nice one on the lagniappe, I had considerred it as well but there goes that idea :)

My gf is out of town this weekend = hopefully extra time to write ..

Greg

That's a good question, you are correct that I forgot to mention this, I will add a section to add this.

This will have 2 distinct behaviors (one when inlined one when not)

With inlining it is smart enough to realize what you are doing (and to undo it)

           for (int i = 0, j = length.Length; i < j; i++) {
00000014  xor         edx,edx
00000016  mov         eax,dword ptr [ecx+4]
00000019  test        eax,eax
0000001b  jle         00000026
               total |= i;
0000001d  or          esi,edx
           for (int i = 0, j = length.Length; i < j; i++) {
0000001f  add         edx,1
00000022  cmp         edx,eax
00000024  jl          0000001D
           }

This is identical to the code produced but i<length.Length

Without inlining it will put it into the preamble of the loop producing functional equivalent results to the other hoisted examples (although slightly different orderring and obviously the variable maintains a better scope) 

          for (int i = 0, j = length.GetUpperBound(0); i < j; i++) {
00000013  xor         esi,esi
00000015  mov         ecx,eax
00000017  xor         edx,edx
00000019  cmp         dword ptr [ecx],ecx
0000001b  call        792666A8
00000020  test        eax,eax
00000022  jle         0000002D
               total |= i;
00000024  or          edi,esi
           for (int i = 0, j = length.GetUpperBound(0); i < j; i++) {
00000026  add         esi,1
00000029  cmp         esi,eax
0000002b  jl          00000024
           }

The key thing to notice is that the JIT still does not realize what we are doing with array bounds hoists ...

            for (int i = 0, j = length.GetUpperBound(0); i < j; i++) {
00000016  xor         esi,esi
00000018  mov         ecx,edi
0000001a  xor         edx,edx
0000001c  cmp         dword ptr [ecx],ecx
0000001e  call        792664C8
00000023  test        eax,eax
00000025  jle         00000039
00000027  mov         edx,dword ptr [edi+4]
                total |= length;
0000002a  cmp         esi,edx
0000002c  jae         0000003F
0000002e  or          ebx,dword ptr [edi+esi*4+8]
            for (int i = 0, j = length.GetUpperBound(0); i < j; i++) {
00000032  add         esi,1
00000035  cmp         esi,eax
00000037  jl          0000002A
            }

Good catch!

Cheers,

Greg

I have some further information on the removal case that I will be posting .. I am waiting to hear back on a few things before I post. Basically if you assign a static/instance to a local variable removal will occur (but often times your explictness is also optimized out). I am trying to figure out if this is a bug or not and whether or not this should be considerred a best practice in 2.0 as the same optimization may in fact incur a penalty dealing with other JITs.

Just under 10 minutes ... I had fairly heavy tackle as I was after alligator blues and was striper fishing during slack tide. I caught 3 other smaller stripers (one of which took about 15 minutes to land, about a 15 lber the thing with him was that he ran back to his home the line for a lobster pot so I had to pull up the 15 lb striper + the weight of that line ... my arms hurt after that)

I am curious on your source derek ... this is not the case.

john:

its compliant with the C# spec

"First, the set of all accessible (§10.5) members named N declared in T
and the base types (§14.3.1) of T is constructed. Declarations that
include an override modifier are excluded from the set."


It being that it is compliant with the specification it cannot be called a compiler bug. I agree that it is non-intuitive and should be changed in the spec, should we fault the C# team for following the spec? Their goal is to provide a compiler that is compliant with ECMA 334.

Could you not offer the best of both worlds?

If the method is on the base it is not considerred for overload resolution. If the method is overriden in the derived class it is.

A few friends told me the house analogy was not a good one before hand but I still used it :( It is not a clean cut analogy you are correct.

Rusty: you make some great selling points against fixed price estimates. I will have to remember these wordings the next time I am forced to deal with it.

The problem does still exist in dealing with the contract though, the hiring company can be shafted on a pure block of hourly time basis. This is one of the things that the fixed price contract does help eliminate as the contract is contingent on working software (usually atleast passing UA testing). I think we can all agree that a huge portion of time is ramp up. If the hiring company loses that consulting firm after say 90 days the next firm will most likely need 30 days of ramp up to be as efficient (not to mention they will want to at the minimum go over everything previously done with a fine tooth comb)

Getting back to our other discussion .. There is still the problem in that many managers etc will outsource projects to absolve themselves of responsibility of the project. This is a problem in many industries but is esepcially prevalent in IT where management often does not have the first clue of how to run a project. If the project comes out well the manager takes full credit for it as it was their brilliant insight and choice of a quality firm to handle the process that made it a success. If it fails it is that the contracting company did not meet the requirements set, ship it to legal. As such we are stuck with a huge corporate mindset problem that I am completely unsure of how to attack ...

Jeff I am not sure that I am following the relation to your special case in the optimizer. Perhaps you can explain a bit more why you think there is a relation for this particular case.

Jeff .. you have brought up many points, I will do my best to address them.

1) for vs while vs etc. This is all handled by the C# compiler .. these things all look the same when viewed as IL. There is no such thing as a "for" in IL. The JIT only operates on the IL level so I don't really see these items causing too much of an issue. These items can be fairly complex but they are complex at the compiler level (not so much at the JIT level). To see better what I am referring to, run ildasm on the examples from the original for article (or the examples listed here).

2) Arrays .. remember that there are specific instructions for different types of arrays in IL so it knows the difference between a SZ and MD case. http://www.codeproject.com/dotnet/arrays.asp is a great article on this. Since it is being given IL instructions to deal with a SZ array it knows that the array does not have multiple dimensions and that it is 0 based etc.

3) "So since the length is not part of an array's type, what really is it.", for SZ arrays which is what we are dealing with here the size of the array is kept with the array instance it is located at the object reference + 4. We can see this being accessed in the following instruction.

0000000b  mov         eax,dword ptr [esi+4] //access array length

The length of an array is immutable, you can only change the array to be a different array (which would have a different length). Since a reference to the array is being held in a register it does not have to deal with the volatility problem it might have to deal with if it were directly reading from memory (i.e. if another thread changes the original reference to point to another array, it will still be pointing at the array it started off with; it will not be updated to point to the new array).

4) "Because of Garbage collection and shifting memory around might also be the reason for this additional check."

I am going to write a post on this but I will give you the abbreviated version here, I had a concern that was partially related (in code with bounds removed that garbage collection could possibly remove the item). This is however coverred in Jeffrey Richter's CLR via C# (chapter 20). Registers are considerred to be GC roots (see pages around 462-464 for a detailed explanation of what happens). The garbage collector will in fact come into managed code and change register values in the case that memory shifts.

"Naturally, moving the objects in memory invalidates all variables and CPU registers that contain pointers to the objects. So the garbage collector must revisit all of the application's roots and modify them so that each root's value points to the object's new memory location." p464

As such in the case of a memory move the esi register in this case (which points to the array's object reference) would be updated to reflect the new memory location. Since the array's length is bound to the instance of the array the length would move as well. The code internal to the loop would continue working with the new memory address as the offset being dealt with is calculated every iteration through the loop based upon the value in esi and the loop counter (edx) in the following line.

00000012  or          ecx,dword ptr [esi+edx*4+8]

So if the garbage collector were to interrupt midway through looping it is quite possible that you could end up with the situation ..

esi = 100000 edx = 0 write to 100008
esi = 100000 edx = 1 write to 100012
esi = 100000 edx = 2 write to 100016
GC
esi = 110000 edx = 3 write to 110016
esi = 110000 edx = 4 write to 110020

notice that GC would have changed the ESI register

that is right Jeffrey! though they would get bonus points for either :)

4- I think I have some but I will need to get into some documentation in order to determine the feasability of my thought.

I had figured out how to do some decent testing for BRE/Maps. Schemas were pretty straight forward (although what are you really going to "unit test" on either?). I would imagine functional tests would be best for schemas/xslts.

Orchestrations are really the big pain point for me as they seem like a place where things can really break :) I have been researching the possibility of hosting an orchestration in my own code. I could then fairly easily mock out the in/out ports and allow for a decent unit test ... I am still researching this though. The big problem here would be in maintainance (its alot faster to just make a small schema change than to go through and then change the mocks as well).

Overall I find biztalk to be a very intriguing product. I do however find a need for a "biztalk light" ... while great for scalability, there is a pretty heavy sacrafice on per item speed for smaller systems.

Also they REALLY need to get a good UI guy or twenty on the team :) the interface takes me back to VS.NET 1.0 and all the lovely intricacies you had to put to memory (like re-adding references so it sees changes, trying a restart of the environment if you have trouble, etc)

Ah good question, I will have to address that ... Of course I can only look at disassembled code in the production JIT (and even doing that to make a comment is well umm against the EULA:))

I can however point you to exactly how this works in the SSCLI the method being called is in prestub.cpp -http://dotnet.di.unipi.it/Content/sscli/docs/doxygen/clr/clr/prestub_8cpp-source.html, it is MethodDesc::DoPreStub .. it is quite a long and involved method but there are some comments there discussing how thread safety is handled (in fact in the SSCLI this is the method that the thunk calls). There is also a bit of discussion on this in SSCLI Essentials from O'Reilly

No edit .. try it for yourself

notice the construction code

00000000  push        esi  
00000001  mov         ecx,913080h
00000006  call        FFB21FAC
0000000b  mov         esi,eax

The address in ECX look familiar? :)


I believe what is happenning here is that the consructor is being inlined (and as such it is not being JIT'ed). Good catch, I hadn't noticed that, that is worth a post on its own!

hmmm ...

Test : JohnsReverse took 42553687187.3528 ns, average ns = 425536.871873528
Test : GregsInt32Reverse took 33369146730.09 ns, average ns = 333691.4673009
Press any key to continue . . .

in release with JIT optimizations ... 80k string size ... maybe I have bigger ratio of processor / memory speed?

 

but you are right .. the shifts are expensive ... using rotl/rotr on the register would remove this but I can't for the life of me get the JIT to produce that code :)

ok tested on another machine and they come out about the same ..

80k string 10000 iterations

Test : JohnsReverse took 3043694595.65126 ns, average ns = 304369.459565126
Test : GregsInt32Reverse took 2963980647.19858 ns, average ns = 296398.064719858

800 byte string 1000000 iterations.
Test : JohnsReverse took 1610683234.92359 ns, average ns = 1610.68323492359
Test : GregsInt32Reverse took 1678762222.35589 ns, average ns = 1678.76222235589

although you are right as well in that I could optimize a bit better too by removing the stop variable and just using begin < end

ROTL ROTL my kingdom for a ROTL

ok after reading up some documentation on various intel chips. ROTL has the same performance as SHL .. I can therefore assume that the following code would execute at the same speed as the ROTL

       public static unsafe string GregsInt32Reverse(string s) {
           UInt32 Low;
           UInt32 High;
           string ret = string.Copy(s);
           fixed (char* start = ret) {
               UInt32* begin = (UInt32*)start;
               UInt32* end = (UInt32*)(start + s.Length - 2);
               while (begin < end) {
                   Low = *begin;
                   Low = (Low) << 16;
                   *end = Low;
                   High = *end;
                   High = (High) << 16;
                   *begin = High;
                   begin++;
                   end--;
               }
           }
           return ret;
       }

This code is about 20% faster than the simple unsafe on the machines where it came up being identical previously. Of course the problem is that its not actually reversing as its losing the overflow :) It wins for 20 byte, 80 byte, 800 byte, 8k, and 80k ... now if only I could get a rotl.

I am toying with adding an IL instruction to mono right now to offer a more definate proof that this optimization really exists (unless people would be willing to accept me copy/pasting the JIT generated assembly to MASM, alterring it and running it there?)

very nice! (I hadnt thought of stackalloc which should be a touch faster)


Per plugin JIT, did you know this was originally looking like it was going to be done? Way back in the days of 1.0 beta there were 3 JITs. There was optjit (if i remember this one properly), jit, and econojit (which implemented code pitching to amortize memory usage this JIT can be found in SSCLI now) ... (there was also prejit ... what a name Pre-JustInTime hmm :)...so they renamed it to ngen)

These jits were plugin based with the CLR, you decided depending on your circumstances which you wanted to use. It had been discussed to make the interface public ... if you look back into the dotnet lists on develop.com you should find them (2001 I believe)

Personally I don't want to write my own JIT but I would like a JIT that optimized to some of the things I mention. This is a prime case of where the CONCEPT of JIT rocks. Not all processors have a hardware based rotate instruction (x86 does) but on a power pc the preferred method is to use 2 32 bit registers emulating a 64 bit register, shl (overflowing into the second register then or them together). The ability for me to be able to write (val << 16) | (val>>16) and it to pick it up and optimize that pattern for the CPU (or to let me use a rotl instruction in IL) is the main benefit of compiling at runtime with a known environment.

*DELETED*