Elf Help: Improving Search Time

How can I make it go faster?

Even for short touches, half-lead spliced composition can be very slow, simply because there are so many billions of possible ways of putting methods together. In fact, spliced composition of any sort is absolutely the worst job you can give to a computer! However, Elf has a few tricks up its sleeve which can turn days into hours and hours into minutes. First though, it's important to understand the factors that affect the speed of a search.

Things that make it go slower

• More leads. It doesn't make much difference how many parts you've chosen - the number of leads in the part has the biggest single impact on the search length. For instance, in a 5-spliced search, every extra lead increases the search time roughly by a factor of 25, because there are 5-times-5 possible combinations of five methods in one lead. So reducing the number of leads (perhaps by increasing the number of parts) is the simplest way of making an impossibly long search more feasible.
• Calls. Checking the "Allow bobs" box dramatically increases the search space. Taking the example above, every extra lead in the part now multiplies the search time by 5x5x2 = 50 times. Fortunately there is often no need to use bobs, because splicing methods at the half-lead usually churns the order of the bells around very quickly anyway.
• More methods. The more methods you are splicing, the more possibilities there are for arranging each lead. For example, in 3-spliced there are 9 ways of arranging one lead; for 8-spliced that figure rises to 64.
• Keeping more compositions. The default is to keep 10 compositions in the "top N" list; in Undómiel, you can change this, for instance to keep more compositions. However, the more you keep, the slower your searches may run. This is not because storing compositions is difficult for Elf - it's just because the "music pruning" part of Elf's algorithm won't be able to work so effectively. Put simply, during a search Elf can ignore any part of the search tree not scoring highly enough to make the "top N" list; but the bigger the list is, the lower the scores of compositions at the bottom. If you made the list big enough to store every composition, Elf would have to search for every composition, not just the higher-scoring ones. The best plan is to stick to a low number of compositions - 10 or less - until you have a useful search that finishes in a reasonable time, and only then increase the number, if you want to look at compositions further down the scoring list.
• The speed of your computer. A faster computer will of course finish a search quicker than a slower computer. However, in practice sheer processing power isn't as beneficial as you might think, because it has a purely linear effect, whereas the tree search of the composing engine is exponential in running time. For example, it's pretty easy to specify a search that, on a 200MHz PC, might take 100 years. If you upgrade to a 2GHz processor you can reduce that search time to 10 years - but it still doesn't make it very practicable!
• The speed of the algorithm. Elf uses a sophisticated rotationally-sorted node-based tree search engine coupled with powerful heuristic pruning systems. It is not a toy - it is a very fast little beast indeed! For more information, see here. It is true that, because Elf is written in Java and runs in a browser, it is not as fast as an equivalent program written in a compiled language such as C++. However, it does get surprisingly close; for instance, it manages some 30-35% of the speed of SMC32, currently the world's fastest composing engine, which is written in hand-optimised assembler.

Pruning

The best way of making a search faster is to ignore parts of the search tree which don't contain good compositions. This is a technique known as "pruning". Elf gives you various composing options which you can play with to alter the pruning parameters. For example, by specifying "Maximum Changes of Method" you can force Elf to consider only those compositions in which the method changes every time. These pruning options can have a huge impact on the search time - so if your search is taking too long, try turning some of them on.

One important thing to bear in mind is that Elf employs an underlying heuristic pruning algorithm which is not affected by the composing options described above. This works by monitoring the output compositions for score, music, changes of method and method balance. As better and better compositions are found, the search is pruned to ignore any touches which do not score as well. This means that the search usually gets faster and faster as it finds the first few compositions, so it is well worth leaving a search to run for several minutes before you start to worry about the "estimated time left" figure. (However, if no results at all are being produced you probably do need to worry - it may be worth examining your search parameters to make sure the search is feasible.)

The efficiency of the heuristic pruning system can be affected by things you set - in particular, custom music definitions, and the number of compositions to keep in the "top N" list. Peversely, adding music definitions can actually have a beneficial effect on composition speed. This is because the more range there is in the music scores produced by different compositions, the more opportunity there is for Elf to prune poorly-scoring parts of the search tree.

Unfortunately, as explained above, increasing the number of compositions in the "top N" list has the opposite effect - the pruning algorithm has to make sure it can always find compositions at least as good as those at the bottom of the list, and so if you make the list bigger, the search will have to work much harder. It's always best to stick to the default 10 "top" compositions until you're sure of your search; you can always run it again with a bigger list, or, perhaps better, change your music scoring criteria to get the compositions you are looking for higher up the list.

Some Rules of Thumb

Unfortunately Elf isn't suitable for peal lengths, because there are just too many leads in the part. Remember that for every single extra lead you add to the composition, the search time increases by a factor of n², where n is the number of methods you are splicing. So for peals, it's back to pen and paper!