Optimizations to Ring.get_more_nodes()
Optimizations to Ring.get_more_nodes()

When we're looking for handoffs, we first try to span all the regions,
then zones, then devices. However, the search loops would always go
over a big subset of the ring, regardless of whether or not there was
anything left to find.

In particular, this would result in long runtimes for the first call
to get_more_nodes() if you didn't have more regions than replicas, as
the region-search loop would chew through a ton of devices and not
find any (since there weren't any). Now we do a little arithmetic,
think about the pigeonhole principle a little bit, and bail out when
there's nothing left to find, rather than waiting until there's no
space left to search.

Similar changes were made for the different-zone and different-device
search loops.

On a 4800-device test ring (4 regions, 5 zones each, 20 node each, 12
drives each), the time to get all handoffs dropped to about 5% of its
previous value (a 95% improvement).

More usefully, on a 1200-device test ring (same as above but only 1
region), the time to get just the first 6 handoffs dropped to about
0.01% of its original runtime, or a 10,000x speedup.

Fixes bug 1225018.

Change-Id: I4c77094186f0032a3e19a099a1a0e71b2ba06719

psachin/swift,clayg/swift,wenhuizhang/swift,openstack/swift,williamthegrey/swift,hbhdytf/mac2,psachin/swift,smerritt/swift,psachin/swift,JioCloud/swift,swiftstack/swift,bradleypj823/swift,hbhdytf/mac2,citrix-openstack/build-swift,Akanoa/swift,openstack/swift,hurricanerix/swift,hurricanerix/swift,tipabu/swift,sarvesh-ranjan/swift,tipabu/swift,xiaoguoai/ec-dev-swift,anishnarang/gswift,eatbyte/Swift,matthewoliver/swift,aerwin3/swift,levythu/swift,notmyname/swift,revoer/keystone-8.0.0,maginatics/swift,shibaniahegde/OpenStak_swift,dpgoetz/swift,bouncestorage/swift,Khushbu27/Tutorial,hurricanerix/swift,hbhdytf/mac,nadeemsyed/swift,notmyname/swift,daasbank/swift,aerwin3/swift,shibaniahegde/OpenStak_swift,zackmdavis/swift,mjwtom/swift,clayg/swift,bkolli/swift,redbo/swift,daasbank/swift,mjzmjz/swift,levythu/swift,swiftstack/swift,iostackproject/IO-Bandwidth-Differentiation,bradleypj823/swift,clayg/swift,hbhdytf/mac2,psachin/swift,larsbutler/swift,maginatics/swift,dencaval/swift,sarvesh-ranjan/swift,dpgoetz/swift,smerritt/swift,tipabu/swift,smerritt/swift,gold3bear/swift,mjwtom/swift,rackerlabs/swift,Khushbu27/Tutorial,thiagodasilva/swift,openstack/swift,takeshineshiro/swift,bkolli/swift,hbhdytf/mac,nadeemsyed/swift,xiaoguoai/ec-dev-swift,AfonsoFGarcia/swift,nadeemsyed/swift,redhat-openstack/swift,matthewoliver/swift,Akanoa/swift,smerritt/swift,thiagodasilva/swift,notmyname/swift,matthewoliver/swift,citrix-openstack-build/swift,IPVL/swift-kilo,wenhuizhang/swift,Em-Pan/swift,mjzmjz/swift,bouncestorage/swift,NeCTAR-RC/swift,AfonsoFGarcia/swift,tipabu/swift,rackerlabs/swift,notmyname/swift,clayg/swift,Seagate/swift,anishnarang/gswift,citrix-openstack-build/swift,hbhdytf/mac2,takeshineshiro/swift,eatbyte/Swift,williamthegrey/swift,gold3bear/swift,NeCTAR-RC/swift,nadeemsyed/swift,dencaval/swift,swiftstack/swift,matthewoliver/swift,prashanthpai/swift,revoer/keystone-8.0.0,scality/ScalitySproxydSwift,scality/ScalitySproxydSwift,citrix-openstack/build-swift,IPVL/swift-kilo,JioCloud/swift,redbo/swift,iostackproject/IO-Bandwidth-Differentiation,openstack/swift,Seagate/swift,prashanthpai/swift,zackmdavis/swift,hurricanerix/swift,larsbutler/swift,redhat-openstack/swift,Em-Pan/swift