Significant Garbage Collection Improvement For Emacs: Reducing Wall Clock Latency For sweep_conses By 50%.

Awesome. Are you planning to submit it?

Yeah, I wanted to show it publicly first because it's an easy patch to apply.

Great, thanks.

This is amazing!

https://tdodge.consulting/blog/eshell/background-output-thread This is also quite nice :)

Love to see it!

Very exciting, but your page fails to load in Firefox.

Which version of firefox are you using? It renders correctly for me on 106.0.1 (64-bit) on Mac OS I'd like to figure out what's going on here, but so that you can see the page in the meantime, here's a version that has less dynamic elements: [https://tdodge.consulting/blog/living-the-emacs-garbage-collection-dream-simple.html](https://tdodge.consulting/blog/living-the-emacs-garbage-collection-dream-simple.html)

Yes, that works, thank you! I'm using 105.0.3, which I realise now is slightly out of date, but not by much. I just see a blank page. I'll update now and see if it's fixed.

There were some service worker issues from prior versions of the website. I just pushed a new change that might fix the regular page on your end as well

This is seriously impressive, but the pessimistic voices in my head are telling me that the random crash inducing upper limit is probably platform-specific and impossible to increase reliably

Yeah, I would not be surprised if that was the case. I'm somewhat concerned about trying to upstream this because I wouldn't be surprised if 1 << 15 doesn't work on other platforms as well. Worst case scenario though, it'd work well as a configure flag to get a little extra optimization.

Awesome, always inspired when stuff like this is found...

Yes, updating Firefox didn't fix it, but your recent change did. Thanks!

&#x200B; Sounds great, thanks for letting me know about it. I'm glad to hear it works correctly now.

Excellent stuff! When I was working on Mono (SGen) we saw similar improvements with a tasteful sprinkling of prefetches during marking. Basically, an arbitrary heap graph is pathologically bad for cache overall, but fortunately we have nearly static knowledge of what we’re going to do, since we’re pretty much going to dereference *everything*. And of course the graphs are very *non*-arbitrary, since there are chunks of high locality. So if Emacs’ GC isn’t already doing so, just prefetching the next handful of pointers in the marking queue is a relatively simple way to tighten up the pipeline a lot.

You can just press F5. Worked for me.

I just looked at your article. When I first looked at it, there was no text, just blue background, but after pressing F5 (to reload) it worked. By the way, good job, thanks for writing it.

Awesome comment! Emacs' GC is not already doing that. I'll definitely look into trying that soon, since that sounds like it'd be relatively easy to implement, and I could imagine how that would improve it even further. &#x200B; Thanks for the suggestion / expertise!

/u/nnreddit-user should be interested.

I would be happy for someone to prove me wrong, but I don't think this gain is really coming from reducing branch misprediction, it is coming from cache friendly behavior of arrays. You have essentially taken the block size form 1024 to 32768 which is 32 times the size. basically you have replaced the linked list with one giant array (which is why I would guess that you are not seeing any benefits over 2^15, because you are not allocating enough conses in your micro-benchmark to fill something larger then 32k). Even if the branch predictor was able to get all the branch predictions correct, you are still jumping around the heap with a smaller block size. The prefectcher will not be able to load those cache lines without delay cycles, regardless of branch predictor accuracy (though there will be less delay with hit instead of miss). However with linear traversal it can load the next cache line well before it is needed. I would expect that just adding some prefetch annotations like /u/evincarofautumn suggested could give a similar benefit.

And you would be wrong.

It also did the blank page then loaded on page reload for me on Linux Chromium just now (so your fix was likely not effective?).

Yeah, your narrative sounds correct. I also did a test with L2\_RQSTS.PF\_HIT and L2\_RQSTS.PF\_MISS, and the difference also roughly correlates, although to a lesser extent than the branch mispredictions which is why I did the original attribution. I probably should've included that in the original post as well. I'll update the post to reflect that. &#x200B; Edit: The benchmark is producing 105,910,837 conses, so I don't think that part of the explanation is correct, but the rest sounds correct to me. 2nd Edit: There's a large gap in the middle of running sweep\_conses in the PF hit vs miss metric in the 1 << 10 case given how I'm measuring it, so it's hard for me to conclude that that is the correct explanation. Let me know if I'm using the wrong performance counters for this, and I'll re-run with the correct ones.

Not bad for two bits flipped! (it's a single character change)

Interesting. It sounds like I am underestimating the performance impact of the misprediction. I would assume it was less then the length of the CPU pipe, which would be around 20 cycles. I expected that to be dwarfed by the actual work in being done in `sweep_conses`. Maybe the CPU is smart enough to prefetch significantly earlier then the actual deference. I would be interested to see if using `__builtin_prefetch` with 1 << 10 is similar or not. Either way very interesting article. I am using your Emacs fork with the buffering update and loving it!

Anyone know if this has been merged yet? o.o

That's awesome to hear that you're using the background output thread fork. I wasn't sure if anyone else was running it haha. I'm working on making it support async writes too, to smooth out some performance issues with large buffers and eglot / flymake. I'll probably fork it out to it's own branch, currently it's commingled with other changes that wouldn't necessarily make sense to push upstream on https://github.com/tyler-dodge/emacs/tree/tyler-main-2

It has not yet. I've been holding off on the effort of getting it ready to push it upstream in favor of working on adding background thread writing to subprocesses. My latest changes are on [https://github.com/tyler-dodge/emacs/tree/tyler-main-2](https://github.com/tyler-dodge/emacs/tree/tyler-main-2) however, I'm planning on pushing a branch with the read/write process background thread changes isolated soon.

Are you planning/have you already tried to submit the original buffer patch to mainline Emacs?

I have done the initial setup for signing over the copyright for the changes, but have not done any of the work past that point. I'm not sure when I will have the time to push for it to get accepted. &#x200B; There's also probably better ways to manage synchronization between the background thread and the main thread than what I implemented, since I optimized a bit for ease of development.

Why the downvote? Aren't you interested in emacs garbage collection?

On a totally unrelated note, can I ask what you used to make those diagrams? They look really good.

Which diagrams specifically? * The charts are [https://www.chartjs.org/docs/latest/](https://www.chartjs.org/docs/latest/) * The performance counter views are screenshots of Apple's [Instruments.app](https://Instruments.app). * The diagram in the background output thread is html + tailwindcss.