首先,标题。如果您使用位整数来保存头和尾“指针”,并调整它们的大小使它们完全同步,则不需要使用模算术来包装缓冲区。即:将4096填充到12位无符号整数中,它本身就是0,没有任何修改。即使对于2的幂,消除模算术也会将速度提高一倍-几乎完全相同。
在我的第三代i7 Dell XPS 8500上,使用Visual Studio 2010的C ++编译器进行默认内联,填充和排空任何类型数据元素的1000万次迭代需要52秒,并且1/8192的时间用于服务一个数据。
我建议重写main()中的测试循环,使它们不再控制流程-应该由返回值指示缓冲区已满或为空以及相应的break;语句来控制。即:填充器和排水器应该能够互相碰撞而不会损坏或不稳定。希望在某个时候我能够将此代码多线程化,届时这种行为将至关重要。
QUEUE_DESC(队列描述符)和初始化函数强制此代码中的所有缓冲区为2的幂。否则,上述方案将无法正常工作。顺便提一下,注意QUEUE_DESC并非硬编码,它使用一个清单常量(#define BITS_ELE_KNT)进行构建。(我假设2的幂在这里足够灵活)
为了使缓冲区大小可以在运行时选择,我尝试了不同的方法(此处未显示),并决定使用USHRTs作为Head、Tail、EleKnt的数据类型,以管理FIFO缓冲区[USHRT]。为避免模数算术,我创建了一个掩码与Head、Tail相&,但该掩码结果为(EleKnt-1),因此只需使用该掩码即可。使用USHRTS而不是位整数可将性能提高约15%,特别是在繁忙的共享机器上,英特尔CPU核心始终比其总线更快,因此打包数据结构可以让您在其他竞争线程之前加载和执行。权衡。
请注意,缓冲区的实际存储是使用calloc()在堆上分配的,并且指针位于结构体的基础上,因此结构体和指针具有完全相同的地址。即;不需要添加偏移量以将结构体地址与寄存器绑定。
在同样的思路下,所有与缓冲服务相关的变量都与缓冲物理相邻,并绑定到同一个结构体中,因此编译器可以生成漂亮的汇编语言。如果不禁用内联优化,你将无法看到任何汇编代码,因为否则它会被压缩成虚无。
为了支持任何数据类型的多态性,我使用了memcpy()而不是赋值。如果您只需要灵活地支持每次编译一个随机变量类型,那么这段代码就完美地工作了。
对于多态性,您只需要知道类型及其存储要求。DATA_DESC描述符数组提供了一种跟踪放入QUEUE_DESC.pBuffer中的每个数据的方法,以便可以正确检索它们。我只分配足够的pBuffer内存来容纳最大数据类型的所有元素,但要跟踪给定数据使用的存储空间量,在DATA_DESC.dBytes中记录。另一种选择是重新发明堆管理器。
这意味着 QUEUE_DESC 的 UCHAR *pBuffer 将有一个相应的伴随数组用于跟踪数据类型和大小,而数据在 pBuffer 中的存储位置将保持不变。新成员将类似于 DATA_DESC *pDataDesc,或者,如果您能找到一种方法来让编译器接受这样的前向引用,可以是 DATA_DESC DataDesc [2 ^ BITS_ELE_KNT]。 在这些情况下,Calloc()始终更具灵活性。
在 Q_Put()、Q_Get() 中仍然需要使用 memcpy(),但实际复制的字节数取决于 DATA_DESC.dBytes,而不是 QUEUE_DESC.EleBytes。对于任何给定的 put 或 get 操作,元素都可能是不同类型/大小的。
我相信这段代码满足速度和缓冲区大小的要求,并且可以满足 6 种不同数据类型的要求。我留下了多个测试固件,以 printf() 语句的形式,这样您就可以自行确认代码是否正常工作。随机数生成器演示了该代码对于任意随机 head/tail 组合的有效性。
enter code here
#include "stdafx.h"
#include <stdio.h>
#include <time.h>
#include <limits.h>
#include <stdlib.h>
#include <malloc.h>
#include <memory.h>
#include <math.h>
#define UCHAR unsigned char
#define ULONG unsigned long
#define USHRT unsigned short
#define dbl double
#define QUEUE_FULL_FLAG 1
#define QUEUE_EMPTY_FLAG -1
#define QUEUE_OK 0
#define BITS_ELE_KNT 12
typedef struct {
UCHAR *pBuffer;
ULONG Tail :BITS_ELE_KNT;
ULONG Head :BITS_ELE_KNT;
ULONG EleBytes :8;
USHRT EleKnt :BITS_ELE_KNT +1;
USHRT IsFull :1;
USHRT IsEmpty :1;
USHRT Unused :1;
} QUEUE_DESC;
QUEUE_DESC *Q_Init(QUEUE_DESC *Q, int BitsForEleKnt, int DataTypeSz);
int Q_Put(QUEUE_DESC *Q, UCHAR *pNew);
int Q_Get(UCHAR *pOld, QUEUE_DESC *Q);
QUEUE_DESC *Q_Init(QUEUE_DESC *Q, int BitsForEleKnt, int DataTypeSz) {
memset((void *)Q, 0, sizeof(QUEUE_DESC));
Q->EleKnt = (USHRT)pow(2.0, BitsForEleKnt);
Q->EleBytes = DataTypeSz;
srand(unsigned(time(NULL)));
Q->Head = Q->Tail = rand();
Q->Head = Q->Tail = 0;
if(NULL == (Q->pBuffer = (UCHAR *)calloc(Q->EleKnt, Q->EleBytes))) {
return NULL;
} else {
return Q;
}
}
int Q_Put(QUEUE_DESC *Q, UCHAR *pNew)
{
memcpy(Q->pBuffer + (Q->Tail * Q->EleBytes), pNew, Q->EleBytes);
if(Q->Tail == (Q->Head + Q->EleKnt)) {
Q->Tail += 1;
return QUEUE_FULL_FLAG;
}
Q->Tail += 1;
return QUEUE_OK;
}
int Q_Get(UCHAR *pOld, QUEUE_DESC *Q)
{
memcpy(pOld, Q->pBuffer + (Q->Head * Q->EleBytes), Q->EleBytes);
Q->Head += 1;
if(Q->Head == Q->Tail) {
return QUEUE_EMPTY_FLAG;
}
return QUEUE_OK;
}
int _tmain(int argc, _TCHAR* argv[]) {
int LoopKnt = 1000000;
int k, i=0, Qview=0;
time_t start;
QUEUE_DESC Queue, *Q;
if(NULL == (Q = Q_Init(&Queue, BITS_ELE_KNT, sizeof(int)))) {
printf("\nProgram failed to initialize. Aborting.\n\n");
return 0;
}
start = clock();
for(k=0; k<LoopKnt; k++) {
for(i=1; i<= Q->EleKnt; i++) {
Qview = i*i;
if(QUEUE_FULL_FLAG == Q_Put(Q, (UCHAR *)&Qview)) {
break;
}
}
Qview = 0;
for(i=1; i; i++) {
if(QUEUE_EMPTY_FLAG == Q_Get((UCHAR *)&Qview, Q)) {
break;
}
}
}
printf("\nQueue time was %5.3f to fill & drain %i element queue %i times \n",
(dbl)(clock()-start)/(dbl)CLOCKS_PER_SEC,Q->EleKnt, LoopKnt);
printf("\nQueue head value is %i, tail is %i\n", Q->Head, Q->Tail);
getchar();
return 0;
}