Tuesday, June 06, 2006

Reached Clockcycle Level

The tactics code is almost finished (1000+ LOC but a lot of that is due to LF's and unrolled loops), and the more I work on it, the faster it becomes.

I have a kind of ADHD, and often, the only way I can design an algorithm is to get away from the keyboard. Depending on the finances and the weather, it's either the pub or the tub :-) Today I walked to the harbor and designed a simple stack-based floodfill algo over a beer. The challenge was splitting empty chains most efficiently by re-using some of the cleverly-represented data, so that I do not have to floodfill both parts of a dual split.

Then I went home and hacked it up.

I keep discovering ways to get that code faster. Letting small arrays start on a cache line is an obvious speedup, but at the moment I am way beyond that and am using AMD's instruction latency table to decide whether a SHR with an AND could be replaced by a table lookup to shave off one cycle, that sort of thing. A pity I have to hit the sack, because I just found yet another dramatic speedup trick that I'm eager to implement because it also makes the source smaller and easier to read (the source looks, um, extraterrestrial).

Of course, the resulting 64-bit MASM assembly that Free Pascal generates will have to be hand-optimized by yours truly, but that will be low-pri. First the thing has to actually work, and it needs stuff around it to automate it as well. No need for undo code: I use a state stack that, due to minimalistic data representation, fits a deep treesearch entirely in the L1 cache.

Someone suggested that my business goal should be perfecting the Help file, but after years of work on Moyo Go, I need to re-invent myself, not to mention the need to do the hardest things when one's brain is youngest. There is an optimum between experience and number of deceased neurons, and it shifts leftwards with algorithmic complexity :-)

If Moyo Go wants to compete with the Big Boys and, as is the goal, ultimately dethrone them, I really have to bootstrap myself out of the swamp of bugfixing ever less serious bugs and perfecting things that are already pretty good. Nothing kills a business faster than lack of innovation. Moyo Go was never intended to be the best Go databasing/pattern system, it got that status because the Joseki library module turned out to be a super-powerful pattern expert system, so successful that even Microsoft tried to copy it. But my goal is to make a dan level Go program, and, heaven permitting, I'll succeed if I can keep away from that Help file :-)