Search mechanism for a queue system6032207Abstract A search mechanism improves the performance of a queue system including a queue for storing a plurality of data items and search mechanism by maintaining a key cache data structure having an array of entries, each of which have a key field and a pointer field. The key and pointer fields respectively of each cache entry are used for storing a key value of a different one of the enqueued data items of the queue and a pointer to that enqueued item. The key of each data item to be enqueued is used to generate an index value for accessing a location of the key cache array to obtain immediate access to the corresponding enqueued data item thereby reducing the search time for determining the proper point within the queue for inserting the data item to be added. Claims I claim: Description BACKGROUND OF THE INVENTION
______________________________________
set Ptr, a pointer, equal to the value of Head
set Searching to TRUE
while Searching is TRUE
if Ptr.Time is greater than T
insert NewItem before Ptr
set Searching to FALSE
otherwise set Ptr to Ptr.Next
______________________________________
wherein "insert" means to perform all of the required operations to put the NewItem into the queue. The search mechanism of the present invention reduces the number of times required to execute the while loop by also maintaining the key cache structure 22-40 of FIG. 2 as described herein. In addition to the key cache structure 22-40, FIG. 2 shows in greater detail, the organization of the queue 22-1. As indicated, queue 22-1 includes head and tail pointers within a queue header structure and a number of enqueued items. Each item has a next and previous pointer fields (forward and backward linked pointers), a key field and a number of data fields. In FIG. 2, four enqueued items of the queue 22-1 are shown with their respective next and previous pointer fields being set to values such that the fifth key cache entry points to the third enqueued item of queue 22-1. In the preferred embodiment, the queue 22-1 is structured so that the queue always contains a First item and a Last item which have respectively, a key value smaller than any to be used by the application and a key value larger than any to be used by the application. This simplifies the insertion and deletion mechanisms, since they then do not need to check for insertion into an empty queue, the head of the queue or the tail of the queue, nor for deletion from such sites. DESCRIPTION OF OPERATION With reference to FIGS. 1 through 5b, the operation of the queue search mechanism 22-2 constructed according to the present invention will now be described in conjunction with the flow charts of FIGS. 6a through 6e. FIG. 3a First, the queue system 22 is initialized by system 10 of FIG. 1. More specifically, key cache structure 22-40 is an array containing n number of entries, each having a key field and a pointer field. After being initialized, the key field of each entry contains a different key value derived as discussed above while the pointer field contains a "0" value as indicated. The head and tail pointers of queue 22-1 also contain "0" values as shown. FIG. 3b illustrates the state of the queue system 22 after the first data item (NewItem) has been enqueued properly. Since this is the first data item, its next and previous pointers are both set to "0" as indicated. The control mechanism 22-20 computes the cache index value from the key value. In the case of the time event simulator application, this is done by performing the operation of T % N wherein % denotes a remainder operation as discussed herein. The result "x" defines the entry location within the key cache structure 22-40 into which the new item is to be inserted as indicated in FIG. 3b. In an application in which the behavior of a microprocessor is being simulated through the means of a discrete event simulation, the key value may be some multiple of the base clock interval of the simulated processor. In an example where the clock interval is 10 nanoseconds and the execution of the 10,000th instruction is being simulated, the key value might plausibly have a value such as 20,000. In that case, if the key cache contained 24 entries the index would be 20,000% 24, or 8 wherein the symbol "%" designates the remainder obtained by dividing 20,000 by 24 which results in the remainder of 8. FIGS. 4a and 4b FIG. 4a illustrates the state of the queue system 22 during normal operation wherein all of the queue and cache key structure locations have been filled with entries as indicated. In FIG. 4a, it is assumed that the fifth key cache item points to the second enqueued item in queue 22-1. Item Insertion The steps for performing an insertion operation by the search mechanism 22-2 are illustrated in the flow chart of FIG. 6a. From FIG. 6a, it is seen that first, the control mechanism 22-20 reads the key from the data item to be inserted (i.e., block 600). Next, the control mechanism 22-20 computes a key cache index value from the key value contained in the data item to be enqueued (i.e., block 602). As indicated, there are then four cases to consider: The first case is when the key cache entry is not valid (shown by the Pointer field of the entry being zero). In this case, the mechanism sets the queue pointer Ptr to the first real entry in the queue, the item following First. The second case is when the key cache entry is valid, and the key value in the item being inserted is greater than the key value in the key cache entry. In this case, the mechanism searches the queue in a forward direction starting at the item indicated by the pointer field of the key cache entry using the queue next item pointer values to find the appropriate point for insertion. The third case is when the key cache entry is valid and the key value in the item being inserted is less than the key value in the key cache entry. In this case, the mechanism searches the queue in a backward direction starting at the item indicated by the pointer field of the key cache entry using the queue next item pointer values to find the appropriate point for insertion The fourth case is when the key cache entry is valid and the key value in the item is the same as the key value in the key cache entry. In this case, the pointer field of the key cache entry indicates the correct entry point. It will be assumed by way of example that the key value of the data item being added is greater causing control mechanism 22-20 to perform the QBwd backward procedure operation of block 610 (i.e., a procedure to search a queue backwards from the item indicated by PTR until an entry whose key field is less than or equal to the supplied key is found and which returns a pointer to that item). As indicated, this operation is illustrated in greater detail in FIG. 6b. First, the control mechanism procedure sets its pointer Here to the value contained in the pointer Ptr passed to it which corresponds to the previous item pointer value of the key cache designated enqueued item (i.e. block 610-4). The key field contents of the queue entry pointed to by its pointer Here are then compared with the key value (Key) of the item to be inserted (NewItem) as indicated in block 610-6. If the key value of the designated enqueued item entry is equal or less than the NewItem key value, control mechanism 22-20 sets the search mechanism Ptr to equal the contents of its Here pointer representing the location of the previous data item (block 610-8). If the key value of the enqueued item entry is greater than the NewItem key value, control mechanism 22-20 performs the operation of block 610-10. That is, control mechanism 22-20 sets the search mechanism pointer Ptr equal to the contents of the Previous pointer field of that queue item to evaluate the next enqueued item (block 610-12). Control mechanism 22-20 continues to execute the operations of blocks 610-6 and 610-10 until it finds a queue item entry whose key field is less than or equal to the supplied item to be enqueued. When such a queue item is found, control mechanism 22-20 then returns a pointer value designating the location of that enqueued item. Since control mechanism 22-20 carries out a forward search in the same manner as a backward search, using the next pointer values of the enqueued items, no further description of a forward search is deemed necessary. As indicated in FIG. 6a, the control mechanism 22-20 uses the returned pointer value to insert the NewItem into queue 22-1 as indicated in block 612. That is, the control mechanism 22-20 inserts the NewItem in the queue location designated by the returned pointer value which results in the pointer values of the enqueued items being set as indicated in FIG. 4b. When the queue pointer Ptr points to an item in the body of the queue (i.e., does not indicate the first or last item in the queue), control mechanism 22-20 performs the operations of block 612-2 in the flow chart of FIG. 6c that depicts a procedure to insert an item into a queue at the point indicated by PTR. Note the queues in the preferred implementation always have a first entry and a last entry which may not be removed so the insertion procedure always inserts in the `middle` of queue. That is, it sets the next pointer value of the NewItem to the value of the queue pointer, sets the next pointer value of the NewItem to the value of the previous pointer of the designated enqueued item, sets the previous pointer of the previous item pointed to by the queue pointer to point at the NewItem and sets the previous pointer of the previous item to point at the NewItem. Next, control mechanism 22-20 updates the entry in key cache structure 22-40 in the manner indicated in block 614-2 of the flow chart of FIG. 6d to reflect the insertion of this item and its key value. That is, it sets the pointer field of the entry to point to the new item and sets the time field (key field) to be equal to the time of the new item (NewItem). Item Removal FIGS. 5a and 5b are used to describe the operations to remove the first useful item in the queue performed by the procedure getItem illustrated in the flow chart of FIG. 6e (recall that the actual first and last items are not to be removed). As indicated in FIG. 5a, it is assumed that the fifth key cache item points to the item being removed. The choice of item in the keycache is defined by the computation of the cache key index from the key value of the item being removed. This first useful item is the second item in the queue. The procedure uses two pointer values called `first` and `item` to remove the item from the queue. As indicated in block 620, the procedure sets its "first" pointer equal to Head.Next (i.e., the contents of the next field of the data item pointed to by the queue head pointer, indicating the actual first item). It also sets its "item" pointer equal to first.Next (indicating the second item in the queue 22-1, the item to be removed). Next, the procedure removes the item from the queue by performing the operations of setting the first.Next pointer equal to item.Next and the item.Next.Previous equal to first (block 621). This operation (step) removes all mention (identification) of the item to be removed from the queue. Next, the procedure computes the key cache index from the key of the data item to be removed and then points the entry at the Index'th entry in the key cache (blocks 622 and 624). The procedure then compares the pointer Ptr to the Entry.Pointer for determining if the pointer is the same (block 626). If it is the same, the pointer field of the entry is set to a NULL or "0" value invalidating the entry (block 628). If the pointer Ptr is different, then the procedure is done. The queuing mechanism may also be used to remove a specific item known to be in the queue. To remove a particular item the procedure getSpecificItem also illustrated in the flow chart of FIG. 6e may be used. It is provided with the address of the item to be removed. As indicated in block 620a, the procedure sets its "first" pointer equal to Item.Previous (i.e., the contents of the previous field of the item to be removed indicating the item preceding the item to be removed). It also sets its "item" pointer equal to Item (the item to be removed). Next, the procedure removes the item from the queue by performing the operations of setting the first.Next pointer equal to item.Next and the item.Next.Previous equal to first (block 621). This operation (step) removes all mention (identification) of the item to be removed from the queue. The sequence of operations of the remaining blocks of FIG. 6e would be performed in the same manner as described above. To remove the first item whose key was smaller than some value, one would, in principle, first search the queue from the front to identify that item, and then remove it. The removal can be done with getSpecificItem(), just described. The searching could be done using a version of insertItem(), modified only to call getSpecifiItem() instead of insertinQ() and to never call updateCache(). From the above, it is seen how the search mechanism of the present invention can be used to reduce search time from a time dependent on the number of entries in a queue to a time which is essentially constant. This reduction in search time is a function of the distribution of times for new items and size of the key cache. The following results have been found by using the queue mechanism as an ordered event queue wherein each event when serviced creates another event at some time in the future and the time is chosen from a uniform distribution. The results shown below are for a queue using 512 events whose "next" time is set to be the current time plus a value chosen randomly from the range 0 to 63 ticks in the future. An uncached run: Experiment::NumEvents=512, dt=U[0 . . . 63], CacheSize=0 Service 512 events. 40269 events in 11.12 secs=3622.40 eps; av search distance=334.77 80928 events in 22.33 secs=3623.64 eps; av search distance=334.27 121364 events in 33.52 secs=3621.00 eps; av search distance=334.36 162027 events in 44.77 secs=3619.37 eps; av search distance=334.43 A cached run: Experiment::NumEvents=512, dt=U[0 . . . 63], CacheSize=8 Service 512 events. 40269 events in 5.98 secs=6725.18 eps; av search distance=165.47 Hits=5045 [12.54] Slops=17601 [43.74] Misses=17593 [43.72] 80928 events in 12.15 secs=6654.49 eps; av search distance=166.14 Hits=10020 [12.39] Slops=35411 [43.80] Misses=35421 [43.81] 121364 events in 18.22 secs=6660.00 eps; av search distance=165.92 Hits=15005 [12.37] Slops=52955 [43.65] Misses=53363 [43.98] 162027 events in 24.33 secs=6657.82 eps; av search distance=165.79 Hits=20114 [12.42] Slops=70793 [43.70] Misses=[43.89] wherein slops are hits which result in a search. The above results illustrate that a very small cache (8 entries) halves the search distance (from 334 to 166) and also improves the actual event servicing rate from about 3600 eps to about 6600 eps. An executable description of the queuing system embodying the present invention is provided in the enclosed Appendix. APPENDIX It can be simpler to understand how an implementation of the mechanism might work if the description is given in a language more suited to such descriptions than English. The programming language `C` is such a language and to aid comprehension a description of the behavior of a possible implementation of the mechanism is given in C as a collection of C procedures hereafter. The version of the mechanism described employs the preferred queuing model in which the first and last items in the queue are unremovable and unchangeable. To further increase the utility of this description, two further procedures (uniform() and main()) are included so that the complete description may be compiled and executed given an appropriate C compiler and computer system on which to execute the compiled description. The use of C language structures to represent items and queues and the use of C procedures to describe the sequences of desired operations will be familiar to those skilled in the art and familiar with modern software practices.
______________________________________
/*
cqueues.c
*/
#include <stdlib.h>
#include <stdio.h>
typedef long int32;
// definition of an Item
typedef struct item{
struct item * Next;
// pointer to next item in queue
struct item * Previous;
// pointer to previous item in queue
int32 Key; // this item's key value
} Item;
// definition of a KeyCache entry
typedef struct {
int32 hits;
Item * Pointer;
int32 Key;
} kCacheEntry;
// definition of a KeyCache
#define cacheSize (23)
kCacheEntry KeyCache[cacheSize];
#define minKey (-1L)
#define maxKey (0x7fffffffL)
// definition of a Queue
typedef struct {
Item * Head;
Item * Tail;
Item First;
Item Last;
} Queue;
static void initCache(void);
static void printCache(void);
static void insertItem(Queue * q, Item *item);
static void insertinQ(Item * Ptr, Item * item);
static Item * searchQFwd(Item * Ptr, int32 Key);
static Item * searchQBwd(Item * Ptr, int32 Key);
static void updateCache(Item * item, int32 Index);
static Item * getItem(Queue * theQ);
static int32 uniform(int32 base, int32 limit);
/* ----------------------- initCache -------------------------- */
static void initCache(void) {
int32 i;
for (i = 0; i < cacheSize; i++) }
KeyCache[i].Key = minKey;
// set to arbitrary value
KeyCache[i].Pointer = NULL;
// set to invalid value
KeyCache[i].hits = 0;
// set to 0
}
/* ----------------------- printCache -------------------------- */
static void printCache(void) {
int32 i;
printf("\nCache contents:\n");
for (i = 0; i < cacheSize; i++) {
printf("\t%3ld::Key=%6ld, ptr = 0x%08lx, hits = %ld\n",
i, KeyCache[i].Key, KeyCache[i].Pointer,
KeyCache[i].hits);
}
}
/* ----------------------- initQ -------------------------- */
static void initQ(Queue * q) {
/* initialise the indicated queue so that q -> First is first
item, q -> Last is last item */
q -> Head = &(q -> First);
q -> Tail = &(q -> Last);
q -> First.Key = minKey;
q -> Last.Key = maxKey;
q -> First.Previous = NULL;
q -> First.Next = q -> Tail;
q -> Last.Previous = q -> Head;
q -> Last.Next = NULL;
}
/* ----------------------- computeIndex -------------------------- */
static int32 computeIndex(int32 Key) {
int32 index;
index = Key % cacheSize;
if (index < 0) index = -index;
return index;
}
/* ----------------------- insertItem -------------------------- */
void insertItem(Queue * q, Item * item) {
Item * Ptr;
int32 Index, miss;
int32 Key, cachedKey;
Key = item -> Key;
Index = computeIndex(Key);
cachedKey = KeyCache[Index].Key;
Ptr = KeyCache[Index].Pointer;
miss = TRUE;
// first check to see if entry is valid
if (Ptr == NULL) {
// invalid entry; need to search from start
Ptr = q -> Head -> Next;
Ptr = searchQFwd(Ptr, Key);
}
else {
// yes, valid; now decide what to do. .
if (Key > cachedKey) {
/* a miss; search the queue forwards until insertion point
is found */
Ptr = searchQFwd(Ptr, Key);
}
else if (Key < cachedKey) {
/* a miss; search the queue backwards until insertion point
is found */
Ptr = searchQBwd(Ptr, Key);
}
else {
miss = FALSE;
KeyCache[Index].hits++;
}
}
// now insert item in queue
insertinQ(Ptr, item);
if (miss) updateCache(item, Index);
}
/* ----------------------- searchQBwd -------------------------- */
static void updateCache(Item * item, int32 Index) {
// updates the keyCache entry Index to indicate item
kCacheEntry * Entry;
Entry = &(KeyCache[Index]);
// point at Index'th entry
Entry -> Key = item -> Key;
// update its key
Entry -> Pointer = item;
// update its pointer
Entry -> hits = 0;
}
/* ----------------------- insertinQ -------------------------- */
static void insertinQ(Item * Ptr, Item * item) {
// insert item in queue in front of item indicated by Ptr
item -> Previous = Ptr -> Previous;
/* item's previous is
Ptr's previous */
item -> Next = Ptr; // item's next is Ptr
Ptr -> Previous -> Next = item;
/* what used to point
at Ptr now indicates item */
Ptr -> Previous = item;
/* and Ptr's previous
is item */
}
/* ----------------------- searchQFwd -------------------------- */
static Item * searchQFwd(Item * Ptr, int32 Key) {
/* searches the queue containing the item indicated by Ptr
forwards (via the Next fields) */
// to find correct place to insert an item with key value Key
/* there is no need to check for end conditions because the
queue always contains an entry */
// with key value maxKey
Item * Here;
Here = Ptr;
while (Ptr -> Key < Key) {
Here = Ptr;
Ptr = Ptr -> Next;
}
return Here; // return the last item which had a smaller key
}
/* ----------------------- searchQBwd -------------------------- */
static Item * searchQBwd(Item * Ptr, int32 Key) {
/* searches the queue containing the item indicated by Ptr
backwards (via the Previous fields) */
// to find correct place to insert an item with key value Key
/* there is no need to check for start conditions because the
queue always contains an entry */
// with key value minKey
Item * Here;
Here = Ptr;
while (Ptr -> Key > Key) {
Here = Ptr;
Ptr = Ptr -> Previous;
}
return Here;
// return the last item which had a larger key
}
/* ----------------------- getItem -------------------------- */
static Item * getItem(Queue * theQ) {
// removes first real item from theQ
Item * item, * first;
int32 Index;
first = theQ -> Head;
item = first -> Next;
// heal up the queue
first -> Next = item -> Next;
item -> Next -> Previous = first;
// fix up cache
Index = computeIndex(item -> Key);
if (KeyCache[Index].Pointer == item) {
// we're in the cache; invalidate the entry
KeyCache[Index].Pointer = NULL;
KeyCache[Index].Key = -1;
KeyCache[Index].hits = 0;
}
return item;
}
/* ----------------------- uniform -------------------------- */
static int32 uniform(int32 base, int32 limit) {
/* returns a uniformly distributed rv in base. .limit
the smallest number returned is base
the largest number returned is base + limit - 1
base, limit MUST both be >= 0
limit MUST be > base
these are NOT checked
*/
#define rvM ((1L << 31) - 1L)
#define rvd (16807L)
#define rvquotient (rvM/rvd)
#define rvremainder (rvM%rvd)
static int32 seed = 1;
int32 result;
result = seed;
result = (rvd * (result % rvquotient)) -
(rvremainder * (result / rvquotient));
if (result <= 0) {
result += rvM;
}
seed = result;
/* got a uniform rv in 0. .2**31, convert to uniform rv in
base. .limit */
result = result % (limit - base);
if (result < 0) result = - result;
return (base + result);
}
/* ----------------------- main -------------------------- */
void main(void) {
Queue * theQ;
int32 numItems, theTime, i;
printf("\nCached Queues Method\n\tstarting. .\n";
// create an empty queue
theQ = malloc(sizeof(Queue));
initQ(theQ);
// initialise the keyCache
initCache ();
printf("\tqueue and cache initialised.\n");
// insert 1000 items on the queue with keys all equal to 100
theTime = 100;
for (numItems = 0; numItems < 1000; numItems++) {
Item * item;
item = malloc(sizeof(Item));
item -> Key = theTime;
insertItem(theQ, item);
}
printf("\t%ld items placed on queue; starting run\n", numItems);
// take items from the front an re-queue some amount later
for (i = 0; i < 100000; i++) {
Item * item;
int32 dt;
item = getItem(theQ);
theTime = item -> Key;
dt = 10 * (uniform(1, 10));
/* increment time in amounts
of 10 between 10 and 100 */
item -> Key = theTime + dt;
insertItem(theQ, item);
if (i < 10) printCache();
if (i % 10000 == 0) printCache();
}
printCache ();
printf("\tDone; completed %ld removals and insertions\n", i);
}
______________________________________
From the above, it is seen how the search mechanism of the present invention improves system performance. It will be appreciated that many changes may be made to the preferred embodiment of the present invention without departing from its teachings. For example, the present invention may be used in different types of data processing systems, such as multiprocessing systems with the addition of appropriate locking mechanisms. The present invention may also be used with other data item formats, etc. While in accordance with the provisions and statutes there has been illustrated and described the best form of the invention, certain changes may be made without departing from the spirit of the invention as set forth in the appended claims and that in some cases, certain features of the invention may be used to advantage without a corresponding use of other features.
|
Same subclass Same class Consider this |
||||||||||