Deque vs Queue Speed

Question

I was working on a problem on LeetCode (Here). When I finished the problem, I came up with:

class MovingAverage {
    std::deque<int> numsToAverage;
    int maxSize;
    int currentTotal;
public:
    /** Initialize your data structure here. */
    MovingAverage(int size) {
        maxSize = size;
        currentTotal = 0;
    }

    double next(int val) 
    {
        currentTotal += val;
        numsToAverage.push_back(val);

        if (numsToAverage.size() > maxSize)
        {
            currentTotal -= numsToAverage[0];
            numsToAverage.pop_front();
        }

        return (double)currentTotal / (double)numsToAverage.size();
    }
};

Afterwards, I saw that another solution was very similar to mine but used a queue. Out of curiosity, I swapped only the deque to a queue and I jumped from the 18th percentile (deque) to the 56th percentile (queue). Here's the queue code:

class MovingAverage {
    std::queue<int> numsToAverage;
    int maxSize;
    int currentTotal;
public:
    /** Initialize your data structure here. */
    MovingAverage(int size) {
        maxSize = size;
        currentTotal = 0;
    }

    double next(int val) 
    {
        currentTotal += val;
        numsToAverage.push(val);

        if (numsToAverage.size() > maxSize)
        {
            currentTotal -= numsToAverage.front();
            numsToAverage.pop();
        }

        return (double)currentTotal / (double)numsToAverage.size();
    }
};

My question is specifically why? I checked std::queue and it defaults to a deque! Why on earth would it be faster just because it's a queue? My only guess is that it's caching that value some where? But at the same time, a queue, by default IS a deque! The insertion/deletion time literally can't be better!

(Side note, I don't account for the case where size == 0 because the question doesn't test for it. In fact, their code violently shatters if you hand it 0)

Answer 1

Here is an educated guess:

• Memory controllers have a prefetch "handedness" that rewards consecutive, ascending memory accesses but is slower for accesses in descending order.

• Accordingly, deques used as a FIFO container have a preferred direction for pushing on one side and popping on the other.

• Likely, your deque code uses the least favored direction. But the queue implementation is already optimized to use the underlying deque in its most favored direction.

• There is an easy way to test this hypothesis (given that these are non-guaranteed implementation details). In your deque code, switch push_back --> push_front and pop_front --> pop_back. If the hypothesis is correct, the deque code should speed-up to just as fast as the queue implementation :-)