Would it be possible for regrtest to do some operations to estimate the speed and choose "good values" for the constants automatically?

If you have the right kind of VM setup, you could simulate a slow buildbot by giving the VM a low CPU share and then running something compute intensive elsewhere on the machine.  Since many of the buidbots *are* VMs, this would probably be a good test :)