Dequeue Performance

[CharlesPublic]

Hello BlueRaja,

I just tried your Priority Queue and the Enqueue time is pretty good. But when i try to use Dequeue i get horrible performance results. (Dequeue is also slow when using FastPriorityQueue)

// Generating 1_000_000 Random Ints
var randomInts = WordHelper.GenerateRandomInts(
    1_000_000, int.MinValue + 5, int.MaxValue - 5);

var simpleQ = new SimplePriorityQueue<int, int>();

// Enqueue total time around 700-800 ms, pretty fine
foreach (var item in randomInts)
{
    simpleQ.Enqueue(item, item);
}

var dequeueList = new List<int>(randomInts.Length);

// The Dequeue time is so slow that its not usable, takes minutes...
while (simpleQ.Count > 0)
{
    if (simpleQ.Count % 100 == 0)
    {
        Debug.WriteLine($"items left {simpleQ.Count}");
    }

    dequeueList.Add(simpleQ.Dequeue());
}

// Helper func to generate random ints
public static int[] GenerateRandomInts
         (int numInts, int min, int maxIncl)
{

    var ret = new int[numInts];
    var rnd = new Random();

    for (int i = 0; i < numInts; i++)
    {
        ret[i] = (rnd.Next(min, maxIncl + 1));
    }

    return ret;
}

Edit: I tried the PriorityQueue from Microsoft https://github.com/dotnet/runtime/blob/main/src/libraries/System.Collections/src/System/Collections/Generic/PriorityQueue.cs

And it has good Enqueue and Dequeue performance. Maybe you can compare these to find out whats wrong.

---

Am i doing something wrong? I tried other Priority Queues i found online and the Dequeue time for 1M elements takes less than a second.

Best Regards

Charles

[BlueRaja]

Are you running in debug mode? The debug build is slow because it does a bunch of safety checks. Those checks are not done in release mode.

(Also you should do performance testing outside of VS, the attached debugger prevents the JIT from making certain optimizations)

[CharlesPublic]

I'm running in debug mode currently, but i don't think that's the problem (its taking many minutes to run, i stopped my test after 30 seconds because it only dequeued a couple of entries...)

Maybe you can try my code, i will try again tomorrow.

[BlueRaja]

It almost certainly is. Please use the version published to nuget, which is the release version compiled with the optimal compiler flags and compile-time constants.