Bug in Microsoft's internal PriorityQueue<T>?

user_5007383 0
Viewed 6614

In the .NET Framework in PresentationCore.dll, there is a generic PriorityQueue<T> class whose code can be found here.

I wrote a short program to test the sorting, and the results weren't great:

using System;
using System.Collections.Generic;
using System.Diagnostics;
using MS.Internal;

namespace ConsoleTest {
    public static class ConsoleTest {
        public static void Main() {
            PriorityQueue<int> values = new PriorityQueue<int>(6, Comparer<int>.Default);
            Random random = new Random(88);
            for (int i = 0; i < 6; i++)
                values.Push(random.Next(0, 10000000));
            int lastValue = int.MinValue;
            int temp;
            while (values.Count != 0) {
                temp = values.Top;
                values.Pop();
                if (temp >= lastValue)
                    lastValue = temp;
                else
                    Console.WriteLine("found sorting error");
                Console.WriteLine(temp);
            }
            Console.ReadLine();
        }
    }
}

Results:

2789658
3411390
4618917
6996709
found sorting error
6381637
9367782

There is a sorting error, and if the sample size is increased, the number of sorting errors increases somewhat proportionally.

Have I done something wrong? If not, where is the bug in the code of the PriorityQueue class located exactly?

priority-queue .net c#
3 Answers

Not reproducible in .NET Framework 4.8

Trying to reproduce this issue in 2020 with the .NET Framework 4.8 implementation of the PriorityQueue<T> as linked in the question using the following XUnit test ...

public class PriorityQueueTests
{
    [Fact]
    public void PriorityQueueTest()
    {
        Random random = new Random();
        // Run 1 million tests:
        for (int i = 0; i < 1000000; i++)
        {
            // Initialize PriorityQueue with default size of 20 using default comparer.
            PriorityQueue<int> priorityQueue = new PriorityQueue<int>(20, Comparer<int>.Default);
            // Using 200 entries per priority queue ensures possible edge cases with duplicate entries...
            for (int j = 0; j < 200; j++)
            {
                // Populate queue with test data
                priorityQueue.Push(random.Next(0, 100));
            }
            int prev = -1;
            while (priorityQueue.Count > 0)
            {
                // Assert that previous element is less than or equal to current element...
                Assert.True(prev <= priorityQueue.Top);
                prev = priorityQueue.Top;
                // remove top element
                priorityQueue.Pop();
            }
        }
    }
}

... succeeds in all 1 million test cases:

enter image description here

So it seems like Microsoft fixed the bug in their implementation:

internal void Pop()
{
    Debug.Assert(_count != 0);
    if (!_isHeap)
    {
        Heapify();
    }

    if (_count > 0)
    {
        --_count;

        // discarding the root creates a gap at position 0.  We fill the
        // gap with the item x from the last position, after first sifting
        // the gap to a position where inserting x will maintain the
        // heap property.  This is done in two phases - SiftDown and SiftUp.
        //
        // The one-phase method found in many textbooks does 2 comparisons
        // per level, while this method does only 1.  The one-phase method
        // examines fewer levels than the two-phase method, but it does
        // more comparisons unless x ends up in the top 2/3 of the tree.
        // That accounts for only n^(2/3) items, and x is even more likely
        // to end up near the bottom since it came from the bottom in the
        // first place.  Overall, the two-phase method is noticeably better.

        T x = _heap[_count];        // lift item x out from the last position
        int index = SiftDown(0);    // sift the gap at the root down to the bottom
        SiftUp(index, ref x, 0);    // sift the gap up, and insert x in its rightful position
        _heap[_count] = default(T); // don't leak x
    }
}

As the link in the questions only points to most recent version of Microsoft's source code (currently .NET Framework 4.8) it's hard to say what exactly was changed in the code but most notably there's now an explicit comment not to leak memory, so we can assume the memory leak mentioned in @JimMischel's answer has been addressed as well which can be confirmed using the Visual Studio Diagnostic tools:

enter image description here

If there was a memory leak we'd see some changes here after a couple of million Pop() operations...

user_97457320
Related