Threading tips

(L) [2007/07/25] [Michael77] [Threading tips] Wayback!

Hi,

am am currenly in the process of making my basic memory classes threadsafe. However, since I am quite new to the topic, I have some problems I don´t know how to solve.

I currently use a dynamic array that is allowed to grow when more memory is requested. So I currently have something like this:

(L) [2007/07/25] [playmesumch00ns] [Threading tips] Wayback!

I'm a little fuzzy on this too, but my best guess would be that you can't. You have to lock both 'reads' and 'writes' to anything that is shared. Now obviously putting a big fat mutex around your push function is going to be very inefficient indeed, so you need to lock the data at a higher level, where you can do more work between locking and unlocking so the overhead of those operations is amortised better.

(L) [2007/07/25] [tbp] [Threading tips] Wayback!

I see plenty of issues with such approach (ie what's your Typ copy atomicity like? you really need a write barrier there) without much chances for good performance, but let's say a big lock is against your religion and you don't want to check what the stdlibc++ does.

Without much thinking i'd say when a realloc is due, 'atomically' swap in a temporary area so that you accumulate incident pushes while you alloc & copy stuff around, swap the new area in and stitch whatever was thrown while you were busy as regular pushes. Hmm, that's full of corners cases already heh.

Btw you're going to migrate stuff all around as any thread potentially can allocate and touch it.

note: on x86 if you put the array pointer and index within the same cacheline, the 'locked' increment gives you the assurance 'locked' writes/swaps to the pointer from other cores/cpus will also be visible; but you have to tell the compiler about.
_________________
May you live in interesting times.

[LINK https://gna.org/projects/radius/ radius] | [LINK http://ompf.org/ ompf] | [LINK http://ompf.org/wiki/ WompfKi]

(L) [2007/07/25] [Michael77] [Threading tips] Wayback!

Mmhhh, ok, seems like I should probably choose another way for dealing with these kind of things. I guess, I could get away with a list of arrays more easily anyway.

Does anyone know good resources about all this threading stuff (mutex/write barrier/semaphore)?

(L) [2007/07/26] [tbp] [Threading tips] Wayback!

The more you can constrain the usage, the better it is. In the best case you have (thread) local DynArray that you later collate together, in the worst case you always have a centrally synchronized blob.

I wouldn't bother trying to shove any lockfreeness into the later case, because even with moderate use you'd be killed by contention (imagine x cores/cpus hammering & snooping that same cacheline with those slow 'locked' ops). That's where a lock and it's fixed fee, be it a spinlock (still bad for contention) or OS lock if some scheduling is desirable (or fairness), makes sense as strange as it may seem; but then it depends on usage pattern.
_________________
May you live in interesting times.

[LINK https://gna.org/projects/radius/ radius] | [LINK http://ompf.org/ ompf] | [LINK http://ompf.org/wiki/ WompfKi]

(L) [2007/07/27] [Michael77] [Threading tips] Wayback!

Mmhh, ok, seems like I have a lot to learn about multithreading (but where???). However, I wonder if something like this would work fine or if it has other problems I am not aware of:

(L) [2007/07/27] [tbp] [Threading tips] Wayback!

When things happen is what matters, really.

Now, it's hard to get it wrong if you're merely bumping an index; in fact you don't need to make it volatile (ie on x86, compilers should know such locked op is a full barrier), you just want it to be properly aligned and sitting alone in its cacheline because touching it (the cacheline) in any way will be expensive.

Multicore cpu act like good old SMP, you'd need a NUMA box to uncover nastier concurrency issues.

edit for waldheinz: he said computations are mildly expensive, so the expensive increment should be amortised already (plus it's a dual core box, so it's not as much of a problem yet).
_________________
May you live in interesting times.

[LINK https://gna.org/projects/radius/ radius] | [LINK http://ompf.org/ ompf] | [LINK http://ompf.org/wiki/ WompfKi]

(L) [2007/07/27] [tbp] [Threading tips] Wayback!

The lock prefix can be used on many instructions on x86, but in your case just use an 'xadd'. Look it up [SMILEY Smile]
_________________
May you live in interesting times.

[LINK https://gna.org/projects/radius/ radius] | [LINK http://ompf.org/ ompf] | [LINK http://ompf.org/wiki/ WompfKi]

Threading tips back