I realized a little while after writing my previous message that I was probably misinterpreting you. I was envisioning you using box-cas! on a box containing a functional queue, so there would be no need to synchronize. You’d just pull the queue out of the box, functionally update it, and use box-cas! to store the new result back. But your original program is using an imperative queue, so it seems plausible you really were using box-cas! to implement a spinlock. Then you would indeed be busy-waiting, after all!
Rereading Matthew’s original email, I have no idea if he was suggesting to use a spinlock or to do something closer to what I had in mind. Either way, I thought it sounded fun to try to implement a lock-free imperative queue in Racket. Then (theoretically) you’d get the best of both worlds: less duplicated work and less allocation than the functional approach (and allocation is expensive for futures!), but no busy-waiting. Here is my solution: https://gist.github.com/lexi-lambda/c54c91867f931b56123e3c595d8e445a As far as I can tell, it works nicely, and it’s not terribly complicated. Inspecting the behavior of my test cases in the futures visualizer, it seems to be doing good things. But I found I needed to use Matthew’s threads + futures trick, and in the process, I discovered a small subtlety needed to make it actually work. Here’s a self-contained program that reproduces the issue I ran into: #lang racket (require racket/logging) (define (slow-sum) (for/sum ([j (in-range 100000000)]) 1)) (define (go) (define workers (for/list ([i (in-range 8)]) (thread (λ () (touch (future slow-sum)))))) (for-each thread-wait workers)) (with-logging-to-port #:logger (current-logger) (current-output-port) (thunk (go) (newline) (newline) (newline) (go)) 'debug 'future) This runs the `go` procedure twice back-to-back, printing future trace messages to stdout. The first execution is good; futures start up in parallel: future: id -1, process 0: created; time: 1590334415654.675049 future: id 1, process 1: started work; time: 1590334415654.749023 future: id 1, process 0: paused for touch; time: 1590334415654.894043 future: id -1, process 0: created; time: 1590334415654.912109 future: id 2, process 2: started work; time: 1590334415654.934082 future: id 2, process 0: paused for touch; time: 1590334415655.214111 future: id 1, process 1: completed; time: 1590334415878.041992 future: id 1, process 1: ended work; time: 1590334415878.049072 future: id 1, process 0: resumed for touch; time: 1590334415878.070068 future: id 2, process 2: completed; time: 1590334415878.167969 future: id 2, process 2: ended work; time: 1590334415878.173096 future: id 2, process 0: resumed for touch; time: 1590334415878.217041 (I reduced the number of futures here from 8 to 2 for this run to keep the log messages from being uselessly verbose for an email.) However, on the second execution, I get no parallelism at all: future: id -1, process 0: created; time: 1590334415878.292969 future: id 3, process 0: started work; time: 1590334415878.298096 future: id -1, process 0: created; time: 1590334415903.156006 future: id 4, process 0: started work; time: 1590334415903.163086 future: id 3, process 0: completed; time: 1590334416300.748047 future: id 3, process 0: ended work; time: 1590334416300.749023 future: id 4, process 0: completed; time: 1590334416322.684082 future: id 4, process 0: ended work; time: 1590334416322.684082 What’s going on? The problem is that `touch` is getting called before the futures have a chance to get started (possibly because the VM is now warmed up and things run faster?). Normally, that would only happen if the futures were really, really short: the first `touch` would run the first future on the main thread, and the other futures would start up in parallel while that first one is running. But in this program, each future is started on its own (green) thread, so I essentially created a race between the thread scheduler and the future scheduler. It seems splitting the future creation from the thread creation is enough to make this issue go away: (define (go) (define futures (for/list ([i (in-range 8)]) (future slow-sum))) (define workers (for/list ([f (in-list futures)]) (thread (λ () (touch f))))) (for-each thread-wait workers)) Now the futures always start up in parallel. This seems like it’s probably pretty reliable, so it isn’t really a problem, but I found the behavior surprising. It suggests the thread and future schedulers are blissfully unaware of one another: the thread scheduler is perfectly happy to run dozens of futures concurrently on the main OS thread rather than kick some of them onto another core. Normally this is something that work-stealing could fix, but it doesn’t seem like the futures scheduler ever steals work from futures executing on the main thread (presumably because those aren’t “real” futures at all). Perhaps someone will find this information useful or interesting... or perhaps not. :) Alexis -- You received this message because you are subscribed to the Google Groups "Racket Users" group. To unsubscribe from this group and stop receiving emails from it, send an email to racket-users+unsubscr...@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/racket-users/2FC91E93-0F70-4076-8D67-6B1E8527A9B8%40gmail.com.
