[m-rev.] for post-commit review: three speedups

[Julien Fischer]

On Thu, 14 Jun 2012, Zoltan Somogyi wrote:

> For post-commit review by anyone.
>
> Zoltan.
>
> This diff makes three main changes to try to speed up the compiler:
>
> - Avoid a double traversal of a map in const_struct.m.
>
> - Speed up that double traversal in const_struct.m when possible.
>
> - Remove any variables eliminated by the conversion of
>  from_ground_term_construct scopes to const structs from the procedure's
>  varset and vartypes. Do so in bulk, if that seems to be worthwhile.
>
> These together speed up the compiler by about 7% when compiling
> training_cars_full.m. About two-thirds of that is from the first change,
> almost a third is from the second, and a tiny bit from the third.

...

> Index: NEWS
> ===================================================================
> RCS file: /home/mercury/mercury1/repository/mercury/NEWS,v
> retrieving revision 1.611
> diff -u -b -r1.611 NEWS
> --- NEWS	5 Jun 2012 18:19:30 -0000	1.611
> +++ NEWS	14 Jun 2012 03:28:10 -0000
> @@ -13,6 +13,14 @@
>   the item, otherwise it fails. The other is all_true: it succeeds if
>   and only if all elements in the set pass a test.
>
> +* The map and varset modules each have a new predicate that deletes
> +  a sorted list of items from a map or varset, and can do so faster than
> +  usual exploiting the order.

  ... by exploiting the order.

> +
> +* The map and tree234 modules each have a new predicate that does a search,
> +  and if the search is unsuccessful, does an insertion during the *same*
> +  traversal.

...

> cvs diff: Diffing library
> Index: library/map.m
> ===================================================================
> RCS file: /home/mercury/mercury1/repository/mercury/library/map.m,v
> retrieving revision 1.129
> diff -u -b -r1.129 map.m
> --- library/map.m	14 Apr 2012 15:00:21 -0000	1.129
> +++ library/map.m	14 Jun 2012 03:28:10 -0000
> @@ -27,6 +27,7 @@
>
> :- import_module assoc_list.
> :- import_module list.
> +:- import_module maybe.
> :- import_module set.
>
> %-----------------------------------------------------------------------------%
> @@ -151,6 +152,15 @@
> :- func map.det_update(map(K, V), K, V) = map(K, V).
> :- pred map.det_update(K::in, V::in, map(K, V)::in, map(K, V)::out) is det.
>
> +    % map.search_insert(K, V, MaybeOldV, !Map):
> +    %
> +    % Search for the key K in the map. If the key is already in the map,
> +    % with corresponding value OldV, set MaybeOldV to yes(OldV). If it
> +    % is not in the map, then insert it into the map with value V.
> +    %
> +:- pred map.search_insert(K::in, V::in, maybe(V)::out,
> +    map(K, V)::in, map(K, V)::out) is det.
> +
>     % Update the value at the given key by applying the supplied
>     % transformation to it.  Fails if the key is not found.  This is faster
>     % than first searching for the value and then updating it.
> @@ -228,6 +238,13 @@
> :- func map.delete_list(map(K, V), list(K)) = map(K, V).
> :- pred map.delete_list(list(K)::in, map(K, V)::in, map(K, V)::out) is det.
>
> +    % Apply map.delete/3 to a sorted list of keys. The fact that the list
> +    % is sorted may make this more efficient.
> +    %

Document what happens if the list of keys is *not* sorted.

...

> Index: library/varset.m
> ===================================================================
> RCS file: /home/mercury/mercury1/repository/mercury/library/varset.m,v
> retrieving revision 1.91
> diff -u -b -r1.91 varset.m
> --- library/varset.m	25 Jul 2011 07:54:21 -0000	1.91
> +++ library/varset.m	14 Jun 2012 03:28:10 -0000
> @@ -89,6 +89,12 @@
> :- pred varset.delete_vars(list(var(T))::in, varset(T)::in, varset(T)::out)
>     is det.
>
> +    % Delete the names and values for a sorted list of variables.
> +    %

Likewise, document what happens if the list is not sorted.

The rest looks fine.

Julien.
--------------------------------------------------------------------------
mercury-reviews mailing list
Post messages to:       mercury-reviews at csse.unimelb.edu.au
Administrative Queries: owner-mercury-reviews at csse.unimelb.edu.au
Subscriptions:          mercury-reviews-request at csse.unimelb.edu.au
--------------------------------------------------------------------------