[Mono-list] Performance / array access

[Mitchell Skinner]

Hello,

The runtime inserts array bounds checks to prevent things like buffer
overflows.  So the following code:
   int len = array.Length;
   for (int i = 0; i < len; ++i)
      sum += array [i];
becomes something like:
   int len = array.Length;
   for (int i = 0; i < len; ++i) {
      if (i >= array.Length) throw new Exception; //forgot which
      sum += array [i];
   }

In the fast case, the MS JIT is smart enough to analyze the following
code and figure out that "i" will not go out of the bounds of the array
(because i starts at zero and stays below array.Length):
   for (int i = 0; i < array.Length; ++i)
      sum += array [i];

If the for loop isn't set up exactly like that, I don't think the MS JIT is able to eliminate the bounds check (unless perhaps there are constants involved).  Is the code you have below (comparing i with a "size" variable) the exact code you tested?  If "size" is not a constant, I would be suprised to find that there was a major difference between MS and mono.

Are you using the MS 1.0 release or the 1.1 release?

Mitch


On Tue, 2003-01-14 at 13:38, Tom Fransen wrote:
> Piers,
> 
> can you spend a few more words on this. Why is the second case slower?
> 
> Furthermore if I use a simple loop to fill an array the
> speed difference is a factor 3. I have a bubble sort method
> that I execute a larger number of times. On Mono it takes 19 seconds
> on the MS stuff ~6 seconds. This is a big difference. So why I am
> losing a factor 3 on the following loop.
> 
>                 // Fill aray worst case, all elements need to be swapped
>                 for(int i=0; i< size; i++)
>                 {
>                     array[i] = size - i;
>                 }
> 
> I am testing with some small benchmarks, but real applications (e.g. an MP3
> decoder)
> often use tables stored in arrays to do certain calculations.
> So although the benchmark maybe syntetic certain application will
> suffer from these penalties.
> 
> regards,
> Tom
> 
> -----Original Message-----
> From: Miguel de Icaza [mailto:miguel@ximian.com]
> Sent: Monday, January 13, 2003 3:22 AM
> To: Piers Haken
> Cc: Tom Fransen; Mono-list@ximian.com
> Subject: RE: [Mono-list] Performance / array access
> 
> 
> Hello,
> 
> > Yeah, Microsoft's JIT lifts invariant bounds-checks. But I believe
> > it's pretty limited.
> >
> > For example, the check is removed in the following case:
> >
> >   for (int i = 0; i < array.Length; ++i)
> >     sum += array [i];
> >
> > But not here:
> >
> >   int len = array.Length;
> >   for (int i = 0; i < len; ++i)
> >     sum += array [i];
> >
> > So the first case is (counter-intuitively) faster than the second.
> >
> > I don't believe Mono's JIT makes this optimization. Maybe the new JIT
> > will ;-)
> 
> This is a very good observation.  Because it seems that this particular
> kind of loop is detected by the JIT engine.
> 
> Array-bounds-check elimination is something we want to do with the new
> JIT, but it is not implemented at this point.  The new JIT features a
> new intermediate representation that simplifies implementing this sort
> of thing, but it is still on its bootstrapping phases of life.
> 
> Miguel
> 
> 
> _______________________________________________
> Mono-list maillist  -  Mono-list@ximian.com
> http://lists.ximian.com/mailman/listinfo/mono-list
-- 
Mitchell Skinner <mitchskin@attbi.com>