Amen!

Wolfgang Draxinger wrote:
> Derek Parnell wrote:
> 
>>> Creating a new instance serves no purpose at all. So, as an
>>> optimization, you can do away without constant allocation;
>>> just reuse the same object.
>> I think you are deliberately missing the point, Hasan. I
>> thought the point was to show that heap-allocated things are
>> inherently slower than stack-allocated things.
> 
> It makes no difference for the use of objects if they are on the
> heap or on the stack. Both are only portions of the same address
> space (and may even clash if they interpenetrate).
> 
> The only thing that makes things slow is the allocation of heap
> memory which may cause the garbage collector to kick in. But
> once the memory is allocated it can be used as fast as stack
> memory.
> 
>> Classes are slower than structs. Prove otherwise. I'm happy to
>> be shown that I'm wrong.
> 
> I don't see a reason for this. There's no difference in accessing
> the data. Put a struct on the stack, the compiler will compile
> it to access it indirectly (i.e. by "pointers"). Allocate a
> class on the heap, it get's accessed in the very same way.
> 
> As a rule of thumb: Any data you going to work with in a D
> program is encapsulated in classes. Stuff that gets dumped into
> files or memory goes into structs. It's that simple.
> 

Derek made the benchmark quite nice, thank you for that.

Wolfgang wrote:
>The only thing that makes things slow is the allocation of heap memory which may cause the garbage collector to kick in.

Wolfgang wrote:
> But
>once the memory is allocated it can be used as fast as stack memory.

This is not entirely correct. Memory fragmentation means that cache miss is much more frequent on heap allocated data structures. Struct makes it such that data can be bundled nicely together in memory, making them faster to access.

Wolfgang wrote:
>I don't see a reason for this. There's no difference in accessing the data. Put a struct on the stack, the compiler will compile it to access it indirectly (i.e. by "pointers"). Allocate a class on the heap, it get's accessed in the very same way.

Derek meant that struct allocation is much faster than class allocation (~150x), allocation needs to be included when measuring performance, not just access speed.

Wolfgang wrote:
>As a rule of thumb: Any data you going to work with in a D program is encapsulated in classes. Stuff that gets dumped into files or memory goes into structs. It's that simple.

This is the minimal struct approach. However, since that we have already shown that struct allocation/deallocation is more than 100x faster, it makes good sense to use struct for data types that require enormous amount of allocation/deallocation, such as Vector3d in computer graphics, or Point in GUI programming. In fact minTL uses struct to create containers.

On Mon, 27 Mar 2006 22:40:21 +1100, Wolfgang Draxinger <wdraxinger@darkstargames.de> wrote:

> Derek Parnell wrote:

>> Classes are slower than structs. Prove otherwise. I'm happy to
>> be shown that I'm wrong.
>
> I don't see a reason for this. There's no difference in accessing
> the data. Put a struct on the stack, the compiler will compile
> it to access it indirectly (i.e. by "pointers"). Allocate a
> class on the heap, it get's accessed in the very same way.

I really do understand the theory. And on the surface, it would seem that your analysis is valid, however the timings show otherwise. There really is a difference between heap-allocated classes and heap-allocated structs. Classes are slower.

Prove it yourself. Write your own benchmark test and submit its results. Critique my example - pull it apart and improve it. Show me where I've bungled. Until then, the figures show that classes are always slower than structs when used for equivalent tasks.

> As a rule of thumb: Any data you going to work with in a D
> program is encapsulated in classes. Stuff that gets dumped into
> files or memory goes into structs. It's that simple.

Yes it is - in theory. Practice may dicate otherwise though.

-- 
Derek Parnell
Melbourne, Australia

In article <17vpw8ovosqie$.1f65d29ys83k6$.dlg@40tude.net>, Derek Parnell says...
>
>On Mon, 27 Mar 2006 04:11:37 +0000 (UTC), Dave wrote:
>
>> These run as the same speed on my system, which is pretty cool since the accessor function for class Point.x is vitual. If you finalize it the class version is actually faster. No doubt the OP has a point when you try to alloc. classes in a tight loop, and I'd agree that stack allocated classes would be great, but if you can work around the allocation bottleneck then classes tend to be faster and easier to code because they are passed around by reference w/o pointer syntax.
>
>I wasn't so sure about the 'passed around' claim. So I amended my test to pass the object and the results were almost identical. So it appears that passing structs is not an issue at all. In fact, if you look at the generated machine code, the struct seems to be passed by reference even if you code otherwise.
>

Not what I'm seeing - give this a try:

import std.stdio, std.date;

struct S
{
char[1000] str;
}

class C
{
char[1000] str;
}

void main()
{
const int y = 1_000_000;
{
S s;
d_time st = getUTCtime();
for(int x = 0; x < y; x++)
{
fooS(s);
}
d_time en = getUTCtime();
writefln((en-st) / cast(double)TicksPerSecond);
}
{
C c = new C;
d_time st = getUTCtime();
for(int x = 0; x < y; x++)
{
fooC(c);
}
d_time en = getUTCtime();
writefln((en-st) / cast(double)TicksPerSecond);
}
}

void fooS(S s)
{
s.str[] = '\0';
}

void fooC(C c)
{
c.str[] = '\0';
}

Hong wrote:
> Structs are second class citizens of... or maybe refugees of D, they are victims
> of discrimination.
> Following are the reasons:
> 
> 1. most D programmers don't use struct, unless they happen to be the poor guy
> writing the C interface.

Or they are writing or using a D interface to a C or other foreign API.  Or they want to save the overhead of memory allocation by using a lightweight alternative for those situations where the power of classes isn't needed.  Or they are interfacing a binary file format.

> 2. to use structs you have to use pointers, but the spec says pointers are only
> provided for C compatibility, structs are to be avoided as long as the world
> spins.

No I don't.  What are you talking about?

> 3. pointers + overloaded operators make a mess.... this is a less offensive
> example: (*o) = (*t)[(*i) * (*j)] ... the pointers and operators are abusing
> each other.
> 
> 4. structs cannot have constructor, "static opCall" is best you can do.

What's wrong with that?  Do you simply miss the word "new" in uses of static opCall?

> 5. structs are more efficient? Not when structs are passed around by value. To
> change a struct member: 1. make a copy 2. change the copy 3. Copy the copy back
> into the original location. Two damned copies for.... efficiency.

If you want classes, you know where to find them.

> 6. yes, you can use pointers to change a struct member without copying, if you
> can be bothered to define 2 accessor methods, one returns a copy another one
> returns a pointer.

Why would anyone want to do that?  What's wrong with simply

    Qwert yuiop = asdfg;    // to create a copy
    Qwert* zxcvb = &asdfg;  // to create a pointer

> 7. Most standard containers (DTL) do not allow a pointer to a contained struct
> to be retrieved, all changes, or just about anything has to be done via copies.

That's an issue with those containers, rather than with structs themselves.

> 8. structs have different behaviours between array and Vector, array [] returns
> a reference, Vector [] returns a copy, nice rookie trap.
> 
> Imho, following are little suggestions for structs to make first class citizens
> of D:
> 
> 1. have some sort of reference semantic to replace pointers. Pointers are not
> necessary unless structs are used with "new"
> 
> 2. add constructor for struct, destructors are not necessary.
> 
> I use structs because I need efficiency and stack allocated data structures,
> however, it is painful to see a C++ program turns into a C like program when
> ported to D.

Maybe you could elaborate on how these reference semantics would work such that they'd be any different from classes.

Stewart.

-- 
-----BEGIN GEEK CODE BLOCK-----
Version: 3.1
GCS/M d- s:-@ C++@ a->--- UB@ P+ L E@ W++@ N+++ o K-@ w++@ O? M V? PS- PE- Y? PGP- t- 5? X? R b DI? D G e++>++++ h-- r-- !y
------END GEEK CODE BLOCK------

My e-mail is valid but not my primary mailbox.  Please keep replies on the 'group where everyone may benefit.

Stewart Gordon wrote:
> Hong wrote:
>> Structs are second class citizens of... or maybe refugees of D, they are victims
>> of discrimination.
>> Following are the reasons:

[snip]

>> 4. structs cannot have constructor, "static opCall" is best you can do.
> 
> What's wrong with that?  Do you simply miss the word "new" in uses of static opCall?

The problem with not having real constructors is that you can not guarantee that your struct gets initialized correctly.

>> 5. structs are more efficient? Not when structs are passed around by value. To
>> change a struct member: 1. make a copy 2. change the copy 3. Copy the copy back
>> into the original location. Two damned copies for.... efficiency.
> 
> If you want classes, you know where to find them.

Small structs (the cases were structs are most useful) can often more efficient to pass by value than by reference.

>> 6. yes, you can use pointers to change a struct member without copying, if you
>> can be bothered to define 2 accessor methods, one returns a copy another one
>> returns a pointer.
> 
> Why would anyone want to do that?  What's wrong with simply
> 
>     Qwert yuiop = asdfg;    // to create a copy
>     Qwert* zxcvb = &asdfg;  // to create a pointer

If I understand correctly, Hong is talking about struct members (i.e. a member variable of a struct type), that should be accessed through an accessor method. I.e:

Array!(Position) points = ...;
points[5].x = 7;

Or:

myInstance.pos.x = 5;
(Where pos is accessed through a getter method)


>> 7. Most standard containers (DTL) do not allow a pointer to a contained struct
>> to be retrieved, all changes, or just about anything has to be done via copies.
> 
> That's an issue with those containers, rather than with structs themselves.

I agree that this is not an issue with structs.  But it is an issue with the language. Given:

struct Position { int x,y; }

There is no way to duplicate the behavior of:

Position[] points = ...;
points[5].y = 5;
points[3].x += 2;

With an user defined container type.

>> Imho, following are little suggestions for structs to make first class citizens
>> of D:
>>
>> 1. have some sort of reference semantic to replace pointers. Pointers are not
>> necessary unless structs are used with "new"
> 
> Maybe you could elaborate on how these reference semantics would work such that they'd be any different from classes.

You could consider:

struct MyPointContainer {
	Position[] points;
	inout Position opIndex(uint ix) { return &points[ix]; }
}

Where inout denotes that the struct is returned by reference.

/Oskar

In article <e0948b$1ihl$1@digitaldaemon.com>, Oskar Linde says...
>
>Stewart Gordon wrote:
>> Hong wrote:
>>> Structs are second class citizens of... or maybe refugees of D, they
>>> are victims
>>> of discrimination.
>>> Following are the reasons:
>
>[snip]
>
>>> 4. structs cannot have constructor, "static opCall" is best you can do.
>> 
>> What's wrong with that?  Do you simply miss the word "new" in uses of static opCall?
>
>The problem with not having real constructors is that you can not guarantee that your struct gets initialized correctly.
>
>>> 5. structs are more efficient? Not when structs are passed around by
>>> value. To
>>> change a struct member: 1. make a copy 2. change the copy 3. Copy the
>>> copy back
>>> into the original location. Two damned copies for.... efficiency.
>> 
>> If you want classes, you know where to find them.
>
>Small structs (the cases were structs are most useful) can often more efficient to pass by value than by reference.
>

You know, with all of the talk of cache locality and what-not w.r.t. passing small structs by value vs. reference, I've yet to see the "conventional wisdom" (that passing byref is faster) proven wrong, even in larger programs where there has to be things being constantly being moved in and out of cache, etc. I'm not saying that is always the case, but 'often' above is pretty strong there. I'd say at best "sometimes" is a better phrase.

// Yes, yes I know this is may not reflect a typical 'real world' program
//  But still there is a 4x difference on my AMD64 and P4 ('modern
//  processor') boxen, with byref being the faster.

import std.stdio, std.date;

struct S { int i, j, k; }

class C { int i, j, k; }

void main()
{
const int y = 100_000_000;
{
S s;
d_time st = getUTCtime();
for(int x = 0; x < y; x++)
{
fooS(s);
}
d_time en = getUTCtime();
writefln("struct byval: ",(en-st) / cast(double)TicksPerSecond);
}

{
S s;
d_time st = getUTCtime();
for(int x = 0; x < y; x++)
{
fooS2(&s);
}
d_time en = getUTCtime();
writefln("struct byref: ",(en-st) / cast(double)TicksPerSecond);
}

{
C c = new C;
d_time st = getUTCtime();
for(int x = 0; x < y; x++)
{
fooC(c);
}
d_time en = getUTCtime();
writefln("class:        ",(en-st) / cast(double)TicksPerSecond);
}
}

void fooS2(S* s) {  s.i = s.j = s.k = 0; }

void fooS(S s) { s.i = s.j = s.k = 0; }

void fooC(C c) { c.i = c.j = c.k = 0; }

Heheh, how funny!

Dude, you're re-iterating my point exactly.

I was *not* trying to prove that classes are faster than structs; I was just proving that the example is flawed, by providing a similarily flawed example!!

Rioshin an'Harthen wrote:
> [sorry, couldn't resist :P]
> 
> "Hasan Aljudy" <hasan.aljudy@gmail.com> wrote:
>> Heh, this is so flawed.
>>
>> it's got nothing to do with classes vs. structs.
>>
>> The benchmark is designed so that the struct version runs faster than the class version.
>>
>> change the class version to:
>>
>> Point p = new Point();
>> for (uint i = 0; i < n; ++i)
>> { Point.count += p.x;
>> // delete p;
>> }
>>
>> and the struct version to:
>>
>> for (uint i = 0; i < n; ++i)
>> {
>> Point * p = new Point();
>> Point.count += p.x;
>> }
>>
>> These programs don't logically do anything different. However, the class version now runs much much faster than the struct version.
> 
> Heh, this is so flawed.
> 
> The benchmark is designed so that the class version runs faster than the struct version.
> 
> change class version to:
> 
> for (uint i = 0; i < n; ++i)
> {
> Point p = new Point();
> Point.count += p.x;
> // delete p;
> }
> 
> and the struct version to:
> 
> Point p;
> for (uint i = 0; i < n; ++i)
> {
> Point.count += p.x;
> }
> 
>> on my machine:
>>> class
>> 100000000
>> operation took 0 m 0.25 s
>>
>>> struct
>> 100000000
>> operation took 0 m 15.265 s
> 
> on my machine:
>> class
> 100000000
> operation took 0 m 43.594 s
> 
>> struct
> 100000000
> operation took 0 m 0.218 s
> 
>> Try to come up with a more realistic example, and optamize both versions. This way, you can prove that it's the class vs. struct issue and not an optimization issue.
> 
> Maybe you should try to come up with a more realistic example, and optimize both. Now you optimized the class version, but not the struct version. It's easy to claim classes as faster when you selectively optimize one and not the other.
> 
> I intentionally optimized the other way around. If your "optimization" proves classes are faster, then mine proves structs are faster. And the code is still the same - there's no logical difference in how they work (except for garbage collecting much more in the class version, as you had in the struct version).
> 
> To be sure, if both are optimized:
> 
> // struct
> Point p;
> for (uint i = 0; i < n; ++i)
> {
> p.count += p.x;
> }
> 
> // class
> Point p = new Point();
> for (uint i = 0; i < n; ++i)
> {
> p.count += p.x;
> // delete p;
> }
> 
> the times for the class version change to:
> 
>> class
> 100000000
> operation took 0 m 0.25 s
> 
> which is equivalent with the 0.218 s it took for the struct version.
> 
> If you want to prove classes faster than structs, please don't go about it optimizing only the class version and not the struct one. Otherwise, you end up looking like a fool. 
> 
> 

Derek Parnell wrote:
> On Mon, 27 Mar 2006 17:12:34 +1100, Hasan Aljudy <hasan.aljudy@gmail.com> wrote:
<snip>
>>
>> The program doesn't really do anything, you know.
> 
> Wow! Really?! Are you sure?

Yes, I'm sure.

In practical situations, allocating stuff on the heap is not really what you want to do in your program; it's just a way to achieve what you want to do.

If you don't understand what I mean, take this very simple example:
You want to print numbers 1 through 1000 on the screen.

you can do it with a while loop:

	int i = 0;
	while( i <= 1000 )
	{
		writefln(i);
		i++;
	}

but, you can also do it with a for loop:

	for( int i = 0; i <= 1000; i++ )
	{
		writefln(i);
	}

and a goto

	int i = 0;
	
	doit:
	i++;
	writefln(i);
	if( i <= 1000 ) goto doit;

and here's another while loop:

	int i = 0;
	while( true )
	{
		writefln(i);
		i++;
		if( i > 1000 ) break;
	}

or, you can do it sorta like this:

	writefln(1);
	writefln(2);
	writefln(3);
	.
	.
	.
	writefln(999);
	writefln(1000);

all these programs do the same thing, they just do it differently.

Philisophically, you can argue that these programs do different things, the first one does a while loop, the second one does a for loop, the third one does a goto, the last one does it sequentially .. etc.

However, practically, you're doing the same thing, in different ways.
Some ways can be faster than the others.

Here for example, is a stupid way of doing the above program:

	for( int i = 0; i <= 1000; i++ )
	{
		writefln(i);
		for( int j = 0; j < 1000000000; j++ )
		{
			//waste time
			int y = 10;
			int x = 5;
			x = x + y;
		}
	}

However, it still works. Just .... very slow.


This applies to the given benchmark.
You're not doing anything, besides wasting heap space and wasting time allocating on the heap.

> 
>> Creating a new instance serves no purpose at all. So, as an optimization, you can do away without constant allocation; just reuse the same object.
> 
> I think you are deliberately missing the point, Hasan. I thought the point was to show that heap-allocated things are inherently slower than stack-allocated things. The original example didn't do a good job of that but my subsequent example does I believe. Can you please comment on my example code?

OK, sorry, I didn't check your example yet. This does not affect my point.

Memory allocation is not the only thing you do with classes/structs. I'd like to think of it as just an implementation/optimization issue.

One thing were classes would win over structs is pass by reference vs. pass by value.

Create a huge struct, with say, 40 or 50 fields, instantiate it once, then pass it around by value inside a loop (say, a 1000 times).
Then edit the program and change the struct to a class, and when you create it, use "new", and don't change anything else.


>> The example serves very well to illustrate how slow it is to allocate millions of objects on the heap in one go.
>> However, it provides no proof that, in pratical situations, structs are much much faster than classes. Which is basically what the example tries to hint at.
> 
> But I think my example does show that classes (allocated on the heap) are slower than structs whether allocated on the heap or on the stack.
> 
> Classes are slower than structs. Prove otherwise. I'm happy to be shown that I'm wrong.
> 
> --Derek Parnell
> Melbourne, Australia

On Mon, 27 Mar 2006 15:16:38 +0000 (UTC), Dave wrote:

> In article <17vpw8ovosqie$.1f65d29ys83k6$.dlg@40tude.net>, Derek Parnell says...
>>
>>On Mon, 27 Mar 2006 04:11:37 +0000 (UTC), Dave wrote:
>>
>>> These run as the same speed on my system, which is pretty cool since the accessor function for class Point.x is vitual. If you finalize it the class version is actually faster. No doubt the OP has a point when you try to alloc. classes in a tight loop, and I'd agree that stack allocated classes would be great, but if you can work around the allocation bottleneck then classes tend to be faster and easier to code because they are passed around by reference w/o pointer syntax.
>>
>>I wasn't so sure about the 'passed around' claim. So I amended my test to pass the object and the results were almost identical. So it appears that passing structs is not an issue at all. In fact, if you look at the generated machine code, the struct seems to be passed by reference even if you code otherwise.
>>
> 
> Not what I'm seeing - give this a try:

You're right. I was using the 'inout' paradigm which uses byRef method. If you just use the 'in' paradigm, then it does copy struct data to the called routine.

-- 
Derek
(skype: derek.j.parnell)
Melbourne, Australia
"Down with mediocracy!"
28/03/2006 10:19:18 AM