Graphs with 1000+ nodes start to become infeasible

[MarcusTomlinson]

In testing graphs of various sizes, I observed more-or-less the following timings (2021 MacBook M1 Pro):

(x-axis = number of nodes, y-axis = number of seconds to compile*)

* or more specifically, the time it takes for engine.link() to return

[MarcusTomlinson]

Test code: https://github.com/MarcusTomlinson/cmajor/blob/test/examples/native_apps/HelloCmajor/Main.cpp

[julianstorer]

Thanks Marcus - we should profile it and see if there's an obvious hotspot.

[cesaref]

What's going on here is that it's duplicating the processor for each of the passthrough instances in the graph, and then compiling this code that many times, and then attempting to inline it all. I'll look through this and see why the duplication is happening - I think we should be able to avoid this.

Interestingly, the resulting optimisation pass is succeeding in turning it into a sensible bit of code. Here's the output for 1000 nodes (100 parallel branches of 10 nodes):

	.build_version macos, 14, 0
	.globl	_initialise                     ; -- Begin function initialise
	.p2align	2
_initialise:                            ; @initialise
; %bb.0:
	ret
                                        ; -- End function
	.globl	_advanceBlock                   ; -- Begin function advanceBlock
	.p2align	2
_advanceBlock:                          ; @advanceBlock
; %bb.0:
	ldr	w8, [x0]
	cmp	w8, w2
	b.eq	LBB1_3
; %bb.1:                                ; %.lr.ph.preheader
	mov	w9, #100
LBB1_2:                                 ; %.lr.ph
                                        ; =>This Inner Loop Header: Depth=1
	add	x8, x1, w8, sxtw #2
	ldr	w10, [x8]
	mul	w10, w10, w9
	str	w10, [x8, #4096]
	ldr	w8, [x0]
	add	w8, w8, #1
	str	w8, [x0]
	cmp	w8, w2
	b.ne	LBB1_2
LBB1_3:                                 ; %._crit_edge
	str	wzr, [x0]
	ret
                                        ; -- End function```

It's managed to work out that this is basically a *100...

[MarcusTomlinson]

Yeah the resulting optimised graph is mad impressive. It's very fast - after waiting an hour for it compile that is ;)

[cesaref]

It turns out it's spending significant time in an O(N^2) algorithm to make names unique, and there's basically lots of similar named functions, one per instance of this processor. So, try dropping this into cmaj_AST_Utilities.h to replace UniqueNameList:

template <typename ObjectType, typename ParentType>
struct UniqueNameList
{
    UniqueNameList() = default;
    UniqueNameList (const UniqueNameList&) = delete;

    std::string getName (const ObjectType& o)
    {
        auto& name = names[std::addressof (o)];

        if (name.empty())
        {
            auto root = static_cast<ParentType&> (*this).getRootName (o);

            if (root.empty())
                root = "_";

            auto exists = [this] (const std::string& nameToCheck) -> bool
            {
                for (auto& n : names)
                    if (n.second == nameToCheck)
                        return true;

                return false;
            };

            auto uniqueName = root;
            auto& suffix = suffixes[root];

            if (suffix != 0)
                uniqueName = root + "_" + std::to_string (suffix++);

            while (exists (uniqueName))
                uniqueName = root + "_" + std::to_string (suffix++);

            name = uniqueName;
        }

        return name;
    }

    void clear()
    {
        names.clear();
    }

    std::unordered_map<const ObjectType*, std::string> names;
    std::unordered_map<std::string, uint32_t> suffixes;
};

This takes the runtime for 4000 nodes (500/8) from 275 secs to 9 secs on my machine, and 10,000 nodes (500/20) with this algorithm takes 65 secs.

I'll see about getting a fix something like this into the codebase.

[cesaref]

I've pushed another performance fix, the 500/8 case is now down to 1.8 secs, and the 10,000 nodes to 9 seconds on my machine. I think that's more reasonable given the size of the graph. The next issue to resolve is to move the duplication of the code for this situation.