[m-rev.] for review: fatter_sparse_bitset.m

[Julien Fischer]

On Mon, 30 Jan 2023, Zoltan Somogyi wrote:

> Add library/fatter_sparse_bitset.m.
> 
> library/fatter_sparse_bitset.m:
>     Add this version of fat_sparse_bitset.m, which stores *two* words
>     worth of bits in each cell, not one. This word would otherwise be unused,
>     because the Boehm-Demers-Weiser allocator rounds up requests for three
>     word cells to four.
> 
> library/MODULES_DOC:
> library/library.m:
>     Add the new module to the list of library modules.
> 
> library/fat_sparse_bitset.m:
> library/sparse_bitset.m:
> library/tree_bitset.m:
>     Update the documentation of all these other bitset modules. Copy
>     the same basic introduction to all the relevant modules. Add documentation
>     of the differences to tree_bitset.m and fatter_sparse_bitset.m, with
>     a pointer in fat_sparse_bitset.m to fatter_sparse_bitset.m.
> 
> library/test_bitset.m:
>     Test the new module as well as the others.
> 
> tests/hard_coded/speedtest_bitset.m:
>     Extend the benchmarking of list_to_set operations to the new module.
>     To allow the benchmarking to be tough enough to be informative, comment
>     out the benchmarking of the old_list_to_set operations.

...

> diff --git a/library/fat_sparse_bitset.m b/library/fat_sparse_bitset.m
> index 9efa6b648..b59b9e1ae 100644
> --- a/library/fat_sparse_bitset.m
> +++ b/library/fat_sparse_bitset.m
> @@ -10,22 +10,23 @@
>  % Author: zs.
>  % Stability: medium.
>  %
> -% This module provides an abstract data type for storing sets of integers.
> -% If the integers stored are closely grouped, a fat_sparse_bitset is much more
> -% compact than either the list-of-elements representations provided by set.m,
> -% set_ordlist.m, and set_unordlist.m, or the tree-of-elements representations
> -% provided by set_bbbtree.m, set_tree234.m or set_ctree234.m. The module
> -% sparse_bitset.m contains a version of this module that uses ordinary lists
> -% instead of the fat lists used by this module.
> +% This module provides an abstract data type for storing sets of items
> +% that can each be represented by non-negative integers.
> +% If the integers being stored are closely grouped, a sparse_bitset
> +% will be much more compact than either the list-of-elements representations
> +% provided by set.m, set_ordlist.m, and set_unordlist.m, or th

s/th/the/

(And elsewhere this has been copy-and-pasted.)

...

> diff --git a/library/fatter_sparse_bitset.m b/library/fatter_sparse_bitset.m
> index e69de29bb..26f352148 100644
> --- a/library/fatter_sparse_bitset.m
> +++ b/library/fatter_sparse_bitset.m

...

> @@ -0,0 +1,2148 @@

...

> +% The fatter_sparse_bitset representation is intended to avoid this last
> +% problem with the fat_sparse_bitset representation, by repurposing the
> +% unused word allocated in each cell to represent up to another word's worth
> +% of items. In cases where this word contains at least one set bit, this
> +% is a worthwhile gain; in cases where this word is usually all zeroes,
> +% there will be no gain, but the (thanks to write buffers) the initialization
> +% cost will typically be negligible as well. There is the additional cost
> +% that each operation on the bits associated with an offset will either
> +% have to select which word of bits it applies to, or has to apply to both
> +% words of bits, but unless typical sets are so sparse that one word of bits
> +% in each cell is almost always empty, the reduction in the number of cells
> +% that have to be visited will more than compensate for those costs,.

Delete the stray comma at the end of that sentence.

That's fine otherwise.

Julien.