Efficient C# byte queue for parsing stream of bytes for binary message packets

Question

Hi,

I'm trying to replace what I would usually implement as a circular-buffer+. The function of the queue is to buffer incoming bytes (eg. from serial port or some other stream of data), whilst a parser examines bytes in the queue and detects and extracts message packets.

Criteria:

• can grow (ie not fixed-sized)
• >= 1 bytes can be enqueued at a time
• >= 1 bytes can be dequeued at a time
• efficient

I'm tempted just to use

System.Collections.Generic.Queue<byte>

... but I'm not sure if this is the most efficient type to use. Any suggestions?

Are there any smarter ways of doing what I'm trying to do? (Eg. Interesting suggestions here)

Thanks for your suggestions & input.

Prembo.

Answer 1

Well, Queue<byte> will be efficient in terms of memory. It will basically be a byte[] behind the scenes. It may be slightly awkward to work with if you want to dequeue or enqueue whole chunks at a time though. Each operation should be amortized O(1) for a single byte, leading to O(n) to enqueue or dequeue a chunk of size n... but the scaling factor will be higher than (say) a buffer block copy.

Answer 2

Queue<byte> is backed by a byte[], but you would see better performance if copying to/from the underlying buffer using Array.Copy rather than looping through Enqueue/Dequeue methods. So personally, if Queue<byte> doesn't give you the performance you want, then you might implement your own queue class that provides QueueMultiple and DequeueMultiple methods.

Answer 3

Depending upon how the incoming bytes are received and how the parser examines them, you might consider a Queue<byte[]>.

Answer 4

I know I'm not be helpful, but you can write one of your own.
The theoretic part:
The queue should be in byte[] and 2 indexes, 1 for head and 1 for tail

0                                                    n
|----------------------------------------------------|
               |                        |
              head                     tail

Each time you need to add k bytes you move tail k units left and put the in the new space created data there.

0                                                    n
|-------------------------------new data-------------|
               |                |       |
              head         new tail  old tail

Each time you need to pop k bytes you move head k units left and take data from the space lost.

0                                                    n
|-------new data-------------------------------------|
       |       |                        |
   new head   head                     tail

In case head and tail collide, you need to double the size of the container and copy each half to the new one.

Keep in mind: if you add 1234 and then pop 2 letters you will get 34

(I don't know if I should mark this post as community wiki)