Struct within a class... on stack?

[Grofit]

Hey,

Just want to confirm something... if i have a struct, lets say a point within a class. Would that point live within the stack, even though the class is a reference type...

Im pretty sure that it would live in the stack whereas everything else would point to the heap... im basically looking at turning a class that gets created and deleted ALOT into a struct, to improve performance, it would be about 16 bytes in size (4xuint) so it *sounds* like a good idea.

Although a few other things that may interfere with my idea ...

- They are all contained within a class
- They *may* need to implement from an interface, although it is rarely called as its interface type
- They *may* need to contain a few simple methods

Anyone think its worth it and if there are any problems from my given info?

[BigEd781]

No, your object will live on the heap, along with all of its members, whether they are value or reference types. If part of your object lived on the stack, what would happen when the method returns? That piece would be destroyed when the stack is cleaned up, but there may be external references to your object. So now you have a corrupted object living somewhere on the heap.

[Grofit]

oh well... i thought it would have just stayed alive in the stack until the class was destroyed... its just if i have a List<T> of structs then it would all dump on the heap and i dont know how many i would have so i cant really use a static array...

[Mutant_Fruit]

Arrays are classes so they're on the heap too. Don't microoptimise memory usage until you know it's an issue

[BigEd781]

The heap is there for a reason and it is meant to be used. Unless memory usage on the heap is a proven issue in your application there is nothing to worry about here. Also, I would avoid even trying to optimize memory usage until you understand what is really going on behind the scenes.

[MadHatter]

also remember that this isn't C++, there is a memory manager, so even if one lived here and the other there, attempting to optimize like that would make it less efficient. the memory manager has built in optimizations so that newing things does not have the same type of overhead as it would in a non-managed space (unless you had your own memory manager that pooled).

[Grofit]

The reason i bring it up is because ive got a simple A* path finder, and at the moment everything is a class and keeps building lists of these waypoints as it traverses the map, the problem is its LOADS of small objects being created, then a couple of milliseconds later being destroyed, and if i have quite a few of these things doing all this at the same time, then i was thinking that i should try and turn my waypoints into structs.

That was only because the way i understood structs was that they lived on the stack so the GC didnt care about them, so they would be created and destroyed based on the scope and would be alot faster and more efficient on the GC as it wouldnt have to worry about these masses of small objects piling up.

[ixilom]

If you are worried about the small classes being created and destroyed over and over again and thus giving some sort of performance issue, considering using some sort of pool ?

[Grofit]

If you are worried about the small classes being created and destroyed over and over again and thus giving some sort of performance issue, considering using some sort of pool ?

Good idea but im not sure if doing pool lookups and resizing the pool would just work out as inefficient in another area due to me looping lots of times, so each loop would require multiple pool lookups. Its definatly worth looking into though...

I just thought that structs were pretty much designed for this sort of scenario, creating and destroying many small (12-16 bytes) objects frequently...

[BigEd781]

Good idea but im not sure if doing pool lookups and resizing the pool would just work out as inefficient in another area due to me looping lots of times, so each loop would require multiple pool lookups. Its definatly worth looking into though...

I just thought that structs were pretty much designed for this sort of scenario, creating and destroying many small (12-16 bytes) objects frequently...

First, don't prematurely optimize your code. Take the most clear approach and optimize only if necessary. Second, optimizing is for experts. You don't really understand how this stuff works, so if you find yourself in a situation where you really need to optimize memory or CPU usage, spend some time learning what is actually going on.

[Grofit]

First, don't prematurely optimize your code. Take the most clear approach and optimize only if necessary. Second, optimizing is for experts. You don't really understand how this stuff works, so if you find yourself in a situation where you really need to optimize memory or CPU usage, spend some time learning what is actually going on.

I already have the code in a stable state,and i want to make it faster as testing with alot of path finds at the same time is starting to get a bit choppy.

I hate it when people tell you not to bother doing something when you don't understand it fully, as how the hell are you meant to learn unless you take a stab at it. If i wasn't willing to learn i wouldn't be posting here, you cant just magically understand something without learning from those who know better.

Anyway if making them into value types opposed to reference types in this instance will not give me any performance difference then no worries and thanks for your help.

[BigEd781]

I hate it when people tell you not to bother doing something when you don't understand it fully, as how the hell are you meant to learn unless you take a stab at it. If i wasn't willing to learn i wouldn't be posting here, you cant just magically understand something without learning from those who know better.

I didn't mean to imply that you should not bother, I suggested that you optimize only after you have shown that it is necessary and to do so with more knowledge than you currently have. That said, you were obviously trying to learn how that works by posting here, so I could have phrased my last response more appropriately .

Anyhow, before you can do any optimization you should be profiling your code in a quantitative way. perhaps you could post some example code and we could help you with that.

[Grofit]

Hey,

Sorry i tried to reply over the weekend but my web host is pretty bad and i couldnt add a new folder and share it... i honestly dont know why, and i didnt want to paste reams of code in here...

Here is the basic implementation i currently have... I started on a 2nd version which would use a multiple tier approach, so you would have less nodes spaced further apart on the top and more closer spaced nodes at the bottom level, allowing quicker lookups unless it came to a more dense area, but it had some bugs so i didnt finish it, here is the current implementation:

// Path.cs
using System;
using System.Collections.Generic;
using System.Text;
using PathLib.interfaces;
 
namespace PathLib
{
public class Path
{
private List<PathNode> m_OpenList;
private List<PathNode> m_ClosedList;
 
private int m_NodesChecked;
 
public int NodesChecked
{
get { return m_NodesChecked; }
}
 
public Path()
{
m_OpenList = new List<PathNode>();
m_ClosedList = new List<PathNode>();
m_NodesChecked = 0;
}
 
public List<PathNode> FindPath(PathNode StartNode, PathNode GoalNode)
{
m_NodesChecked = 0;
List<PathNode> Solution = new List<PathNode>();
 
m_OpenList.Add(StartNode);
PathNode CurrentNode = null;
 
while (m_OpenList.Count > 0)
{
m_OpenList.Sort();
CurrentNode = m_OpenList[0];
m_OpenList.RemoveAt(0);
 
if (CurrentNode.isGoal())
{ break; }
 
//for each node_successor or node_current
foreach (KeyValuePair<WaypointDirection, IWaypoint> PossibleWaypoint in CurrentNode.Waypoint.LinkedWaypoints)
{
m_NodesChecked++;
 
int Cost = CurrentNode.Cost;
 
switch (PossibleWaypoint.Key)
{
case WaypointDirection.UP_LEFT:
case WaypointDirection.UP_RIGHT:
case WaypointDirection.DOWN_RIGHT:
case WaypointDirection.DOWN_LEFT:
{ Cost += 14; } break;
 
case WaypointDirection.UP:
case WaypointDirection.RIGHT:
case WaypointDirection.DOWN:
case WaypointDirection.LEFT:
{ Cost += 10; } break;
}
 
PathNode PossibleRoute = new PathNode(CurrentNode, GoalNode, Cost, PossibleWaypoint.Value);
 
//if node_successor is on the OPEN list but the existing one is as good
//or better then discard this successor and continue
int LocatedOpenIndex = m_OpenList.IndexOf(PossibleRoute);
if (LocatedOpenIndex > 0)
{
PathNode ExistingNode = m_OpenList[LocatedOpenIndex];
if (ExistingNode.CompareTo(CurrentNode) <= 0)
{ continue; }
}
 
//if node_successor is on the CLOSED list but the existing one is as good
//or better then discard this successor and continue;
int LocatedClosedIndex = m_ClosedList.IndexOf(PossibleRoute);
if (LocatedClosedIndex > 0)
{
PathNode ExistingNode = m_ClosedList[LocatedClosedIndex];
if (ExistingNode.CompareTo(CurrentNode) <= 0)
{ continue; }
}
 
//Remove occurences of node_successor from OPEN and CLOSED
if (LocatedOpenIndex != -1)
{ m_OpenList.RemoveAt(LocatedOpenIndex); }
if (LocatedClosedIndex != -1)
{ m_ClosedList.RemoveAt(LocatedClosedIndex); }
 
m_OpenList.Add(PossibleRoute);
}
m_ClosedList.Add(CurrentNode);
}
 
while (CurrentNode != null)
{
Solution.Insert(0, CurrentNode);
CurrentNode = CurrentNode.Parent;
}
 
return Solution;
}
}
}

// Waypoint.cs
using System.Collections.Generic;
using PathLib.interfaces;
 
#if SILVERLIGHT
using Point = System.Windows.Point;
#else
using Point = System.Drawing.Point;
#endif
 
namespace PathLib
{
public class Waypoint : IWaypoint
{
protected Point m_Position;
protected int m_Score;
protected Dictionary<WaypointDirection, IWaypoint> m_LinkedWaypoints;
 
public Waypoint()
{
m_Position = new Point();
m_Score = 0;
m_LinkedWaypoints = new Dictionary<WaypointDirection, IWaypoint>();
}
 
public Waypoint(Point Position, int Score)
{
m_Position = Position;
m_Score = Score;
}
 
#region IWaypoint Members
 
public Point Position
{
get { return m_Position; }
set { m_Position = value; }
}
 
public int Score
{
get { return m_Score; }
set { m_Score = value; }
}
 
public Dictionary<WaypointDirection, IWaypoint> LinkedWaypoints
{
get { return m_LinkedWaypoints; }
set { m_LinkedWaypoints = value; }
}
 
#endregion
}
}

// PathNode.cs
using System;
using PathLib.interfaces;
 
#if SILVERLIGHT
using Point = System.Windows.Point;
#else
using Point = System.Drawing.Point;
#endif
 
namespace PathLib
{
public class PathNode : IComparable, IComparable<PathNode>, IEquatable<PathNode>
{
private IWaypoint m_Waypoint;
 
private PathNode m_Parent;
private PathNode m_GoalNode;
private int m_Cost;
private int m_GoalCost;
 
public IWaypoint Waypoint
{
get { return m_Waypoint; }
set { m_Waypoint = value; }
}
 
public PathNode Parent
{
get { return m_Parent; }
set { m_Parent = value; }
}
 
public PathNode GoalNode
{
get { return m_GoalNode; }
set { m_GoalNode = value; }
}
 
public int Cost
{
get { return m_Cost; }
set { m_Cost = value; }
}
 
public int GoalCost
{
get { return m_GoalCost; }
set { m_GoalCost = value; }
}
 
public int TotalCost
{
// Add the cost of the distance so far, then the estimated
// goal cost, then the underlying waypoint's base score
get { return m_Cost + m_GoalCost + m_Waypoint.Score; }
}
 
public bool isGoal()
{ return Equals(m_GoalNode); }
 
public PathNode(PathNode Parent, PathNode GoalNode, int Cost, IWaypoint Waypoint)
{
m_Parent = Parent;
m_Cost = Cost;
m_GoalNode = GoalNode;
m_Waypoint = Waypoint;
 
m_GoalCost = CalculateGoalCost();
}
 
public PathNode(IWaypoint Waypoint)
{
m_Parent = null;
m_Cost = 0;
m_GoalCost = 0;
m_GoalNode = null;
m_Waypoint = Waypoint;
}
 
public PathNode(PathNode GoalNode, IWaypoint Waypoint)
{
m_Parent = null;
m_Cost = 0;
m_GoalNode = GoalNode;
m_Waypoint = Waypoint;
 
m_GoalCost = CalculateGoalCost();
}
 
private int CalculateGoalCost()
{
var ResultX = GoalNode.Waypoint.Position.X - m_Waypoint.Position.X;
var ResultY = GoalNode.Waypoint.Position.Y - m_Waypoint.Position.Y;
return (int)Math.Max(Math.Abs(ResultX), Math.Abs(ResultY));
}
 
#region IComparable<PathNode> Members
 
public int CompareTo(PathNode other)
{ return TotalCost.CompareTo(other.TotalCost); }
 
#endregion
 
#region IEquatable<PathNode> Members
 
public bool Equals(PathNode other)
{ return m_Waypoint.Position.Equals(other.m_Waypoint.Position); }
 
#endregion
 
#region IComparable Members
 
public int CompareTo(object obj)
{
return TotalCost.CompareTo((obj as PathNode).TotalCost);
}
 
#endregion
}
}

Those are the main 3 files... i was thinking of turning the waypoints and pathnodes into structs if this would allow for better performance, although i would also need to change the classes slightly and not contain the pre-generated linkings and some other stuff so it all contained value types.

The linked neighbours are generated from an AreaAnalyzer class, which basically gets passed a levels layout and generates a quadtree of waypoints which already has the neighbour relationships stored to stop having to do lookups for neighbours each itteration...

(Sorry the code wouldnt format correctly)