欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

手写单向队列性能秒杀std::queue

程序员文章站 2022-03-14 15:05:15
...

std::queue即单向队列,是一种先入先出的FIFO队列。具有以下特点:

  • 只允许从队尾插入元素,从队头删除元素
  • 先进先出(First In First Out)
  • 不允许在中间部位进行操作

一共6个函数front()、back()、push()、pop()、empty()、size(),自己手写实现,也是比较简单的。

接下来, 我们就手写实现一个定制的queue队列,然后将其与std::queue性能进行对比。

一、IORequestQueue队列类实现

IORequestQueue.h

#ifndef IOREQUESTQUEUE_H
#define IOREQUESTQUEUE_H

#include <assert.h>

struct IORequest
{
    IORequest* p;
    int data;
    int ioType;
    unsigned int requestIndex;
};

class IORequestQueue
{
public:
    IORequestQueue()
        : pHead(nullptr),
          pTail(nullptr),
          count(0)
    {}

    // 队列是否为空
    bool empty() const
    {
        return (pHead == nullptr);
    }

    // 返回队列中元素个数
    size_t size() const
    {
        return count;
    }

    // 返回队头元素
    IORequest* front()
    {
        assert(!empty());
        return pHead;
    }

    // 返回队尾元素
    IORequest* back()
    {
        assert(!empty());
        return pTail;
    }

    // 将变量request从队列尾入队
    void push(IORequest* request)
    {
        request->p = nullptr;
        if (pHead == nullptr)
        {
            assert(pTail == nullptr);
            pHead = request;
        }
        else
        {
            assert(pTail != nullptr);
            pTail->p = request;
        }
        pTail = request;
        count++;
    }

    // 将队头元素弹出
    void pop()
    {
        assert(!empty());
        pHead = pHead->p;
        if (pHead == nullptr)
        {
            pTail = nullptr;
        }
        count--;
    }

private:
    IORequest* pHead;
    IORequest* pTail;
    size_t count;
};

#endif // IOREQUESTQUEUE_H

struct IORequest结构体是需要加入到队列中的元素类型,其中IORequest* p为指向下一个元素的指针,其余均为测试成员变量。

IORequestQueue类是队列实现,分别参考std::queue实现了6个函数,基本原理是记录首尾元素的地址,其间各元素之间依靠IORequest* p进行连接。

二、IORequestQueue与std::queue性能对比

对IORequestQueue与std::queue进行测试,main.cpp如下:

#include <QCoreApplication>
#include <queue>
#include <QDebug>
#include "IORequestQueue.h"
#include "CTimer.h"

void testStdQueue(std::vector<IORequest>& requests)
{
    /***********************测试入队*************************/
    CTimer timer;
    timer.reset();
    std::queue<IORequest*> stdQueue;
    for (unsigned int i = 0; i < requests.size(); i++) // 将IO请求添加到std::queue队列中
    {
        stdQueue.push(&requests[i]);
    }
    double elapsed = timer.end();
    qDebug() << "std::queue push:" << elapsed << "us";

    /***********************测试出队*************************/
    timer.reset();
    for (unsigned int i = 0; i < requests.size(); i++) // 从std::queue出队列
    {
        IORequest* req = stdQueue.front(); // 返回队头元素
        stdQueue.pop(); // 将队头元素弹出
    }
    elapsed = timer.end();
    qDebug() << "std::queue pop:" << elapsed << "us";
}

void testIOQueue(std::vector<IORequest>& requests)
{
    /***********************测试入队*************************/
    CTimer timer;
    timer.reset();
    IORequestQueue ioQueue;
    for (unsigned int i = 0; i < requests.size(); i++) // 将IO请求添加到IORequestQueue队列中
    {
        ioQueue.push(&requests[i]);
    }
    double elapsed = timer.end();
    qDebug() << "IORequestQueue push:" << elapsed << "us";

    /***********************测试出队*************************/
    timer.reset();
    for (unsigned int i = 0; i < requests.size(); i++) // 从IORequestQueue出队列
    {
        IORequest* req = ioQueue.front(); // 返回队头元素
        ioQueue.pop(); // 将队头元素弹出
    }
    elapsed = timer.end();
    qDebug() << "IORequestQueue pop:" << elapsed << "us";
}

int main(int argc, char *argv[])
{
    QCoreApplication a(argc, argv);

    // 准备测试元素10000个
    std::vector<IORequest> requests;
    for (unsigned int index = 0; index < 10000; index++)
    {
        IORequest req;
        req.data = 0;
        req.ioType = 0;
        req.requestIndex = index;
        requests.push_back(req);
    }

    testStdQueue(requests); // 测试std::queue
    testIOQueue(requests);  // 测试IORequestQueue

    return a.exec();
}

程序中分别对10000个元素,使用std::queue进行入队和出队,使用IORequestQueue进行入队和出队,并记录每个步骤消耗的时间。

运行结果:

手写单向队列性能秒杀std::queue

可以看到同样入队10000个元素时:

  • std::queue消耗173062 us
  • IORequestQueue消耗499.2 us

IORequestQueue性能比std::queue提升99.7%

同样出队10000个元素时:

  • std::queue消耗2338 us
  • IORequestQueue消耗274.9 us

IORequestQueue性能比std::queue提升88.2%

然而,这还只是MSVC编译器,debug版本下的测试结果,release下提升更多。

三、总结

std::queue由于使用模板,适用于各种类型,另外其底下使用deque(double-ended queue,双端队列)实现,可能在性能上,有一些下降。

在性能和类型通用性上有一些兼顾,故而导致性能不及为某一特定类型元素定制的queue,也可以理解。

建议:

  • 在频繁入队、出队的场合下,尽量使用自己手写实现的queue,这样性能损失较少,并在业务代码中,尽量复用元素对象,避免频繁申请和释放内存。可参考IORequestQueue实现,比较简单。

  • 在非频繁入队、出队的场合下,使用std::queue,适用于各种类型,代码实现更方便。

本文涉及工程代码:

https://gitee.com/bailiyang/cdemo/tree/master/C++/20Queue/Queue


===================================================

===================================================

业余时间不定期更新一些想法、思考文章,欢迎关注,共同探讨,沉淀技术!

手写单向队列性能秒杀std::queue手写单向队列性能秒杀std::queue            手写单向队列性能秒杀std::queue手写单向队列性能秒杀std::queue