That's a point I'll have to think about. Unfortunately, if we already knew we were going to backtrack before we transformed the array, we wouldn't need to transform the array. Furthermore, we don't save anything by not detecting that the very next row is completely threatened.

What we could do is insert code into the transform functor to determine whether there are any dominated rows already, starting two rows down, and if so stop copying. I'm doubtful this will improve performance, for two reasons: the vast majority of the time, there won't be any dominated rows that far below us, and this would probably inhibit the compiler from generating SIMD instructions for the loop. As an alternative, we could finish the loop and then scan for dominated rows over the horizon, but that would make the rest of the program do more work.
Thank you. That's actually the basis for my refactoring.

Thought I'd give an update. I think the secret of your success, FrenchFrog, is that you did a much better job of writing loops the compiler can unroll. I've designed a new algorithm (or, at least, one I haven't heard of before) that I expect should improve performance considerably, but I've had limited time to implement it, and I don't want to make any guarantees until I've tested that it works.

Please post your idea even if it's not faster It's constructive to see what people can come up with.

Thanks. The reason I haven't been able to is that the program is very long and not finished. I did an almost-complete rewrite of the main procedure, and now that I'm sure its basic structure is correct, I'm trying to implement a different algorithm. Here are the benchmarks from the last version that ran correctly: That version uses a slower algorithm than the one I'm attempting to implement. This is still slower than your version for N < 18, but it's made up most of the difference, and I suspect that it catches up for higher values of N. Unfortunately, it's impractical for me to test N higher than 17 without running the program overnight.