If thread-safe, any chances to make more concurrent

Question

The class AnagramGameDefault simulates an anagram game.

The submitScore() should recalculate the positions, the one with highest score has position 1, there can be several players on the same position.

The getLeaderBoard() fetches the entry for a user plus two above and two below.

The concerns I have :

I tested the code for multiple threads and I guess it's working but I would like to know if there are some race conditions or failure in sharing state in the code

I have used quite a stringent mutually exclusive locking by using 'synchronized'. I don't think this can be avoided as submitScore() and getLeaderBoard() rely heavily on sorting and correct positions of score but is there a possibility ? I read a bit about ReentrantLock but it's more suitable where there are multiple reads and lesser writes, in this case, even the reads need calculations.

public enum AnagramGameDefault{

INSTANCE;

private Map<String, Entry> leaderBoardUserEntryMap;

{
    leaderBoardUserEntryMap = new LinkedHashMap<>();
}

public int calculateScore(String word, String anagram) {

    if (word == null || anagram == null) {
        throw new NullPointerException("Both, word and anagram, must be non-null");
    }

    char[] wordArray = word.trim().toLowerCase().toCharArray();
    char[] anagramArray = anagram.trim().toLowerCase().toCharArray();

    int[] alphabetCountArray = new int[26];

    int reference = 'a';

    for (int i = 0; i < wordArray.length; i++) {
        if (!Character.isWhitespace(wordArray[i])) {
            alphabetCountArray[wordArray[i] - reference]++;
        }
    }
    for (int i = 0; i < anagramArray.length; i++) {
        if (!Character.isWhitespace(anagramArray[i])) {
            alphabetCountArray[anagramArray[i] - reference]--;
        }
    }

    for (int i = 0; i < 26; i++)
        if (alphabetCountArray[i] != 0)
            return 0;

    return word.length();

}

public void submitScore(String uid, int score) {

    Entry newEntry = new Entry(uid, score);
    sortLeaderBoard(newEntry);
}

private void sortLeaderBoard(Entry newEntry) {

    synchronized (leaderBoardUserEntryMap) {
        leaderBoardUserEntryMap.put(newEntry.getUid(), newEntry);

        // System.out.println("Sorting for " + newEntry);

        List<Map.Entry<String, Entry>> list = leaderBoardUserEntryMap.entrySet().stream()
                .sorted(Map.Entry.comparingByValue(Collections.reverseOrder())).collect(Collectors.toList());
        leaderBoardUserEntryMap.clear();

        int position = 0;
        int previousPosition = 0;
        int currentPosition = 0;

        for (Map.Entry<String, Entry> entry : list) {
            currentPosition = entry.getValue().getScore();
            if (!(currentPosition == previousPosition))
                position++;

            entry.getValue().setPosition(position);
            leaderBoardUserEntryMap.put(entry.getKey(), entry.getValue());

            previousPosition = currentPosition;

        }
    }

}

public List<Entry> getLeaderBoard(String uid) {

    final int maxEntriesAroundAnEntry = 2;

    if (!leaderBoardUserEntryMap.containsKey(uid))
        return Collections.emptyList();

    Entry userEntry = null;

    final List<Entry> leaderBoard = new ArrayList<>();
    List<Entry> lowerEntries = null;
    List<Entry> higherEntries = null;

    synchronized (leaderBoardUserEntryMap) {

        printBoard();

        userEntry = leaderBoardUserEntryMap.get(uid);
        int userPosition = userEntry.getPosition();
        int upperPosition = userPosition - maxEntriesAroundAnEntry;
        int lowerPosition = userPosition + maxEntriesAroundAnEntry;

        // Higher entries
        higherEntries = leaderBoardUserEntryMap.values().stream()
                .filter(entry -> (entry.getPosition() < userPosition && entry.getPosition() >= upperPosition))
                .map(entry -> new Entry(entry.getUid(), entry.getScore(), entry.getPosition()))
                .collect(Collectors.toList());

        // Lower entries
        lowerEntries = leaderBoardUserEntryMap.values().stream()
                .filter(entry -> (entry.getPosition() > userPosition && entry.getPosition() <= lowerPosition))
                .map(entry -> new Entry(entry.getUid(), entry.getScore(), entry.getPosition()))
                .collect(Collectors.toList());

        userEntry = new Entry(userEntry.getUid(), userEntry.getScore(), userEntry.getPosition());

        // }

        if (higherEntries != null && !higherEntries.isEmpty()) {

            if (higherEntries.size() >= maxEntriesAroundAnEntry) {
                higherEntries = higherEntries.subList(higherEntries.size() - maxEntriesAroundAnEntry,
                        higherEntries.size());
            }

            leaderBoard.addAll(higherEntries);
        }

        leaderBoard.add(userEntry);

        if (lowerEntries != null && !lowerEntries.isEmpty()) {

            if (lowerEntries.size() >= maxEntriesAroundAnEntry) {
                lowerEntries = lowerEntries.subList(0, maxEntriesAroundAnEntry);
            }

            leaderBoard.addAll(lowerEntries);
        }
    }

    return leaderBoard;
}

public void printBoard() {

    System.out.println("---------Start : Current leader board---------");
    leaderBoardUserEntryMap.forEach((key, value) -> {
        System.out.println("BOARD ENTRY : " + key + " : " + value);
    });
    System.out.println("---------End : Current leader board---------");
}

}

The Entry POJO :

public class Entry implements Comparable<Entry> {

    private String uid;
    private int score;
    private int position;

    public Entry(String uid, int score) {

        this.uid = uid;
        this.score = score;

    }

    public Entry(String uid, int score, int position) {

        this.uid = uid;
        this.score = score;
        this.position = position;
    }

    public Entry() {

    }

    public String getUid() {
        return uid;
    }

    public void setUid(String uid) {
        this.uid = uid;
    }

    public int getScore() {
        return score;
    }

    public void setScore(int score) {
        this.score = score;
    }

    public int getPosition() {
        return position;
    }

    public void setPosition(int position) {
        this.position = position;
    }

    @Override
    public int hashCode() {
        final int prime = 31;
        int result = 1;
        result = prime * result + score;
        result = prime * result + ((uid == null) ? 0 : uid.hashCode());
        return result;
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj)
            return true;
        if (obj == null)
            return false;
        if (getClass() != obj.getClass())
            return false;
        Entry other = (Entry) obj;
        if (score != other.score)
            return false;
        if (uid == null) {
            if (other.uid != null)
                return false;
        } else if (!uid.equals(other.uid))
            return false;
        return true;
    }

    @Override
    public String toString() {
        return "Entry [uid=" + uid + ", score=" + score + ", position=" + position + "]";
    }

    @Override
    public int compareTo(Entry o) {
        // TODO Auto-generated method stub
        if (o == null)
            return -1;

        return Integer.compare(score, o.getScore());
    }

}

The tester class :

public class AnagramGameDefaultDemo {

    public static void main(String[] args) {

        if (args == null || args.length < 1) {
            System.out.println("Enter testing approach - 1 for single threaded, 2 for multi-threaded");
            return;
        }

        switch (args[0]) {

        case "1": {
            new AnagramGameDefaultDemo().testSingleThreaded();
            break;
        }

        case "2": {
            new AnagramGameDefaultDemo().testMultithreaded();
            break;
        }

        default: {
            System.out.println("Enter proper option(1 or 2)");
            break;
        }
        }

    }

    private void testMultithreaded() {

        Map<String, String> stringAnagramMap = new HashMap<>();

        CountDownLatch countDownLatchOne = new CountDownLatch(1);

        stringAnagramMap.put("raw", "war");
        stringAnagramMap.put("raw", "wars");
        AnagramGamePlayer jake = new AnagramGamePlayer("jake", stringAnagramMap, countDownLatchOne);
        new Thread(jake, "jake").start();

        stringAnagramMap.clear();

        stringAnagramMap.put("tool", "loot");
        AnagramGamePlayer ace = new AnagramGamePlayer("ace", stringAnagramMap, countDownLatchOne);
        new Thread(ace, "ace").start();

        stringAnagramMap.clear();

        stringAnagramMap.put("William Shakespeare", "I am a weakish speller");
        AnagramGamePlayer max = new AnagramGamePlayer("max", stringAnagramMap, countDownLatchOne);
        new Thread(max, "max").start();

        stringAnagramMap.clear();

        stringAnagramMap.put("School master", "The classroom");
        AnagramGamePlayer tBone = new AnagramGamePlayer("tBone", stringAnagramMap, countDownLatchOne);
        new Thread(tBone, "tBone").start();

        stringAnagramMap.clear();

        countDownLatchOne.countDown();

        CountDownLatch countDownLatchTwo = new CountDownLatch(1);

        stringAnagramMap.put("Punishments", "Nine Thumps");
        AnagramGamePlayer razor = new AnagramGamePlayer("razor", stringAnagramMap, countDownLatchTwo);
        new Thread(razor, "razor").start();

        stringAnagramMap.clear();

        stringAnagramMap.put("Dormitory", "Dirty Room");
        AnagramGamePlayer chip = new AnagramGamePlayer("chip", stringAnagramMap, countDownLatchTwo);
        new Thread(chip, "chip").start();

        stringAnagramMap.clear();

        countDownLatchTwo.countDown();

        CountDownLatch countDownLatchThree = new CountDownLatch(1);

        stringAnagramMap.put("Mother in law", "Hitler woman");
        AnagramGamePlayer dale = new AnagramGamePlayer("dale", stringAnagramMap, countDownLatchThree);
        new Thread(dale, "dale").start();

        countDownLatchThree.countDown();

        stringAnagramMap.clear();
    }

    private final class AnagramGamePlayer implements Runnable {

        private Map<String, String> stringAnagramMap = new HashMap<>();
        private String uid;
        private CountDownLatch countDownLatch;

        public AnagramGamePlayer(String uid, Map<String, String> stringAnagramMap, CountDownLatch countDownLatch) {
            this.stringAnagramMap.putAll(stringAnagramMap);
            this.uid = uid;
            this.countDownLatch = countDownLatch;
        }

        @Override
        public void run() {
            AnagramGameDefault anagramGameDefault = AnagramGameDefault.INSTANCE;

            try {
                countDownLatch.await();
            } catch (InterruptedException e) {
                // TODO Auto-generated catch block
                e.printStackTrace();
            }

            System.out.println("Player " + uid + " started playing with " + stringAnagramMap);
            stringAnagramMap.entrySet().forEach(entry -> {
                anagramGameDefault.submitScore(uid,
                        anagramGameDefault.calculateScore(entry.getKey(), entry.getValue()));
                printLeaderBoard(uid, anagramGameDefault.getLeaderBoard(uid));

            });

            System.out.println("Player " + uid + " completed playing");
        }

    }

    private void testSingleThreaded() {
        AnagramGameDefault anagramGameDefault = AnagramGameDefault.INSTANCE;
        anagramGameDefault.submitScore("Jake", 3);
        anagramGameDefault.submitScore("Ace", 7);
        anagramGameDefault.submitScore("Max", 1);
        anagramGameDefault.submitScore("T-Bone", 14);
        anagramGameDefault.submitScore("Razor", 6);
        anagramGameDefault.submitScore("Razor", 7);
        anagramGameDefault.submitScore("He-Man", 4);
        anagramGameDefault.submitScore("Men-at-Arms", 8);
        anagramGameDefault.submitScore("BattleCat", 3);
        anagramGameDefault.submitScore("Jake", 2);
        anagramGameDefault.submitScore("BattleCat", 3);
        anagramGameDefault.printBoard();

        anagramGameDefault.submitScore("Men-at-Arms", 21);
        anagramGameDefault.submitScore("Orko", 20);
        anagramGameDefault.submitScore("Jake", 4);
        anagramGameDefault.printBoard();

        System.out.println();
        printLeaderBoard("user5", anagramGameDefault.getLeaderBoard("user5"));
        System.out.println();
        printLeaderBoard("user4", anagramGameDefault.getLeaderBoard("user4"));
        System.out.println();
        printLeaderBoard("user15", anagramGameDefault.getLeaderBoard("user15"));
        System.out.println();
        List<Entry> entries = anagramGameDefault.getLeaderBoard("user1");
        printLeaderBoard("user1", entries);

        System.out.println("Changing state of the received entries");
        entries.forEach(entry -> {
            entry.setPosition(1);
            entry.setScore(0);
        });

        anagramGameDefault.printBoard();
        printLeaderBoard("user1", anagramGameDefault.getLeaderBoard("user1"));
    }

    private static void printLeaderBoard(String user, List<Entry> leaderBoard) {

        if (user == null || leaderBoard.isEmpty()) {
            System.out.println("Either user " + user + " doesn't exist or leader board is empty " + leaderBoard);
        }

        System.out.println("**********Printing leader board for " + user);
        leaderBoard.forEach(System.out::println);
        System.out.println("**********");
    }

}

Ok, I will try that - honestly, I didn't know such a site exists :D — Kaliyug Antagonist, Sep 17 '17 at 18:53

lexicore · Accepted Answer · 2017-09-17T19:00:27.460

1

It seems the only shared state you have in the whole thing is leaderBoardUserEntryMap. You synchronize on it when updating in sortLeaderBoard. In getLeaderBoard for some reason you don't yet synchronize on it when checking if (!leaderBoardUserEntryMap.containsKey(uid)). That's minor, but you should do it as well. Later, you synchronize on it when constructing the leader board.

From this point of view your synchronization seems adequate.

What I find a bit problematic is that your Entry is mutable and stores position. This makes your update operation more problematic. You have to re-sort and re-set positions on every update. And you're locking all other update or even read operations. I'd avoid mutable objects in multithreaded code.

I'd use a SortedSet instead and let the implementation handle sorting. To find out the position of the element you'd just do set.headSet(element).size() + 1. So no need to store position at all.

I initially wanted to suggest using concurrent collection implementations like ConcurrentHashSet which would allow "full concurrency of retrievals and adjustable expected concurrency for updates". Basically, retrievals could be non-blocking, only updates were.

However, this won't help much as your "retrieval" logic (creating the leader board around target entry) is not so simple and involves several reads. So I think it's better not use concurrent collections but instead actually synchronize on the collection and make updates and retrievals as compact as possible. If you give up on the idea of having position in Entry then update is a trivial add. Then you'll only need to read entries around the entry as fast as possible (within the synchronized block). This should be quite fast with tree sets.

edited Sep 17 '17 at 19:00

answered Sep 17 '17 at 18:48

lexicore

42,748
17
132
221

The Sorted implementations like TreeMap, SortedSet(set doesn't allow adding duplicates but here the same user can submit the same or different scores) etc. run into issues because the comparator(works on the score) and equals(works on uid and score) aren't inconsistent. I tried several posts : https://stackoverflow.com/questions/46218998/update-a-pojo-property-with-position-in-a-sortedmaptreemap https://stackoverflow.com/questions/46198930/store-entries-in-sorted-order-and-retrieve-entries-around-an-entry – Kaliyug Antagonist Sep 17 '17 at 19:00
Yeah I thought about the position calculation but the requirement dictates that to be the part of Entry pojo – Kaliyug Antagonist Sep 17 '17 at 19:01
@KaliyugAntagonist "requirement diotates" - unreasonable. – lexicore Sep 17 '17 at 19:02
Well, I have received a low-level design doc. that dictates the classes, of course, I will have to reason about it when I get a chance – Kaliyug Antagonist Sep 17 '17 at 19:03
@KaliyugAntagonist This duplicate problem is quite easy to overcome I think. You'll need an entry per user id, trial id and score. Sure there will be quirck but it's doable. – lexicore Sep 17 '17 at 19:04
Can you spare some time and have a look at the questions that I have mentioned, in addition to the below one https://stackoverflow.com/questions/46172817/retrieve-fixed-number-of-entries-around-an-entry-in-a-map-sorted-by-values – Kaliyug Antagonist Sep 17 '17 at 19:05
@KaliyugAntagonist No, sorry. This goes beoynd what I'm ready to invest. I think you have enough hints already. – lexicore Sep 17 '17 at 19:31

If thread-safe, any chances to make more concurrent

1 Answers1