Java Performance using Concurrency

Answer 1

I could be way off here, but that looks about as good as you'll get. That's basically cookie cutter sync-map accessors there.

Answer 2

Dumping all the synchronized keywords and defining dict as a ConcurrentHashMap might be worth trying.

Answer 3

First thing you want to do is get rid of all synchronized key words.

The easiest way of doing that is be declaring dict to be a ConcurrentHashMap:

private final ConcurrentMap<String,String> dict = new ConcurrentHashMap<String,String>();

Doing this you can immidiatly remove the synchronized part of translate so it would look like:

 public String translate (String word) throws IllegalArgumentException { ..

The reason for this is the contract in which the CCHM holds regarding up to date reads.

Finally, add to dictionary can look like:

 public void addToDictionary (String word, String translation) throws IllegalArgumentException {
            if (dict.putIfAbsent(word,translation)!=null) {
                throw new IllegalArgumentException(word + " already exists.");
            }
        }

Also remove synchronized from getAllWords as well.

Edit: After thinking about tom's comment. Having a double look up in this 'exception case' probably isnt worth it. If the case didnt throw an exception then it would be appropriate.

Answer 4

if you have more reads than writes (that's usually the case) consider using ReadWriteLock this way readers are not blocking each other.

Answer 5

1. Constructing and throwing exception is slow, so don't do that.
2. Make sure you only use a single map operation in each method, rather than doubling the look up.
3. If significantly used concurrently, use ConcurrentHashMap instead of synchronized.

Note, the getAllWords method is not thread-safe, or at least, the Set it returns is not.

Answer 6

There are a lot of efficient ways to store dictionaries. Using heavyweight things like Java's default HashMap and String objects is not one of them.

So, sure, you can get rid of the synchronized keyword and try gain a tiny bit of speed left and right by working around Java idiosynchrasies.

Sure, a Map's contains is O(1)... But the map resizing when you put millions of String in it ain't O(1) ;)

Food for thought: determining if a word is present using, say, a Trie, will probably be faster than simply computing a String's hashcode (I'm not saying a trie is what you need is: all I'm saying is: there's more than "let's use a HashMap, it's O(1) so you can't beat that"-meets-the-eye.

And I can tell you that, say, Google's 'translate' and Google's 'find-as-you-type' are definitely not implemented by storing millions of Java String object in I-need-constant-resizing-and-I-resize-very-slowly Java HashMaps.

What are your requirements? How many words? How many languages to be supported?

Answer 7

When you say improve the performance, do you have any idea about the usage statistics? How many writes to reads for instance, and how large the internal map is?

If the number of reads is proportionally high and the map is populated mostly at startup (and isn't enormous), a copy-on-write strategy might be your best bet. We have used (and maintain) a CopyOnWriteMap that has better performance for concurrent reads than ConcurrentHashMap (by about 10% in our tests).

Answer 8

You should be using ConcurrentHashMap however with your current implementation its worth nothing that the getAllWords() has a thread safe copy on the data only inside the synchronized block, i.e. unless the caller also synchronizes the collction, its not thread safe. One way around this is to take a copy before returning (or use ConcurrentHashMap)

In the following example, the map is accessed once per method, rather than twice. (without synchronized)

public class SlowDictionary { 
    private final ConcurrentMap<String,String> dict = new ConcurentHashMap<String,String>(); 

    public String translate (String word) throws IllegalArgumentException { 
        String translation = dict.get(word);
        if (translation == null) 
            throw new IllegalArgumentException(word + " not found."); 
        return translation; 
    } 

    public void addToDictionary (String word, String translation) throws IllegalArgumentException { 
        if (dict.putIfAbsent(word, translation) != null) 
            throw new IllegalArgumentException(word + " already exists."); 
    } 

    public Set<String> getAllWords () {     
        return dict.keySet(); 
    } 
}