readonly arrays

[Mark]

I've been reading many of the articles on why C# doesn't have true readonly
arrays and I was doing a little time testing.

I found the ReadOnlyCollection<T> = Array.AsReadOnly<T>(T[]) construct but
when I ran some time tests, I was appalled to see that simple read access was
between 8x and 9x slower than just using a regular array (for type char
anyway).

I threw together a simple wrapper:
public class RArray<T>
{
private T[] holdme;
public RArray(T[] init)
{
holdme = (T[])init.Clone();
}

public T this[int i]
{
get { return holdme; }
set { throw new InvalidOperationException("No way"); }
}
}

And the same timing test had my wrapper at around 75% slower.

Using Reflector, I looked at ReadOnlyCollection<T>'s get method and saw it
was doing essentially the same thing my wrapper was, so I couldn't explain
why ReadOnlyCollection<T> was just so much slower.

Any ideas?

Thanks
Mark

 

[Family Tree Mike]

I've been reading many of the articles on why C# doesn't have true
readonly
arrays and I was doing a little time testing.

I found the ReadOnlyCollection<T> = Array.AsReadOnly<T>(T[]) construct but
when I ran some time tests, I was appalled to see that simple read access
was
between 8x and 9x slower than just using a regular array (for type char
anyway).

I threw together a simple wrapper:
public class RArray<T>
{
private T[] holdme;
public RArray(T[] init)
{
holdme = (T[])init.Clone();
}

public T this[int i]
{
get { return holdme; }
set { throw new InvalidOperationException("No way"); }
}
}

And the same timing test had my wrapper at around 75% slower.

Using Reflector, I looked at ReadOnlyCollection<T>'s get method and saw it
was doing essentially the same thing my wrapper was, so I couldn't explain
why ReadOnlyCollection<T> was just so much slower.

Any ideas?

Thanks
Mark

I only get a factor of slightly more than two using the following test code:

class Program
{
static int ListSize = 10000000;
static int [] SearchIDs;
static char [] OriginalArray;
static ReadOnlyCollection<char> ROC;

static void Setup()
{
Random r = new Random();
OriginalArray = new char[ListSize];
SearchIDs = new int[ListSize];
for (long idx = 0; idx < ListSize; ++idx)
{
OriginalArray[idx] = (char) r.Next();
SearchIDs[idx] = r.Next(ListSize);
}
ROC = Array.AsReadOnly<char>(OriginalArray);
}

static long TimeTestNormal()
{
char val;
Stopwatch sw = new Stopwatch();
sw.Start();
foreach (int idx in SearchIDs)
val = OriginalArray[idx];
return sw.ElapsedMilliseconds;
}

static long TimeTestRO()
{
char val;
Stopwatch sw = new Stopwatch();
sw.Start();
foreach (int idx in SearchIDs)
val = ROC [idx];
return sw.ElapsedMilliseconds;
}

static void Main(string[] args)
{
Setup();
Console.Out.WriteLine(string.Format("Test Normal: {0} milliseconds.",
TimeTestNormal()));
Console.Out.WriteLine(string.Format("Test Read Only: {0} milliseconds.",
TimeTestRO()));
Console.In.ReadLine();
}
}

 

[Family Tree Mike]

I've been reading many of the articles on why C# doesn't have true
readonly
arrays and I was doing a little time testing.

I found the ReadOnlyCollection<T> = Array.AsReadOnly<T>(T[]) construct
but
when I ran some time tests, I was appalled to see that simple read access
was
between 8x and 9x slower than just using a regular array (for type char
anyway).

I threw together a simple wrapper:
public class RArray<T>
{
private T[] holdme;
public RArray(T[] init)
{
holdme = (T[])init.Clone();
}

public T this[int i]
{
get { return holdme; }
set { throw new InvalidOperationException("No way"); }
}
}

And the same timing test had my wrapper at around 75% slower.

Using Reflector, I looked at ReadOnlyCollection<T>'s get method and saw
it
was doing essentially the same thing my wrapper was, so I couldn't
explain
why ReadOnlyCollection<T> was just so much slower.

Any ideas?

Thanks
Mark

I only get a factor of slightly more than two using the following test
code:

class Program
{
static int ListSize = 10000000;
static int [] SearchIDs;
static char [] OriginalArray;
static ReadOnlyCollection<char> ROC;

static void Setup()
{
Random r = new Random();
OriginalArray = new char[ListSize];
SearchIDs = new int[ListSize];
for (long idx = 0; idx < ListSize; ++idx)
{
OriginalArray[idx] = (char) r.Next();
SearchIDs[idx] = r.Next(ListSize);
}
ROC = Array.AsReadOnly<char>(OriginalArray);
}

static long TimeTestNormal()
{
char val;
Stopwatch sw = new Stopwatch();
sw.Start();
foreach (int idx in SearchIDs)
val = OriginalArray[idx];
return sw.ElapsedMilliseconds;
}

static long TimeTestRO()
{
char val;
Stopwatch sw = new Stopwatch();
sw.Start();
foreach (int idx in SearchIDs)
val = ROC [idx];
return sw.ElapsedMilliseconds;
}

static void Main(string[] args)
{
Setup();
Console.Out.WriteLine(string.Format("Test Normal: {0} milliseconds.",
TimeTestNormal()));
Console.Out.WriteLine(string.Format("Test Read Only: {0} milliseconds.",
TimeTestRO()));
Console.In.ReadLine();
}
}

And yes, I know the initialization of the random character array is far from
a good way to do that, but, it does not affect the timing...

 

[Mark]

Hi Mike...

My test might not be much more representative. I simply had a 3-element
char array and referenced the last one 50 million times. First test on the
read/write array, like so, the second test using the Array.AsReadOnly()
result. That's when I saw the 8x difference with ReadOnlyCollection, and
then the only 70% increase for my own (simplistic) version of
ReadOnlyCollection which got me puzzled...

char[] barchars = { 'a', 'b', 'c' };

start = Timers.QueryPerformanceCounter();
for (int idx = 0; idx < 50000000; idx++)
{
char z = barchars[2];
}
start = Timers.SinceMilliSeconds(start);
Console.WriteLine(start);

Thanks
Mark

I've been reading many of the articles on why C# doesn't have true
readonly
arrays and I was doing a little time testing.

I found the ReadOnlyCollection<T> = Array.AsReadOnly<T>(T[]) construct
but
when I ran some time tests, I was appalled to see that simple read access
was
between 8x and 9x slower than just using a regular array (for type char
anyway).

I threw together a simple wrapper:
public class RArray<T>
{
private T[] holdme;
public RArray(T[] init)
{
holdme = (T[])init.Clone();
}

public T this[int i]
{
get { return holdme; }
set { throw new InvalidOperationException("No way"); }
}
}

And the same timing test had my wrapper at around 75% slower.

Using Reflector, I looked at ReadOnlyCollection<T>'s get method and saw
it
was doing essentially the same thing my wrapper was, so I couldn't
explain
why ReadOnlyCollection<T> was just so much slower.

Any ideas?

Thanks
Mark

I only get a factor of slightly more than two using the following test
code:

class Program
{
static int ListSize = 10000000;
static int [] SearchIDs;
static char [] OriginalArray;
static ReadOnlyCollection<char> ROC;

static void Setup()
{
Random r = new Random();
OriginalArray = new char[ListSize];
SearchIDs = new int[ListSize];
for (long idx = 0; idx < ListSize; ++idx)
{
OriginalArray[idx] = (char) r.Next();
SearchIDs[idx] = r.Next(ListSize);
}
ROC = Array.AsReadOnly<char>(OriginalArray);
}

static long TimeTestNormal()
{
char val;
Stopwatch sw = new Stopwatch();
sw.Start();
foreach (int idx in SearchIDs)
val = OriginalArray[idx];
return sw.ElapsedMilliseconds;
}

static long TimeTestRO()
{
char val;
Stopwatch sw = new Stopwatch();
sw.Start();
foreach (int idx in SearchIDs)
val = ROC [idx];
return sw.ElapsedMilliseconds;
}

static void Main(string[] args)
{
Setup();
Console.Out.WriteLine(string.Format("Test Normal: {0} milliseconds.",
TimeTestNormal()));
Console.Out.WriteLine(string.Format("Test Read Only: {0} milliseconds.",
TimeTestRO()));
Console.In.ReadLine();
}
}

And yes, I know the initialization of the random character array is far from
a good way to do that, but, it does not affect the timing...

 

[Mark]

Looking at the il getting generated by my tests, my guess is that the
difference between my very simplistic ReadOnlyCollection and the real
ReadOnlyCollection has to do with the amount of inheritence in
ReadOnlyCollection.

get_Item(i) ends up being a callvirt for ReadOnlyCollection. My simple
version didn't implement any interfaces or override any methods, so the
indexer is just a straight call.

Using the built-in array support, it ends up being
IL_0041: ldelem.u2
..

I also included an empty loop timing in my test this morning to see how much
of the time was just being eaten up in looping, and it showed that the margin
is much worse than I imagined to begin with.

Taking out the loop time, the difference between accessing
ReadOnlyCollection and a basic array (under my admittedly contrived
conditions) is more like a 70x penalty.

The upshot being don't use a ReadOnlyCollection unless you really, really
need it to be readonly...

Thanks
Mark

I've been reading many of the articles on why C# doesn't have true
readonly
arrays and I was doing a little time testing.

I found the ReadOnlyCollection<T> = Array.AsReadOnly<T>(T[]) construct
but
when I ran some time tests, I was appalled to see that simple read access
was
between 8x and 9x slower than just using a regular array (for type char
anyway).

I threw together a simple wrapper:
public class RArray<T>
{
private T[] holdme;
public RArray(T[] init)
{
holdme = (T[])init.Clone();
}

public T this[int i]
{
get { return holdme; }
set { throw new InvalidOperationException("No way"); }
}
}

And the same timing test had my wrapper at around 75% slower.

Using Reflector, I looked at ReadOnlyCollection<T>'s get method and saw
it
was doing essentially the same thing my wrapper was, so I couldn't
explain
why ReadOnlyCollection<T> was just so much slower.

Any ideas?

Thanks
Mark

I only get a factor of slightly more than two using the following test
code:

class Program
{
static int ListSize = 10000000;
static int [] SearchIDs;
static char [] OriginalArray;
static ReadOnlyCollection<char> ROC;

static void Setup()
{
Random r = new Random();
OriginalArray = new char[ListSize];
SearchIDs = new int[ListSize];
for (long idx = 0; idx < ListSize; ++idx)
{
OriginalArray[idx] = (char) r.Next();
SearchIDs[idx] = r.Next(ListSize);
}
ROC = Array.AsReadOnly<char>(OriginalArray);
}

static long TimeTestNormal()
{
char val;
Stopwatch sw = new Stopwatch();
sw.Start();
foreach (int idx in SearchIDs)
val = OriginalArray[idx];
return sw.ElapsedMilliseconds;
}

static long TimeTestRO()
{
char val;
Stopwatch sw = new Stopwatch();
sw.Start();
foreach (int idx in SearchIDs)
val = ROC [idx];
return sw.ElapsedMilliseconds;
}

static void Main(string[] args)
{
Setup();
Console.Out.WriteLine(string.Format("Test Normal: {0} milliseconds.",
TimeTestNormal()));
Console.Out.WriteLine(string.Format("Test Read Only: {0} milliseconds.",
TimeTestRO()));
Console.In.ReadLine();
}
}

And yes, I know the initialization of the random character array is far from
a good way to do that, but, it does not affect the timing...

 

[Jeroen Mostert]

I also included an empty loop timing in my test this morning to see how much
of the time was just being eaten up in looping, and it showed that the margin
is much worse than I imagined to begin with.

To put it simply: it doesn't work that way. Timing an empty loop is
meaningless. You cannot subtract the "time needed for looping" from an
actual loop, because the very time needed for the loop is affected by its
contents. This is especially true for JIT-compiled code.

Taking out the loop time, the difference between accessing
ReadOnlyCollection and a basic array (under my admittedly contrived
conditions) is more like a 70x penalty.

Looping through an array is a highly optimized operation, in some cases
boiling down to special machine language instructions for it (which is again
why timing an empty loop is going to skew results heavily in its favor).
There is really not much that's *faster* than going through an array. It can
even beat hashtable lookups for small arrays and largish keys. Does that
mean we should do everything with arrays? Well, no.

The upshot being don't use a ReadOnlyCollection unless you really, really
need it to be readonly...

Wrong way around, false economy. Without any context, you don't know how
fast your lookups need to be. Even if you could show that a particular
collection will be accessed heavily, it's trivial for the caller to avoid
the penalty by calling .ToArray() on the result.

Conversely, once you let the modifiable cat out of the bag and return arrays
directly, there's no way to put it back in again without copying the array
on every single access -- if you want to talk inefficient, that would be it.
Using ReadOnlyCollection, such copies are restricted to when they're needed.

Finally, if it ever does become highly important for ReadOnlyCollection to
be as fast as regular array access (it might, if concurrency comes into
play) Microsoft can simply make it that way. Well, not simply, but the
compiler and the framework can certainly work together to fold
ReadOnlyCollection accesses back to array accesses if the inner collection
is in fact an array.

 

[Mark]

Hi Jeroen,

To put it simply: it doesn't work that way. Timing an empty loop is
meaningless. You cannot subtract the "time needed for looping" from an
actual loop, because the very time needed for the loop is affected by its
contents. This is especially true for JIT-compiled code.

I was just going by what I saw in the il (and seemed born out by the actual
run). I was actually a little surprised that the completely empty loop
wasn't just optimized out. I was also looking to see if the loop invariants
had been optimized outside the loop which they weren't. I figured it may
have been a function of compiling debug.

Looping through an array is a highly optimized operation, in some cases
boiling down to special machine language instructions for it (which is again
why timing an empty loop is going to skew results heavily in its favor).
There is really not much that's *faster* than going through an array. It can
even beat hashtable lookups for small arrays and largish keys. Does that
mean we should do everything with arrays? Well, no.

I agree, use the right tool for the job. Most of the interest in this point
comes from C and C++ programmers who are used to being able to declare both
the array *and* it's constants readonly and are puzzled with the behavior of
..Net.

In my particular case, I started picking at it because we had a small array
of constants being used in a routine (a derivation of HexEncoding from the
Code Project, which was less efficient than it could be). While nobody is
expecting the array of hex chars to change, it's nice to make sure it doesn't
just for cleanliness.

I started testing to see what the difference was in using a basic array and
a ReadOnlyCollection and was surprised to see how much difference there was.

Wrong way around, false economy. Without any context, you don't know how
fast your lookups need to be. Even if you could show that a particular
collection will be accessed heavily, it's trivial for the caller to avoid
the penalty by calling .ToArray() on the result.

Making array copies also incurs penalties on the garbage collector.
Admittedly my method of comparing times for doing the same thing 50 million
times over does exacerbate the cost of anything that results in new object
creation.

Conversely, once you let the modifiable cat out of the bag and return arrays
directly, there's no way to put it back in again without copying the array
on every single access -- if you want to talk inefficient, that would be it.
Using ReadOnlyCollection, such copies are restricted to when they're needed.
Agreed...

Finally, if it ever does become highly important for ReadOnlyCollection to
be as fast as regular array access (it might, if concurrency comes into
play) Microsoft can simply make it that way. Well, not simply, but the
compiler and the framework can certainly work together to fold
ReadOnlyCollection accesses back to array accesses if the inner collection
is in fact an array.

Understood... I was just surprised, at a very nit-picky level, at how much
difference there currently was in the implementation.

Thanks
Mark

 

[Jeroen Mostert]

I was just going by what I saw in the il (and seemed born out by the actual
run). I was actually a little surprised that the completely empty loop
wasn't just optimized out.

This is deliberate. GCC for one actually used to do this, before they
realized that this was too clever by half -- people produce empty loops on
purpose, mostly for small delays. Optimizing this away shows that your
optimizer's clever, but it doesn't actually help the user.

Optimizing away empty loops makes sense if the loop is a result of a
compiler transformation of a loop that wasn't empty before, but otherwise,
the compiler should leave it alone, be nice, and just produce a nice tight
empty loop.

In my particular case, I started picking at it because we had a small array
of constants being used in a routine (a derivation of HexEncoding from the
Code Project, which was less efficient than it could be).

Heh, funny thing, that. I wrote my own class for that too, and I did
optimize the hell out of that. It exposes no constants, though. You don't
need them, the class does all the work.

As an aside, if all you need is to convert bytes to hex strings you have to
try quite hard to beat BitConverter.ToString(...).Replace("-", "") -- that's
what I'd recommend to people who don't feel like writing their own class.
It's short and very fast. The other way around (parsing hex strings to
bytes) is a different kettle of fish.

As a really small aside, I don't like the name "HexEncoding". It fools you
into thinking this class is related to the Encoding-derived classes in
System.Text. Going to and from hex strings is *not* text encoding, that goes
from characters to bytes and back, not from bytes to bytes. I called my
class "HexCoding" for that reason.

While nobody is expecting the array of hex chars to change, it's nice to
make sure it doesn't just for cleanliness.

An array of constants is very unlikely to be frequently looped through by
external clients (you'd expect a hashtable if lookups are frequent), so I
wouldn't worry about performance in any case.

Making array copies also incurs penalties on the garbage collector.

Thankfully, it's smart and diligent. Now you're optimizing for the case
that 1) the array is large (if it's small the GC really isn't going to have
a problem immediately cleaning it up), 2) the client needs fast looping and
3) there are many clients who need to do that or the same client has to do
that frequently. I like those odds, compared to the havoc that can result
from exposing an array that shouldn't be modified and having some dunderhead
do it anyway.

As long as your class isn't mean for a very general audience, this probably
doesn't matter that much. Slip in a few public fields too if you like. But
as soon as it's library material, even just for an internal library, I'd
really favor the readonly approach heavily over hoping for the best.

Understood... I was just surprised, at a very nit-picky level, at how much
difference there currently was in the implementation.

And I was just quick to prevent future generations from finding your post
and concluding that ReadOnlyCollection should never be used, because, boy,
who would ever agree to a 70x slowdown? I'm pretty sure it's not as awful as
that.

On the other hand, programmers who focus on "the fastest code possible" (and
who ignore the fact that except in trivially limited circumstances it's
impossible to determine the fastest code possible) will probably not be
interested anyway.

 

[Mark]

Hi Jeroen...

And I was just quick to prevent future generations from finding your post
and concluding that ReadOnlyCollection should never be used, because, boy,
who would ever agree to a 70x slowdown? I'm pretty sure it's not as awful as
that.

On the other hand, programmers who focus on "the fastest code possible" (and
who ignore the fact that except in trivially limited circumstances it's
impossible to determine the fastest code possible) will probably not be
interested anyway.

I agree with you an Patrice that focusing on speed differences that take 50
million executions to emphasize is really picayune, but since she asked and
since I haven't put any numbers to display what I mean, I'll post a sample
run.

The numbers vary +/- a few milliseconds here and there but overall are
fairly consistent:
Empty loop of 50 million: 193 milliseconds
Accessing last element in 3 element array: 211 milliseconds (net 18
milliseconds from loop cost)
Accessing last element in same ReadOnlyCollection: 1818 milliseconds (net
1625 milliseconds)

Full disclosure would probably require me to say class of machine and
current ram state, but I've already admitted I'm being overly picayune

As you said, array access is heavily optimized into a handful of
instructions while ReadOnlyCollection.get_Item(int) has to work its way
through the virtual table.

Thanks
Mark

 

[nickdu]

I'm curious, could you write some managed C++ code which allocated read-only
memory (VirtualAlloc) and then creates the array on that memory?
--
Thanks,
Nick

(e-mail address removed)
remove "nospam" change community. to msn.com