Comment on: A Memory-Efficient Queue for Primitive Types (in Java)

Have you ever designed and coding something and got it working and felt really satisfied and then went to bed and woke up then next morning with the sparkling clear thought in your mind that all of that work was unneeded, that there was a much better and much simpler way to do the exact same thing?   Did that happen after you had blogged about your cool piece of work?  Well, it just happened to me.

Well, in my previous post I carefully justified a queue that directly contained primitive types, in order to have a queue that could hold hundreds of millions of elements.  That’s alright, and the discussion of memory consumption and when to optimize it is good, but …

It is now clear as can be to me that the right way to handle this queue is to write my tuples-of-primitive-types to a file, not keep them in memory at all, and to run the file as a queue.  The code is very simple – here it is: externalqueue.zip.  Basically, I open a RandomAccessFile and keep track of head and tail filePointers.  The queue class is parameterized by a small interface that the caller must pass in to the constructor, where the caller takes responsibility for serializing and deserializing his element objects to via a DataInput or DataOutput.  (This isn’t official Java serialization, where objects are tracked.  This queue is meant largely for “struct-like” things.)

This simple class is enough for my needs but it has a limitation that might need to be fixed, depending on the usage.  The external file grows to contain all the elements that have ever been written to the queue.  It is only truncated when the queue becomes empty.  For my application (the retrograde analysis of the 15-puzzle) the queue never becomes empty until the algorithm terminates, yet this is fine since all the enqueued elements will still fit on disk (it should take no more than 5-7Gb).  But in other applications it might be desirable to enhance this queue to start using alternate files once the files reach a certain threshold.  Then you can start deleting files once the head pointer (next element to be dequeued) advances past the end of a file and you rotate to the next one.