Examples of DFA

[Dennis]

On Tuesday, 23 September 2025 at 22:10:22 UTC, Walter Bright 
wrote:
> It does more than O(V) only when there are cycles.

Just step 2, constructing the bit vectors, is already O(V^2). 
Even without cycles, you can hit the O(V^3) case if you have a 
deep call stack.

On Tuesday, 23 September 2025 at 22:10:22 UTC, Walter Bright 
wrote:
> The reusable memory buffer thing was benchmarked by myself long 
> ago, and was a big win.

The problem is, a trick is found to be useful in one spot at one 
time, and 15 years later it's still blanketed everywhere without 
question. Meanwhile, it's 2025, the TypeScript compiler got a 3x 
speed up from leveraging multi-threading, and dmd is still stuck 
in `__gshared` town, population 500+. Mutable global buffers are 
even being used in dmd's brand new ARM disassembler, which is a) 
not performance critical and b) if it were, the key to make it 
run fast on modern hardware is not `__gshared char[5 + hw.sizeof 
* 3 + 1 + 1]`.

> I don't know what you mean by bit-hacking.

I meant things like using an `int flags` parameter with 2 bits 
or'd in instead of 2 `bool` parameters. But it's not the best 
example, I'm talking about the general pattern of 
micro-optimizations, not specific instances of the problem.

> My general approach is to make it work first, not worrying too 
> much about algorithms.
>
> (...)
>
> It paid off to not be too pre-judgmental about what time it 
> would take.

Which is why it puzzles me:

There's a simple, classic algorithm that runs in linear time, 
which is pre-judged to be slow because there's array 
concatenation in it.

Then there's a complex algorithm with a nested for-loop triple, 
which is pre-judged to be fast because it's going to use bit 
vectors, and it has extra logic to prune the search space making 
it not as bad hopefully.

And you think the latter fits the philosophy "make it work 
first"? I mean, be my guest and implement it, I just think you're 
making it harder for yourself if you do. And I am going to be 
wary and test performance when something like that lands in dmd 😉

> I appreciate your efforts here, it is very valuable work you 
> are doing!

Thanks!