Efficiently represent several finite sets or small integers as a single non-negative integer.

bitfield

#+TITLE: Bitfield

* How It Works

The =bitfield= library provides a simple, efficient mechanism for storing
multiple discrete states into a single non-negative integer.  Its main API
is the macro =define-bitfield= that defines a certain kind of bitfield
consisting of a constructor, a function for creating modified clones, and
one reader function for each slot.

The following example illustrates these features for the case of defining
cards from a standard 52 card deck:

#+BEGIN_SRC lisp
(define-bitfield card
  (suit (member clubs diamonds hearts spades))
  (rank (member ace 2 3 4 5 6 7 8 9 10 jack queen king)))

(defparameter *card* (make-card :rank 'ace :suit 'spades))

(values
 ,*card*
 (card-suit *card*)
 (card-rank *card*))
;; => 3
;; => spades
;; => ace

(defparameter *card* (clone-card *card* :rank 'queen))

(values
 ,*card*
 (card-suit *card*)
 (card-rank *card*))
;; => 91
;; => spades
;; => queen
#+END_SRC

* Kinds of Bitfield Slots

Each bitfield slot is described by a list whose first element is the slot
name and whose second element is a slot specifier.  The remaining entries
form a plist that may supply additional keyword arguments.  The bitfield
slot specifier is then parsed using an extensible protocol to obtain a
bitfield slot class, the number of distinct states of that slot, and a
(possibly empty) plist of additional keyword arguments.  These properties
are then used to create a bitfield slot instance.  In the end, the
properties of the bitfield slot instances of all slots constitute the
behavior of the resulting bitfield.

The different kinds of bitfield slots are illustrated in this second
example:

#+BEGIN_SRC lisp
(define-bitfield examplebits
  (a boolean)
  (b (signed-byte 2))
  (c (unsigned-byte 3) :initform 1)
  (d (integer -100 100))
  (e (member foo bar baz)))

(defun examplebits-values (examplebits)
  (list
   (examplebits-a examplebits)
   (examplebits-b examplebits)
   (examplebits-c examplebits)
   (examplebits-d examplebits)
   (examplebits-e examplebits)))

(defparameter *default* (make-examplebits))

(examplebits-values *default*)
;; => (nil 0 1 -100 foo)

(defparameter *explicit* (make-examplebits :a t :b -1 :c 7 :d 42 :e 'baz))

(examplebits-values *explicit*)
;; => (t -1 7 42 baz)

(defparameter *clone* (clone-examplebits *explicit* :a nil :b -1 :c 2 :d -12 :e 'bar))

(examplebits-values *clone*)
;; => (nil -1 2 -12 bar)
#+END_SRC

This library comes equipped with parsers for =boolean=, =bit=,
=(unsigned-byte N)=, =(signed-byte N)=, =(integer A B)=, and =(member OBJ1
... OBJN)= slot specifiers.  New kinds of slots and slot specifiers can be
defined by extending the existing protocol functions, as shown in the next
section.

* Custom Bitfield Slots

In the next example, we show how the protocol can be augmented by
introducing both a bitfield slot class and the corresponding atomic
bitfield slot specifier parser for an =ascii= slot.

#+BEGIN_SRC lisp
(defclass bitfield-ascii-slot (bitfield-slot)
  ())

(defmethod bitfield-slot-pack ((slot bitfield-ascii-slot) value-form)
  `(char-code ,value-form))

(defmethod bitfield-slot-unpack ((slot bitfield-ascii-slot) value-form)
  `(code-char ,value-form))

(defmethod parse-atomic-bitfield-slot-specifier
    ((specifier (eql 'ascii)) &key (initform #\?))
  (values 'bitfield-ascii-slot
          128
          `(:initform ,initform)))

(define-bitfield four-letter-word
  (first-letter ascii)
  (second-letter ascii)
  (third-letter ascii)
  (fourth-letter ascii))

(defun four-letter-word-string (four-letter-word)
  (format nil "~C~C~C~C"
          (four-letter-word-first-letter four-letter-word)
          (four-letter-word-second-letter four-letter-word)
          (four-letter-word-third-letter four-letter-word)
          (four-letter-word-fourth-letter four-letter-word)))

(four-letter-word-string
 (make-four-letter-word))
;; => "????"

(four-letter-word-string
 (make-four-letter-word
  :fourth-letter #\n
  :second-letter #\v
  :first-letter #\o
  :third-letter #\e))
;; => "oven"
#+END_SRC

* Performance

Bitfields are defined or redefined exclusively via keyword arguments.
Thanks to inlining, this doesn't affect performance at all.  In this
example, we inspect the assembler code that is generated for manipulations
of a particular bitfield.  The examples are shown for SBCL.

#+BEGIN_SRC lisp
(define-bitfield hero
  (dex (integer 1 24))
  (str (integer 1 24))
  (int (integer 1 24)))
#+END_SRC

Firstly, we look at the code that is generated for a bitfield whose
arguments are constant:

#+BEGIN_SRC lisp
(defun make-archmage ()
  (make-hero :dex 10 :str 8 :int 24))

(disassemble #'make-archmage)
; disassembly for make-archmage
; Size: 21 bytes. Origin: #x52E2147C                          ; make-archmage
; 7C:       498B4510         mov RAX, [R13+16]                ; thread.binding-stack-pointer
; 80:       488945F8         mov [RBP-8], RAX
; 84:       BAD2B90000       mov EDX, 47570
; 89:       488BE5           mov RSP, RBP
; 8C:       F8               clc
; 8D:       5D               pop RBP
; 8E:       C3               ret
; 8F:       CC10             int3 16                          ; Invalid argument count trap

#+END_SRC

We see that the entire constructor has been folded into a single constant,
47570, which is the value of an Archmage shifted left by one bit.  The
shift is due to SBCL's internal representation of fixnums.

A more interesting example is when we consider constructors where not all
arguments are constant.  Here, we define a constructor for a wizard where
we supply the =int= attribute as an argument:

#+BEGIN_SRC lisp
(defun make-wizard (int)
  (make-hero :dex 10 :str 8 :int int))

(disassemble #'make-wizard)
; disassembly for make-wizard
; Size: 53 bytes. Origin: #x52E21510                          ; make-wizard
; 10:       498B5D10         mov RBX, [R13+16]                ; thread.binding-stack-pointer
; 14:       48895DF8         mov [RBP-8], RBX
; 18:       4885C0           test RAX, RAX
; 1B:       7422             jeq L0
; 1D:       A801             test AL, 1
; 1F:       751E             jne L0
; 21:       4883F830         cmp RAX, 48
; 25:       7718             jnbe L0
; 27:       488BD0           mov RDX, RAX
; 2A:       4883C2FE         add RDX, -2
; 2E:       48C1E20A         shl RDX, 10
; 32:       4881CAD2010000   or RDX, 466
; 39:       488BE5           mov RSP, RBP
; 3C:       F8               clc
; 3D:       5D               pop RBP
; 3E:       C3               ret
; 3F: L0:   CC1E             int3 30                          ; OBJECT-NOT-TYPE-ERROR
; 41:       00               byte #X00                        ; RAX
; 42:       23               byte #X23                        ; '(integer 1 24)
; 43:       CC10             int3 16                          ; Invalid argument count trap
#+END_SRC

The generated assembler code is slightly more complicated, but most of this
is about checking that the =int= argument is actually a positive integer
that is at most 24.  If we strip the argument checking code, we end up with

#+BEGIN_SRC lisp
; 27:       488BD0           mov RDX, RAX
; 2A:       4883C2FE         add RDX, -2
; 2E:       48C1E20A         shl RDX, 10
; 32:       4881CAD2010000   or RDX, 466
; 39:       488BE5           mov RSP, RBP
; 3C:       F8               clc
; 3D:       5D               pop RBP
; 3E:       C3               ret
#+END_SRC

We see that adding one variable argument to a bitfield constructor only
costs one =add= instruction and one =shl= (left-shift) instruction.

The next example is about cloning bitfields.  The next function takes a
hero and returns a copy of that hero but with a slightly higher =str=
attribute.

#+BEGIN_SRC lisp
(defun go-to-gym (hero)
  (clone-hero hero :str (1+ (hero-str hero))))
#+END_SRC

If we disable argument checking (e.g., by declaring =(safety 0)=) we end up
with the following sequence of instructions for our =go-to-gym= function:

#+BEGIN_SRC lisp
; 12:       8BD8             mov EBX, EAX
; 14:       C1EB05           shr EBX, 5
; 17:       83E33E           and EBX, 62
; 1A:       4883C302         add RBX, 2
; 1E:       4883C302         add RBX, 2
; 22:       488BD0           mov RDX, RAX
; 25:       8BF2             mov ESI, EDX
; 27:       83E63E           and ESI, 62
; 2A:       4883C602         add RSI, 2
; 2E:       488BCA           mov RCX, RDX
; 31:       48C1F90A         sar RCX, 10
; 35:       4883E1FE         and RCX, -2
; 39:       4883C102         add RCX, 2
; 3D:       488D56FE         lea RDX, [RSI-2]
; 41:       4883C3FE         add RBX, -2
; 45:       48C1E305         shl RBX, 5
; 49:       4809DA           or RDX, RBX
; 4C:       4883C1FE         add RCX, -2
; 50:       48C1E10A         shl RCX, 10
; 54:       4809CA           or RDX, RCX
; 57:       488BE5           mov RSP, RBP
; 5A:       F8               clc
; 5B:       5D               pop RBP
; 5C:       C3               ret
#+END_SRC

We count one =shr= instruction, two =shl= instructions, six =add=
instructions and two =or= instructions.  Not bad for parsing three keyword
arguments with complicated values.  With argument checking, the code grows
further by two conditional branches per argument.  But with the branch
prediction of a modern CPU, those branches will be almost for free.

* Conclusion

I wrote this library because I am tired of manually fiddling with bits just
to save memory.  Now I can finally pack plenty of information into a single
machine word without worrying about correctness.  I hope you find this
useful, too.


bitfield

Upstream URL

Author

License

bitfield

License:

Authors:

Dependencies:

Dependencies (0)

Dependents (0)