C# generic containers from a "C++ perspective"

G

Giovanni Dicanio

When I have a List<T> in C#, I think that the "list" (i.e.: dynamically
growing array) stores "pointers" to T instances, e.g. considering a
pseudo-equivalent C++ code, my understanding is that the C# version:

List< MyClass >

is equivalent to something like this in C++:

std::vector< MyClass * >

Is that correct?

Now, the question is: if we have List of "primitive" types (like an 'int',
or 'double'...), how are these "primitive types" stored in the List? Are
they stored "by value"? Or are they stored "by pointers"?

i.e. the C# version:

List< double >

is equivalent to C++ :

vector< double >

or instead:

vector< double * >

?

Thanks in advance,
Giovanni
 
A

Anthony Jones

Giovanni Dicanio said:
When I have a List<T> in C#, I think that the "list" (i.e.: dynamically
growing array) stores "pointers" to T instances, e.g. considering a
pseudo-equivalent C++ code, my understanding is that the C# version:

List< MyClass >

is equivalent to something like this in C++:

std::vector< MyClass * >

Is that correct?

Close enough. All memory for classes are allocated from a heap anyway and
all references point to that space in the heap. Hence in C# there is no
need to differentiate between a class instance and a class pointer.
Now, the question is: if we have List of "primitive" types (like an 'int',
or 'double'...), how are these "primitive types" stored in the List? Are
they stored "by value"? Or are they stored "by pointers"?

i.e. the C# version:

List< double >

is equivalent to C++ :

vector< double >

or instead:

vector< double * >

?


They are stored by value IOW vector< double >.
 
I

ignacio machin

When I have a List<T> in C#, I think that the "list" (i.e.: dynamically
growing array) stores "pointers" to T instances, e.g. considering a
pseudo-equivalent C++ code, my understanding is that the C# version:

 List< MyClass >

is equivalent to something like this in C++:

 std::vector< MyClass * >


Hi,

They are stored by value. That is the good thing about generics
in .NET, you do not need to box (create a reference) a value type.
The opposite happens when you use for example ArrayList , in that case
the value type is converted to a reference type

Ignacio Machin ( .NET/ C# MVP )
machin TA laceupsolutions.com
 
J

Jon Harrop

Giovanni said:
i.e. the C# version:

List< double >

is equivalent to C++ :

vector< double >

or instead:

vector< double * >

The former. This is one of the things that C++ screwed up and is fixed in
C#, making it much nicer to program in.
 
G

Giovanni Dicanio

Jon Harrop said:
The former. This is one of the things that C++ screwed up and is fixed in
C#, making it much nicer to program in.

I agree with you.
And that is not the only thing done better in C# than in C++ (other things
include better string management and built-in support for Unicode strings,
reflection, etc.)

However, there are also some things that IMHO are better in C++ than C#,
like RAII and deterministic destruction.
(The garbage collector is good for memory resources, but there are also
*non*-memory resources, like files, sockets, textures... for them garbage
collector is useless, and RAII and deterministic destruction are better.)

Giovanni
 
B

Ben Voigt [C++ MVP]

Jon said:
The former. This is one of the things that C++ screwed up and is
fixed in C#, making it much nicer to program in.

Go ahead, spread the FUD. Or explain exactly how you feel the .NET (not C#)
way is better than the stl containers. Surely the OP would be interested in
knowing the differences and advantages of each.

Actually templates and generics are different in a lot of ways, but
templates are much more powerful, effectively a superset of generics (modulo
some bad error messages which will be fixed in C++0x).
 
J

Jon Skeet [C# MVP]

Actually templates and generics are different in a lot of ways, but
templates are much more powerful, effectively a superset of generics (modulo
some bad error messages which will be fixed in C++0x).

In terms of being a superset, a couple of things I don't *think* you
can do with C++ templates:

1) Create a constructed type at execution time via reflection. I don't
know how much reflection exists at *all* in C++ (or standard/common
libraries) but my understanding of templates would suggest this would
be harder.

2) Ship a generic type without any source. I could very well be wrong
on this, but my understanding is that when you use a template you need
the source code, so the compiler can build the specialized version. In
..NET the compiler just says "I want a List<int>" and refers to the
*binary* List<T>. This comes with a bunch of corollaries to do with
versioning/upgrades, of course.

Please, please correct me if I'm wrong though :)
 
B

Ben Voigt [C++ MVP]

Jon said:
In terms of being a superset, a couple of things I don't *think* you
can do with C++ templates:

1) Create a constructed type at execution time via reflection. I don't
know how much reflection exists at *all* in C++ (or standard/common
libraries) but my understanding of templates would suggest this would
be harder.

C++ reflection gives dynamic type testing, but nothing more. COM gives more
reflection-like capabilities, as long as you are using type libraries.
Using CoCreateInstance or the factory pattern for instantiation, if you
compiled the template against an interface type (pure abstract class), you
could then use it with any coclass implementing that interface, pretty much
the same as a generic. These execution-time constructed types aren't
offering compile-time type safety in .NET anyway, so I don't consider it a
drawback that C++/COM might require calls to QueryInterface.
2) Ship a generic type without any source. I could very well be wrong
on this, but my understanding is that when you use a template you need
the source code, so the compiler can build the specialized version. In
.NET the compiler just says "I want a List<int>" and refers to the
*binary* List<T>. This comes with a bunch of corollaries to do with
versioning/upgrades, of course.

The C++ standard supports this, but Visual C++ doesn't. On other platforms
that define a C++ ABI, this might give you some ability to upgrade templates
without a recompile, but not much.
Please, please correct me if I'm wrong though :)

..NET generics do preserve "type identity" across instantiations in different
modules as well, while C++ needs COM to accomplish that.

But this list pales in comparison to the things templates do that generics
don't and can't emulate.
 
J

Jon Harrop

Ben said:
Go ahead, spread the FUD.

The design flaws in C++ are widely appreciated.
Or explain exactly how you feel the .NET (not C#) way is better than the
stl containers. Surely the OP would be interested in knowing the
differences and advantages of each.

This has nothing to do with containers or even templates. The OP's confusion
stems from the fact that C++ forces you to use pointers in order to make
full use of its object system. In reality, pointers are not necessary for
OOP.
Actually templates and generics are different in a lot of ways, but
templates are much more powerful, effectively a superset of generics

Turing argument.

Your subjective notion of "power" equates to slow compilation and poor error
messages in practice, neither of which are desirable. The advantage of
templates is a rather naff form of metaprogramming, long since obsoleted by
JIT compilers.
(modulo some bad error messages which will be fixed in C++0x).

And Fortran 2003 will rule the world...
 
A

Arne Vajhøj

Ben said:
.NET generics do preserve "type identity" across instantiations in different
modules as well, while C++ needs COM to accomplish that.

If C++ needs COM to do something then the C++ language/C++
standard environment does not support it.

It is a fair assumption that C# code is running on Windows, but
it is a very bad assumption that C++ code is running on Windows.

Arne
 
A

Arne Vajhøj

Jon said:
Turing argument.

Your subjective notion of "power" equates to slow compilation and poor error
messages in practice, neither of which are desirable. The advantage of
templates is a rather naff form of metaprogramming, long since obsoleted by
JIT compilers.

Try and search for C# generic calculate.

There are plenty of functionality in C++ templates that are not
in C# generics.

And JIT does not change anything about that.

Arne

PS: That something is missing from a language does not necessarily mean
that it will be good to add it. More is not always better.
 
J

Jon Harrop

Arne said:
Try and search for C# generic calculate.

I cannot find what you are indicating. Do you have a specific reference?
There are plenty of functionality in C++ templates that are not
in C# generics.

Exactly. C# provides parametric polymorphism in the form of generics (which
is one use of C++ templates) and JIT compilation for metaprogramming (which
is the other use of templates).
And JIT does not change anything about that.

On the contrary, template metaprogramming in C++ is used to work around the
absence of a JIT compiler. This is a fundamental aspect of lots of
mainstream C++ libraries like Blitz++ and Boost. Reams have been written on
the subject. But it is all a waste of time because run-time code generation
is vastly more productive than template metaprogramming: orders of
magnitude faster to compile and easier to debug.
PS: That something is missing from a language does not necessarily mean
that it will be good to add it. More is not always better.

The problem is that people like Ben Voigt spread mindless propaganda
like "templates are much more powerful, effectively a superset of
generics", implying that the Turing completeness of templates makes them
superior with no regard for the crippling degradation in programming
productivity incurred by slow compile times and awful error messages in
C++.

In practice, the usability of generics easily outweights the benefits of
templates.
 
B

Ben Voigt [C++ MVP]

Jon said:
I cannot find what you are indicating. Do you have a specific
reference?

C# generics cannot possibly use any feature of the type argument that is not
expressed as an interface implementation. Some things, like constructor
parameters, cannot be expressed with interfaces, while others, like simple
arithmetics, aren't on the built-in types. Whatever the reason, if there's
no interface, C# generics can't do it.

Just so you understand fully, I challenge you to create a .NET generic for a
moving average (ring buffer of N entries that returns the mean) which can be
instantiated on both double and decimal (the only operations needed are add
and divide). For bonus points make it work with any UDT that defines those
two operations.

The C++ template is both more straightforward and more efficient.
Exactly. C# provides parametric polymorphism in the form of generics
(which is one use of C++ templates) and JIT compilation for
metaprogramming (which is the other use of templates).


On the contrary, template metaprogramming in C++ is used to work
around the absence of a JIT compiler. This is a fundamental aspect of

Or gain the same capabilities but precompiled, so the deployed application
is lightweight and ready to run immediately. JIT is a disaster if you need
fast startup.
lots of mainstream C++ libraries like Blitz++ and Boost. Reams have
been written on the subject. But it is all a waste of time because
run-time code generation is vastly more productive than template
metaprogramming: orders of magnitude faster to compile and easier to
debug.

More FUD, especially the "easier to debug" part is just outright wrong.
It's like saying that dynamic languages are more productive -- well they are
for small tasks, but for larger ones the benefits of static typing outweigh
the additional effort.

As an example of how much "easier to debug" run-time generated code is, try
just getting a stack trace of a .NET program from a minidump. It's both far
more complicated a user interface and far more complicated underneath, plus
it won't work with a selective dump, you need all the internal JIT data
structures included, bloating your dumps by hundreds of megabytes.
 
J

Jon Harrop

Ben said:
C# generics cannot possibly use any feature of the type argument that is
not
expressed as an interface implementation. Some things, like constructor
parameters, cannot be expressed with interfaces, while others, like simple
arithmetics, aren't on the built-in types. Whatever the reason, if
there's no interface, C# generics can't do it.

Sure. I'm not contesting that templates try to solve problems that generics
do not. I am saying that all of the other problems solved by templates are
better solved by other techniques, most notably explicit code generation.
Moreover, in the overlap between generics and templates, generics are a
clear win because they are so much easier to use.
Just so you understand fully, I challenge you to create a .NET generic for
a moving average (ring buffer of N entries that returns the mean) which
can be instantiated on both double and decimal (the only operations needed
are add
and divide). For bonus points make it work with any UDT that defines
those two operations.

The C++ template is both more straightforward and more efficient.

You have drawn that conclusion before looking at any evidence.

Let's look at some real examples. For trivial cases like the (useless)
static factorial function you can encode your metaprograms in C++
templates:

http://aszt.inf.elte.hu/~gsd/halado_cpp/ch06s04.html

Here is their factorial implementation:

#include <iostream>

template <int N>
struct Factorial
{
enum { value = N * Factorial<N-1>::value };
};

template <>
struct Factorial<1>
{
enum { value = 1 };
};

int main()
{
const int fact5 = Factorial<15>::value;
std::cout << fact5 << endl;
return 0;
}

This is useless because you can just use a lookup function.

Now let's look at something non-trivial, like a high-performance FFT
implementation. The fastest cross-platform FFT implementation is FFTW,
which is C code generated by an OCaml program.

Many C++ advocates have tried to do the same code generation using C++
templates because it would make such a compelling example of templates
actually being good for metaprogramming. However, every single person to
have ever attempted to do this has completely and utterly failed. Dr Dobb's
even published an article on exactly this:

http://www.ddj.com/cpp/199500857

If you look at the OCaml source code of FFTW you will see many non-trivial
symbolic optimizations implemented using pattern matching over variant
types that optimize the generated code in ways that are prohibitively
difficult to implement using C++ templates.

The fact that C++ templates are theoretically capable of doing this because
they are Turing complete is useless because it is practically impossible to
do so because templates are so cumbersome to use for metaprogramming.
Or gain the same capabilities

That is wrong. C++ templates cannot perform specialization based upon
run-time values.
but precompiled,

JIT provides both precompilation and run-time compilation. C++ only provides
precompilation.
so the deployed application is lightweight and ready to run immediately.

That is also wrong. Because C++ templates cannot handle run-time values the
only efficient solution is to precompile every conceivable permutation of
inputs. This results in combinatorial code explosion with incredibly
heavy-weight libraries and very slow loading times. C++ is famously bad for
this.

In contrast, JIT compilation can lazily compile code as and when it is
needed. This results in leaner libraries and executables that load faster
and even work cross-platform.
JIT is a disaster if you need fast startup.

If your application requires submillisecond startup times, sure.
More FUD, especially the "easier to debug" part is just outright wrong.
It's like saying that dynamic languages are more productive -- well they
are for small tasks, but for larger ones the benefits of static typing
outweigh the additional effort.

I'm just going to pull rank here. You need to learn some decent languages.
Look at modern statically-typed functional programming languages for a
start.
 
B

Ben Voigt [C++ MVP]

Jon said:
Sure. I'm not contesting that templates try to solve problems that
generics do not. I am saying that all of the other problems solved by
templates are better solved by other techniques, most notably
explicit code generation. Moreover, in the overlap between generics
and templates, generics are a clear win because they are so much
easier to use.

[snip talking about OCaml]

I'm just going to pull rank here. You need to learn some decent
languages. Look at modern statically-typed functional programming
languages for a start.

Last I checked we were comparing C++ templates to .NET generics. Are you
claiming that you could insert F# everywhere you said OCaml and all your
claims remain true? Last I heard you were complaining about the miserable
performance of F#'s allocator.

You need to learn about .NET generics before you start saying they are
oh-so-much-better than C++ templates. They aren't. Maybe OCaml generic
programming is, I haven't played with that for a while, but definitely .NET
generics fall far short.

Also you completely avoided my example.

For that matter, I don't think the OCaml moving average is going to beat the
C++ template either, for performance or readability. Plus anyone trying to
do an FFT with metaprogramming is doing it for the challenge, no other
reason. A much better way is selecting between several pre-optimized
routines based on a couple of conditions like magnitude of length and
whether the length is a power of 2.

For example, how much .NET code (pick your language) would you need to
accomplish the same thing as this?

template <typename Integral>
inline bool isPowerOfTwo(Integral const n)
{
return (n & (n-1)) == 0;
}
 
M

Marc Gravell

Just so you understand fully, I challenge you to create a .NET generic fora
moving average (ring buffer of N entries that returns the mean) which can be
instantiated on both double and decimal (the only operations needed are add
and divide).  For bonus points make it work with any UDT that defines those
two operations.

If the mood took me, I'm pretty sure U could take that challenge, and
the bonus points for UDT:
www.pobox.com/~skeet/csharp/genericoperators.html

(full download available in MiscUtil, and for the record, I also have
a .NET 2.0 version as well as the .NET 3.5 version cited)
The C++ template is both more straightforward and more efficient.

Stating it (by itself) isn't exactly conclusive. Besides; C++
templates are compile time; I can make new types and use them with
generics at runtime. The JIT isn't perfect, but generally does a
pretty good job... pretty flexible.

Marc
 
J

Jon Harrop

Ben said:
Last I checked we were comparing C++ templates to .NET generics.

Yes. In the process, you brought up a problem (metaprogramming) that
templates can solve but generics do not. My point is that .NET languages
already have better ways to solve that problem, independently of generics.
Are you claiming that you could insert F# everywhere you said OCaml and
all your claims remain true?
Yes.

Last I heard you were complaining about the miserable performance of F#'s
allocator.

The single-threaded symbolic optimizer from FFTW would currently be ~5x
slower in F# than it is in OCaml. There is no easy way to improve this.
You need to learn about .NET generics before you start saying they are
oh-so-much-better than C++ templates. They aren't.

The error reporting from generics is much better than templates.
Maybe OCaml generic programming is, I haven't played with that for a
while, but definitely .NET generics fall far short.

That's because you're trying to use a tool for parametric polymorphism for
code generation. They are completely different problems best solved by
completely independent solutions like generics and JIT compilation.
Also you completely avoided my example.

Your problem statement does not make sense to me. If you want the moving
average to work properly over ints and floats then you must use different
algorithms. Or do you want to cast the ints to floats?
For that matter, I don't think the OCaml moving average is going to beat
the C++ template either, for performance or readability.

On what basis?
Plus anyone trying to do an FFT with metaprogramming is doing it for the
challenge, no other reason.

On the contrary, this is how professionals write production-quality code.
FFTW has millions of users and is at the core of one of the world's most
successful technical computing environments, MATLAB.
A much better way is selecting between several pre-optimized
routines based on a couple of conditions like magnitude of length and
whether the length is a power of 2.

All of the world's best FFT implementations used to do that. Actually, they
even wrote dozens of painstakingly hand-optimized routines and chose
between them at run-time.

Then FFTW came along with its thousands of automatically optimized routines
(codelets) and beat all other implementations hands down on performance
whilst remaining platform independent.
For example, how much .NET code (pick your language) would you need to
accomplish the same thing as this?

template <typename Integral>
inline bool isPowerOfTwo(Integral const n)
{
return (n & (n-1)) == 0;
}

In F#:

let inline is_pow2(n : #Math.INumeric) =
n &&& (n - n.One) = n.Zero

As long as you stick to trivial examples you won't see the downside of C++
templates.
 
B

Ben Voigt [C++ MVP]

Jon said:
Yes. In the process, you brought up a problem (metaprogramming) that
templates can solve but generics do not. My point is that .NET
languages already have better ways to solve that problem,
independently of generics.


The single-threaded symbolic optimizer from FFTW would currently be
~5x slower in F# than it is in OCaml. There is no easy way to improve
this.


The error reporting from generics is much better than templates.

That is a known issue which I spoke of in my first post in this thread.
C++0x fixes that too.
That's because you're trying to use a tool for parametric
polymorphism for code generation. They are completely different
problems best solved by completely independent solutions like
generics and JIT compilation.

Generics, which are early bound, don't provide parametric polymorphism.
Templates do.
Your problem statement does not make sense to me. If you want the
moving average to work properly over ints and floats then you must
use different algorithms. Or do you want to cast the ints to floats?

What part of "both double and decimal" didn't you understand?

And why would different algorithms be needed? In C++ the same algorithm
will work for both int and float (until overflow becomes a problem, but the
accumulator can be a different type) except for roundoff, which is expected
for int.
On what basis?


On the contrary, this is how professionals write production-quality
code. FFTW has millions of users and is at the core of one of the
world's most successful technical computing environments, MATLAB.


All of the world's best FFT implementations used to do that.
Actually, they even wrote dozens of painstakingly hand-optimized
routines and chose between them at run-time.

Then FFTW came along with its thousands of automatically optimized
routines (codelets) and beat all other implementations hands down on
performance whilst remaining platform independent.

through the use of JIT?

No, as I recall the comparison process is very slow (I may be thinking of
ATLAS rather than FFTW), and the compile time is only a small fraction of
that.
In F#:

let inline is_pow2(n : #Math.INumeric) =
n &&& (n - n.One) = n.Zero

Oh, F# defines the bitwise and operation for all types it pretends to
implement INumeric for? It's not part of the INumeric interface. It's not
even part of the IIntegral interface. And it must turn that into something
pretty ugly in order for the CLR to accept it.
As long as you stick to trivial examples you won't see the downside
of C++ templates.

If they are so trivial, how come .NET generics can't solve them?
 
B

Ben Voigt [C++ MVP]

Marc said:
If the mood took me, I'm pretty sure U could take that challenge, and
the bonus points for UDT:
www.pobox.com/~skeet/csharp/genericoperators.html

(full download available in MiscUtil, and for the record, I also have
a .NET 2.0 version as well as the .NET 3.5 version cited)


Stating it (by itself) isn't exactly conclusive. Besides; C++
templates are compile time; I can make new types and use them with
generics at runtime. The JIT isn't perfect, but generally does a
pretty good job... pretty flexible.

Except that .NET's JIT is neutered when it comes to reference types as
generic arguments. Or does your .NET 3.5 Expression-based implementation
overcome that as well?
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Top