Re: Is there a Queue size limit ?

Tech-Archive recommends: Speed Up your PC by fixing your registry

On Mon, 13 Apr 2009 15:58:51 -0700, Michael D. Ober <obermd.@.alum.mit.edu.nospam.> wrote:

[...]
It's more memory intensive and (on average) slower for _all_ queue lengths. Depending on the exact data being stored in the queue, it could be as much as two or three times as memory intensive. And since Queue<T> eventually has zero memory allocations and garbage collections associated with it, the time cost for Queue<T> is much less than for a LinkedList-based implementation.

Only if you don't break the underlying performance assumption of the built-in Queue<T> class. This assumption is that items are dequeued at the same or higher rate as they are enqueued. I ran into a situation that breaks that assumption, enqueing items orders of magnitude faster than they could be dequeued.

Over the long term, you obviously can't have that happen. Eventually, you have to dequeue, on average, the same number of items queued. Even if the queuing is relatively slow initially (and it wasn't, I assure you...see below), over the total time spent it couldn't be a significant cost.

However, for larger queues, the built in queue class is very inefficient with regards to garbage collection and growth since adding to a queue can result in linear time delays while the IList<T> is copied and expanded.

The reallocation of the internal storage of Queue<T> should not happen very often, especially not as the queue approaches larger sizes.

I was putting hundreds of thousands of items into multiple queues.

You must have had something else wrong with your code. I wrote a quick test application, and using Queue<T> I can enqueue 10 MILLION "int" elements in 2/10ths of a second. That's without dequeuing _anything_. Using a LinkedList<T>, it takes TWENTY times longer.

I was able to narrow the gap a bit by using a user-defined struct with 6 ints instead; but even there, LinkedList<T> wound up two to four times SLOWER than Queue<T> at best (and I still had one run where it came in 10x slower). Note, of course, that at that scale, the backing storage for the Queue<T> winds up allocated from the large-object heap even more quickly, which can actually ease the work the GC has to do.

I have no idea why you had a performance problem, but whatever it was, it wasn't because of the cost of enqueuing elements into a Queue<T> instance, nor did you fix whatever performance problem you had simply by switching to LinkedList<T> instead of Queue<T>.

[...] The program this was developed for was a console console application actually ran 20 threads gathering work, loading 10 queues. There was a single thread unloading each queue as well. The average number of work items added to each queue was over 600,000 with the longest queue receiving over a 1.6 million items. Each item was a string of 9 to 14 characters. The mainframe enforced uniqueness of the work items - they were primary keys in a database.

See above. Whatever was slowing your program down, it wasn't the cost of adding something to a Queue<T> instance.

The program was internally partitioned into independent threads to take advantage if overlapped IO and CPU cores on all systems and network links involved, without impacting human real time processing on those same systems. Each thread's IsBackground property was set to False so that the main thread could exit (and thus release resources on the mainframe) as soon as it completed reading the work items. The hardware this program was running was a dual core AMD Opteron based Windows 2003 R2 SP2 x86 server with 2Gb of RAM. The GC simply couldn't handle the reallocations of the IList<T> objects.

I'm sure that's not true. I won't speculate publicly on what kinds of mistakes I think you were making instead, especially since I have not nearly enough information about the larger implementation for speculation to be useful.

But, even a queue with 1.6 million items in it only winds up being reallocated a couple dozen times at most. Even if the GC had to collect each of those allocations one at a time (which would be unusual, happening only if you were inappropriately forcing the GC to collect, or the allocations happened over a relatively long period of time), it wouldn't be a significant cost.

[...]
Causing garbage doesn't add pressure to the GC. In fact, creating garbage by dropping all references to an object actually improves the performance of the next GC pass by reducing the number of items it must track and move during the memory movement phase of the collection.

That depends on your definition of "pressure". The problem that occurs when you repeatedly allocate and free a large number of objects is the gaps that are created in the heap, which then adds to the cost of collecting garbage, when the heap has to be compacted.

If you can organize things so that compaction is avoided altogether, that's great. But otherwise, the more objects you are creating and destroying, the greater the likelihood one of those objects is going to leave a gap.

Other than by calling GC.AddMemoryPressure(), allocations are the only way to add pressure to the GC. With Queue<T>, although no new objects are created, there is a potential O(n) copy of the underlying IList<T>.

That happens rarely. As I pointed out, a couple dozen times at the most, even for a queue of 1.6 million elements. And it doesn't cost much to perform that copy, even for relatively large queue elements (and if you've got very large value types that are causing a performance problem, the solution is to make them reference types, not to change from Queue<T> to LinkedList<T>).

With a LinkedList<T>, you do indeed create a LinkedListNode<T> object, but this object is realatively small, consisting of four pointers (owning list, previous, next, and value) plus the object container for the runtime to identify the object class.

Assuming we're talking about a queue of a reference type, that's a quadrupling of the memory overhead. The nominal additional overhead for a 1.6 million element queue is about 20MB extra, with the LinkedList<T> taking nearly 30MB of memory when the Queue<T> would have only taken just under 7MB.

[...]
Yes and no. I have actually profiled GCs and forcing a generational GC to age objects only incurs major penalties if you force the GC to process multiple generations in a single collection. If you're only forcing Gen(0) collections, there isn't much penalty because the bulk of your items will already have been moved to higher numbered generations.

In general, you should not be forcing garbage collection at all.

There is, however, a huge penalty if you have a Gen(0) item larger than the available space in Gen(1). Then you immediately force a Gen(1) collection before you can complete the Gen(0) collection. If, during a Gen(0) collection, the GC tries to move a large object such as large IList<T> at the end of a generation collection you can inadvertenly force a Gen(1) collection.

First, objects aren't literally "moved" from one generation to another. They may be moved if the heap has to be compacted, but of course as I've pointed out, the best way to create compaction overhead is to allocate lots of little objects ensuring that a gap appears. Once the heap has been compacted, an object is "moved" from one generation to another simply by virtue of the generation pointer being adjusted to the appropriate position.

Second, you're not going to see very many Queue<T> storage objects in the regular heap at all anyway. Objects larger than ~85K wind up on the large-object-heap (LOH). So once your queue has more than 20,000 elements or so (which happens after about a dozen reallocations, all of which occur -- in your described scenario -- very early in the lifetime of the queue), it's not being allocated in the regular heap at all. Furthermore, the LOH isn't (currently) subject to compaction; this is a risk in terms of possibly fragmenting the heap, but that's an allocation _failure_ issue. There's no GC compaction overhead associated with the Queue<T> storage once it's large enough to wind up in the LOH.

What happens in this case is that Gen(0) items that had been moved to Gen(1) prior to the Gen(1) collection starting, are moved again. This time to Gen(2). Basically, you end up moving stuff twice in a single collection, which effectively moves anything that had been moved from Gen(0) to Gen(1) before the Gen(1) collection was in Gen(0). With linked lists, each element is moved independently.

With Queue<T>, once the queue is large enough, nothing winds up being moved at all. So compaction overhead is infinitely greater for LinkedList<T> than for Queue<T>.

[...] I did the timings with a wall clock since the work item gathering took about 30 minutes with this LinkedList<T> based QuickQueue class. Queue Item processing with the LinkedList<T> took 15 to 20 hours and memory usage did indeed decrease during this processing. With the built-in Queue<T> class, the work item collection was taking over 12 hours (and, actually, never completed). Queue Item processing with Queue<T> stalled as the garbage collector took over the process, so it never completed either.

You had something else wrong. Apples-to-apples, Queue<T> would have out-performed LinkedList<T>. If it didn't, there was something else broken that just coincidentally got fixed when you changed to LinkedList<T>. There's just not enough overhead in Queue<T> to cause a half-day delay in processing.

For that matter, even at 30 minutes, it's a certainty that the overhead of the queue data structure was _not_ significant, whether you used Queue<T> or LinkedList<T>.

Contrast with Queue<T> where, once you've reached a reasonably steady state in terms of the queue length, there are no more memory operations at all. GC becomes a complete non-issue.

If your application follows the underlying assumption that items are taken off the queue at roughly the same rate as they are added, you are correct. My case was a worst case scenerio for a queue - high enqueue rate vs. slow dequeue rate.

Even if you don't dequeue the elements ever, Queue<T> is much faster than LinkedList<T>. With a fraction of the memory overhead.

[...]
Your points on the exception handling are correct. In my case, clearing the queue was valid.

If you're certain about that, the above is the only relevant point. The following, is not:

Also, in practice, I have never had the exception occur - in my production code, the debug.print statement writes to an application specific log file and I review the log files routinely.

An exception that never occurs is one you don't need to handle. More importantly, in a data-corruption scenario (not applicable for your specific usage, apparently), finding the data corruption later when a log file is reviewed isn't useful.

-- It's also generally a bad idea to synchronize on a reference exposed to other code. In this case, that means your "Queue" field. Use an object allocated specifically for the purpose of locking, rather than "Queue", to avoid a dependency on other code that might inappropriately lock using the "Queue" reference.

The Queue field is a private, not protected, instance variable. Since the only code that can see this variable is inside the QuickQueue class, this isn't an issue. If it were a protected variable, you would be correct and I would have needed a private sync object.

The LinkedList<T> class sees the reference itself. That is sufficient cause for concern. The fact that it's a private field isn't relevant, unless you never pass that reference to ANY code outside your control, including the code implementing the ListedList<T> class.

For that matter, even if you do never pass that reference to any code outside your control, a dedicated "object" instance is still preferable, due to its self-documenting nature. It's much more likely that in the course of future changes to the class, a reference to a LinkedList<T> will be passed to code outside the class than that a reference to an appropriately-named "object" instance (e.g. "_objQueueLock") would be.

Pete
.

Relevant Pages

  • Re: Fast way to allocate buffer for producer/consumer scenario
    ... queue and triggers another thread to handle the received data. ... What I now did was to restructure this so that instead of copying the buffer ... VirtualAllochowever interoperates with the OS to reserve pages in virtual and physical memory, which in itself presents an overhead. ... However, I think you'll get the biggest benefit by using a "small buffer" optimization, where smaller allocations are held directly in the object and therefore copied rather than moved. ...
    (microsoft.public.vc.language)
  • Re: Cpp Considered Harmful
    ... was received would push it on the queue. ... It's main advantages are the multiple use ... research and experience into concurrency and system design in order to ... Threads share memory, the problem is they share all memory (well not ...
    (comp.lang.cpp)
  • Re: Wait free queue
    ... dealloc, lock-free remote memory dealloc among producers, wait-free ... memory allocator blows the msvcrt away--why bother with it, ... Writing a Generalized Concurrent Queue ... struct queue_node* next; ...
    (comp.programming.threads)
  • Re: P2P Events - growing memory
    ... The recommended practice is that the event callback keeps calling ... PeerGroupGetData until it get the PEER_S_NO_EVENT_DATA error code, ... signifying that you've handled all events in the queue. ... > is where all the memory allocations for all the structures are done. ...
    (microsoft.public.win32.programmer.networks)
  • Re: Information About A BlockingQueue
    ... add items to the queue for processing. ... I'm a little confused about how a BlockingQueue works. ... have a memory leak. ... application to see where the memory leak is taking place, ...
    (comp.lang.java.programmer)