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

[Julien Fischer]

Hi Zoltan,

On Wed, 12 Feb 2020, Zoltan Somogyi wrote:

> Add a new module, kv_list, to the standard library.
> 
> library/kv_list.m:
>     This new module is a version of assoc_list.m in which the list of
>     key/value pairs is represented not by a list of pairs (which has
>     two two-word cells per key/value pair) but by a bespoke, flattened
>     data structure (which has one three-word cell per key/value pair).
>     This should improve performance by reducing the number of memory
>     allocations and traffic to and from the data cache.
>     (The *amount* of memory allocated will not be affected, since Boehm
>     rounds up three words to four. And since cache block sizes are also
>     powers of two, traffic to and from memory should stay roughly the same.)

I suspect this will make a difference to one of our fleet scheduling
optimisers, since it uses assoc_lists quite heavily.  I'll measure it
after you commit.

>
>     The new module has one operation for every operation in assoc_list.m,
>     plus two functions for converting between assoc_lists and kv_lists
>     (one for each direction).

...
>
> diff --git a/NEWS b/NEWS
> index 5df05f8..9417fab 100644
> --- a/NEWS
> +++ b/NEWS
> @@ -4,6 +4,12 @@ NEWS since Mercury 20.01.x
>  Changes to the Mercury standard library
>  ---------------------------------------
> 
> +### Changes to the `assoc_list` module
> +
> +* The following predicate has been added:
> +
> +    - pred `lookup/3`
> +
>  ### Changes to the `char` module
>
>  * The following function and predicate have been added:
> @@ -41,6 +47,15 @@ Changes to the Mercury standard library
>      - func `hash/1`
>      - pred `hash/2`
> 
> +### Changes to the `kv_list` module
> +
> +The module kv_list (short for key-value list) has been added.
> +It contains the same functionality as the existing assoc_list module,
> +but stores lists of key/value pairs in a more space-efficient manner.
> +The tradeoff is that unlike assoc_lists, kv_lists are not standard
> +lists, and cannot be manipulated using functions and predicates
> +of the list module.

New standard libarary modules should be listed that the start of
the standard library section, thus:

     ### New module: `kv_list`

     This module contains the same functionality as the existing `assoc_list`
     module etc etc ...

I think you should be more specific as the the benefits of this data structure
over assoc_lists, e.g. reduction memory allocation (e.g. what you have in the
log message.)

...

> diff --git a/library/assoc_list.m b/library/assoc_list.m
> index 7e16d6d..c24d492 100644
> --- a/library/assoc_list.m
> +++ b/library/assoc_list.m

...


> @@ -95,9 +101,9 @@
>  :- pred map_values(pred(K, V, W), assoc_list(K, V), assoc_list(K, W)).
>  :- mode map_values(pred(in, in, out) is det, in, out) is det.
> 
> -    % filter(Pred, List, TrueList) takes a closure with one
> -    % input argument and for each member K - V of List X, calls the closure
> -    % on the key. K - V is included in TrueList iff Pred(K) is true.
> +    % filter(Pred, List, TrueList) takes a closure with one input argument,
> +    % and for each key/value pair in List, calls the closure on the key K.

Elsewhere in the library, e.g. in the map module, we use key-value pair, rather
than key/value pair.

That looks fine otherwise.

Julien.