4 ms·

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

by sakras 3y ago

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.

samsquire 3y ago
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.
- sakras 3y ago
  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
yvdriess 3y ago
FYI Cray developed an interesting allocator for scaling to a massive amount of threads https://dl.acm.org/doi/10.1145/1122971.1122999 https://dl.acm.org/doi/10.1145/1122971.1122999
menaerus 3y ago
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.
- sakras 3y ago
  > 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.

by sakras 3y ago

samsquire 3y ago

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.

sakras 3y ago
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

yvdriess 3y ago

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

menaerus 3y ago

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.

sakras 3y ago
> 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.