[m-rev.] for review: kv_list.m
jfischer at opturion.com
Thu Feb 13 11:57:04 AEDT 2020
On Wed, 12 Feb 2020, Zoltan Somogyi wrote:
> Add a new module, kv_list, to the standard library.
> 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
> 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.
More information about the reviews