Hello- I'm looking to implement a new programming language using LLVM as a
back-end. Generally it's looking very good, I only have one question.
The language is going to be an ML-style language, similiar to Haskell or
Ocaml, except explicitly multithreaded and (like Haskell but unlike Ocaml)
purely functional. But this means that speed of allocation is essential-
purely functional languages have been measured to allocate an average of 1
word every 6 instructions. Generally they allocate larger blocks (often
10-20 words at a shot) less often, but we're still talking about an insane
(to imperitive programming language standards) allocation rate.
What I'd like is something similiar to the Ocaml garbage collector, but
with a unique young heap for each thread (so I don't have to acquire a
lock to allocate). But this requires me to have two words of thread-local
storage for every thread (young_heap_pointer and young_heap_limit). So
this is the question I have: what is the best way to implement this, given
exceedingly tight constraints on performance? I'd like something that
could be implemented on both Unix/Mac and Windows, just to make it more of
a problem.
By far the best way I can think of is to play games with the virtual
memory- have the two pointers (and maybe a little bit of other per-thread
information) on a global page all by themselves, and remap that virtual
page for every thread. Then I could simply dereference the globals. On
Unix I think I can do this playing games with mmap(), but I'm not sure how
to do this on Windows. I played around a little with the VirtualAlloc
function, but it doesn't look like it does what I need. Almost as good
would be to add a level of indirection, have a global pointer to where the
page is to be mapped, and just map it in the same place in every thread.
Another possibility, and I'm not sure how to do this in LLVM, would be to
sacrifice a register to hold the pointer to the unique per-thread
structure. This would be worthwhile to me even on the register-starved
x86-32. I suppose I could also just add a "hidden" (compiler-added
and
-maintained) argument to every function which is the pointer to the
per-thread data.
Using the normal thread-local storage scares me, because I don't know the
performance implications. Obviously calling a syscall every allocation
would be unacceptable, nor would I like an O(log N) tree-walking hit.
Ocaml's allocation is like 3-5 clock cycles for the common case (no minor
GC needed), so adding another 5 clock cycles to get the thread-local data
doubles the cost of allocation. Adding 50 or 1000 clock cycles is right
out. Basically, I'd like allocation to remain single-digit clock cycle
cost for the common case. If someone can convince me that thread-local
storage is that fast, then we're good. Otherwise, I need to look
elsewhere.
Opinions, advice, and/or alternative ideas about this problem would all be
greatly welcomed. Which of the above alternatives do you think would work
best? Or some other approach entirely?
Thanks.
Brian