What would be a faster alternative to boxing/unboxing?

[Frank Hileman]

That's not hard. Use an array of unsigned ints; upper 3 can be type
identifier; remaining bits index into array of a specific type. For example,
wrap it in a struct to make it easier:

enum ArrayType
{
Int = 0x1,
Double = 0x2,...
}

struct ArrayEntry
{
const unsigned int typeMask = 0x7 << 29;
const unsigned int indexMask = ~ typeMask;

usigned int data;

public ArrayEntry(ArrayType type, int index)
{
data= 0; // for compiler warning
Type = type;
Index = index;
}

ArrayType Type
{
get { return (ArrayType)(data>> 29); }
set { value = Index | ((int)data) << 29); }
}

int Index
{
get { return data & indexMask; }
set { data = Type | (value & indexMask); }
}
}

Then if you have ArrayEntry[] a, you do a.Index, a.Type, then use that
info to index into the type-specific arrays, which I would call pools, if
you choose to use them that way.

Regards,
Frank Hileman
Prodige Software Corporation

check out VG.net: www.prodigesoftware.com/screen5.png
An animated vector graphics system integrated in VS.net
beta requests: vgdotnetbeta at prodigesoftware.com

The real problem with this idea is - how we can possibly know which type is
the object at given index in order to know what overload to use to retrieve
the data. We can provide method that returns the type of an object by index
value. But then we need to check this type and call the appropriate method
which will introduce more overhead when reading data. It may turns that
boxing/unboxing is the best solution and the problem with the prformance is
not there.

That's why I think we can't come up with good idea unless Mountain gives us
an example how he is planning to use this storage. He may not need to have
the objects ordered and then this solution will work and we won't have the
problem of wasting the memory.

B\rgds
100

Hi Paul,
You are hundred percent right. That was my fault. I wrote this minutes
before I went home yesterday and its my fault that I posted this without any
revision.

Thanks for bringing this out. We can't use indexer for that. What we can do
is to use separate operations SetData and GetData with as many overloads as
different types we want to accept. GetData cannot return value because ot
will introduce the same problem that we have already with the indexer.

So

we
can have prototype like

void GetData(int index, out <type> value)
{
}

this should fix the problem.

B\rgds
100

100 wrote:

class Storage
{
int[] intArr= new int[10];
double[] dblArr = new int[10];
object[] refArr = new object[10];

public int this[int i]
{
get{return intArr;}
set{intArr = value;}
}

public double this[int i]

I thought that C# couldn't do polymorphism on return types only ? Am I
wrong ?

 

[Mountain Bikn' Guy]

Frank,
That's awesome! Beautiful! Just what I was looking for, and the style is
consistent with other code I've written, so it's a beautiful fit! Thanks.

I think I'll use 6 bits for the types (I probably have about 15 different
types I use already). My (upper) array length will not need to be more than
1 million, so this leaves me plenty of room. I might even allocate another
bit for the types.

The obvious way to do the last step you mention, indexing into the
type-specific sub arrays (pools), is to select the type specific array via a
switch or if/else block. Do you have a better suggestion? This step could
end up negating some of the potential performance gains if it isn't done
correctly. Another indexing/dereferencing operation at this step would be
great. Maybe I can put all the type-specific sub arrays in an object[] and
cast from an object to a type[] (ie, double[], bool[], int[] etc.).

object[] poolArray = new object[numberOfTypes]; //array of type specific
arrays

//this statement would exist inside an overloaded "Get" method that requests
a double:
return ((double[])poolArray[typeNdx])[itemNdx];

I have the above code because I was putting type specific arrays of length 1
inside each slot in the upper array as a way to avoid boxing and unboxing.
(In that case the 2nd index was always 0. This is the experimental solution
I previously mentioned that I would post. It's fairly simple to implement,
so I'll just skip a full post.)

Also, I will need to come up with a nice way to properly size the type
specific arrays (pools) before processing starts. My current design should
support this, with a little work. I already know the total size (ie, total
number of items to go into the array) in advance. However, I do not
currently know the size (count) needed on a per-type basis, so I'll have to
figure a way to compute this. This step isn't really as peformance critical
because it only needs to be done once.

Regards,
Mountain

P.S. Your code is a perfect example of why I love C# so much.

That's not hard. Use an array of unsigned ints; upper 3 can be type
identifier; remaining bits index into array of a specific type. For example,
wrap it in a struct to make it easier:

enum ArrayType
{
Int = 0x1,
Double = 0x2,...
}

struct ArrayEntry
{
const unsigned int typeMask = 0x7 << 29;
const unsigned int indexMask = ~ typeMask;

usigned int data;

public ArrayEntry(ArrayType type, int index)
{
data= 0; // for compiler warning
Type = type;
Index = index;
}

ArrayType Type
{
get { return (ArrayType)(data>> 29); }
set { value = Index | ((int)data) << 29); }
}

int Index
{
get { return data & indexMask; }
set { data = Type | (value & indexMask); }
}
}

Then if you have ArrayEntry[] a, you do a.Index, a.Type, then use that
info to index into the type-specific arrays, which I would call pools, if
you choose to use them that way.

Regards,
Frank Hileman
Prodige Software Corporation

check out VG.net: www.prodigesoftware.com/screen5.png
An animated vector graphics system integrated in VS.net
beta requests: vgdotnetbeta at prodigesoftware.com

The real problem with this idea is - how we can possibly know which type is
the object at given index in order to know what overload to use to retrieve
the data. We can provide method that returns the type of an object by index
value. But then we need to check this type and call the appropriate method
which will introduce more overhead when reading data. It may turns that
boxing/unboxing is the best solution and the problem with the prformance is
not there.

That's why I think we can't come up with good idea unless Mountain gives us
an example how he is planning to use this storage. He may not need to have
the objects ordered and then this solution will work and we won't have the
problem of wasting the memory.

B\rgds
100

 

[Frank Hileman]

I think I'll use 6 bits for the types (I probably have about 15 different

types I use already). My (upper) array length will not need to be more than
1 million, so this leaves me plenty of room. I might even allocate another
bit for the types.

With 5 bits you have 16 different enum values that can be put in (0-15).

The obvious way to do the last step you mention, indexing into the
type-specific sub arrays (pools), is to select the type specific array via a
switch or if/else block. Do you have a better suggestion? This step could
end up negating some of the potential performance gains if it isn't done
correctly. Another indexing/dereferencing operation at this step would be
great. Maybe I can put all the type-specific sub arrays in an object[] and
cast from an object to a type[] (ie, double[], bool[], int[] etc.).

object[] poolArray = new object[numberOfTypes]; //array of type specific
arrays

//this statement would exist inside an overloaded "Get" method that requests
a double:
return ((double[])poolArray[typeNdx])[itemNdx];

That would work, but I think the switch would be faster. The one thing I
worry about with your method is possible array type conversion. I don't
think it would happen but the compiler might put some dynamic type checking
in there that is really unnecessary (to make sure the cast is fair). So I
think a switch is most likely faster (small switches optimize down to tight
machine code), since no dynamic cast is needed. Also no array bounds
checking is needed:

switch (typeNdx)
{
ArrayType.Int:
return intArray[itemNdx];
....
}

In C of course, the array indexing would not cause typechecking or array
bounds checking. But even there the switch would probably win because it
does not require an extra memory dereference (every array index operation is
an extra dereference).

Also, I will need to come up with a nice way to properly size the type
specific arrays (pools) before processing starts. My current design should
support this, with a little work. I already know the total size (ie, total
number of items to go into the array) in advance. However, I do not
currently know the size (count) needed on a per-type basis, so I'll have to
figure a way to compute this. This step isn't really as peformance critical
because it only needs to be done once.

I would not precompute the sizes at all. Instead, allocate the typespecific
arrays on the fly, in the same way an arraylist works. For example, here is
a types-pecific arraylist sort of collection. It is a bit of code, I will
put it in the next message.

P.S. Your code is a perfect example of why I love C# so much.

Thanks! Structs in C# wrap bitfields beautifully. I think perhaps Brad Adams
and others should not discourage mutable structs so much, because they are
very useful when used as fields in objects. And the compiler can catch the
use of a temporary struct as an lvalue.

I thought of a way to clean up the "magic numbers" a bit (0x7 and 29 in my
sample). In the ArrayType enum:

[Flags]
enum ArrayType : unsigned int
{
Int = 0x1,
Double = Int << 1,
...
All = Int | Double | ...
}

That would give you an unshifted bit mask in the enum, called All. Then, if
you write a function which can count the bits in an unsigned int, you could
compute the constants this way:

static readonly insigned int typeShift = 32 -
BitFunctions.CountBits(ArrayType.All);
static readonly unsigned int typeMask = ArrayType.All << typeShift;
static readonly unsigned int indexMask = ~typeMask;

and in the property:

ArrayType Type
{
get { return (ArrayType)(data >> typeShift); }
set { data = Index | ((unsigned int)value) << typeShift); }
}

Note the change to the set function! I made a mistake before, and swapped
the words "value" and "data". I just wrote the code out without an editor
or compiler.

- Frank

 

[Frank Hileman]

With 5 bits you have 16 different enum values that can be put in (0-15).

Whoops! I meant, with 4 bits you have 16 possible enum values. And the way I
assigned the values was wrong, they are not bitflags:

enum ArrayType : unsigned int
{
Int = 1,
Double = 2,
String = 3,
...
Max= what ever the biggest one is...
}

Then in the bit shifting computation, you would use Max instead, but if it
is not all 1 bits, you have to count the position of the topmost set bit,
and not the number of bits set.

Sorry about that. Should always run these things through a compiler...

 

[Frank Hileman]

Here is the basic code for an arraylist style collection. I took out some of
the ICollection stuff, enumerator, etc. It is called PointList, but really
it is an array of Vector structs (x and y values). So you can see how it can
be used for any data type. Just swap your type name for "Vector".

public class PointList
{
// -------- static members --------
private const int DefaultCapacity = 4;

// -------- instance members --------
private Vector[] items;
private int count;

publicPointList()
{
items = new Vector[DefaultCapacity];
}

public int Count
{
get { return count; }
}

public int Capacity
{
get { return items.Length; }
set
{
if (items.Length == value)
return;
Check.Argument(value >= count, "value",
"Capacity must be greater or equal to Count");
int newCapacity = value > DefaultCapacity ? value : DefaultCapacity;
Vector[] newItems = new Vector[newCapacity];
if (count > 0)
Array.Copy(items, 0, newItems, 0, count);
items = newItems;
}
}

public Vector this[int index]
{
get { return items[index]; }
set
{
if (index >= count)
throw new ArgumentOutOfRangeException("index", index,
"Index must be smaller than Count.");
if (items[index] == value)
return;
items[index] = value;
}
}

public int Add(Vector point)
{
if (items.Length == count)
Capacity = items.Length * 2;
int index = count;
items[index] = point;
++count;
return index;
}

public void AddRange(Vector[] points)
{
int minCapacity = count + points.Length;
if (minCapacity > items.Length)
Capacity = minCapacity > DefaultCapacity ? minCapacity :
DefaultCapacity;
Array.Copy(points, 0, items, count, points.Length);
count += points.Length;
}

public virtual void Clear()
{
Array.Clear(items, 0, count);
count = 0;
}
}

 

[Mountain Bikn' Guy]

Frank,
Thanks for your additional comments. My responses are inline.
Regards,
Mountain

That would work, but I think the switch would be faster. The one thing I
worry about with your method is possible array type conversion. I don't
think it would happen but the compiler might put some dynamic type checking
in there that is really unnecessary (to make sure the cast is fair). So I
think a switch is most likely faster (small switches optimize down to tight
machine code), since no dynamic cast is needed. Also no array bounds
checking is needed:

I'll take your advice on this. My only experience in this regard is a data
structure I wrote in C++ that used dereferencing extensively and in place of
conditionals whenever possible. It was super fast, out performing the
optimum data structure in this category. (Just so this doesn't sound too
vague, I'll add that it was a binary tree that outperformed an identically
implemented height balanced AVL tree.) This experience has made me inclined
to favor dereferencing whenever possible, but obviously that was a limited
situation.

I would not precompute the sizes at all. Instead, allocate the typespecific
arrays on the fly, in the same way an arraylist works. For example, here is
a types-pecific arraylist sort of collection. It is a bit of code, I will
put it in the next message.

Thanks.
I will use a "type-specific arraylist sort of collection" if I can implement
it such that when I clear my arrays and prepare for new data I don't have to
reallocate anything. That way the cost would be incurred only once. I'm sure
this won't be a problem. All subsequent writes (thousands of them) of new
data (after the first full population and clear) will be identically sized
and identically indexed.

Note the change to the set function! I made a mistake before, and swapped
the words "value" and "data". I just wrote the code out without an editor
or compiler.

I didn't see that one, but I did see this:
"usigned int data;"

That clued me in that you wrote it without an editor/compiler -- I was
impressed. If I don't check my code samples by compiling, I typically end up
with something nonsensical in there somewhere.

 

[Richard A. Lowe]

I had to work up my own example since you didn't post any code (Hey, I was
bored today) so maybe my assumptions are really different from yours, but I
found one way of doing it that was 28% faster than the object array in pure
C# and 41% faster with a few easy IL modifications.

Rather than create a specific container *class* create a container *union
struct* with all value types residing in the same space on your struct. Now
I only tried with with one reference type and two value types, but it did
work a lot faster (a plain struct was slower, for some reason creating a
union via the StructLayout attribute was faster).

My 4 tests are downloadable from here:
http://chadich.mysite4now.com/FastestHeterogenousArray.zip

There's a PDF/Word doc that shows a snapshot of the IL I took out of EACH of
the sturct constructors (should be obvious which code is redundant). But
post again if you are unsure how to use ILDasm and ILAsm to de/re-compile
it.

Richard

 

[Frank Hileman]

I'll take your advice on this. My only experience in this regard is a data

structure I wrote in C++ that used dereferencing extensively and in place of
conditionals whenever possible. It was super fast, out performing the
optimum data structure in this category. (Just so this doesn't sound too
vague, I'll add that it was a binary tree that outperformed an identically
implemented height balanced AVL tree.) This experience has made me inclined
to favor dereferencing whenever possible, but obviously that was a limited
situation.

Yep, sounds like you had a killer implementation. It all depends on the
assembly generated. When you start poking at the assembly level you can see
that every pointer deref has a cost that can be avoided. We are probably
making a lot of assumptions about the generated code from a high level
language. I would be curious to see if there was any speed diff between the
switch and the generic array method. The other thing mentioned, a union,
sounds interesting too, but that requires special permissions at run-time,
because that technique theoretically has security implications. I miss the
union from C. Union would have been my first thought in C++ for this
problem. Seems like they might have put union somehow in C# without this
security problem -- perhaps by forcing the CLR to clear the bits before you
cast it differently.

have fun - Frank

 

[100]

Hi Frank,
Yes, you can do that. Haw I said "We can provide method that returns the
type of an object by index
value. But then we need to check this type and...". As far as I remember
Mountain was concerned about reading performance. My question now is: what
is your suggestion about the storage-class (as a whole) interface.
So if you have
class MyStorage
{
.....
}

What interface you suggest to retrieve the data. If you have one method
XXXX GetData(int index)
What is the type of XXXX if it is an 'obect' we have to unbox the object
(Montian wanted to avoid exactly this).
If your idea is not to use one class, but insted bunch of different arrays
for each type + one for ArrayElements
We'll have something like this
ArrayElements e = arrElements[index];
switch(e.Type)
{
case Integer:
int i = intArr[e.Index];
/// do sth with int
break;
case Double:
double d = dblArr[e.Index];
/// do sth with double
break;
......

}


Ok, we avoided boxing/unboxing. But how many copy operations we do have?

1 for returning the ArrayElement value + 1 for extracting the index + 1 for
extracting the type + 1 for extracting the concrete value from the
type-cpecific array. At least 4 copy operations + supporting opeations as
shift and logical ops + 2 array indexing(all bound checks, etc). Mountain
finds unboxing(one copy + one typecheck) for expensive. Do you thing it is
more cheap?

B\rgds
100

That's not hard. Use an array of unsigned ints; upper 3 can be type
identifier; remaining bits index into array of a specific type. For example,
wrap it in a struct to make it easier:

enum ArrayType
{
Int = 0x1,
Double = 0x2,...
}

struct ArrayEntry
{
const unsigned int typeMask = 0x7 << 29;
const unsigned int indexMask = ~ typeMask;

usigned int data;

public ArrayEntry(ArrayType type, int index)
{
data= 0; // for compiler warning
Type = type;
Index = index;
}

ArrayType Type
{
get { return (ArrayType)(data>> 29); }
set { value = Index | ((int)data) << 29); }
}

int Index
{
get { return data & indexMask; }
set { data = Type | (value & indexMask); }
}
}

Then if you have ArrayEntry[] a, you do a.Index, a.Type, then use that
info to index into the type-specific arrays, which I would call pools, if
you choose to use them that way.

Regards,
Frank Hileman
Prodige Software Corporation

check out VG.net: www.prodigesoftware.com/screen5.png
An animated vector graphics system integrated in VS.net
beta requests: vgdotnetbeta at prodigesoftware.com

The real problem with this idea is - how we can possibly know which type is
the object at given index in order to know what overload to use to retrieve
the data. We can provide method that returns the type of an object by index
value. But then we need to check this type and call the appropriate method
which will introduce more overhead when reading data. It may turns that
boxing/unboxing is the best solution and the problem with the prformance is
not there.

That's why I think we can't come up with good idea unless Mountain gives us
an example how he is planning to use this storage. He may not need to have
the objects ordered and then this solution will work and we won't have the
problem of wasting the memory.

B\rgds
100

Hi Paul,
You are hundred percent right. That was my fault. I wrote this minutes
before I went home yesterday and its my fault that I posted this

without
any

revision.

Thanks for bringing this out. We can't use indexer for that. What we

can
do

is to use separate operations SetData and GetData with as many

overloads
as

different types we want to accept. GetData cannot return value because ot
will introduce the same problem that we have already with the indexer.

So

we
can have prototype like

void GetData(int index, out <type> value)
{
}

this should fix the problem.

B\rgds
100

message 100 wrote:

class Storage
{
int[] intArr= new int[10];
double[] dblArr = new int[10];
object[] refArr = new object[10];

public int this[int i]
{
get{return intArr;}
set{intArr = value;}
}

public double this[int i]

I thought that C# couldn't do polymorphism on return types only ? Am I
wrong ?

 

[Frank Hileman]

If you cannot use strong typing throughout, and avoid casting to object,
then you may as well stick to an ArrayList and boxing. The only interface
that can be used to efficiently retrieve the data is a strongly typed one,
GetInt, GetDouble, etc. Otherwise the whole concept is defeated.

Regarding the overhead from the copy, shift, logical ops, etc. These are all
very fast and inlined. This is the great thing about structs. Time it and
see. Make sure the class you use is not derived from MarshalByRefObject,
which defeats inlining. Based on my own perf tuning experience strongly
typed arrays should beat the boxing alternative hands down.

regards, Frank

 

[100]

Hi Richard,
Thanx for the post. I was palnning to make the suggestion with "unions ",
but I didn't because I found potential problems with it. I'll try to explain
my issues.
I modified a bit your examples and I got the following results:
* Example using normal obect array - reading 10M items for 0.34s
(29,069,637.13 items/s)
* UnionStruct - reading 10M items for 0.30s (33,025,715.36 items/s).
The others are way worse so I don't want to discuss them.
Way to go "UnionStruct" )

IMHO we gain this performance because using unions we copy less data when we
read Value items.

Now my issues.
1. In your case you have value types and one reference type. As you know we
can make an union only with value types. You cannot map reference types to
the same memory with other references or value types.
If we try the UnionStruct example with 2 reference types and one value type
the performance goes as bad as ValueArry exmaple (10M for 0.45s or
22,381,528.52 items/s ).
The ObjectArray with the same types is doing as good as before.

2. Even if you have only value types like big structures "UnionStruct"
example suffer performance hit. ObjectArray is doing better.
I tried your examaples with 1 ref type, 1 double and one structure defined
as
struct MyStruct
{
public int a;
public int b;
public int c;
}
The *double* and the struct share the same memory.

So, the results were UnionStruct example - 0.44s; ObjectArray - 0.4s.

IMHO "unions" could be good in some special casses, but they are not easy
for maintenance (hard to be extended, etc). So, I give my preferences to the
ObjectArrays

B\rgds
100

 

[Mountain Bikn' Guy]

my comments are inline
Mountain

If you cannot use strong typing throughout, and avoid casting to object,
then you may as well stick to an ArrayList and boxing. The only interface
that can be used to efficiently retrieve the data is a strongly typed one,
GetInt, GetDouble, etc. Otherwise the whole concept is defeated.

Absolutely!
I use an overloaded GetData method that includes an 'out' parameter for each
data type. The GetData overloads simply call GetInt, GetDouble, etc.

Regarding the overhead from the copy, shift, logical ops, etc. These are all
very fast and inlined. This is the great thing about structs. Time it and
see.

Agreed. I'm doing timing tests at each step. I've often been surprised to
get results I didn't expect, which, in this case, is what led to my initial
post on this topic.

Make sure the class you use is not derived from MarshalByRefObject,
which defeats inlining.

Good tip. I wasn't aware of this.

Based on my own perf tuning experience strongly
typed arrays should beat the boxing alternative hands down.

Frank, you've given me some great tips. I'm working on the implementation
now. As a side effect of using strongly typed arrays, at steps further down
the line I will be able to eliminate the use of reflection, which should
give even further performance gains.

Regards,
Mountain

regards, Frank

Hi Frank,
Yes, you can do that. Haw I said "We can provide method that returns the
type of an object by index
value. But then we need to check this type and...". As far as I remember
Mountain was concerned about reading performance. My question now is: what
is your suggestion about the storage-class (as a whole) interface.
So if you have
class MyStorage
{
.....
}

What interface you suggest to retrieve the data. If you have one method
XXXX GetData(int index)
What is the type of XXXX if it is an 'obect' we have to unbox the object
(Montian wanted to avoid exactly this).
If your idea is not to use one class, but insted bunch of different arrays
for each type + one for ArrayElements
We'll have something like this
ArrayElements e = arrElements[index];
switch(e.Type)
{
case Integer:
int i = intArr[e.Index];
/// do sth with int
break;
case Double:
double d = dblArr[e.Index];
/// do sth with double
break;
......

}


Ok, we avoided boxing/unboxing. But how many copy operations we do have?

1 for returning the ArrayElement value + 1 for extracting the index + 1 for
extracting the type + 1 for extracting the concrete value from the
type-cpecific array. At least 4 copy operations + supporting opeations as
shift and logical ops + 2 array indexing(all bound checks, etc). Mountain
finds unboxing(one copy + one typecheck) for expensive. Do you thing it is
more cheap?

B\rgds
100

 

[100]

Hi Frank,

If you cannot use strong typing throughout, and avoid casting to object,
then you may as well stick to an ArrayList and boxing.

I didn't get that. Sorry ;(

Do you want to say that if we use strong typing we cannot avoid casting?

The only interface
that can be used to efficiently retrieve the data is a strongly typed one,
GetInt, GetDouble, etc. Otherwise the whole concept is defeated.

That is the point. you cannot know, which method overload to use without
checking the type of the item at given index.
I haven't tested it, but I might do it when I have more time. At the moment
I'm very sceptic that reading data from two arrays (one array for items's
info, which involves copying data - the expensive part of unboxing and one
for the actual data, which copy data anyway) will be faster than reading
reference type of reference array + type checking+unboxing. These doubts of
mine are only regarding the reading operation; storing value-type data in
reference array will be much slower.
Of course using vaue types and arrays (not dynamic collections) as a storage
gives good opportunity to c# compiler and JITter for optimizations. So it
might be faster.

Regarding the overhead from the copy, shift, logical ops, etc. These are all
very fast and inlined. This is the great thing about structs. Time it and
see.

Yes, bringing shift and logical ops was overkill. BTW they are not inlined
because there is nothing to inline. There are no methods behind them.
About the copy operation as operation which doesn't have to be considered as
a factor when it comes for performance.... hmmm. Again I'm having doubts. I
have timed reading 10,000,000 structures from an array (structs and arrays
good for optimization) and the size of data has noticeable impact on the
results.

Make sure the class you use is not derived from MarshalByRefObject,
which defeats inlining.

It would be really unfortunate if it does inlining

B\rgds
100

Hi Frank,
Yes, you can do that. Haw I said "We can provide method that returns the
type of an object by index
value. But then we need to check this type and...". As far as I remember
Mountain was concerned about reading performance. My question now is: what
is your suggestion about the storage-class (as a whole) interface.
So if you have
class MyStorage
{
.....
}

What interface you suggest to retrieve the data. If you have one method
XXXX GetData(int index)
What is the type of XXXX if it is an 'obect' we have to unbox the object
(Montian wanted to avoid exactly this).
If your idea is not to use one class, but insted bunch of different arrays
for each type + one for ArrayElements
We'll have something like this
ArrayElements e = arrElements[index];
switch(e.Type)
{
case Integer:
int i = intArr[e.Index];
/// do sth with int
break;
case Double:
double d = dblArr[e.Index];
/// do sth with double
break;
......

}


Ok, we avoided boxing/unboxing. But how many copy operations we do have?

1 for returning the ArrayElement value + 1 for extracting the index + 1 for
extracting the type + 1 for extracting the concrete value from the
type-cpecific array. At least 4 copy operations + supporting opeations as
shift and logical ops + 2 array indexing(all bound checks, etc). Mountain
finds unboxing(one copy + one typecheck) for expensive. Do you thing it is
more cheap?

B\rgds
100

 

[Mountain Bikn' Guy]

Frank,
I assume you've seen the Rotor source and maybe used it as a "go-by" for
your arraylist-style collection. I'm thinking about just doing a
search/replace of "object" with my type (double, etc.) to create all my
strongly typed expandable collections. I wanted to ask if you know of any
issues or problems in the Rotor ArrayList source code that I should be aware
of, or any other reason why I shouldn't take the "easy way out" via
search/replace. That is of course, assuming that you may have already done
(or considered and rejected) what I'm thinking about doing.
Regards,
Mountain

 

[Frank Hileman]

Mr. Mountain,

No, actually, that did not come from Rotor. I extracted it from some common
list code we have been using a very long time now, (over a year and a half)
so it is stable. Not much to it really, except the Array calls. I think if
you review it carefully you can see how it is straightforward logic.

Search and replace is unfortunately the way to go. We have a ListBase that
encapsulates the Array stuff but the array itself must be strongly typed so
we were never able to reuse much code with a base class. In the future
generics will eliminate this problem...

By the way I created several strongly type collections with search/replace
and it worked fine.

regards, Frank

 

[Frank Hileman]

Frank, you've given me some great tips. I'm working on the implementation

now. As a side effect of using strongly typed arrays, at steps further down
the line I will be able to eliminate the use of reflection, which should
give even further performance gains.

Yes, you are damn right there! We got a great speedup once by replacing
reflection with generated, strongly typed code. Of course it has to be
something in a fairly tight loop to make a difference.

 

[Frank Hileman]

hello 100, some inline...

Do you want to say that if we use strong typing we cannot avoid casting?

Once you cast to object you box anyway. So if there is a cast to object
anywhere in the chain just use an object array.

I haven't tested it, but I might do it when I have more time. At the moment
I'm very sceptic that reading data from two arrays (one array for items's
info, which involves copying data - the expensive part of unboxing and one
for the actual data, which copy data anyway) will be faster than reading
reference type of reference array + type checking+unboxing. These doubts of
mine are only regarding the reading operation; storing value-type data in
reference array will be much slower.

Not sure I understand what you mean here. With a strongly typed array, the
strongly typed value is just copied right out of the array, and through a
function call. Arrays are fast. You are hitting two or more arrays, but it
is contiguous blocks. Boxing allocates memory on the heap and messes up
locality of reference, pressures the GC. Really I did not time it but I hope
someone else will.

Yes, bringing shift and logical ops was overkill. BTW they are not inlined
because there is nothing to inline. There are no methods behind them.

I meant the struct functions.

 

[Mountain Bikn' Guy]

Hi Frank,
Thanks again for your feedback. I just finished an implementation of a
DoubleArrayList based on the Rotor source I've seen. It ended up not being a
simple search/replace because I had to take the IList implementation out. I
implemented IEnumerable, ICollection and ICloneable, and I also implemented
all the private nested classes, so there are classes like this:
private class IListWrapper : DoubleArrayList, IList
that do implement IList.

So far all I've done is compile it. This definitely wasn't the easy way to
go. The DoubleArrayList class is almost 3000 lines of code. I wouldn't do it
this way again, especially because its useful life will end when generics
are available. However, for this one time it was probably worth it just to
become more intimately acquainted with the Rotor implementation of the
ArrayList class.

Let me know if you care to see any of it. I doubt it contains anything you
would find interesting. It's just a more complex version of what you already
have -- and the complexity is stuff I might not even use now -- stuff like
the various wrappers and thread safe code.

Once I test this class, I'll just use search/replace to create the other
type specific versions.

Regards,
Mountain

 

[100]

Hi Frank,

Once you cast to object you box anyway. So if there is a cast to object
anywhere in the chain just use an object array.

I'm still confused what we are talking about here. Anyway, it is not so
important. I agree with you for what you said here.

Not sure I understand what you mean here.

Ok, I'll try to explain.
Lets assume that you want to store two different value types in our storage.
As far as I understand your suggestion to Mountain is to use 2 separate
arrays (strongly typed) for each of it and one array for your structure
ArrayEntry.
When we want to get a value you check in array-entry array to see in which
data array and at which index we can find the value. Am I right?
So, My point is that using this will be slower (in terms of reading) than
using one array of untyped references (reference to Object) and chek the
type and unbox to apropriate value type.

To back up my point I did some timing of both techniques esterday. Unboxing
beats the other method off. It is indeed faster. Once again I'm talking
about reading. If we want performance for writing (storing) your method is
definitely the winner and I never argue against it.
But as far as I remember Mountains issues were about the performance at
reading or maybe I'm wrong.
So, if I were to implement such a storage I would use your method (or
something similar) if I want to make a storage for general use (since the
performance is good for reading and writing) or I would go with unboxing if
the performance for reading is critical and I don't care for writing since,
for example, it is done only once (the impression I got from the first
Mountain's post).

If you are curious I can give you the test project. I don't want to attach
it to this post because I believe attaching files to posts in newsgroups is
bad practice.

I meant the struct functions.

Yes, they are good for oprimization.

BTW your method of keeping datatype(table type) and index in one unsigned
value is used internaly from CLR as metadata tokens for indexing metdata in
different tables.

B\rgds
100

 

[Mountain Bikn' Guy]

Hi 100,
See my comments inline.
Regards,
Mountain

To back up my point I did some timing of both techniques esterday. Unboxing
beats the other method off. It is indeed faster. Once again I'm talking
about reading. If we want performance for writing (storing) your method is
definitely the winner and I never argue against it.
But as far as I remember Mountains issues were about the performance at
reading or maybe I'm wrong.

Yes, reading occurs more often than writing. The ratio is about 2:1.

So, if I were to implement such a storage I would use your method (or
something similar) if I want to make a storage for general use (since the
performance is good for reading and writing) or I would go with unboxing if
the performance for reading is critical and I don't care for writing since,
for example, it is done only once (the impression I got from the first
Mountain's post).

If you are curious I can give you the test project.

Yes, I'm interested in taking a look at it. I appreciate you following up on
this in so much depth. Please email it to me.

the first part of my address is "Number_235"
and the domain is yahoo dot com