Internal Queueing Mechanism for Java

schlaps

I have a problem concerning the storage of Objects(or can be Strings, they can easily be converted). I have a thread that reads in messages. These messages can be requests or registrations. However i want to put the registration message on some form of internal java "queue" or "collection" for another thread to read from, as they have lower priority.

However there could be 20,000 registration messages put on the message Holder or queue. These messages could be 4kb in size.

The question is what to use as the message holder. Performance is an issue. Would a Hashmap or some form of collection run out of memory or be sufficient. External data storage, e.g. Oracle Advanced Queues is out of the question.

Can anyone suggest another mechanism or java api that could be used.

Any help would be greatly appreciated

tempest

JMS Messaging API

for programming and

JBOSS MQ

for deployment.

Of course you can always just create your own implementation as you are suggesting. HashMap should not run out of memory as long as the VM doesn't run out of memory (4kb * 20000 = 80000kb = ~80MB), which shouldn't break the back of any application really, although you might find that HashMap isn't the most efficient for your purposes. You don't really need to be able to hash into it, so a sequential data collection like an ArrayList or a LinkedList would probably serve your purposes better. Even better write a Queue interface that extends collection or List, implement the FIFOQueue as a FIFO Queue and back this implementation with a LinkedList or an ArrayList.

Actually check out org.apache.commons.collections.buffer.UnboundedFifoBuffer at Jakarta Commons which might be the exact data structure you need.

schlaps

Although the queueing mechanism is FIFO, the application must be able to delete or override messages, if they timeout or another registration message is sent with an already used unique id.

Which mechanism is the most efficient in this case. My gut feeling would be a treeMap or hashMap, however I am inexperienced when it comes to collections holding thie amount of objects. Would JMS be excessive overhead and can you search through JMS messages.

GillyS

Schlaps,

You could probably use the LinkedHashMap (jdk 1.4) , it keeps the order of insertion so you would get the FIFO mechanism and also be able to key into an individual item if required. I'd try this out and see if it will fit your performance requirements before I'd try a JMS implementation - might be overkill for what you are doing.

Gilly

schlaps

From what I looked at, a LinkedHashMap would be the best option, it keeps the order of insertion so you would get the FIFO mechanism. From what i read, LinkedHashMaps and LinkedHashSets have an efficiency roughly equal to that of HashMaps and HashSets. The operation of adding or removing an element is slightly slower, since the hidden linked lists must be maintained.

In HashMaps, The arrays are sparse, which means that a significant number of the slots are empty. Searching this array incurs a certain waste of time, since the searching must visit each slot in the array whether it is empty or not. A LinkedHashMap has the added benefit of another linked list forming yet another chain through the elements. Traversing this list doesn’t require searching empty slots, because there are no empty slots in the linked list.

When the size of a Hashmap reaches the value which is the product of the load factor and the capacity, the capacity will be increased automatically to twice the old capacity +1. A LinkedHashMaps size is equal to the number of entries.

I also looked at JMS as an option, but after reading into it, I believe it to be complicated to implement, inefficient for my requirements.

Sorry i didnt reply earlier, but im up to my eyes, if anyone can suggest other options please let me know, as it will be a while before I get to implement these changes.

Thanks Tempest and GillyS, that was a great help

PhilH

In HashMaps, The arrays are sparse, which means that a significant number of the slots are empty. Searching this array incurs a certain waste of time, since the searching must visit each slot in the array whether it is empty or not.

I don't think that sounds correct to me. When you call map.get(key) the hash code of the key is computed. This gives an integer value which the map uses to pick a list of the key-value pairs whose keys (probably) have the same hash code. Then a comparison is done with each of these (using the equals() method) until a match is found, and the value from the key-value is returned. There should not be any walking of empty array elements.

The LinkedHashMap stores additionally a linked list to maintain the iteration order, so that it is stable. Be very carefull about using it in access-ordered mode, as this will cause the list order to rearrange itself in response to each get() call. However, the lookup of a key-value pair in a LinkedHashMap uses the getEntry from its superclass (the HashMap), so the lookup of elements is no more efficient (and depending on your access-order, it is much less efficient).

I'm not saying that it is the wrong data structure for your purposes, it's just that the 'empty slots' comparison.

Also, since LinkedHashMap is a subclass of HashMap, your observations about them growing at different rates don't ring true. I think you are getting size (the number of mapping stored) and capacity (the number of mappings it has room for) confused.

In fact, just re-reading over the thread, are you sure you need to be able to look these suckers up by their keys at all? If not, the Map is the wrong choice. If you're only interested in the order then you should just use a List implementation (probably LinkedList). Be careful about threading though. The javadocs for (at least) HashMap and LinkedList warn that they are not synchronised and therefore not safe to use across threads without a little exta work.