Open Mind Tree

• Take a "high" pointer and a "low" pointer and keep cutting the space between them in half until they run into each other.
• One of them points to what you're looking for, or it's not there.

 1    static public int search1(int [] array, int target)
 2    {
 3      int high = array.length, low = -1, probe;
 4      while (high - low > 1)
 5      {
 6          probe = (low + high) >>> 1;
 7          if (array[probe] > target)
 8              high = probe;
 9          else
10              low = probe;
11      }
12      if (low == -1 || array[low] != target)
13          return -1;
14      else
15          return low;
16    }

• Line 3: Note that the high and low bounds are set one off the ends of the array, neither of them are initially valid array indices. This makes all sorts of corner cases go away.
• Line 4: This loop runs till the high and low bounds are next to each other; there is no loop breakout.
• Line 6: Check and satisfy yourself that probe can never fail to be a valid array index, nor can it end up out of the closedhigh-low interval.
• Lines 7-10: The loop invariant is that high is one off the end of the array, or it points at something greater than target; lowis either -1 or points to something <= target.
• Lines 12-15: If the search succeeded, low will end up pointing at the target. We can't test for that directly, because if we started with something lower than the lowest value in the array, low will be left at -1.

static public int search(int [] array, int target)
{
    int high = array.length, low = -1, probe;
    while (high - low > 1)
    {
        probe = (low + high) >>> 1;
        if (array[probe] < target)
            low = probe;
        else
            high = probe;
    }
    if (high == array.length || array[high] != target)
        return -1;
    else
        return high;
}

static public int [] range(int [] array, int floor, int ceiling)
{
    int [] answer = new int[2];
    int high, low, probe;

    // work on floor
    high = array.length; low = -1;
    while (high - low > 1)
    {
        probe = (low + high) >>> 1;
        if (array[probe] < floor)
            low = probe;
        else
            high = probe;
    }
    answer[0] = low;

    // work on ceiling
    high = array.length; low = -1;
    while (high - low > 1)
    {
        probe = (low + high) >>> 1;
        if (array[probe] > ceiling)
            high = probe;
        else
            low = probe;
    }
    answer[1] = high;
    return answer;
}

Linear versus Binary Search

  
public class Search
{
    //--------------------------------------------------------------
    // Linear search method: searches an array of characters.
    // Returns the index of the first element that matches search
    // target, if possible. If no match is found, returns -1.
    //--------------------------------------------------------------
    public static int linear(char[] x, char target) 
    {
 int index; 
 for (index=0; index < x.length; index++)
     if (target == x[index]) return index;

 return -1; //not found
    }

    //--------------------------------------------------------------
    // Linear search method: searches an array of integers.
    // Returns the index of the first element that matches search
    // target, if possible. If no match is found, returns -1.
    //--------------------------------------------------------------
    public static int linear(int[] x, int target) 
    {
 int index; 
 for (index=0; index < x.length; index++)
     if (target == x[index]) return index;

 return -1; //not found
    }

    //--------------------------------------------------------------
    // Linear search method: searches an array of Strings.
    // Returns the index of the first element that matches search
    // target, if possible. If no match is found, returns -1.
    //--------------------------------------------------------------
    public static int linear(String[] x, String target) 
    {
 int index; 
 for (index=0; index < x.length; index++)
     if ( target.equals(x[index]) ) return index;

 return -1; //not found
    }


    //--------------------------------------------------------------
    // Binary search method: searches a SORTED array of characters.
    // Returns the index of the first element that matches search
    // target, if possible. If no match is found, returns -1.
    //--------------------------------------------------------------
    public static int binary(char[] x, char target)
    {
 int midpoint;
 int start=0, end=x.length-1;
 while (start <= end) 
     {
  midpoint = (start + end)/2;
  if (target < x[midpoint]) end = midpoint-1;
  if (target == x[midpoint]) return midpoint;
  if (target > x[midpoint]) start = midpoint+1;
     }

 return -1;
    }

    //--------------------------------------------------------------
    // Binary search method: searches a SORTED array of integers.
    // Returns the index of the first element that matches search
    // target, if possible. If no match is found, returns -1.
    //--------------------------------------------------------------
    public static int binary(int[] x, int target)
    {
 int midpoint;
 int start=0, end=x.length-1;
 while (start <= end) 
     {
  midpoint = (start + end)/2;
  if (target < x[midpoint]) end = midpoint-1;
  if (target == x[midpoint]) return midpoint;
  if (target > x[midpoint]) start = midpoint+1;
     }

 return -1;
    }

    //--------------------------------------------------------------
    // Binary search method: searches a SORTED array of Strings.
    // Returns the index of the first element that matches search
    // target, if possible. If no match is found, returns -1.
    //--------------------------------------------------------------
    public static int binary(String[] x, String target)
    {
 int midpoint;
 int start=0, end=x.length-1;
 while (start <= end) 
     {
  midpoint = (start + end)/2;
  if ( target.compareTo(x[midpoint]) < 0 ) end = midpoint-1;
  if ( target.compareTo(x[midpoint]) == 0 ) return midpoint;
  if ( target.compareTo(x[midpoint]) > 0 ) start = midpoint+1;
     }

 return -1;
    }




    //--------------------------------------------------------------
    // A simple main method to test our Search methods. 
    //--------------------------------------------------------------
    public static void main(String[] args)
    {
 char[] c =  {'w', 'e', '9', 'q', '[', 'a', 'u', '3', 'z', 
                     'b', '%', 'q', 'n', 'A', '-', 'D', 'k', 'I',
                     'S', 'q', 'T', '#', 'G', 'Y', 'E', '8'};
      
 char[] d = {'A', 'C', 'E', 'I', 'O', 'P', 'U', 'X' , 'Z'}; 

 int[] e = {10, 24, 32, 33, 40, 51, 53, 55, 61, 72}; 

 String[] f = {"cat", "dog", "horse", "iguana", "llama", "monkey"};
 
 System.out.println("Test linear (char):");
        System.out.println(Search.linear(c,'#'));
        System.out.println(Search.linear(c,'&'));

 System.out.println("\nTest linear (int):");
        System.out.println(Search.linear(e,61));
        System.out.println(Search.linear(e,50));

 System.out.println("\nTest linear (String):");
        System.out.println(Search.linear(f, "cat"));
        System.out.println(Search.linear(f, "elephant"));


 System.out.println("\n\n\nNow we test binary (char):");
        System.out.println(Search.binary(d,'E'));
        System.out.println(Search.binary(d,'P'));
        System.out.println(Search.binary(d,'Z'));
        System.out.println(Search.binary(d,'A'));
        System.out.println(Search.binary(d,'&'));

 System.out.println("\nTest binary (int):");
        System.out.println(Search.binary(e,32));
        System.out.println(Search.binary(e,33));
        System.out.println(Search.binary(e,10));
        System.out.println(Search.binary(e,72));
        System.out.println(Search.binary(e,50));

 System.out.println("\nTest binary (String):");
        System.out.println(Search.binary(f,"dog"));
        System.out.println(Search.binary(f,"llama"));
        System.out.println(Search.binary(f,"monkey"));
        System.out.println(Search.binary(f,"cat"));
        System.out.println(Search.binary(f,"elephant"));


    }
}

[doty@weyl doty]$ javac Search.java
[doty@weyl doty]$ java Search
Test linear (char):
21
-1

Test linear (int):
8
-1

Test linear (String):
0
-1



Now we test binary (char):
2
5
8
0
-1

Test binary (int):
2
3
0
9
-1

Test binary (String):
1
4
5
0
-1

"I promise I will not ship slow code. Speed is a feature I care about. Every day I will pay attention to the performance of my code. I will regularly and methodically measure its speed and size. I will learn, build, or buy the tools I need to do this. It's my responsibility."

{ complex a, b, c, d; … a = b + c * d; }

"It is important to understand how your programming language is implemented. Such knowledge dispels the fear and wonder of "What on earth is the compiler doing here?"; imparts confidence to use the new features; and provides insight when debugging and learning other language features. It also gives a feel for the relative costs of different coding choices that is necessary to write the most efficient code day to day."

Why Managed Code?

What Is the Secret to Writing Faster Managed Code?

The Knowledge

Towards a Cost Model for Managed Code

The Just-in-Time compiler

• Constant folding
• Constant and copy propagation
• Common subexpression elimination
• Code motion of loop invariants
• Dead store and dead code elimination
• Register allocation
• Method inlining
• Loop unrolling (small loops with small bodies)

Automatic Memory Management

What Things Cost in Managed Code

Arithmetic Operations

int add               a = a + b + c + d + e + f + g + h + i;
0000004c 8B 54 24 10      mov         edx,dword ptr [esp+10h] 
00000050 03 54 24 14      add         edx,dword ptr [esp+14h] 
00000054 03 54 24 18      add         edx,dword ptr [esp+18h] 
00000058 03 54 24 1C      add         edx,dword ptr [esp+1Ch] 
0000005c 03 54 24 20      add         edx,dword ptr [esp+20h] 
00000060 03 D5            add         edx,ebp 
00000062 03 D6            add         edx,esi 
00000064 03 D3            add         edx,ebx 
00000066 03 D7            add         edx,edi 
00000068 89 54 24 10      mov         dword ptr [esp+10h],edx 

float add            i += a + b + c + d + e + f + g + h;
00000016 D9 05 38 61 3E 00 fld         dword ptr ds:[003E6138h] 
0000001c D8 05 3C 61 3E 00 fadd        dword ptr ds:[003E613Ch] 
00000022 D8 05 40 61 3E 00 fadd        dword ptr ds:[003E6140h] 
00000028 D8 05 44 61 3E 00 fadd        dword ptr ds:[003E6144h] 
0000002e D8 05 48 61 3E 00 fadd        dword ptr ds:[003E6148h] 
00000034 D8 05 4C 61 3E 00 fadd        dword ptr ds:[003E614Ch] 
0000003a D8 05 50 61 3E 00 fadd        dword ptr ds:[003E6150h] 
00000040 D8 05 54 61 3E 00 fadd        dword ptr ds:[003E6154h] 
00000046 D8 05 58 61 3E 00 fadd        dword ptr ds:[003E6158h] 
0000004c D9 1D 58 61 3E 00 fstp        dword ptr ds:[003E6158h] 

Method Calls

interface I { void itf1();… void itf5();… }
public class T : I {
    static bool falsePred = false;
    static void dummy(int a, int b, int c, …, int p) { }

    static void inl_s1() { } …    static void s1()     { if (falsePred) dummy(1, 2, 3, …, 16); } …    void inl_i1()        { } …    void i1()            { if (falsePred) dummy(1, 2, 3, …, 16); } …    public virtual void v1() { } …    void itf1()          { } …    virtual void itf5()  { } …}

static void s1() { if (false) dummy(1, 2, 3, …, 16); }

    T t = new T();

               t.i1();
00000012 8B 0D 30 21 A4 05 mov         ecx,dword ptr ds:[05A42130h] 
00000018 39 09             cmp         dword ptr [ecx],ecx 
0000001a E8 C1 DE FF FF    call        FFFFDEE0 

               this.i1();
00000012 8B CE            mov         ecx,esi
00000014 E8 AF FE FF FF   call        FFFFFEC8

               this.v1();
00000012 8B CE            mov         ecx,esi 
00000014 8B 01            mov         eax,dword ptr [ecx] ; fetch method table address
00000016 FF 50 38         call        dword ptr [eax+38h] ; fetch/call method address

               i.itf1();
00000012 8B 0D 34 21 A4 05 mov        ecx,dword ptr ds:[05A42134h]; instance address
00000018 8B 01             mov        eax,dword ptr [ecx]         ; method table addr
0000001a 8B 40 0C          mov        eax,dword ptr [eax+0Ch]     ; interface map addr
0000001d 8B 40 7C          mov        eax,dword ptr [eax+7Ch]     ; itf method table addr
00000020 FF 10             call       dword ptr [eax]             ; fetch/call meth addr

Calls to Methods Yet to be Jitted

New Object Creation

               A a1 = new A(); ++a1.a;
00000020 C7 45 FC 00 00 00 00 mov     dword ptr [ebp-4],0 
00000027 FF 45 FC         inc         dword ptr [ebp-4] 

               C c1 = new C(); ++c1.c;
00000024 8D 7D F4         lea         edi,[ebp-0Ch] 
00000027 33 C0            xor         eax,eax 
00000029 AB               stos        dword ptr [edi] 
0000002a AB               stos        dword ptr [edi] 
0000002b AB               stos        dword ptr [edi] 
0000002c FF 45 FC         inc         dword ptr [ebp-4] 

               E e1 = new E(); ++e1.e;
00000026 8D 7D EC         lea         edi,[ebp-14h] 
00000029 33 C0            xor         eax,eax 
0000002b 8D 48 05         lea         ecx,[eax+5] 
0000002e F3 AB            rep stos    dword ptr [edi] 
00000030 FF 45 FC         inc         dword ptr [ebp-4] 

    public class A     { int a; }
    public class B : A { int b; }
    public class C : B { int c; }
    public class D : C { int d; }
    public class E : D { int e; }

               new A();
0000000f B9 D0 72 3E 00   mov         ecx,3E72D0h 
00000014 E8 9F CC 6C F9   call        F96CCCB8 

               new C();
0000000f B9 B0 73 3E 00   mov         ecx,3E73B0h 
00000014 E8 A7 CB 6C F9   call        F96CCBC0 

               new E();
0000000f B9 90 74 3E 00   mov         ecx,3E7490h 
00000014 E8 AF CA 6C F9   call        F96CCAC8 

1. New rt empty ctor L1, …, new rt empty ctor L5: Each type A, …, E has an empty user-defined constructor. These are all inlined away and the generated code is the same as the above.
2. New rt ctor L1, …, new rt ctor L5: Each type A, …, E has a user-defined constructor that sets its instance variable to 1:
       public class A     { int a; public A() { a = 1; } }
       public class B : A { int b; public B() { b = 1; } }
       public class C : B { int c; public C() { c = 1; } }
       public class D : C { int d; public D() { d = 1; } }
       public class E : D { int e; public E() { e = 1; } }
   
   

               new A();
00000012 B9 A0 77 3E 00   mov         ecx,3E77A0h 
00000017 E8 C4 C7 6C F9   call        F96CC7E0 
0000001c C7 40 04 01 00 00 00 mov     dword ptr [eax+4],1 

               new C();
00000012 B9 80 78 3E 00   mov         ecx,3E7880h 
00000017 E8 14 C6 6C F9   call        F96CC630 
0000001c C7 40 04 01 00 00 00 mov     dword ptr [eax+4],1 
00000023 C7 40 08 01 00 00 00 mov     dword ptr [eax+8],1 
0000002a C7 40 0C 01 00 00 00 mov     dword ptr [eax+0Ch],1 

               new E();
00000012 B9 60 79 3E 00   mov         ecx,3E7960h 
00000017 E8 84 C3 6C F9   call        F96CC3A0 
0000001c C7 40 04 01 00 00 00 mov     dword ptr [eax+4],1 
00000023 C7 40 08 01 00 00 00 mov     dword ptr [eax+8],1 
0000002a C7 40 0C 01 00 00 00 mov     dword ptr [eax+0Ch],1 
00000031 C7 40 10 01 00 00 00 mov     dword ptr [eax+10h],1 
00000038 C7 40 14 01 00 00 00 mov     dword ptr [eax+14h],1 

1. New rt no-inl L1, …, new rt no-inl L5: Each type A, …, E has a user-defined constructor that is has been intentionally written to be too expensive to inline. This scenario simulates the cost of creating complex objects with deep inheritance hierarchies and largish constructors.
     public class A     { int a; public A() { a = 1; if (falsePred) dummy(…); } }
     public class B : A { int b; public B() { b = 1; if (falsePred) dummy(…); } }
     public class C : B { int c; public C() { c = 1; if (falsePred) dummy(…); } }
     public class D : C { int d; public D() { d = 1; if (falsePred) dummy(…); } }
     public class E : D { int e; public E() { e = 1; if (falsePred) dummy(…); } }
   
   

Interlude: CLR Profiler Demo

Casts and Instance Type Checks

  bac = ac as B;

public static void castUp2Down1(int n) {
    A ac = c; B bd = d; C ce = e; D df = f;
    B bac = null; C cbd = null; D dce = null; E edf = null;
    for (n /= 8; --n >= 0; ) {
        bac = (B)ac; cbd = (C)bd; dce = (D)ce; edf = (E)df;
        bac = (B)ac; cbd = (C)bd; dce = (D)ce; edf = (E)df;
    }
}

               bac = (B)ac;
0000002e 8B D5            mov         edx,ebp 
00000030 B9 40 73 3E 00   mov         ecx,3E7340h 
00000035 E8 32 A7 4E 72   call        724EA76C 

Properties

Write Barriers

Array Element Access

                          ; i in ecx, a in edx, sum in edi
               sum += a[i];
00000024 3B 4A 04         cmp         ecx,dword ptr [edx+4] ; compare i and array.Length
00000027 73 19            jae         00000042 
00000029 03 7C 8A 08      add         edi,dword ptr [edx+ecx*4+8] 
…                         ; throw IndexOutOfRangeException
00000042 33 C9            xor         ecx,ecx 
00000044 E8 52 78 52 72   call        7252789B 

1. check array index is in bounds;
2. check object is an instance of the array element type;
3. perform a write barrier (noting any intergenerational object reference from the array to the object).

                          ; objarray in edi
                          ; obj      in ebx
               objarray[1] = obj;
00000027 53               push        ebx  
00000028 8B CF            mov         ecx,edi 
0000002a BA 01 00 00 00   mov         edx,1 
0000002f E8 A3 A0 4A 72   call        724AA0D7   ; store object array element helper

Boxing and Unboxing

box               object o = 0;
0000001a B9 08 07 B9 79   mov         ecx,79B90708h 
0000001f E8 E4 A5 6C F9   call        F96CA608 
00000024 8B D0            mov         edx,eax 
00000026 C7 42 04 00 00 00 00 mov         dword ptr [edx+4],0 

unbox               sum += (int)o;
00000041 81 3E 08 07 B9 79 cmp         dword ptr [esi],79B90708h ; "type == typeof(int)"?
00000047 74 0C            je          00000055 
00000049 8B D6            mov         edx,esi 
0000004b B9 08 07 B9 79   mov         ecx,79B90708h 
00000050 E8 A9 BB 4E 72   call        724EBBFE                   ; no, throw exception
00000055 8D 46 04         lea         eax,[esi+4]
00000058 3B 08            cmp         ecx,dword ptr [eax] 
0000005a 03 38            add         edi,dword ptr [eax]        ; yes, fetch int field

Delegates

    A* pa = new A;
    void (A::*pmf)() = &A::af;
    (pa->*pmf)();

Of Cache Misses, Page Faults, and Computer Architecture

sum int array:            sum += a[i];
00000024 3B 4A 04         cmp         ecx,dword ptr [edx+4]       ; bounds check
00000027 73 19            jae         00000042 
00000029 03 7C 8A 08      add         edi,dword ptr [edx+ecx*4+8] ; load array elem
               for (int i = 0; i < m; i++)
0000002d 41               inc         ecx  
0000002e 3B CE            cmp         ecx,esi 
00000030 7C F2            jl          00000024 


sum int linked list:         sum += l.item; l = l.next;
0000002a 03 70 08         add         esi,dword ptr [eax+8] 
0000002d 8B 40 04         mov         eax,dword ptr [eax+4] 
               sum += l.item; l = l.next;
00000030 03 70 08         add         esi,dword ptr [eax+8] 
00000033 8B 40 04         mov         eax,dword ptr [eax+4] 
               sum += l.item; l = l.next;
00000036 03 70 08         add         esi,dword ptr [eax+8] 
00000039 8B 40 04         mov         eax,dword ptr [eax+4] 
               sum += l.item; l = l.next;
0000003c 03 70 08         add         esi,dword ptr [eax+8] 
0000003f 8B 40 04         mov         eax,dword ptr [eax+4] 
               for (m /= 4; --m >= 0; ) {
00000042 49               dec         ecx  
00000043 85 C9            test        ecx,ecx 
00000045 79 E3            jns         0000002A 

• Experiment with, and measure, your scenarios because it is hard to predict second order effects and because rules of thumb aren't worth the paper they're printed on.
• Some data structures, exemplified by arrays, make use of implicit adjacency to represent a relation between data. Others, exemplified by linked lists, make use of explicit pointers (references) to represent the relation. Implicit adjacency is generally preferable—"implicitness" saves space compared to pointers; and adjacency provides stable locality of reference, and may allow the processor to commence more work before chasing down the next pointer.
• Some usage patterns favor hybrid structures—lists of small arrays, arrays of arrays, or B-trees.
• Perhaps disk-access-sensitive scheduling algorithms, designed back when disk accesses cost only 50,000 CPU instructions, should be recycled now that DRAM accesses can take thousands of CPU operations.
• Since the CLR mark-and-compact garbage collector preserves the relative order of objects, objects allocated together in time (and on the same thread) tend to remain together in space. You may be able to use this phenomenon to thoughtfully collocate cliquish data on common cache line(s).
• You may wish to partition your data into hot parts that are frequently traversed and must fit in cache, and cold parts that are infrequently used and can be "cached out".

Do-It-Yourself Time Experiments

    [System.Runtime.InteropServices.DllImport("KERNEL32")]
    private static extern bool QueryPerformanceCounter(
        ref long lpPerformanceCount);

    [System.Runtime.InteropServices.DllImport("KERNEL32")]
    private static extern bool QueryPerformanceFrequency(
        ref long lpFrequency);

A Space Cost Model?

• The size of a value type is generally the total size of its fields, with 4-byte or smaller fields aligned to their natural boundaries.
• It is possible to use [StructLayout(LayoutKind.Explicit)] and [FieldOffset(n)] attributes to implement unions.
• The size of a reference type is 8 bytes plus the total size of its fields, rounded up to the next 4-byte boundary, and with 4-byte or smaller fields aligned to their natural boundaries.
• In C#, enum declarations may specify an arbitrary integral base type (except char)—so it is possible to define 8-bit, 16-bit, 32-bit, and 64-bit enums.
• As in C/C++, you can often shave a few tens of percent of space off a larger object by sizing your integral fields appropriately.
• You can inspect the size of an allocated reference type with the CLR Profiler.
• Large objects (many dozens of KB or more) are managed in a separate large object heap, to preclude expensive copying.
• Finalizable objects take an additional GC generation to reclaim—use them sparingly and consider using the Dispose Pattern.

• Each AppDomain currently incurs a substantial space overhead. Many runtime and Framework structures are not shared across AppDomains.
• Within a process, jitted code is typically not shared across AppDomains. If the runtime is specifically hosted, it is possible to override this behavior. See the documentation for CorBindToRuntimeEx and the STARTUP_LOADER_OPTIMIZATION_MULTI_DOMAIN flag.
• In any event, jitted code is not shared across processes. If you have a component that will be loaded into many processes, consider precompiling with NGEN to share the native code.

Reflection