[r-t] Big searches
mark at snowtiger.net
Sun Jan 6 10:55:19 UTC 2008
> 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...
More information about the ringing-theory