[r-t] Big searches

[Mark Davies]

Don writes,

> Except the coding and debugging. :-)

Nah, real men get their machine code right first time. :-D

Actually, it's very easy to write small pieces of assembler. An inner loop -
which is all you need to do really - is normally straightforward. 
Increasingly however, high-level languages are getting the edge. SMC32 is 
optimised for early Pentiums, and I'm sure you could do better with modern 
architectures, but you might have to have several different versions of the 
code. In theory with a JIT you write the code once and the virtual machine 
gives you the best code for the platform you're running on. Well that's the 
theory - in practice we're not there yet, and SMC32's inner loop still goes 
like the  proverbial off a digging implement.

I do remember I had problems with my fragment search loop, though. I wonder,
is this the sort of thing you have developed for your Rutland search Don?
The idea was you did a short breadth-first search to identify sets of call
sequences ("fragments") which were identical both in terms of permutation
and music. Then the inner composing loop would check the current calls
against the fragment list, and backtrack if a match was found. This is an
extremely useful optimisation, especially if two types of call are being
used; for instance, it would automatically find the "plain before single"
rule for MUG Minor. The actual mechanics of the machine code were fairly
straightforward (there are some MMX instructions which allowed the fragment
matching to be done very efficiently) however getting assembler to index
into complex data structures created by a high-level language isn't always
easy. The code is still in the state where it runs, but doesn't generate the
right output. Maybe one day...

MBD