Thanks for the detailed reply Christian - I'll merge this conversation back into the Gambit list since there's some good stuff here.
On Tue, Feb 26, 2008 at 1:51 PM, Christian Jaeger christian@pflanze.mine.nu wrote:
James Long wrote:
Yes, all I need is a *little* bit of sharing so that I don't have to copy potentially large amounts of data every frame (frame being a scene rendering pass, which happens ~60 times a second). Having a few structures (which would receive a lot of attention) shared is the efficiency boost I'm looking for. How would you do this, however? Using shared memory objects and mmap?
Yes. Or pthreads and multiple Gambit runtimes in the same process, but that might involve making the Gambit runtime not use any C globals, first.
I thought about that at one point, but I just don't know enough about the Gambit runtime to know if that's feasible or not.
I'm not sure how you could share Gambit objects across processes, since the Gambit system is so isolated within itself.
Not sure what you mean with "so isolated"; of course if you want the Gambit gc alone to collect unreachable memory it needs access to all memory.
There are several ways approaching it.
(A) use the refcount in still objects. One Gambit engine is the master, the others are slaves and increase/decrease the refcount as they need. This requires either the ability to run multiple Gambit runtimes in the same process, or an extension to make Gambit allocate still objects from another heap.
You would have to lock the the whole memory allocator per allocation, and every object per refcount increase/decrease. I'm not sure if it would be safe for the allocator to be garbage collecting across the buffer in parallel either - because it's just scanning for memory which has a refcount of 0 it might be safe. Still though, seems like you would get a bad case of lock contention.
(B) use wrapper objects around shared storage outside of the Gambit heap. E.g. you would use plain C arrays/datastructures in shared memory, each carrying a refcount, and the finalizers in the normal Gambit FFI objects around them can decrement the refcount and free the C datastructure wenn it drops to zero.
This could work, but the refcount would only be for each runtime. Also, I'm assuming you'd have to use a separate memory allocator to manage this external heap. There's probably thread-safe memory allocators out there. As for garbage collection, I think you'd have to manually free these objects.
For B you want a module system with parametrization so that you can run your code calling e.g. f64vector-ref transparently for a f64vector-ref implementation which really accesses the C data.
For performance, those ops would be (transparently, by the module system) inlined into the client module body as ##c-code forms.
The ops would normally have to do a pointer indirection through the FFI object; there are several ways around that (for inside tight loops):
(- you would just write those parts in C)
- you first get the address of the C object (as a fixnum), then act upon
that address with a second set of ops; e.g.:
(define (f64vector-map! outvec invec fn) ;; outvec and invec are (possibly) FFI objects (let ((inadr (f64vector-address invec)) (outadr (f64vector-address outvec)) (len (min (f64vector-length invec) (f64vector-length outvec)))) (let lp ((i 0)) (if (< i len) (begin (direct-f64vector-set! outadr i (fn (direct-f64vector-ref inadr i))) (lp (+ i 1)))))))
That's easy to implement, but a little less pretty since you have then an additional "fast-access" operator set. Also using fixnums looses type safety, of course; but you want to avoid runtime type checking in performance critical places anyway, and I've got the idea that the module system would let the library know whether it is being used in safe or unsafe mode, and the library implementing the shared f64vector ops could then decide whether it would use a fixnum (in unsafe mode) or a typed structure (in safe mode), so in safe mode you'd still get type checking of the above; for perfect safety, this would require analyzing the code for "leaks" where such addresses / address objects are passed on to places with different safety settings, and either throw an error or warning if found, or wrap/unwrap the object at those boundaries--this is quite a bit involved, though, but could be realistic, after all I'm already into lexical / (type / dataflow) analysis anyway. Perfect safety would also require static checking that the ffi object is not released as long as the adresses taken from it are still being used.
- The compiler (/ module system) would recognize places where such
optimizations can be done automatically. This will require similar involvement as the above safety analysis mentioned above.
Yeah - I'd say disregard type checking. We're already pretty far down the rabbit hole, and essentially coding like C at this point. As as far as being released, like I said before, I would just say these special objects should be manually freed. I'm not going to be doing this a whole lot, but just for a few special buffers that will already be receiving a lot of attention.
A fundamental thing to keep in mind is that shared objects can only ever contain references to other shared objects, not to objects residing in any private Gambit heap. The easy way is simply not using any references at all, of course; working on homogenous vectors first may offer the most benefit for the least work. Shared objects containing references will be difficult for a few reasons; one is how local objects should be transformed into shared ones (if at all (should we just get an error?)), another one is garbage collection: either you resort to reference counting there, too (which would at least be consistent, but has it's usual problems with cyclic data structures, and won't be fast on modern/future machines), or implement a garbage collector that stops the world (not nice, right?), or implement an incremental asynchronous garbage collector (which I think will not work with mutation, here is the point where I'm not sure whether transparently transforming mutating programs to functional ones would be possible, and if so, worthwhile). I think a pool of shared objects containing references to other shared objects is best thought of as a database; now this is the area which I've been talking about last month in the thread about Mnesia.
That's certainly where it starts getting tricky. And it's where I feel like I want the system that deals with shared memory to be as explicit and restrictive as possible. It should almost be discouraged because of the complexities of it. Only the people who want to get dirty can allocate these special objects, manipulate their data, and deallocate them.
Regarding freeing memory: the easy way is to use e.g. linux tmpfs and a separate file for each object. This should work well enough when only big objects are used. If it should work for small objects, probably one of the free memory allocation implementations could be used on a single file. (For many very small objects and purely functional data structures, a mostly-lockfree copying GC, as mentioned in the Mnesia thread, would be better.)
I'll have to look at the Mnesia thread and mostly-lockfree copying GC. I'm still unclear how you could have a thread-safe GC, even with refcounts.
I would be interested in this kind of work.
Jeff Read's comment about supporting Unix domain sockets in Termite is interesting also. I didn't know about Unix domain sockets - I was looking all over the web for that exact thing. I still think there would be too much overhead serializing/deserializing structures, but that would certainly help avoid so much overhead.
Unix domain sockets are only marginally faster than local TCP/IP; you probably won't usually notice the difference with Termite, since the serialization/deserialization overhead will overshadow it (but I'd love to be proven otherwise; I think there is room for speed improvements in the ser/deser routines, at least if it gives up on cyclic data structures, which may not be a problem for a purely functional language).
(Feel free to reply to the list for further answers.)
Christian.
Good to know. At some point I'll play around with them and see how well they work.