Optimizing Custom Data Structures for Primitive Types

[jehugaleahsa]

Hello:

When developing data structures for C#, there is an obvious
performance hit when utilizing primitive types. For instance, a recent
hash table implementation I wrote works exceedingly fast on strings.
It can run through a million randomly generated strings in less than
half of a second (in most tests). The built-in dictionary class takes
close to 10 seconds. (Just trust my measurements; I don't want to
argue about the correctness of my tests)

However, switching over to a primitive type, such as int, double,
decimal, etc. will usually take significantly longer. The interesting
part is that C#'s built-in data structures seems to excel when
primitives are involved. The tables seems to turn, sort of speak.

The first thing that pops into mind is that there is some sort of
boxing occurring behind the scenes. If not that, it is some other
bottleneck I am overlooking.

Does anyone know why the built-in data structures are so primitive
friendly? Is there a way to utilize the technique(s) in my own data
structures?

Thanks for your time,
Travis

[Peter Morris]

You really need to post your test code somewhere. It's not very easy for
anyone to tell you why something is happening without you showing what you
are doing.
--
Pete
====
http://mrpmorris.blogspot.com
http://www.capableobjects.com

[=?ISO-8859-1?Q?Arne_Vajh=F8j?=]

je**********@gm ail.com wrote:

When developing data structures for C#, there is an obvious
performance hit when utilizing primitive types. For instance, a recent
hash table implementation I wrote works exceedingly fast on strings.
It can run through a million randomly generated strings in less than
half of a second (in most tests). The built-in dictionary class takes
close to 10 seconds. (Just trust my measurements; I don't want to
argue about the correctness of my tests)

However, switching over to a primitive type, such as int, double,
decimal, etc. will usually take significantly longer. The interesting
part is that C#'s built-in data structures seems to excel when
primitives are involved. The tables seems to turn, sort of speak.

The first thing that pops into mind is that there is some sort of
boxing occurring behind the scenes. If not that, it is some other
bottleneck I am overlooking.

Does anyone know why the built-in data structures are so primitive
friendly? Is there a way to utilize the technique(s) in my own data
structures?

The MS code is available.

If you make your code available, then you may get some
response.

It is obviously not possible to explain performance characteristics
of unknown code.

Arne

[Family Tree Mike]

This artical seems to agree with your observation:

http://en.csharp-online.net/CSharp_G...ic_Counterpart

<je**********@g mail.comwrote in message
news:50******** *************** ***********@p49 g2000hsd.google groups.com...

Hello:

When developing data structures for C#, there is an obvious
performance hit when utilizing primitive types. For instance, a recent
hash table implementation I wrote works exceedingly fast on strings.
It can run through a million randomly generated strings in less than
half of a second (in most tests). The built-in dictionary class takes
close to 10 seconds. (Just trust my measurements; I don't want to
argue about the correctness of my tests)

However, switching over to a primitive type, such as int, double,
decimal, etc. will usually take significantly longer. The interesting
part is that C#'s built-in data structures seems to excel when
primitives are involved. The tables seems to turn, sort of speak.

The first thing that pops into mind is that there is some sort of
boxing occurring behind the scenes. If not that, it is some other
bottleneck I am overlooking.

Does anyone know why the built-in data structures are so primitive
friendly? Is there a way to utilize the technique(s) in my own data
structures?

Thanks for your time,
Travis

[Peter Duniho]

On Sat, 04 Oct 2008 22:07:26 -0700, je**********@gm ail.com
<je**********@g mail.comwrote:

Hello:

When developing data structures for C#, there is an obvious
performance hit when utilizing primitive types. For instance, a recent
hash table implementation I wrote works exceedingly fast on strings.
It can run through a million randomly generated strings in less than
half of a second (in most tests). The built-in dictionary class takes
close to 10 seconds. (Just trust my measurements; I don't want to
argue about the correctness of my tests)

All due respect, you cannot expect to make a statement about performance,
especially one that may be contrary to others own observations, and expect
people to just trust your measurements and to not get into a discussion as
to whether you're measurements are valid.

At the very least, it's always possible that you've implemented something
in a non-optimal fashion, rendering your measurements irrelevant. And in
any case, there's absolutely no reason for anyone to make an assumption
that you've made relevant measurements just on your say-so. No offense
intended here -- I myself have mistakenly written benchmark code that
turned out to be bogus -- it's just a matter of fact.

However, switching over to a primitive type, such as int, double,
decimal, etc. will usually take significantly longer. The interesting
part is that C#'s built-in data structures seems to excel when
primitives are involved. The tables seems to turn, sort of speak.

The first thing that pops into mind is that there is some sort of
boxing occurring behind the scenes. If not that, it is some other
bottleneck I am overlooking.

Boxing certainly could be an issue. But since you're unwilling to post a
concise-but-complete code sample that illustrates what you're talking
about, there's no way to know.

Does anyone know why the built-in data structures are so primitive
friendly? Is there a way to utilize the technique(s) in my own data
structures?

What "built-in data structures" are you talking about? As "Family Tree
Mike" suggests, it's possible you're seeing a different between the use of
a generic class versus a non-generic class. For example, while the
article he links to isn't very explicit about the issue, the generic
Dictionary<TKey , TValueclass can be much more efficient with value types
than the Hashtable class, because of the lack of a need for boxing when
using the generic class.

But if you won't post code, no one can have a useful discussion with you
about the topic. It's all pure conjecture until you're willing to provide
concrete details.

Pete