Hacker News Reader

Comment by sakras | Hacker News Reader

I'm messing around with implementing a parallel runtime system right now^, and I also had to implement a shared-nothing allocator. I ended up making each thread have a Chase-Lev Deque of 2MB pages. If you want to allocate a page, you do the usual pop-or-try-to-steal thing, and if that doesn't work, THEN you do the mmap to get another 2MB page. I was going to benchmark it and write a post about it, but I never got around to it. Glad shared-nothing allocation seems to be a problem worth solving.

^ actually it's basically implemented. I model-checked it with TLA+ and found a bug that I haven't fixed yet. Next up I'm writing a query engine on it.

View on HN

FYI Cray developed an interesting allocator for scaling to a massive amount of threads https://dl.acm.org/doi/10.1145/1122971.1122999

If you're backing up your memory through pages stored in N work-stealing queues (chase-lev deque in this case), doesn't that contradict the shared-nothing architecture? When queue is empty, I understand your allocator will try to steal a page from another queue before it asks an OS for a new 2MB page - and that essentially means synchronization and thus sharing. Also, I think this approach is going to result with bad memory locality since your data will now be spread all over the place, e.g. different queues.

> contradicts shared-nothing architecture

Sort of? The stealing happens very rarely, only when the thread doesn’t have a page. It’s done using relaxed atomics, so synchronization is pretty mild in this case.

> bad data locality

This will be relevant when I make it NUMA-aware, but generally speaking this shouldn’t matter as each page is much bigger than a core’s L2 cache anyway. And also memory living in the deque is freed, I don’t think there’s generally expectations on locality of memory returned to you from the allocator.

This is very interesting!

I am especially interested in how you share memory between threads in your parallel runtime - what thread safety approach do you use?

I've been thinking about static memory as permanent regions that are permanent fixtures and the program flows through them and there must be backpressure when buffers get full.

I just wrote a nonblocking multithreaded barrier with a lock free algorithm.

My threads generally don’t share memory inside the runtime. The only time they touch each others’ stuff is when they perform work stealing or memory stealing, and that’s all provided by the CL-Deque

Reply on news.ycombinator.com