471,089 Members | 1,663 Online
Bytes | Software Development & Data Engineering Community
Post +

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 471,089 software developers and data experts.

Optimizing Custom Data Structures for Primitive Types

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
Oct 5 '08 #1
4 1917
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

Oct 5 '08 #2
je**********@gmail.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
Oct 5 '08 #3
This artical seems to agree with your observation:

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

<je**********@gmail.comwrote in message
news:50**********************************@p49g2000 hsd.googlegroups.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
Oct 5 '08 #4
On Sat, 04 Oct 2008 22:07:26 -0700, je**********@gmail.com
<je**********@gmail.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
Oct 5 '08 #5

This discussion thread is closed

Replies have been disabled for this discussion.

Similar topics

11 posts views Thread by Innocence | last post: by
2 posts views Thread by wtnt | last post: by
7 posts views Thread by Luc Tremblay | last post: by
9 posts views Thread by Gonçalo Rodrigues | last post: by
4 posts views Thread by Thomas Paul Diffenbach | last post: by
14 posts views Thread by SD | last post: by
3 posts views Thread by Bear | last post: by
6 posts views Thread by Dennis Myrén | last post: by
1 post views Thread by jehugaleahsa | last post: by

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.