#Measuring the Space complexity of a given piece of code

1 messages · Page 1 of 1 (latest)

fiery plank
#

Hi!! I have a project which I have created and I wish to use it to measure the "space complexity" of a given piece of code. The problem is that I have tried GC but it doesnt get me what I want. I have also come across Memory Profiling too, but am not sure whether it will do the job for scripts. The thing is that the project doesnt have much visuals and the memory usage is entirely depended on the script. So I wanted to know if there is anything for my purpose. The sole idea is to check the efficiency of a code in terms of space complexity.

Thanks

gritty roost
# fiery plank Hi!! I have a project which I have created and I wish to use it to measure the "...

The profiler alone can show you how much memory was allocated during a frame, or you can specify a sample too to isolate sections of your code
https://docs.unity3d.com/6000.1/Documentation/ScriptReference/Profiling.Profiler.BeginSample.html
The memory profiler would be used to capture snapshots and you could take a deeper dive into every object. I don't know if you'd want to use the memory profiler here unless you truly don't know what objects are being created, which you probably should in this case

fiery plank
gritty roost
neon spire
#

space complexity is how much it scales at large values, not how much it actually uses

gritty roost
#

if its creating unity objects, itd make sense using the profiler since you cant easily determine the cost of spawning a prefab for example. Though yea if this is just an array or common algorithm being measured, then its already known

neon spire
#

the complexity of spawning N prefabs is O(N)

#

the cost is not easily known yeah, but the complexity definitely is

gritty roost
# neon spire the complexity of spawning a prefab is O(1)

in theory sure, but im sure you're aware this is just an oversimplification thats meaningless. I dont know what they were trying to specifically check, but if someone asked you roughly how much space some prefabs take and you told them O(1), you'd definitely feel like thats a shit answer.

neon spire
#

right, but that's not asking about space complexity

#

if i asked about space complexity i'd expect an answer in big-O

#

space complexity is wholly about theory

#

a dictionary's O(1) access time is a lot slower than an array's O(1) access time

#

complexity doesn't measure amount, it measures scaling

gritty roost
#

🤷‍♂️ if we focus so hard on 2 words, while actively avoiding what the questions true intent is, we aren't helping anyone at that point.

neon spire
#

i don't know what the intent is and im not gonna assume much
I do know that they used a very specific term, "complexity"

#

and i did already explain what im referring to with "space complexity" in the case that was mentioned by mistake as well

gritty roost
#

and focusing so hard on what you know "space complexity" to mean, to shift the conversation away from the persons true intent doesn't achieve anything. it doesn't have to be defined using big O. It's defined in any way that people want to measure it

neon spire
#

why are you so focused on their true intent

#

are you in their head lmao

#

do you really know their true intent

#

all i see is a specific term being used thrice, and i answered accordingly

#

im not trying to be an ass about it

#

there are many ways to measure complexity, yes, but all of them deal with theory because that's what complexity is

neon spire
#

maybe they misunderstood the term and they're really asking about dynamic usage or cost. maybe they do mean complexity and they're approaching it wrong

who am I to assume what they meant?

fiery plank
#

apologies about the confusion, its actually the memory usage that I am looking for

autumn tapir
#

can you share the snippet of code?

fiery plank
# autumn tapir can you share the snippet of code?

I couldnt find anything concrete yet... and have been trying the different things I could find on the internet... but following is the last thing I got to which uses the Profiler class:

{
    public EvaluationResult OnEvaluate(int evalSize, bool bSaveAndExport)
    {
        if (evalSize <= 0)
        {
            Debug.LogError("Evaluation size must be greater than 0.");
            return null;
        }

        // Evaluate the algorithms and collect the results
        var result = Evaluate(evalSize);

        if (result == null) return null;

        // If bSave is true, save the evaluation results
        if (bSaveAndExport)
            Export();
        
        return result;
    }

    private EvaluationResult Evaluate(int evalSize) 
    {
        Profiler.logFile = "pathfinder_analysis";
        Profiler.enableBinaryLog = true;
        Profiler.BeginSample($"Pathfinding: {GetType().Name}");

        var result = evaluator.Evaluate(evalSize);
        
        Profiler.EndSample();
        Profiler.enabled = false;

        return result;
    }

    private void Export()
    {
        var results = evaluator.GetEvaluationResults();
        
        var data = saveManager.CreateSaveData(mGrid.GetGridConfig(), results);
        saveManager.AddSaveData(data);
        saveManager.SaveAndExport();

        evaluator.ClearResults();
    }
}```
#

The problem in this is the overhead which results in incorrect data

#

I have also tried playing around with the GC abit more and the problem with that is that its inconsistent... I could have taken the average data but they also produce negative results

the following is the code I tried using earlier:

public static (T result, StatData stats) RecordStats<T>(Func<T> func)
{
    // Measure time separately without GC interference
    var sw = Stopwatch.StartNew();
    var result = func();
    sw.Stop();
    
    // Then measure memory
    GC.Collect();
    GC.WaitForPendingFinalizers();
    GC.Collect();
    
    long before = GC.GetTotalMemory(true);
    var temp = func(); // Run again just for memory measurement
    long after = GC.GetTotalMemory(false);
    
    return (result, new StatData
    {
        TimeTaken = sw.ElapsedMilliseconds,
        MemoryUsed = Math.Max(0, (after - before) / 1024f),
        PeakMemoryUsed = 0
    });
}
fiery plank
gritty roost
fiery plank
fiery plank
#

its the MemoryUsed I am trying to get

gritty roost
#

usually for the time we just accept the fact the profiler adds overhead. if you were using the deep profiler, that adds even more so you could turn off deep profiling if you just want a result in MS. IMO finding the exact time it took on your device doesn't achieve anything

fiery plank
#

hmm... I see... actually this is for a research paper... so I was hoping if I could find solutions which are more accurate

#

guess I cant do it in a loop and stick to doing it manually

gritty roost
#

Is there something specific you're trying to determine here because pathfinding algorithms are already heavily researched. for example you can easily find the space and time complexity in big O notation
Seeing how much memory or time it takes on your device really doesn't achieve much. As for memory you don't exactly need to profile it either since you could calculate how many bytes an example should take. These algorithms don't rely on anything unity related

#

usually when you profile something, it's because you have a performance issue somewhere and are trying to narrow that down to an exact section of code that can be improved. It could highlight when something is allocating when it shouldnt be

autumn tapir
#

you are overthinking this

#

you can just look at the code and figure it out

autumn tapir
#

compare relative memory usage of pathfinding approaches?

#

show RunGBFS and RunAStar

#

show the code that implements all these things

fiery plank
# autumn tapir compare relative memory usage of pathfinding approaches?

yeah... thats what I am trying to do here... memory usage and time taken to execute the code, Run() methods are calling the Navigate()

so basically this:

public abstract class BasePathfinding : MonoBehaviour
{
    public PathResult Navigate(Node start, Node end, HashSet<Node> allowedNodes = null, bool trackStats = true)
    {
        if (trackStats)
        {
            var (result, stats) = Stats.RecordStats(() => FindPath(start, end, allowedNodes));

            if (result != null)
            {
                result.TimeTaken = stats.TimeTaken;
                return result;
            }
            return null;
        }
        return FindPath(start, end, allowedNodes) ?? null;
    }

    protected virtual PathResult FindPath(Node start, Node goal, HashSet<Node> allowedNodes = null) => null;
}
autumn tapir
#

🫲 i like that you are using unity to make an interesting, practical and aesthetically pleasing piece of research
🫱 the algorithms themselves are almost certainly better off being written with a non-garbage-collected memory model, like "HPC#" (aka Unity Burst / Jobs) or using only C# stack allocations

fiery plank
autumn tapir
#

so the literature about e.g. a* uses O(n) where n is the length of the optimal solution

#

does it make sense why

#

for example, so what if your "array" - i think you mean the size of the space your character is moving around in - is n if you are asking to go from coordinate (0,0) to coordinate (0,1) for example

fiery plank
#

I do understand what you try to explain... but tell me something... with a growing size of the grid, do you think that the memory usage would increase too?

autumn tapir
#

no.

#

not from the POV of the algorithmic space complexity of pathfinding

#

not for your heuristic

#

you can see how the constraints and heuristic matter

fiery plank
#

but research shows... that it does

image.png
#

how is that possible

#

this paper is cited by a paper published in IEEE

#

and interestingly, with both A* and Dijkstra, it grows until a certain threshold and than the memory usage starts coming down

#

but the author doesnt explore the threshold but they do show the trend

autumn tapir
#

i think this is saying that the test cases that have names like 64^3 have longer optimal solutions so of course there will be more memory usage observed

#

if they tested the same journey in 32^3 and 64^3 with a manhattan heuristic and constant weight cost between nodes it would be the same memory usage

#

which should be kind of obvious, a* isn't going to visit the whole grid

#

the worst case space complexity for A* is O(k^n) if you allow any weights for example, it should be clear why - what if there is a negative weight at the end of your search? you will have to visit every path and since it's bfs it is exponential

fiery plank
#

this is the trend they show

image.png
fiery plank
autumn tapir
fiery plank
autumn tapir
#

it's not like what i am saying is wrong

#

it doesn't matter if your tracing includes the node graph, for example, because all four algorithms you are testing would have it in the scope of tracing, right? so we don't really care about that

#

in the literature for this stuff, n means the length of the optimal solution. i would think about why first

#

try to understand why

autumn tapir
#

i think probably the coordinates were always from (0,0,0) to (size,size,size), so of course if the solution distance were longer it will use more memory

#

but i don't think it does enough work to evaluate that

#

it doesn't really matter

#

we don't see the source code so it could be any number of mistakes

#

it's up to you

#

basically it's measuring something idiosyncratic about how he generated his environments

#

it looks like the author said "Mathf.random < 0.25f" the cell gets a block, otherwise no.

#

which... you know, you can reason about what that will do

#

anyway. you got a very valuable opinion from me i hope

#

all of his results are measuring something idiosyncratic about his environments

#

we already know the space complexities of these algorithms

#

he didn't use real environments so i don't know how practical his results are

#

it would be interesting to compare pathfinding in cases that really matter, like typical RTS maps with tons of units

#

or in light of some specific gameplay

#

but... id on't think the results will be unexpected

fiery plank
#

I was only interested in how they tried to test their scalability... my original aim is to extend a recently researched algorithm to 3D virtual space as it showed improvements against the classical algorithms in 2D... so I thought it would be interesting to see if this algorithm would work there too... so I made a PCG based grid map to test this out

autumn tapir
#

that's cool

#

I was only interested in how they tried to test their scalability
he did it poorly is i guess the punchline