Java-Gaming.org Hi !
Featured games (91)
games approved by the League of Dukes
Games in Showcase (806)
Games in Android Showcase (239)
games submitted by our members
Games in WIP (868)
games currently in development
News: Read the Java Gaming Resources, or peek at the official Java tutorials
 
    Home     Help   Search   Login   Register   
Pages: [1]
  ignore  |  Print  
  Sharing data between threads  (Read 5089 times)
0 Members and 1 Guest are viewing this topic.
Offline kaffiene
« Posted 2015-10-03 10:54:50 »

Hiya.  Just for fun I was wanting to see what speed difference would come from doing Conway's game of Life multi threaded vs single threaded.  I'm using a naive implementation where I keep a front and back buffer and swap between these as I process. I didn't want to implement any clever hashing or dead space detection since I'm interested in seeing the difference threading makes, not in implementing the fastest algorithm.

The results I got were these:

Single threaded: 28 million cells/sec
Multithreaded (4 cores): 40 million cells/sec

So that's about a 30% increase.  Now, I've never seen huge speed increases by multithreading and I think my CPU is pretty shit for multithreading (intel Q6700) so I wasn't too surprised but there was one thing I was wondering about which I couldn't find any definitive information about.  The approach I'm taking is to get each thread to render 1/4 of the data.  What I was wondering is whether there is any penalty getting each thread to write into the same array?  I had assumed that as each thread writes to a different area in the array then that should not suffer any kind of slow down due to the threaded access.  Is that correct?

Thanks!
Offline Riven
Administrator

« JGO Overlord »


Medals: 1371
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #1 - Posted 2015-10-03 11:01:45 »

What I was wondering is whether there is any penalty getting each thread to write into the same array?  I had assumed that as each thread writes to a different area in the array then that should not suffer any kind of slow down due to the threaded access.  Is that correct?

If thread A writes into
arr[i]
and thread B reads from or writes into
arr[i+1]
, odds are these values are in the same cache line (which are 64 bytes wide). At this point we get in the realm of false sharing, which you can google if you please. Simply put: try to have your threads not write into memory adjacent to memory that other threads access (reads or writes).

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings!
Offline kaffiene
« Reply #2 - Posted 2015-10-03 11:05:27 »

Sooo.... does that mean the best thing to do is to have each thread having a local buffer for their own portion of the work and copy that to the render thread when complete?
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline Riven
Administrator

« JGO Overlord »


Medals: 1371
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #3 - Posted 2015-10-03 11:14:27 »

Sooo.... does that mean the best thing to do is to have each thread having a local buffer for their own portion of the work and copy that to the render thread when complete?
Memory copies are exceptionally expensive.

As for your case, simply try to have each thread work on data in a set of rows in the grid, not interleaved columns, which would be worst case, obviously). Each row should have its data in a (segment of a) primitive array, say a boolean[] or even a BitSet (which is 8x as memory efficient, although it introduces some computational overhead)

As for whether a 30% performance increase is OK: multi threading introduces some overhead, so it won't help much in small data sets (or few calculations). Try to increase (and later decrease) the grid with factor 4, and see whether that affects the performance gains of multi threading.

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings!
Offline kaffiene
« Reply #4 - Posted 2015-10-03 11:30:46 »

I am doing the thread's work in a contiguous hunk of rows already.  I tried increasing the image size and as you said, that increased the improvement from threading.

Thanks for your advice!

Offline theagentd
« Reply #5 - Posted 2015-10-03 16:34:00 »

Indeed, writing to the same cache line from two different threads causes a cache flush on pretty much each write. I've had code that were reduced to zero scaling with 8 threads due to them all incrementing the same integer counter (was an old preformance measurement variable that wasn't even synchronized). I removed that single x++ and scaling went up to 3.5x on 4 Hyperthreaded cores with 8 threads.

Myomyomyo.
Pages: [1]
  ignore  |  Print  
 
 

 
Riven (587 views)
2019-09-04 15:33:17

hadezbladez (5529 views)
2018-11-16 13:46:03

hadezbladez (2410 views)
2018-11-16 13:41:33

hadezbladez (5790 views)
2018-11-16 13:35:35

hadezbladez (1233 views)
2018-11-16 13:32:03

EgonOlsen (4669 views)
2018-06-10 19:43:48

EgonOlsen (5688 views)
2018-06-10 19:43:44

EgonOlsen (3205 views)
2018-06-10 19:43:20

DesertCoockie (4104 views)
2018-05-13 18:23:11

nelsongames (5125 views)
2018-04-24 18:15:36
A NON-ideal modular configuration for Eclipse with JavaFX
by philfrei
2019-12-19 19:35:12

Java Gaming Resources
by philfrei
2019-05-14 16:15:13

Deployment and Packaging
by philfrei
2019-05-08 15:15:36

Deployment and Packaging
by philfrei
2019-05-08 15:13:34

Deployment and Packaging
by philfrei
2019-02-17 20:25:53

Deployment and Packaging
by mudlee
2018-08-22 18:09:50

Java Gaming Resources
by gouessej
2018-08-22 08:19:41

Deployment and Packaging
by gouessej
2018-08-22 08:04:08
java-gaming.org is not responsible for the content posted by its members, including references to external websites, and other references that may or may not have a relation with our primarily gaming and game production oriented community. inquiries and complaints can be sent via email to the info‑account of the company managing the website of java‑gaming.org
Powered by MySQL Powered by PHP Powered by SMF 1.1.18 | SMF © 2013, Simple Machines | Managed by Enhanced Four Valid XHTML 1.0! Valid CSS!