ConcurrentCounter

[mikelaud]

Fast concurrent counter for 2 threads (c++):


class ConcurrentCounter {

private: // counters

long mCounter_byFirstThread;
long mCounter_bySecondThread;

public: // init

ConcurrentCounter() {
mCounter_byFirstThread = 0;
mCounter_bySecondThread = 0;
}

public: // interface for first thread

void increment_byFirstThread() { mCounter_byFirstThread++; }
void decrement_byFirstThread() { mCounter_byFirstThread--; }

public: // interface for second thread

void increment_bySecondThread() { mCounter_bySecondThread--; }
void decrement_bySecondThread() { mCounter_bySecondThread++; }

public: // concurrent interface

long getCounter() {
return labs(mCounter_byFirstThread - mCounter_bySecondThread);
}

};

(original link: http://sites.google.com/site/mmxmmx/algorithms/concurrentcounter)

[James Gan]

Add volatile to following variables?

   long mCounter_byFirstThread;
   long mCounter_bySecondThread;

--
Best Regards
James Gan
Current Project: Concurrent Building Block at http://amino-cbbs.sourceforge.net/
Blog: http://ganzhi.blogspot.com

[mikelaud]

On Mar 23, 5:36 am, James Gan <gan...@gmail.com> wrote:
> Add *volatile* to following variables?
>
>    long mCounter_byFirstThread;
>    long mCounter_bySecondThread;

Yes - of course
volatile or without+SHM

--
Best Regards,
Oksenenko Michael
http://mikelaud.ca

[Alexander Chemeris]

On Mon, Mar 23, 2009 at 10:08 AM, mikelaud <mmx...@gmail.com> wrote:
> On Mar 23, 5:36 am, James Gan <gan...@gmail.com> wrote:
>> Add *volatile* to following variables?
>>
>>    long mCounter_byFirstThread;
>>    long mCounter_bySecondThread;
>
> Yes - of course
> volatile or without+SHM

What do you mean by SHM here?

--
Regards,
Alexander Chemeris.

SIPez LLC.
SIP VoIP, IM and Presence Consulting
http://www.SIPez.com
tel: +1 (617) 273-4000

[mikelaud]

> > Yes - of course
> > volatile or without+SHM
>
> What do you mean by SHM here?
>

SHM == POSIX Shared Memory (or System V)

[Landmann]

Also proper alignment is missing here to prevent sharing and I find it
counterintuitive to reverse the operations for the 2nd thread.

[Kimo Crossman]

Has there been a review of the counting methods analyzed in Chapter 12 of
the recently published Art of Multiprocessor Programming draft version
which does not include that chapter is here:

http://courses.csail.mit.edu/6.852/08/papers/lists-book-chapter.pdf

12 Counting, Sorting, and Distributed Coordination 321
12.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . .
321
12.2 Shared Counting . . . . . . . . . . . . . . . . . . . . . . . . . 321
12.3 Software Combining . . . . . . . . . . . . . . . . . . . . . . . 322
12.3.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . 323
12.3.2 An Extended Example . . . . . . . . . . . . . . . . . . 330
12.3.3 Performance and Robustness . . . . . . . . . . . . . . 333
12.4 Quiescently-Consistent Pools and Counters . . . . . . . . . . 333
12.5 Counting Networks . . . . . . . . . . . . . . . . . . . . . . . . 334
12.5.1 Networks that count . . . . . . . . . . . . . . . . . . . 334
12.5.2 The Bitonic Counting Network . . . . . . . . . . . . . 337
12.5.3 Performance and Pipelining . . . . . . . . . . . . . . . 345
12.6 Diffracting Trees . . . . . . . . . . . . . . . . . . . . . . . . . 348
12.7 Parallel Sorting . . . . . . . . . . . . . . . . . . . . . . . . . .
353
12.8 Sorting Networks . . . . . . . . . . . . . . . . . . . . . . . . . 354
12.8.1 Designing a Sorting Network . . . . . . . . . . . . . . 354
12.9 Sample Sorting . . . . . . . . . . . . . . . . . . . . . . . . . . 357
12.10Distributed Coordination . . . . . . . . . . . . . . . . . . . . 360
12.11Chapter Notes . . . . . . . . . . . . . . . . . . . . . . . . . . 361
12.12Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 362

[Kimo Crossman]

Powerpoint slides for chapter 12 are here:
http://www.elsevierdirect.com/companion.jsp?ISBN=9780123705914

http://courses.csail.mit.edu/6.852/08/papers/lists-book-chapter.pdf

[mikelaud]

On Mar 23, 11:16 pm, Landmann <landmann_...@gmx.de> wrote:
> Also proper alignment is missing here to prevent sharing and I find it

GCCs alignment
on my 64 bit system:
sizeof(ConcurrentCounter_default): 16
sizeof(ConcurrentCounter_aligned): 16
sizeof(ConcurrentCounter_packed): 16

on my 32 bit system:
sizeof(ConcurrentCounter_default): 8
sizeof(ConcurrentCounter_aligned): 16
sizeof(ConcurrentCounter_packed): 8

do you think counter fail in last case ?

> counterintuitive to reverse the operations for the 2nd thread.

1) counter overflow 2 times later with reverse
2) counter with reverse - count forward after overflow

[Landmann]

> > Also proper alignment is missing here to prevent sharing and I find it
> GCCs alignment

>[...]
That was not the alignment I was thinking of, I was thinking about
cache lines.

> 1) counter overflow 2 times later with reverse

I don't see that. If a+b becomes too big for your
data type than a-(-b) is to big too.

> 2) counter with reverse - count forward after overflow

Counting direction does not depend on overflow but on how you
call the methods. Your counter has two directions, it can overflow/
wrap-around
in both and will be monoton on all other places if you use
one specific direction.

[mikelaud]

On Mar 24, 11:05 am, Landmann <landmann_...@gmx.de> wrote:
> > > Also proper alignment is missing here to prevent sharing and I find it
> > GCCs alignment
> >[...]
>
> That was not the alignment I was thinking of, I was thinking about
> cache lines.

ok
use without volatile and cpu cache like this:

void* shm = takeShm();
ConcurrentCounter* counter = (ConcurrentCounter*) shm;
counter->...

> > 1) counter overflow 2 times later with reverse
>
> I don't see that. If a+b becomes too big for your
> data type than a-(-b) is to big too.
>
> > 2) counter with reverse - count forward after overflow
>
> Counting direction does not depend on overflow but on how you
> call the methods. Your counter has two directions, it can overflow/
> wrap-around
> in both and will be monoton on all other places if you use
> one specific direction.

Thanks for comments.
Yes, you right.
But this simple counter has bug ! :)
because abs(INT_MIN) == INT_MIN

so - final code must be like this:

class ConcurrentCounter {

private: // counters

unsigned long mCounter_byFirstThread;
unsigned long mCounter_bySecondThread;

public: // init

ConcurrentCounter() {
mCounter_byFirstThread = 0;
mCounter_bySecondThread = 0;
}

public: // interface for first thread

void increment_byFirstThread() { mCounter_byFirstThread++; }
void decrement_byFirstThread() { mCounter_byFirstThread--; }

public: // interface for second thread

void increment_bySecondThread() { mCounter_bySecondThread++; }
void decrement_bySecondThread() { mCounter_bySecondThread--; }

public: // concurrent interface

unsigned long getCounter() {
return (mCounter_byFirstThread + mCounter_bySecondThread);
}

};

[Landmann]

> ok
> use without volatile and cpu cache like this:
>
> void* shm = takeShm();
> ConcurrentCounter* counter = (ConcurrentCounter*) shm;
> counter->...

No, that is not enough. Within that ShM-Section both counting
variables (mCounter_byXXX) might be located within the same cache
line. So either one allocated them seperately (which breaks your 'one-
class' design) or the class itself has to ensure that there is enough
padding in between.

[mikelaud]

> No, that is not enough. Within that ShM-Section both counting
> variables (mCounter_byXXX) might be located within the same cache
> line. So either one allocated them seperately (which breaks your 'one-
> class' design) or the class itself has to ensure that there is enough
> padding in between.

I make small test below,
but don't see breaks.

Do you can show - how break it ?


Source:

#include <stdio.h>
#include <pthread.h>
#include <unistd.h>

using namespace std;

struct ConcurrentCounter {

public: // counters

unsigned long mCounter_byFirstThread;
unsigned long mCounter_bySecondThread;

public: // interface for first thread

void increment_byFirstThread() { mCounter_byFirstThread++; }
void decrement_byFirstThread() { mCounter_byFirstThread--; }

public: // interface for second thread

void increment_bySecondThread() { mCounter_bySecondThread++; }
void decrement_bySecondThread() { mCounter_bySecondThread--; }

public: // concurrent interface

unsigned long getCounter() {
return (mCounter_byFirstThread + mCounter_bySecondThread);
}

} __attribute__((__packed__));

int COUNTER_COUNT = 10000000;
int MEMORY_SIZE = 1000;
ConcurrentCounter* gCounter;

void* functionThread1(void* arg) {
printf("functionThread1... \n");
for (int i = 0; i < COUNTER_COUNT; i++) {
gCounter->increment_byFirstThread();
}
sleep(3);
printf("(thread1) counter: %ld \n", gCounter->getCounter());
sleep(3);
printf("functionThread1 done. \n");
return 0;
}

void* functionThread2(void* arg) {
printf("functionThread2... \n");
for (int i = 0; i < COUNTER_COUNT; i++) {
gCounter->increment_bySecondThread();
}
sleep(3);
printf("(thread2) counter: %ld \n", gCounter->getCounter());
sleep(3);
printf("functionThread2 done. \n");
return 0;
}

int main (int argc, char *argv[]) {

char* memoryChunk = new char[MEMORY_SIZE];
gCounter = (ConcurrentCounter*) (memoryChunk);

pthread_t thread1, thread2;
pthread_create(&thread1, 0, functionThread1, 0);
pthread_create(&thread2, 0, functionThread2, 0);
pthread_join(thread1, 0);
pthread_join(thread2, 0);
printf("counter: %ld \n", gCounter->getCounter());
printf("done. \n");
}


Output:

(thread1) counter: 20000000
(thread2) counter: 20000000
functionThread1 done.
functionThread2 done.
counter: 20000000
done.

[Landmann]

Sharing a cache line does not break the algorithm, it only slows it
down.
Image two threads running on two cores...the cache line containing
both values then has to travel back and forth between those two.
However, if you call getCounter very frequently it won't make a big
difference because you need the two values anyways.

[mikelaud]

Thanks Landmann

[mikelaud]

> Counting direction does not depend on overflow but on how you
> call the methods. Your counter has two directions, it can overflow/
> wrap-around
> in both and will be monoton on all other places if you use
> one specific direction.

PS: signed counter is not monoton
because (INT_MIN__by_real_OS/HARDWARE) - 1 == (INT_MIN__by_ISO_C)

[Landmann]

Which exotic hardware and compiler are you using?
There is no INT_MIN__by_ISO_C, the standard only guarantees "at least"
values.
On all HW I used so far it matched the hardware's minimum values (but
that does
not count as an argument, of course).

[mikelaud]

Yes,
ISO guaranted "at least" INT_LEASTN_MIN == -(2^(N-1) -1) // vs
INTN_MIN == -(2^(N-1))

and gnu gcc NOT guaranted abs() for INTN_MIN:

Most computers use a two's complement integer representation,
in which the absolute value of INT_MIN (the smallest possible int)
cannot be represented;
thus, abs (INT_MIN) is not defined.