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

[Zoltan Somogyi]

2020-02-13 11:57 GMT+11:00 Julien Fischer<jfischer at opturion.com>:
> 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.

Please do. I am interested in the results. They are much less predictable
than one would wish, because the change's significant effect on totally
unrelated data structures.Moving from assoc_lists to kv_lists will reduce
the number of allocations of two-word blocks, and will increase
the number of allocations of four-word blocks. This means that
e.g. what previously were contiguously allocate four-word blocks
for another data structure may not be contiguously allocated anymore,
while non-contiguous two-word block allocations could become contiguous.
Disentangling the effects of such changes from the effects on the
key-value pairs themselves is effectively impossible.

> 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.)

Done, though you will probably want to look it over.

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

Done.

> That looks fine otherwise.

Thanks.

I forgot to mention that I had a couple of questions about the remove predicate.

First, our other standard library modules that have a semidet remove predicate
also have a det delete predicate as well, which succeeds even if the given key
is not present, and a det_remove predicate, which throws an exception
in that case. Should we add either or both to assoc_list and kv_list?

Second, assoc_list has two versions of remove, remove itself and svremove,
with only the latter being state var friendly. At some point, we should bite
the bullet and (a) delete the old remove pred, and (2) rename svremove
as plain remove. Would now, after the release, be a good time?

Zoltan.