make random acquire queues work less random

Queues feeding workers like rred are created in a random pattern to get
a few of them to run in parallel – but if we already have an idling queue
we don't need to assign it to a (potentially new) random queue as that
saves us the (agruably small) overhead of starting up a new queue,
avoids adding jobs to an already busy queue while others idle and as
a bonus reduces the size of debug logs a bit.

We also keep starting new queues now until we reach our limit before
we assign work at random to them, which should give us a more effective
utilisation overall compared to potentially adding work to busy queues
while we haven't reached our queue limit yet.

1 files changed, 22 insertions, 8 deletions

diff --git a/apt-pkg/acquire.cc b/apt-pkg/acquire.cc
index 757fab057..c65aef329 100644
--- a/apt-pkg/acquire.cc
+++ b/apt-pkg/acquire.cc
@@ -352,23 +352,37 @@ string pkgAcquire::QueueName(string Uri,MethodConfig const *&Config)
       return U.Access;
 
    string AccessSchema = U.Access + ':';
-	string FullQueueName;
+   string FullQueueName;
 
    if (U.Host.empty())
    {
-      long randomQueue = random();
+      long existing = 0;
+      // check how many queues exist already and reuse empty ones
+      for (Queue const *I = Queues; I != 0; I = I->Next)
+	 if (I->Name.compare(0, AccessSchema.length(), AccessSchema) == 0)
+	 {
+	    if (I->Items == nullptr)
+	       return I->Name;
+	    ++existing;
+	 }
+
 #ifdef _SC_NPROCESSORS_ONLN
       long cpuCount = sysconf(_SC_NPROCESSORS_ONLN) * 2;
 #else
-      long cpuCount = _config->FindI("Acquire::QueueHost::Limit",10);
+      long cpuCount = 10;
 #endif
-      if (cpuCount > 0)
-         randomQueue %= cpuCount;
+      cpuCount = _config->FindI("Acquire::QueueHost::Limit", cpuCount);
 
-      strprintf(FullQueueName, "%s%ld", AccessSchema.c_str(), randomQueue);
-      if (Debug) {
-         clog << "Chose random queue " << FullQueueName << " for " << Uri << endl;
+      if (cpuCount <= 0 || existing < cpuCount)
+	 strprintf(FullQueueName, "%s%ld", AccessSchema.c_str(), existing);
+      else
+      {
+	 long const randomQueue = random() % cpuCount;
+	 strprintf(FullQueueName, "%s%ld", AccessSchema.c_str(), randomQueue);
       }
+
+      if (Debug)
+         clog << "Chose random queue " << FullQueueName << " for " << Uri << endl;
    } else
    {
       FullQueueName = AccessSchema + U.Host;