saturn icon indicating copy to clipboard operation
saturn copied to clipboard

Optimize SPSC queue

Open polytypic opened this issue 1 year ago • 2 comments

This PR optimizes the SPSC queue.

See the individual commits to better understand the motivation behind the optimizations.

Here is a run of the benchmarks on my M3 Max before the optimizations:

➜  saturn git:(rewrite-bench) ✗ dune exec --release -- ./bench/main.exe -budget 1 Single | jq '[.results.[].metrics.[] | select(.name | test("over")) | {name, value}]'
[                                    
  {
    "name": "messages over time/2 workers, capacity 1",
    "value": 6.500299359098922
  },
  {
    "name": "messages over time/2 workers, capacity 8",
    "value": 12.632201914378621
  },
  {
    "name": "messages over time/2 workers, capacity 64",
    "value": 14.90261050891111
  },
  {
    "name": "messages over time/2 workers, capacity 512",
    "value": 14.960086955505428
  },
  {
    "name": "messages over time/2 workers, capacity 4096",
    "value": 20.06888141824778
  },
  {
    "name": "messages over time/2 workers, capacity 32768",
    "value": 22.94386410808166
  }
]

Here is a run of the benchmarks after the optimizations:

➜  saturn git:(optimize-spsc-queue) ✗ dune exec --release -- ./bench/main.exe -budget 1 Single | jq '[.results.[].metrics.[] | select(.name | test("over")) | {name, value}]'
[                                    
  {
    "name": "messages over time/2 workers, capacity 1",
    "value": 6.868795322207784
  },
  {
    "name": "messages over time/2 workers, capacity 8",
    "value": 18.420713908583064
  },
  {
    "name": "messages over time/2 workers, capacity 64",
    "value": 30.26195314050038
  },
  {
    "name": "messages over time/2 workers, capacity 512",
    "value": 38.7165046104334
  },
  {
    "name": "messages over time/2 workers, capacity 4096",
    "value": 123.22902197665648
  },
  {
    "name": "messages over time/2 workers, capacity 32768",
    "value": 270.82312457121435
  }
]

TODO:

  • [ ] Add comments on the use/lack of fences in the code.

polytypic avatar Jan 19 '24 14:01 polytypic

Thanks for the PR ! All the optimizations (except maybe the ones mentioned in my previous message :p) are great and thanks again for making the git history so readable. And obviously, the gain in performance is amazing !

lyrm avatar Feb 07 '24 16:02 lyrm

I should have added that the optimization with the cashes is very cool !!

lyrm avatar Feb 08 '24 17:02 lyrm

The changes proposed in this PR have already been merged in two different PRs (#133 and #135) that separate "safe" and "unsafe" optimizations. Thanks @polytypic for all this work!

lyrm avatar Jun 10 '24 09:06 lyrm