<blockquote class="gmail_quote" style="margin-top:0px;margin-right:0px;margin-bottom:0px;margin-left:0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">As far as I know (correct me if I'm wrong), when you execute a CPU<br>
instruction that writes to a memory location that's also cached by<br>another CPU core, will cause the system to execute its cache coherence<br>protocol. This protocol will invalidate the cache lines in other CPU<br>cores for this memory location.</blockquote>
<div><br></div><blockquote class="gmail_quote" style="margin-top:0px;margin-right:0px;margin-bottom:0px;margin-left:0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">
When I say "memory locations" I actually mean cache lines. Memory is<br>cached in blocks of usually 64 bytes. Google "false sharing".</blockquote><div><br></div><div>If this is right then there should be no advantage of processes over threads considering point (2). Cache invalidations will only occur for the data that really needs to be shared, not for all program's data. Whether you use easy thread-memory-sharing or not-so-easy-inter-process-memory-sharing, in any case there would be cache collisions among the cores whenever you write to shared variables.</div>
<div><br></div><div>If there are no cache invalidations when two threads _read_ from the same memory location, then threads even offer an advantage of saving memory footprint as read-only data is not duplicated (if I understand it right).</div>
<div><br></div><div>Practical recommendations that I can conclude from this:</div><div><br></div><div>- carefully consider what data really needs to be shared among threads, do not share things that are easier to duplicate (e.g. event loops)</div>
<div>- do not place variables writable by different threads close to each other (e.g. whithin same structs) so they do not fall into the same cache line</div><div> </div><br><div class="gmail_quote">On Mon, Jan 2, 2012 at 2:05 PM, Hongli Lai <span dir="ltr"><<a href="mailto:hongli@phusion.nl">hongli@phusion.nl</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div class="im">On Mon, Jan 2, 2012 at 10:29 AM, Yaroslav <<a href="mailto:yarosla@gmail.com">yarosla@gmail.com</a>> wrote:<br>

> (2.1) At what moments exactly this syncronizations occur? Is it on every<br>
> assembler instruction, or on every write to memory (i.e. on most variable<br>
> assignments, all memcpy's, etc.), or is it only happening when two threads<br>
> simultaneously work on the same memory area (how narrow is definition of the<br>
> area?)? Perhaps there are some hardware sensors indicating that two cores<br>
> have same memory area loaded into their caches?<br>
<br>
</div>As far as I know (correct me if I'm wrong), when you execute a CPU<br>
instruction that writes to a memory location that's also cached by<br>
another CPU core, will cause the system to execute its cache coherence<br>
protocol. This protocol will invalidate the cache lines in other CPU<br>
cores for this memory location. MESI is a protocol that's in wide use.<br>
See <a href="http://www.akkadia.org/drepper/cpumemory.pdf" target="_blank">http://www.akkadia.org/drepper/cpumemory.pdf</a><br>
<br>
You can see your multi-core system as a network of computers. You can<br>
see each CPU cache as a computer's memory, and the main memory as a<br>
big NFS server.<br>
<div class="im"><br>
<br>
> (2.2) Are there ways to avoid unnecessary synchronizations (apart from<br>
> switching to processes)? Because in real life there are only few variables<br>
> (or buffers) that really need to be shared between threads. I don't want all<br>
> memory caches re-synchronized after every assembler instruction.<br>
<br>
</div>If other CPU cores' caches do not have this memory location cached,<br>
then the CPU does not need to do work to ensure the other caches are<br>
coherent. In other words, just make sure that you don't read or write<br>
to the same memory locations in other threads or processes. Or, if you<br>
do read from the same memory locations in other threads, you shouldn't<br>
have more than at most 1 writer if you want things to be fast. See<br>
"Single Writer Principle":<br>
<a href="http://mechanical-sympathy.blogspot.com/2011/09/single-writer-principle.html" target="_blank">http://mechanical-sympathy.blogspot.com/2011/09/single-writer-principle.html</a><br>
<br>
When I say "memory locations" I actually mean cache lines. Memory is<br>
cached in blocks of usually 64 bytes. Google "false sharing".<br>
<br>
That said, locks are still necessary. Locks are usually implemented<br>
with atomic instructions, but they're already fairly expensive and<br>
will continue to become more expensive as CPU vendors add more cores.<br>
The JVM implements what they call "biased locking" which avoids atomic<br>
instructions if there's little contention on locks:<br>
<a href="http://mechanical-sympathy.blogspot.com/2011/11/java-lock-implementations.html" target="_blank">http://mechanical-sympathy.blogspot.com/2011/11/java-lock-implementations.html</a><br>
The benchmark on the above post turned out to be wrong; he fixed the<br>
benchmark here:<br>
<a href="http://mechanical-sympathy.blogspot.com/2011/11/biased-locking-osr-and-benchmarking-fun.html" target="_blank">http://mechanical-sympathy.blogspot.com/2011/11/biased-locking-osr-and-benchmarking-fun.html</a><br>
As you can see, biased locking results in a huge performance boost.<br>
Unfortunately I don't know any pthread library that implements biased<br>
locking.<br>
<div class="im"><br>
<br>
> Point (3) is completely unclear to me. What kind of process data is this all<br>
> about? How often is this data need to be accessed?<br>
<br>
</div>This depends on your application. In<br>
<a href="http://lists.schmorp.de/pipermail/libev/2011q4/001663.html" target="_blank">http://lists.schmorp.de/pipermail/libev/2011q4/001663.html</a> I presented<br>
two applications, one using threads and one using child processes. The<br>
one using child processes can store its working data in global<br>
variables. These global variables have a constant address, so<br>
accessing them only takes 1 step. In the application that uses<br>
threads, each thread has to figure out where its working data is by<br>
first dereferencing the 'data' pointer. That's two steps. You can't<br>
use global variables in multithreaded applications without locking<br>
them (which makes things slow). In multiprocess software you don't<br>
have to lock because processes don't share memory.<br>
<br>
However I don't think this really makes that much of a difference in<br>
practice. Using global variables is often considered bad practice by<br>
many people. I tend to avoid global variables these days, even when<br>
writing non-multithreaded software, because not relying on global<br>
variables automatically makes my code reentrant. This makes it easy to<br>
use my code in multithreaded software later, and makes things easier<br>
to test in unit tests and easier to maintain.<br>
<div class="im"><br>
<br>
> (4.1) Can TLS be used as a means of _unsharing_ thread memory, so there are<br>
> no synchronizations costs between cpu cores?<br>
<br>
</div>Yes. Though of course you can still do strange things such as passing<br>
a pointer to a TLS variable to another thread, and have the other<br>
thread read or write to it. Just don't do that.<br>
<br>
You don't necessarily need to use __thread for that. The 'void *data'<br>
argument in pthread_create's callback is also (conceptually)<br>
thread-local storage. You can store your thread-local data in there.<br>
<div class="im"><br>
<br>
> (4.1) Does TLS impose extra overhead (performance cost) compared to regular<br>
> memory storage? Is it recommended to use in performance-concerned code?<br>
<br>
</div>It requires an extra indirection. The app has to:<br>
1. Figure out which thread it's currently running on.<br>
2. Look up the location of the requested data based on the current thread ID.<br>
How fast this is and whether there's any locking involved depends on<br>
the implementation. I've benchmarked __thread in the past and<br>
glibc/NTPL's implementation seems pretty fast. It was fast enough for<br>
the things I wanted to do it with, though I didn't benchmark how fast<br>
it is compared to a regular pointer access.<br>
<div class="im"><br>
<br>
> For example, I have a program that has several threads, and each thread has<br>
> some data bound to that thread, e.g. event loop structures. Solution number<br>
> one: pass reference to this structure as a parameter to every function call;<br>
> solution number two: store such reference in TLS variable and access it from<br>
> every function that needs to reference the loop. Which solution will work<br>
> faster?<br>
<br>
</div>This really depends on the TLS implementation. You should benchmark it.<br>
<div class="im HOEnZb"><br>
--<br>
Phusion | Ruby & Rails deployment, scaling and tuning solutions<br>
<br>
Web: <a href="http://www.phusion.nl/" target="_blank">http://www.phusion.nl/</a><br>
E-mail: <a href="mailto:info@phusion.nl">info@phusion.nl</a><br>
Chamber of commerce no: 08173483 (The Netherlands)<br>
<br>
</div><div class="HOEnZb"><div class="h5">_______________________________________________<br>
libev mailing list<br>
<a href="mailto:libev@lists.schmorp.de">libev@lists.schmorp.de</a><br>
<a href="http://lists.schmorp.de/cgi-bin/mailman/listinfo/libev" target="_blank">http://lists.schmorp.de/cgi-bin/mailman/listinfo/libev</a><br>
</div></div></blockquote></div><br>