5 ms·

Actor-based dynamic language author here. (Doesn't matter which one; I think I speak for all of us.) Thank you for being honest with us; we are not a very perfo

Actor-based dynamic language author here. (Doesn't matter which one; I think I speak for all of us.) Thank you for being honest with us; we are not a very performance-oriented group sometimes. We're generally in favor of things which accelerate message passing between shared-nothing concurrent actors. Hardware mailboxes or transactional memory are nifty. OS-supported message queues are nifty; can those be lowered to hardware in a useful way?

ori_b 10y ago
It seems to me that Intel TSX and general work on improved atomics is what you want. The high level constructs themselves probably shouldn't be directly in hardware.
qznc 10y ago
> Hardware mailboxes or transactional memory If you do them in hardware, they always come bounded. At most n elements of size m bytes and both numbers usually single digit. If you want to lift that limitation, it usually is just as slow as doing it in software.
- dkersten 10y ago
  Unbounded queues are arguably not a good idea (although single digit bounds are possibly too low?), at the very least there would probably need to be some concept of back pressure.
meredydd 10y ago
Well, I never thought I'd be plugging my PhD research here, but: "Asynchronous Remote Stores for Inter-Core Communication" http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.592.1178&rep=rep1&type=pdf http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.592... To my knowledge, this is still the only hardware-assisted message passing scheme that is virtualisable (ie compatible with a "real" OS like Linux). Hardware mailboxes are great, but time-sharing OSs can't deal with finite hardware resources that can't be swapped out easily. Software-based queues die a fiery death thanks to cache coherency - reading something that another core just wrote will block you for hundreds of cycles.
- _yosefk 10y ago
  Virtualizable hardware-assisted message passing is awesome. (MIPS for instance had a big fat ISA extension for hardware-assisted message passing and cheap hardware multithreading which Linux couldn't use and they then threw out the window exactly when they introduced hardware virtualization of the entire set of processor resources.) As to software-based queues dying a fiery death - in what scenarios? As I said in a sister comment, I (think that I) know that things work out in computational parallelism scenarios where many tasks are mapped onto a thread pool, TBB-style, that is, I don't think the hardware overhead is ridiculously large in these systems. Where do things go badly? 100K lightweight threads communicating via channels, Go-style?
  - meredydd 10y ago
    Whoa - MIPS virtualised their message passing hardware? How?! Software-based queues die a fiery death when the latency of a send/receive is critical, because you end up stalling on a really slow cache-coherence operation. So, for example, anything like a cross-thread RPC call takes ages (you wait for the transmission and wait for a response, so it's much slower than a function call and often a system call - the Barrelfish research OS suffers a bunch from this). There are also algorithms you just can't parallelise because you can't split them into large chunks, and if you split them into small chunks the cost of communicating so frequently destroys your performance. (Eg there was a brave attempt to parallelise the inner loop of bzip2 - which resists coarse parallelisation thanks to loop-carried dependencies - this way). Software based queues perform just fine on throughput, though - if you're asynchronous enough to let a few messages build up in your message queue, you'll only pay the latency penalty once per cache line when you drain it (and with a good prefetcher, even less than that). The examples you cite are actually both instances of software cunningly working within the limits of slow inter-core communication. Work-queue algorithms typically keep local, per-core queues and only rebalance tasks between cores ("work stealing") infrequently, so as to offset how expensive that operation is. Lightweight threads with blocking messages (like Go or Occam or some microkernels) work by turning most message sends into context switches within one core - when you send a message on a Go channel, you can just jump right into the code that receives it. Again, they can then rebalance infrequently. (For an extra bonus, by making it easy to create 100k "threads", they hope to engage in latency-hiding for individual threads - and once you're in "throughput" mode it's all gravy).
exDM69 10y ago
Have you tried or heard anyone trying to tinker with caching attributes (ie. uncached, write-combining, etc) for message passing buffers? I think you do need to be in kernel mode to be able to change the attributes, but you can access the memory in userspace once set up. Sounds to me like you could have some improvoment in shared-nothing message passing by avoiding traffic on the CPU core interconnect due to unnecessary caching. That said, I only have experience of tinkering with caching attributes in CPU to GPU communication and I'm not very well familiar with the internals of CPU interconnects so take my words with a grain of salt.
- meredydd 10y ago
  Ick, no. Nasty as the latencies of cache coherence are, going out to memory every time will slaughter your performance coming and going. Do not want.
  - exDM69 10y ago
    There are various levels of caching, which have very different performance characteristics with different access patterns from multiple cores. Don't dismiss it outright. You can reduce the pressure on the cache coherency protocol by making different tradeoffs.
    - meredydd 10y ago
      Yes there are, and there were a bunch of interesting research machines in the 90s that played with weird cache modes for shared data. (If you're interested, I can go dig out the literature review section of my thesis for you. There were some weird and wacky schemes, none of which saw industrial deployment). But the bottom line is that the cache options available in modern desktop/server processors won't really help. They all basically disable the cache in one way or another. (They're really intended for controlling memory-mapped devices.) And while the latency of fetching something out of another core's L1 cache is nasty, going all the way out to DRAM for every access is really, really slow. So, I'll stand by my summary, albeit less caustically. While it's an interesting idea, you really don't want to do what you suggest.
_yosefk 10y ago
I'm not sure whether today's coherent caches, atomic operations etc. are a poor fit for what you want to do leaving much room for improvement (I'm sure someone familiar with say the Go stack will be able to say more; I can say that for computational parallelism everything is fine with current hw but there 100K tasks would map to dozens of threads, tops and if you want 100K concurrent actors maybe things look differently, at any rate I don't see how the shared-nothing part creates a problem hardware can solve here, I think maybe there are problems in the (lots and lots of concurrent actors) part but I'm not sure.) Incidentally, IMO shared-nothing is an inherently inefficient model for multiple actors cooperating to perform a single computation, and nothing done in hardware can fully eliminate the cost introduced by the model (and if something can be done is can be done by code analysis transforming the code into a more efficient shared memory model.) This is not to say that there's no value in such a system - far from it, just that it's a poor fit for something things which can only mapped onto it with some overhead that hardware cannot eliminate.

ori_b 10y ago

It seems to me that Intel TSX and general work on improved atomics is what you want. The high level constructs themselves probably shouldn't be directly in hardware.

qznc 10y ago

> Hardware mailboxes or transactional memory If you do them in hardware, they always come bounded. At most n elements of size m bytes and both numbers usually single digit. If you want to lift that limitation, it usually is just as slow as doing it in software.

dkersten 10y ago
Unbounded queues are arguably not a good idea (although single digit bounds are possibly too low?), at the very least there would probably need to be some concept of back pressure.

meredydd 10y ago

Well, I never thought I'd be plugging my PhD research here, but: "Asynchronous Remote Stores for Inter-Core Communication" http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.592.1178&rep=rep1&type=pdf http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.592... To my knowledge, this is still the only hardware-assisted message passing scheme that is virtualisable (ie compatible with a "real" OS like Linux). Hardware mailboxes are great, but time-sharing OSs can't deal with finite hardware resources that can't be swapped out easily. Software-based queues die a fiery death thanks to cache coherency - reading something that another core just wrote will block you for hundreds of cycles.

_yosefk 10y ago
Virtualizable hardware-assisted message passing is awesome. (MIPS for instance had a big fat ISA extension for hardware-assisted message passing and cheap hardware multithreading which Linux couldn't use and they then threw out the window exactly when they introduced hardware virtualization of the entire set of processor resources.) As to software-based queues dying a fiery death - in what scenarios? As I said in a sister comment, I (think that I) know that things work out in computational parallelism scenarios where many tasks are mapped onto a thread pool, TBB-style, that is, I don't think the hardware overhead is ridiculously large in these systems. Where do things go badly? 100K lightweight threads communicating via channels, Go-style?
- meredydd 10y ago
  Whoa - MIPS virtualised their message passing hardware? How?! Software-based queues die a fiery death when the latency of a send/receive is critical, because you end up stalling on a really slow cache-coherence operation. So, for example, anything like a cross-thread RPC call takes ages (you wait for the transmission and wait for a response, so it's much slower than a function call and often a system call - the Barrelfish research OS suffers a bunch from this). There are also algorithms you just can't parallelise because you can't split them into large chunks, and if you split them into small chunks the cost of communicating so frequently destroys your performance. (Eg there was a brave attempt to parallelise the inner loop of bzip2 - which resists coarse parallelisation thanks to loop-carried dependencies - this way). Software based queues perform just fine on throughput, though - if you're asynchronous enough to let a few messages build up in your message queue, you'll only pay the latency penalty once per cache line when you drain it (and with a good prefetcher, even less than that). The examples you cite are actually both instances of software cunningly working within the limits of slow inter-core communication. Work-queue algorithms typically keep local, per-core queues and only rebalance tasks between cores ("work stealing") infrequently, so as to offset how expensive that operation is. Lightweight threads with blocking messages (like Go or Occam or some microkernels) work by turning most message sends into context switches within one core - when you send a message on a Go channel, you can just jump right into the code that receives it. Again, they can then rebalance infrequently. (For an extra bonus, by making it easy to create 100k "threads", they hope to engage in latency-hiding for individual threads - and once you're in "throughput" mode it's all gravy).

exDM69 10y ago

Have you tried or heard anyone trying to tinker with caching attributes (ie. uncached, write-combining, etc) for message passing buffers? I think you do need to be in kernel mode to be able to change the attributes, but you can access the memory in userspace once set up. Sounds to me like you could have some improvoment in shared-nothing message passing by avoiding traffic on the CPU core interconnect due to unnecessary caching. That said, I only have experience of tinkering with caching attributes in CPU to GPU communication and I'm not very well familiar with the internals of CPU interconnects so take my words with a grain of salt.

meredydd 10y ago
Ick, no. Nasty as the latencies of cache coherence are, going out to memory every time will slaughter your performance coming and going. Do not want.
- exDM69 10y ago
  There are various levels of caching, which have very different performance characteristics with different access patterns from multiple cores. Don't dismiss it outright. You can reduce the pressure on the cache coherency protocol by making different tradeoffs.
  - meredydd 10y ago
    Yes there are, and there were a bunch of interesting research machines in the 90s that played with weird cache modes for shared data. (If you're interested, I can go dig out the literature review section of my thesis for you. There were some weird and wacky schemes, none of which saw industrial deployment). But the bottom line is that the cache options available in modern desktop/server processors won't really help. They all basically disable the cache in one way or another. (They're really intended for controlling memory-mapped devices.) And while the latency of fetching something out of another core's L1 cache is nasty, going all the way out to DRAM for every access is really, really slow. So, I'll stand by my summary, albeit less caustically. While it's an interesting idea, you really don't want to do what you suggest.

_yosefk 10y ago

I'm not sure whether today's coherent caches, atomic operations etc. are a poor fit for what you want to do leaving much room for improvement (I'm sure someone familiar with say the Go stack will be able to say more; I can say that for computational parallelism everything is fine with current hw but there 100K tasks would map to dozens of threads, tops and if you want 100K concurrent actors maybe things look differently, at any rate I don't see how the shared-nothing part creates a problem hardware can solve here, I think maybe there are problems in the (lots and lots of concurrent actors) part but I'm not sure.) Incidentally, IMO shared-nothing is an inherently inefficient model for multiple actors cooperating to perform a single computation, and nothing done in hardware can fully eliminate the cost introduced by the model (and if something can be done is can be done by code analysis transforming the code into a more efficient shared memory model.) This is not to say that there's no value in such a system - far from it, just that it's a poor fit for something things which can only mapped onto it with some overhead that hardware cannot eliminate.