MMAP would be a good, but I would like to have support multiple databases in seperate files, and I possibly may need to map more data than I have address space on a 32 bit machine. I'm currently using a combination of (sb-int:make-static-vector) and (sb-sys:vector-sap) to get a lisp array of (unsigned-byte 8) that can be passed into C as a ubyte8*. The resulting 'raw' space is divided, using displaced arrays and pointer arithmatic, amongst N cachebuffers. It feels clean to me.<br/><br/>In my case a block is 1 page (4096 bytes). It starts with a header that has num-items. Immediately after the header item entries are packed. Each item entry has key-size, and data-size and the key binary follows. At the end of the page, data-size of arbitrary data is written. Items grow from the header upwards, data grows from the page end downwards.<br/><br/>To process this, I would need a) accessors for header, b) size-of header, c) accessors for items (which are positioned at arbitrary offsets), d) bulk copiers to read the key-binary and data-binary and e) a loop to count forward item-offset, and backwards data-offset.<br/>None of these things are impossible to do, but all in combination becomes hackish fast. It's the absence of pointers; without them you must manually carry 'out-of-band' extra offsets and deserialized forms. <br/><br/>I don't see a lisp solution to this. Real pointers are too dangerous considering the bit-mangling Lisp does to support dynamic types, and a user-created psuedo-pointer structure would be application specific -- tied to the deserializers and backing store they had used.<br/><br/>Cheers,<br/>Warren Wilkinson<br/><br/><br/><br/>Sep 12, 2009 02:54:38 AM, nikodemus@... wrote:<br/><br/>===========================================<br/><br/>2009/9/11 wagwilk@.../>> The trouble is, Lisp isn't good at imposing structure onto a block of<br/>> memory, and C is good for nothing else. So what I'm doing is defining my on<br/>> disk formats as C-structures, and writing C-routines to do the fine<br/>> manipulation, while lisp does the overall planning. For example, in my<br/>> B+Tree implementation, Lisp decides where to go, and C reads whats there.<br/><br/>No quarrel with that.<br/><br/>I would suggest calling mmap directly (well, via the FFI) to allocate<br/>memory in your case, since it sounds like you may end up wanting<br/>things like protection eventually anyways -- and the ability to map<br/>files directly.<br/><br/>As for imposing structure on memory ... yeah, a<br/>DEFINE-BINARY-STRUCTURE macro would be nice, for defining packed<br/>formats. Presumably when you say it's longer than C means that the<br/>macro-definition + using it is longer than C? I've done this manually<br/>a few times, and while individually it's not that hard, it is still a<br/>pain that cries out of a generalized macro.<br/><br/>Here's a bit of code that is packing KD tree building events into a<br/>vector to ease the GC overhead (having a pointer per event is too<br/>expensive for my purposes here.) An event here consists of 28bit<br/>object ID, axis K in range 0-2, TYPE code in range 0-2, and a<br/>single-float distance from origin E. (Object ID range dictated by what<br/>I could pack into two words...)<br/><br/>(defun make-events (n)<br/> (make-array (* 2 n) :element-type '(unsigned-byte 32)))<br/><br/>(defun event-count (vector)<br/> (truncate (length vector) 2))<br/><br/>(defun save-event (vector n &key type id k e)<br/> (let ((p (* 2 n)))<br/> (setf (aref vector p) (logior (ash id 4) (ash type 2) k)<br/> (aref vector (1+ p)) (pack-single e))<br/> n))<br/><br/>(defun event-packed-e (vector n)<br/> (aref vector (1+ (* 2 n))))<br/>(defun event-e (vector n)<br/> (unpack-single (event-packed-e vector n)))<br/><br/>(defun event-data (vector n)<br/> (aref vector (* 2 n)))<br/>(defun event-data-k (data)<br/> (ldb (byte 2 0) data))<br/>(defun event-data-type (data)<br/> (ldb (byte 2 2) data))<br/>(defun event-data-id (data)<br/> (ldb (byte 28 4) data))<br/><br/>(PACK-SINGLE and UNPACK-SINGLE are wrappers around bits of<br/>SBCL-internals that I mean to clean up and export at some point.)<br/><br/>Cheers,<br/><br/> -- Nikodemus<br/>
|