[LLVMdev] Advice on implementing fast per-thread data

[Brian Hurt]

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