[m-rev.] for review: exploit sortedness in bag.m

[Julien Fischer]

On Sat, 9 Mar 2024, Zoltan Somogyi wrote:

> Act on some old XXXs in bag.m.
> 
> library/bag.m:
>     An old diff added several XXXs to this module about exploiting
>     the sortedness of set inputs. This diff replaces one of those XXXs
>     with code that does exploit that sortedness, and rewrites the others
>     to document the reason why doing so in those cases is probably not
>     a good idea.
>
>     Add some dividers around function/predicate definition pairs
>     that both implement the same operation, to make it easier to distinguish
>     them from the previous and next such pairs, whose names are often
>     very similar.
>
> diff --git a/library/bag.m b/library/bag.m
> index 5fb6306cb..41a596e9b 100644
> --- a/library/bag.m
> +++ b/library/bag.m
> @@ -474,12 +492,22 @@ det_insert_duplicates(N, Item, !Bag) :-
>          error($pred, "number of items is negative")
>      ).
> 
> +%---------------------%
> +
>  insert_set(!.Bag, Xs) = !:Bag :-
>      bag.insert_set(Xs, !Bag).
>
>  insert_set(Set, !Bag) :-
>      set.to_sorted_list(Set, List),
> -    % XXX We should exploit the sortedness of List.
> +    % XXX We could try to exploit the sortedness of List, but
> +    % 
> +    % - it would make a difference only if the size of Set 
> +    %   is comparable to the number of keys in Bag, and
> +    %
> +    % - using a test to restrict the special casing to just
> +    %   the invocations for which it would help rather than hurt
> +    %   will impose its own cost as well, which would need
> +    %   to be paid on *all* invocations.
>      bag.insert_list(List, !Bag).

I think you can omit the "XXX" since there's nothing that needs to be
addressed there, just documentation of an implementation choice.

...

> @@ -525,19 +561,33 @@ det_remove_list(Xs, !Bag) :-
>          unexpected($pred, "some item not in bag")
>      ).
> 
> +%---------------------%
> +
>  remove_set(Set, !Bag) :-
>      set.to_sorted_list(Set, Xs),
> -    % XXX We should exploit the sortedness of Xs.
> +    % XXX We could try to exploit the sortedness of List, but
> +    % 
> +    % - it would make a difference only if the size of Set 
> +    %   is comparable to the number of keys in Bag, and
> +    %
> +    % - using a test to restrict the special casing to just
> +    %   the invocations for which it would help rather than hurt
> +    %   will impose its own cost as well, which would need
> +    %   to be paid on *all* invocations.
>      bag.remove_list(Xs, !Bag).

Ditto.

...

> @@ -574,22 +628,42 @@ from_list(Xs, Bag) :-
>      bag.init(Bag0),
>      bag.insert_list(Xs, Bag0, Bag).
> 
> +%---------------------%
> +
>  from_sorted_list(Xs) = Bag :-
>      bag.from_sorted_list(Xs, Bag).
>
>  from_sorted_list(Xs, Bag) :-
> -    bag.init(Bag0),
> -    % XXX We should exploit the sortedness of Xs.
> -    bag.insert_list(Xs, Bag0, Bag).
> +    % Instead of adding each X in Xs one-by-one to an initially empty map,
> +    % we construct the map in its final form directly.
> +    %
> +    % The approach we use here allocates only two memory cells per item
> +    % that does not end up in the final result: the pair and cons cells.

s/does/do/

> +    % For any list over about half a dozen items, this is fewer cells than
> +    % would be used by intermediate forms of the map with the other approach.
> +    % And for any list shorter than about half a dozedn items, the memory

s/dozedn/dozen/

> +    % needed, and the time taken by allocations, would both be too small
> +    % to matter either way.
> +    acc_rev_items(Xs, [], RevXsOnes),
> +    map.from_rev_sorted_assoc_list(RevXsOnes, Map),
> +    Bag = bag(Map).

That looks fine otherwise.

Julien.