I just encountered a case where changing (?=A(?=B)) to (?=AB) made things dramatically slower and I feel like this shouldn’t happen

@Grimy Hi! Interesting. I think you mean changing it to (?=A)(?=B)? Or when can you change (?=A(?=B)) to (?=AB)?

Oops

Misread that as (?=(?=A)B)

Hmmm. Yes, if anything, (?=A(?=B))should be a tiny bit slower. Is it slower in JS, RME, or both?

Also I'm intrigued by your idea about changing the state encoding. With your idea, could it still be a seedless loop?

It’s slower in RME, didn’t test in JS

I had seeding sorted out, but accessing the prime factors of N was longer than I thought, so I dropped the idea as unlikely to give a gain

Otoh I have a (?*) 386 using a very wonky way to iterate prime factors

Currently seeing if I can drop the (?*)

It worked =D

Could you please show me the (?=A(?=B)) to (?=AB) slowdown?

Oooh

Sure, 30s

@Grimy What's the resultant length?

384

Wow!

Here’s the slow 386 with (?*): pastebin.com/raw/T0cYNPMM

and if you replace (?=(x+?)\1+$) with (?=(x+?)(?=\1+$)) it gets a lot faster

9.19s to 1.17s in my test

:-O

And here’s the (unfortunately even slower) 384: pastebin.com/raw/P2kvR9La

Those are both iterating prime factors out of order, which is hilarious and also a miracle it works at all

Out of order? Is this related to the (x*)x* to (x*)+ optimization?

I’m not sure which optimization you’re talking about

Oh, and how did you even find out that that change made it faster? Found by accident?

No, changing (?=A(?=B)) to (?=AB) was an obvious golf and it made it slower

Of course I wouldn’t have written (?=A(?=B)) first, but it used to be (?=A(?=B)x) and I moved other things around to be able to remove the x

Ahh

@Grimy regex out-of-order optimization.txt - I can flesh this out if necessary

I was investigating in exactly what way those constructs are out of order relative to their "unoptimized" versions

And thinking about whether it'd be worthwhile making RME recognize them and skipping the unnecessary redundant evaluations (i.e. optimize them)

Oh that’s not what I meant by out-of-order

Oh?

Just that your solution iterates prime factors of N from largest to smallest, and my new one doesn’t

And also doesn’t iterate from smallest to largest

Yeah, just like what I just showed you

These iterate through numbers in an order that isn't smallest-to-largest or largest-to-smallest

Except that in this case, it's order of backtracking, whereas yours is not backtracking

That sounds barely-related to me

I'm just wondering how you can iterate prime factors out of order.

I’ll let you figure it out ;)

I thought you were going to comment it and make a post?

Yes yes eventually

I’m bad at commenting though

(?=\7((x+?)\1+)$) to (?=\7((x+?)\1+$)) - 18% speedup (because RME doesn't optimize that yet)

Nice one

Ahhh, that speedup is because RME optimizes a certain form and not its non-lookahead equivalent

The speedup is nonexistent with -O0

So it's somewhere in runtimeOptimize_matchSymbol_Character_or_Backref()

382 (=

Wowww

Probably not getting much lower. The only part I haven’t thoroughly scrubbed is the floored division at the end, and I don’t think there’s much to gain there.

Okay, the optimization is totalLength += thisCapture * currentSymbol->minCount;

That's why (?=A(?=B)) was faster

in (?=(x+?)(?=\1+$)) it skips over the (x+?) values that won't make \1+$ match, but only if the \1+$ is in a lookahead

Which I did because it's commonly used for multiplication

Oh hey I have two \10 and three \11 so I could make \5 and \9 non-capturing for an easy 1 byte save

Ooh

Good thing I rewrote that \11{2} to \11\11

Just curious, why do you use 4-space indents in some places and 8-space in others?

Got messed up on copy-paste

Hmmm if I drop 3 more bytes the total improvement over your 504 will be exactly 25%

:D

@Grimy But an improvement of 24.76% would be even better ;)

That's the density of abundant numbers

That's a joke BTW :) please don't limit your optimizations to fit a contrived amount :)

I can’t get exactly 24.76% though, it’s either 24.60 or 24.80

@Grimy I was hoping you'd show me the 381 before signing off...

Also I'm wondering, how do you keep track of which capture group is which with only partial comments?

And uh mostly memory, sometimes counting

And here’s 380: pastebin.com/raw/yHgkcs4V