Concurrent frequency counter updates java

Question

I am trying to implement a frequency counter that counts the occurrences of each element. In this case two processes can call the hfc.count(1) and hfc.count(2) concurrently. I'm summing up the the number of processes to make sure its 2000000, but I am off by like ~100000.

class FrequencyCounter {
HashMap frequencyMap = new HashMap();
int max ;

FrequencyCounter(int max) {
    this.max = max ;
    for (int i = 0; i < max; i++) {
        frequencyMap.put(i, 0);
    }
}

void count(int event) {
    synchronized (this) {
        if (frequencyMap.containsKey(event)) {
            frequencyMap.put(event, frequencyMap.get(event) + 1);
        }
    }
}

/**
 * @param event
 * @return the frequency of event since creation.
 */
int frequency(int event) {

    return frequencyMap.get(event);
}

Concurrent freq counter

class HighFrequencyCounter extends FrequencyCounter {

int[] count;
static int n;

/**
 * @ClassInvariant {frequencyMap != null && max > 0}
 */

HighFrequencyCounter(int max) {
    super(max);

    count = new int[max];
}

void count(int event) {
    if (count[event] != 0) {
        n++;
        super.count(event);
    }
    if (count[event] < 1) {
        count[event] = 1;
        frequencyMap.put(event, frequencyMap.get(event) + 1);
        count[event] = 0;

    }
}

public static void main(String Args[]) throws InterruptedException {

    class HEventer extends Thread {
        HighFrequencyCounter hfc;

        HEventer(HighFrequencyCounter hfc) {
            this.hfc = hfc;
        }

        public void run() {
            Random r = new Random();
            for (int i = 0; i < 20000; i++) {
                hfc.count(r.nextInt(10));
            }
        }
    }

    HighFrequencyCounter hfc = new HighFrequencyCounter(10);
    HEventer hev[] = new HEventer[1000];
    for (int i = 0; i < 1000; i++) {
        hev[i] = new HEventer(hfc);
    }

    long hstartTime = System.currentTimeMillis();
    for (int i = 0; i < 1000; i++) {
        hev[i].start();
    }
    for (int i = 0; i < 1000; i++) {
        hev[i].join();
    }
    long hendTime = System.currentTimeMillis();
    System.out.println(hendTime - hstartTime);

    int sumProcesses = 0;
    for (int i = 0; i < 10; i++) {
        System.out.println(i + " =  " + hfc.frequency(i));
        sumProcesses = sumProcesses + hfc.frequency(i);

    }
    System.out.println(sumProcesses);
    System.out.println(hfc.n);

}

}

I know this is possible using java's concurrent hashmaps, but i am trying to synchronize just simple hashmaps. My normal frequencyCounter class does, work as expect, but I'm not sure how i to synchronize the count method.

For high frequency counter i synchronized the count method, and used wait within the while(count[event] != 0) wait() however this was allowing for concurrent calls because i needed to synchronize the count method.

user_641955 · Answer

You need to synchronize all shared access to frequencyMap, not just when writing to it. Since writing to the map is guarded by a lock on this, you need to synchronize on the same lock when reading from the map.

int frequency(int event) {
    synchronized (this) {
        return frequencyMap.get(event);
    }
}

Without synchronization, one thread may not see what was written by another. And that explains the inconsistent values you are getting.

Btw, I notice that the constructor sets initial values in the map to 0 in the range [0..max). If the map will only ever use keys in this range, then an array would be more appropriate and lighter than a hash map.

As you wrote in a comment:

My issue is regarding the count(event) function of HighFrequencyCounter. If i want to allow for two threads of different integer events, say hfc.count(4) and hfc.count(3) to run concurrently but not two concurrent calls to hfc.count(3), i used a count[0..Max] as an array to hold the condition. This is where i'm running into difficulties in synchronizing

Based on this description, you need one lock per counter. Here's a simple implementation using one array for the counts, and one for the locks:

class FrequencyCounter {
    private final int[] counts;
    private final Object[] locks;

    FrequencyCounter(int max) {
        counts = new int[max];
        locks = new Object[max];
        IntStream.range(0, max).forEach(i -> locks[i] = new Object());
    }

    void count(int event) {
        synchronized (locks[event]) {
            counts[event]++;
        }
    }

    int frequency(int event) {
        synchronized (locks[event]) {
            return counts[event];
        }
    }
}

Concurrent frequency counter updates java

1 Answers