Changes to SRFI 217 sample implementation Wolfgang Corcoran-Mathe 05 Jan 2021 19:24 UTC
Re: Changes to SRFI 217 sample implementation Wolfgang Corcoran-Mathe 09 Jan 2021 01:17 UTC

Changes to SRFI 217 sample implementation Wolfgang Corcoran-Mathe 05 Jan 2021 19:24 UTC

Hi all,

I'd like to announce some major changes to the SRFI 217 sample
implementation.  I've added "buddy compression" to the Okasaki-Gill
radix tree implementation, which allows runs runs of consecutive
integers to be stored in bitmaps.  This should make dense isets a
bit more space-efficient, without a reciprocal penalty for sparse
sets.  Since an integer is now represented by a (fixnum) prefix and
a bitmapped suffix, we also get a little more resolution (5 bits on
top of fx-width in most 64-bit Schemes, 4 in 32-bit Schemes).

I've used fixnums for bitmaps, rather than SRFI 178 bitvectors.
Although the latter choice might simplify the implementation, we'd
only obtain a space-efficiency improvement with a packing
implementation of bitvectors.  The SRFI 178 sample implementation
currently provides only unpacked (one byte to a bit) bitvectors; using
these would lead to significant inefficiency for sparse sets.

An important pieces of remaining work: Provide a new, faster
implementation of make-iset-range, leveraging the inherent dense
nature of the iset constructed by this function.  The current
implementation runs in time linear to the size of the range.

Error reports and suggestions for improvements are welcome, of course.

Best regards,

--
Wolfgang Corcoran-Mathe  <xxxxxx@sigwinch.xyz>

"It is a syntax error to write FORTRAN while not wearing
a blue tie." --James Iry