3 ms·

I could just move a hashmap into it's own thread, but then I have to deal with the problem of communicating with that thread - this will inevitably involve some

I could just move a hashmap into it's own thread, but then I have to deal with the problem of communicating with that thread - this will inevitably involve some kind of a lock-free queue or plain old array with a lock. Otherwise, what is the point? Or am I missing something fundamental about this?

naasking 9y ago
To some extent. ffwd appears to use sockets. However, they also appear to batch requests so the single thread managing the shared abstraction accepts multiple requests simultaneously and responds to them all in a single round trip. So amortizing that overhead combined with all the cache benefits of single threading appears to be quite an advantage. I still have to go through the paper in detail to see if there's something else that would impact this bottom line.
- jeriksson 9y ago
  There are no sockets in ffwd - everything is done by shared memory within a single process. By "round trip", we refer to communication latency across the CPU interconnect.
  - naasking 9y ago
    Strange because the paper mentions sockets 36 times, even in the sections discussing the interconnect. Maybe I missed something in my skim since I haven't read it in detail yet.
    - jsnell 9y ago
      That's talking about physical CPU sockets, not the socket API :)
jsnell 9y ago
There are two points. One is that having just one thread access the data structure gives optimal cache locality. The other is that locking causes full serialization: if 8 threads want to access a data structure protected by a lock at the same time, you need 8 full cache coherency round-trips. Locking also causes lots of ping-pong on the cache line that contains the lock. This scheme does away with the serialization by allowing batching of operations. If 8 threads need to access a data structure at the same time, their requests can be handled in a single round-trip. It does away with the ping-pong by making every single cache-line have just one writer. (I think it doesn't need locks or atomic ops, just TSO.) Which isn't to say it's a free lunch. Two probable downsides: You need to care about whether you have the right mix of threads doing real work and threads that are just thin shims on some data structure. I bet that the data structure threads have to be polling for requests in a busy-loop for this scheme to have good performance. This would be a major problem for most applications.
- jeriksson 9y ago
  You are right, the "data structure threads", which we call servers, poll on requests in a busy loop. If your data structures aren't very busy, dedicating a thread to serving the data structures may not be a good trade-off, in which case you don't want to use delegation. Note, however, that a single server can host any number of data structures, core counts are growing rapidly, and hyperthreading doubles the number of available hardware threads, making the trade-off easier to swallow.
gumby 9y ago
The point of the paper is in the summary: yes, you have all of that overhead, but you have locking overhead already. And in exchange for the queuing overhead you may get significantly better performance if the other thread is on another processor due to cache "hot spot" effects

naasking 9y ago

To some extent. ffwd appears to use sockets. However, they also appear to batch requests so the single thread managing the shared abstraction accepts multiple requests simultaneously and responds to them all in a single round trip. So amortizing that overhead combined with all the cache benefits of single threading appears to be quite an advantage. I still have to go through the paper in detail to see if there's something else that would impact this bottom line.

jeriksson 9y ago
There are no sockets in ffwd - everything is done by shared memory within a single process. By "round trip", we refer to communication latency across the CPU interconnect.
- naasking 9y ago
  Strange because the paper mentions sockets 36 times, even in the sections discussing the interconnect. Maybe I missed something in my skim since I haven't read it in detail yet.
  - jsnell 9y ago
    That's talking about physical CPU sockets, not the socket API :)

jsnell 9y ago

There are two points. One is that having just one thread access the data structure gives optimal cache locality. The other is that locking causes full serialization: if 8 threads want to access a data structure protected by a lock at the same time, you need 8 full cache coherency round-trips. Locking also causes lots of ping-pong on the cache line that contains the lock. This scheme does away with the serialization by allowing batching of operations. If 8 threads need to access a data structure at the same time, their requests can be handled in a single round-trip. It does away with the ping-pong by making every single cache-line have just one writer. (I think it doesn't need locks or atomic ops, just TSO.) Which isn't to say it's a free lunch. Two probable downsides: You need to care about whether you have the right mix of threads doing real work and threads that are just thin shims on some data structure. I bet that the data structure threads have to be polling for requests in a busy-loop for this scheme to have good performance. This would be a major problem for most applications.

jeriksson 9y ago
You are right, the "data structure threads", which we call servers, poll on requests in a busy loop. If your data structures aren't very busy, dedicating a thread to serving the data structures may not be a good trade-off, in which case you don't want to use delegation. Note, however, that a single server can host any number of data structures, core counts are growing rapidly, and hyperthreading doubles the number of available hardware threads, making the trade-off easier to swallow.

gumby 9y ago

The point of the paper is in the summary: yes, you have all of that overhead, but you have locking overhead already. And in exchange for the queuing overhead you may get significantly better performance if the other thread is on another processor due to cache "hot spot" effects