The first-in, first-out stack (or queue) is one of several fundamental data structures. The concept came to hand very early, because like the LIFO stack and similar structures it is just so darned useful.
Useful, that is, for certain classes of problems. We rely on queues constantly in computing, though most programmers never deal with them directly. Most of the services enabled by using queues are embedded in operating systems and other system software today.
This article introduces a very short Visual Basic program that demonstrates how the Collection object can be used as one way to implement a queue.
I was developing a data communication service in Visual Basic, a message-switching service (MSS). My MSS needed to accept many client connections and “concentrate” their requests over a small number of remote server connections and then return the corresponding responses to the proper clients. The remote server was limited to accepting a request and then replying to it before accepting the next request. With even three remote server connections then, at most my MSS could have three client requests outstanding with the remote server.
The clients were many more than three at once. They were also allowed to send new requests before their prior response was received. The MSS required somewhere to hold pending client request messages in cases where all remote server connections were busy. But where?
The answer? Client request queues. But what would be most appropriate, or even a good enough way to implement queues?
I searched around and didn’t find much on the topic of VB FIFO queues. I did dredge up one interesting article at Microsoft’s MSDN site after I came up with the notion described here. The URL seems unstable, but you might find it at MSDN by searching on “VB FIFO” or “VB queue.” It goes into more depth than I do here, and discusses more advanced data structures such as priority queues as well. I only wish the author had included performance information.
My “messages” consisted of variable-length byte-streams. These could be handled either as VB strings or dynamic byte arrays. The most obvious choice was an array of strings or an array of dynamic byte arrays (not the same as a 2-dimensional byte array). Then maintain next and last indices, and use modulus arithmetic to handle wraparound. This works fine if you have a reasonable, known maximum queue depth – but I didn’t.
A dynamic array of dynamic byte arrays would be another possibility. Or just a fully dynamic 2-dimensional byte array.
I considered MSMQ briefly. Though that mechanism offers protected queues, which can live through a system reboot - it seemed like overkill for my purpose. It was also intended more for process-to-process communication and I only needed an internal queue. I decided to forego the overhead in this case.
Then I remembered the VB Collection object. I built a demo program in VB to look at its behavior for this purpose and do some speed and memory consumption profiling. As it turns out I liked what I found.
The Visual Basic online Help documentation provided through the MSDN Library does a pretty good job of describing the VB Collection object. It is careful to make a distinction between the VB Collection object and other collections available to the VB programmer (the Forms collection, et al.), which have somewhat different behavior.
The Collection object has three methods:
It also has one property: Count.
Items stored in a Collection are Variants, permitting a wide array of things to be stuffed into them including objects of many kinds. Items stored in a VB Collection can be addressed by key (a string valued “tag” which can be stored with each item), or by index (an item’s position within the Collection). A Collection may also be traversed using the For Each… Next mechanism.
Using a Collection as a simple queue requires only part of this functionality.
To use a VB Collection object as a queue I needed only a few operations: insert item into queue, remove item from queue, check queue depth. The code samples shown below assume I have created a queue Collection by declaring:
Where sItem is a String (or Variant containing a String value) holding the message I wish to add at the end of the queue.
Here I first extract the value of the “top” item from the front of the queue using its index of 1. VB Collection objects are based at 1 rather than 0 like many other types of collections in VB. The Item method requires a parameter.
Next I use the Remove method to delete the item from the Collection. Remove also requires a parameter.
The Item and Remove methods are interesting in that they perform different actions depending on the type of the index parameter. If a numeric expression is supplied these methods treat it as the item index. If a string expression is supplied it is treated as the item’s key value, and the collection will be searched for the desired item. We only need the numeric-parameter behavior here.
The Count property returns the number of items in the queue (Collection).
When using the VB Collection object to implement a queue in this manner you should normally wrap it as a class. This isolates its implementation details from the rest of your program and should result in a program with fewer bugs that is easier to read and understand.
I purposely did not do this in my VBQueue sample program to avoid swaying your decisions about what properties and methods to provide in your own queue classes.
The sample source can be downloaded as vbq.zip.
When I started considering my “queue options” in VB I created a series of small test bed programs. This is the one I’ve been using most to evaluate VB Collection objects as queues:
Operation is simple. Once you start the program the “Empty the Queue” button is hidden. You press the “Go” button, which runs a series of loops that insert and delete strings into and from the queue (Collection).
The loops may look a little strange: I wanted to mix things up, insert a bunch of items, removing part of them, inserting some more, and then removing most of the queue contents. Then I repeat the process some number of times to give it a workout.
As the sample is provided, when the “Go” process finishes there are some items left in the queue. The “Empty the Queue” button becomes visible at this point to allow you to “clean up” if desired – though this isn’t a serious concern.
The reason for the “Item” column on the form is to let me verify that all my items were indeed being processed in the original sequence. In this screen-shot above you can see that the last “Go” finished with the Dequeuing Count value being mismatched from the last Item Dequeued.
This doesn’t reflect a problem with the queue mechanism. I had pressed “Go” once, left some excess items in the queue, and pressed “Go” a second time. This simply got the “Go” Counts out of sync with the queue contents, which was intended behavior and not an error.
Finally, I pressed the “Empty the Queue” button to drain off the junk I had left queued.
Pretty good, actually.
I don’t see any evidence of a serious memory leak, though there may be issues with different combinations of Windows versions, VB versions, and service packs. I believe that despite its other limitations the Collection object is pretty well-behaved.
The machine I was testing on was a PIII 533EB with 192MB of RAM, running Windows XP Professional RC2. I ran the sample program within the IDE of VB5CCE, which means that performance should only get better in serious use (VB6 native code for example). How is that for a mixed bag of technologies? Gee, and all the software was free!
VBQueue’s self-clocked “queue operations per second” yielded numbers from 5,000 to 12,000 under these conditions. I got very consistent results on lengthy tests of between 7,000 and 8,500 operations per second. I have not attempted any “scientific” profiling (isolating the queue operations from string handling, eliminating the form updating and “DoEvents” interruptions, etc.) because this performance was more than adequate for my needs.
Unless something serious happens after long-term continuous use I suspect that the cost of these queue operations will be invisible next to the other work a real application does. And my message-switching service runs just great!
Nearly three and a half years later, the MSS using this form of internal queueing has been in continuous use serving web applications on a 24 by 7 by 365 basis. It has never been a performance bottleneck nor the cause of any problems for the server that it runs on. The MSS routinely sustains a load of up to 8 transactions per second in this application running on a PIII 700 machine with Windows 2000 Server alongside several IIS applications. Not a heavy load and well within the abilities of an NT service written in VB6. Testing on Windows Server 2003 show no issues.
Variants and Collections are gone in VB.Net, though I assume there will be some similar facility available with appropriate capabilities.
Until then, enjoy!
October 2001
