Steel Bank Common Lisp

2009/9/11  <wagwilk@...>:

> The trouble is, Lisp isn't good at imposing structure onto a block of
> memory, and C is good for nothing else. So what I'm doing is defining my on
> disk formats as C-structures, and writing C-routines to do the fine
> manipulation, while lisp does the overall planning. For example, in my
> B+Tree implementation, Lisp decides where to go, and C reads whats there.

No quarrel with that.

I would suggest calling mmap directly (well, via the FFI) to allocate
memory in your case, since it sounds like you may end up wanting
things like protection eventually anyways -- and the ability to map
files directly.

As for imposing structure on memory ... yeah, a
DEFINE-BINARY-STRUCTURE macro would be nice, for defining packed
formats. Presumably when you say it's longer than C means that the
macro-definition + using it is longer than C? I've done this manually
a few times, and while individually it's not that hard, it is still a
pain that cries out of a generalized macro.

Here's a bit of code that is packing KD tree building events into a
vector to ease the GC overhead (having a pointer per event is too
expensive for my purposes here.) An event here consists of 28bit
object ID, axis K in range 0-2, TYPE code in range 0-2, and a
single-float distance from origin E. (Object ID range dictated by what
I could pack into two words...)

(defun make-events (n)
  (make-array (* 2 n) :element-type '(unsigned-byte 32)))

(defun event-count (vector)
  (truncate (length vector) 2))

(defun save-event (vector n &key type id k e)
  (let ((p (* 2 n)))
    (setf (aref vector p) (logior (ash id 4) (ash type 2) k)
          (aref vector (1+ p)) (pack-single e))
    n))

(defun event-packed-e (vector n)
  (aref vector (1+ (* 2 n))))
(defun event-e (vector n)
  (unpack-single (event-packed-e vector n)))

(defun event-data (vector n)
  (aref vector (* 2 n)))
(defun event-data-k (data)
  (ldb (byte 2 0) data))
(defun event-data-type (data)
  (ldb (byte 2 2) data))
(defun event-data-id (data)
  (ldb (byte 28 4) data))

(PACK-SINGLE and UNPACK-SINGLE are wrappers around bits of
SBCL-internals that I mean to clean up and export at some point.)

Cheers,

 -- Nikodemus

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/>

2009/9/12  <wagwilk@...>:

> 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.

I might try using SAPs: accessor for a pointer would return a SAP,
SAP+ and SAP- provide arithmetic, and SAP-REF-FOOs provide different
widths of access with offsets.

I would caution you mildly against SB-INT:MAKE-STATIC-VECTOR, though:
it is unsupported and liable to be deprecated sooner or later. Also,
the address space it can allocate to is quite small -- limited to the
static portion of the Lisp heap.

Cheers,

 -- Nikodemus

> I would caution you mildly against SB-INT:MAKE-STATIC-VECTOR, though:<br/>> it is unsupported and liable to be deprecated sooner or later. Also,<br/>> the address space it can allocate to is quite small -- limited to the<br/>> static portion of the Lisp heap.<br/>> <br/>> Cheers,<br/>> <br/>>  -- Nikodemus<br/><br/>Thanks for the heads-up, I've now looked into it to see that static space is only 1 meg, while the dynamic space is 512 megs. I found some old posts (http://osdir.com/ml/lisp.steel-bank.general/2005-06/msg00024.html, http://osdir.com/ml/lisp.steel-bank.general/2005-09/msg00027.html) that discuss it. <br/><br/>I tried writing a make-sap-array method (patterned of make-static-array) but I'm led to believe that an sbcl lisp array requires the array data to directly follow the array-header.  This means I cannot use make-alien to heap-allocate the space, and then point an array at it. Seperating array headers from their data would require changing how SBCL handles dynamic types -- and if you change that, you may as well just start a new compiler.<br/><br/>I then looked into adding SAP support to the :displaced-to option. It might work, but other array operations depend on the displaced-array being a lisp array, so adding support for SAP's here would be a lot of extra code paths for a very specific use case: Not worth the doing, in my opinion.<br/><br/>I settled for increasing static space (/src/compiler/x86/parms.lisp) and recompiling SBCL.  I've taken 150 megs following the dynamic space.  I recognize that this is completely unportable, but I'm lucky enough to have complete control over the servers, so it's an acceptable solution.  Using SAP references (and not having Lisp-side arrays) would also work, but I'm hoping that having the arrays on both sides will be convenient.  <br/><br/>Cheers,<br/>Warren Wilkinson

2009/9/14  <wagwilk@...>:

> I tried writing a make-sap-array method (patterned of make-static-array) but
> I'm led to believe that an sbcl lisp array requires the array data to
> directly follow the array-header. This means I cannot use make-alien to
> heap-allocate the space, and then point an array at it

Correct.

You can, however, allocate foreign memory and make it look like a lisp
array by starting it with the appropriate header, and making a tagged
pointer to it. (Something along these lines would be nice to add
support directly, but that's a topic for sbcl-devel...) If you're
interested, I can provide more details as required. The upside is a
nice lispy-looking immovable array, the downside is that you need to
deal with various unsupported bits and pieces.

You might also want to look at ALLOCATE-SYSTEM-MEMORY, and
DEALLOCATE-SYSTEM-MEMORY, which use mmap to allocate large blocks of
foreign memory, and using various SAP-functions on that. This should
all be more-or-less supported, but you need to do your own
bounds-checking, though. :/

Cheers,

 -- Nikodemus