Does hashlife JIT away interpretive layers?

[Johnicholas]

Would it be true to say that for any unit cell (like David Bell's unit life cell, or Brice Due's metapixel, or calcyman's stable, programmable metapixel), that hashlife will churn through figuring out the operation of the unit cell in constant time, and then spend all of the rest of its time operating at or above the level of the emulated CA?

That is, will inefficiencies in the unit cell circuitry will only have an O(1) impact on the hashlife runtime, if the runtime is measured in physical time, and the stopping criterion is "X generations of the emulated CA"?

Relevant:
http://eigenratios.blogspot.com/ - Clive Gifford thinks that measuring the presumed multiplicative slowdown of self-interpreters might be useful somehow; Hashlife seems like a counterexample, that has an additive slowdown for another interpretive layer.
http://thyer.name/phd-thesis/ - Mike Thyer has a lambda-calculus interpreter that can specialize away interpretive layers, and incur only additive slowdowns. I suspect that sufficently convoluted or inefficient code might fool his algorithm, but it can "see through" normal, straightforward interpreters.

[calcyman]

Yes and no. If you have sufficient RAM, my metacells (having power-of-two spatiotemporal dimensions) will only add constant time to simulation; other metacells are less efficient. Brice Due's (theoretically) increases time 69-fold, theoretically, and David Bell's is not HashLife-friendly at all.

For my computer, though, Brice Due's cells are the most efficient, because I don't have sufficient RAM to fully store all possible states of my metacell.

Do you want any specific patterns meta- or mega-fying? My work-in-progress C++ program can make meta^2-cells etc.

[Johnicholas]

I'm not sure, but would it be correct to say that if golly (or rather, hashlife) stops adding macrocells of a particular size (because new macrocells of that size stop turning up) then it's done thinking about that level? That is, all of its questions are being answered with a hash lookup, and it doesn't need to go down to a smaller level any more. If it was going down to a smaller level, then it would also be coming back up from a smaller level, and adding a new macrocell to memoize that excursion.

Once we've achieved that "level is done" point, any inefficiencies in the circuitry of the unit cell don't matter any longer, and the algorithm is running roughly as fast as if it had started with the simulated rule as the basic rule, and no unit cells at all.

Then wouldn't a unit cell that is not a power of two still get compiled away? The O(1) would be bigger because it would take until all of the shifts of the unit cell within the next power of two are accumulated, and the number of "colors" in the algorithm's simulated CA (as opposed to the designer's intended simulated CA) would be huge.

How do you calculate "69-fold"? Is it experimental, or based on the dimensions of the unit cell? And do you mean hashlife running a metafied pattern vs quicklife running the pre-metafied pattern? Or hashlife vs. hashlife?

[calcyman]

I'm not sure, but would it be correct to say that if golly (or rather, hashlife) stops adding macrocells of a particular size (because new macrocells of that size stop turning up) then it's done thinking about that level?

Correct.

Once we've achieved that "level is done" point, any inefficiencies in the circuitry of the unit cell don't matter any longer

That's not strictly true. Brice Due's metacells, for example, have a period of 35328 = 69 * 2^9. This means that HashLife must store 69 copies of each of {live,dead} metacells when running at a large power-of-two step size. (Strictly speaking, it's slightly more complicated than that.) This propagates up the quadtree, resulting in 69 times more effective copies of the simulated pattern (wlog, assume it's an oscillator) than in non-metafied HashLife.

And do you mean hashlife running a metafied pattern vs quicklife running the pre-metafied pattern? Or hashlife vs. hashlife?

HashLife vs. HashLife.

The O(1) would be bigger because it would take until all of the shifts of the unit cell within the next power of two are accumulated, and the number of "colors" in the algorithm's simulated CA (as opposed to the designer's intended simulated CA) would be huge.

Entirely correct. Except it's not the O(1) (constant additive term) that increases, but rather the constant scaling factor (increasing memory from ~n to ~kn, where k is the largest odd divisor of the product of the width, height and period of the metacell -- 1 in my case, 23 in Brice Due's, and 703125 in David Bell's).

[Johnicholas]

Thank you very much!