Examples of DFA

[Dennis]

On Tuesday, 23 September 2025 at 17:46:20 UTC, Walter Bright 
wrote:
> Your algorithm is interesting, but I don't think it is 
> fundamentally different from the one I sketched out.

I think both algorithms compute the same thing, but your 
algorithm represents the graph with an adjacency matrix and does 
an inefficient search. The algorithm be O(V + E), with V = 
vertices = number of function declarations, and E = edges = 
number of function calls.

That is, compile time should scale linearly with the amount of 
source code being compiled.

Your algorithm does a O(V^2) traversal O(V) times, running in 
O(V^3) time. That's a pathological worst case scenario, but I'm 
not convinced the constant factor is so large that it's more 
practical than a linear search.

> Also, it uses expensive operations like array appends, and the 
> filter function. The bit mask route should be much faster.

I wrote the example as a simple illustration, not as optimized 
production code. The filter function is trivially replaced with 
an if statement if the optimizer doesn't already do that.

On a slight tangent, I'm not a fan of how dmd's performance 
culture seems to be hyper focused on local constant time code 
optimizations that worsen code quality (like bit-hacking and 
using global variables for reusable memory buffers) when there's 
a number of glaring issues related to time complexity, which are 
way more severe than a redundant allocation here and there could 
ever be.

Whenever I investigate what slows down compilation time of real 
code, it's usually because it triggers a bad case of one of the 
many quadratic or even exponential algorithms in dmd's code. I'm 
talking:

- O(n^2) MSCoff section insertion 
(https://github.com/dlang/dmd/pull/16780)
- O(n^2) Checking for missing/duplicated switch case statements 
(TODO)
- O(2^n) Nested function sibling detection 
(https://github.com/dlang/dmd/pull/14886)
- O(2^n) Return type isolated from parameters check 
(https://github.com/dlang/dmd/pull/12885)
- O(n*m) CTFE execution because AA literals aren't memoized 
(https://github.com/dlang/dmd/issues/20179)
- O(2^n) Function inlining 
(https://github.com/dlang/dmd/issues/20315)
- O(n^2) Loop optimizations 
(https://github.com/dlang/dmd/issues/20535)

A fast constant factor is nice, but let's not introduce more 
'compilation time landmines' into dmd's code base, and prefer 
linear algorithms over quadratic ones.