Hashing for efficient definition
- To: mathgroup at yoda.ncsa.uiuc.edu
- Subject: Hashing for efficient definition
- From: jacobson at cello.hpl.hp.com
- Date: Tue, 15 Jan 91 14:51:32 PST
At the recent Mathematica conference there was a panel discussion on
optimizing the performance of Mathematica programs. I was on the
panel and mentioned a technique for eliminating a problem that occurs
when may defintions are attached to the same symbol. Several people
expressed interest. So here is a fuller discussion of the problem and
the code I use to get around it. Note, however, that Roman Maeder of
WRI said that Version 2.0 has changed the implemention so this is no
longer necessary, once you actually get 2.0.
Suppose that you have some function "foo" and you want to define lots
of rules for foo.
foo[red]=stop, foo[green]=go, foo[1]=whatever ...
Now the problem is that these rules are all linked together in a
linear list (accessed with the undocumented DownValue function)
associated with the symbol foo. When you have several thousand rules
things get real slow.
The solution is to use TagSet or UpSet to associate the symbol with
something else. But what? With foo[zzz] you could write zzz/:
foo[zzz] = ..., which puts the rule in a list (accessed with the
undocumented UpValue function) associated with the symbol zzz.
There are two problems with this approach.
1. It fails when zzz is a number or protected symbol.
2. It only pushes the problem down a level if the lhs of the
rules look like foo[bar[x]], for lots of different x. Now
we get a long UpValue list on bar instead of a long DownValue
list on foo.
The solution is to create new symbol names that are very unlikely to
have many rules associated with them.
First the syntax: Whenever you would have used x, instead use Wrap[x].
Rules look like foo[Wrap[x]]=val. You can also assign directly as in
Wrap[x]=val. Delayed setting is also supported: foo[Wrap[x]]:=expr.
You can UnSet: Wrap[x]=.
What Wrap does is detect when it is called from Set and rewrite the
Set like this:
foo[Wrap[x]]=val
becomes something like
HASH$$12345/: wp[HASH$$12345,x] = val
with the exact funny symbol being derived from x by the Mathematica
Hash function. There is a similar transformation for SetDelayed and
UnSet. When Wrap[x] appears by itself, it is transformed to
wp[HASH$$12345,x], which then evaluates to the value. Some strange
hacking suppresses the first expansion if wp[HASH$$12345,x] has no
value.
Known bug/limitation:
In foo[Hash[x]] = val, the x gets evaluated. This is the same as with
Set. But neither foo[Literal[Hash[x]]] nor foo[Hash[Literal[x]]] will
work right.
Here it is. I've converted the code I had at the conference into a
package. I just added the hack so Wrap[x] does not evaluate if it had
not been assigned a value. I sure hope I didn't introduce any bugs.
The old version is shown in a comment if you want more efficiency (and
after all that is why you are using this is the first place) and don't
care if Wrap[x] evaluates to something even if you had not assigned to
it.
As usual, Hewlett-Packard will not be responsible for this.
-- David
==========================
BeginPackage["Wrap`"]
Wrap::usage = "Wrap[x] can be used in place of x to improve efficiency in programs that define many rules of the form f[x]=val for the same f."
Hashify::usage = "Hashify[expession] returns a symbol derived from expression."
Begin["`Private`"]
Hashify[name_] := ToExpression[StringJoin["HASH$$",ToString[Hash[name]]]]
Wrap/:Set[Literal[Wrap[arg_]],val_] := wrapset[Hashify[arg],arg,val]
wrapset[h_,arg_,val_] := h/: wp[h,arg] = val
Wrap[arg_] := Block[{hashsym,val},val/;
(hashsym=Hashify[arg]; (* do computation in condition, Yuk! *)
val=wp[hashsym,arg];
!MatchQ[val,wp[_,_]])] (* Make sure it really evalutated.
We assume that nobody else uses wp. *)
(* Here is a more efficent verson of Wrap, but it evaluates even if it has
not been assigned a value. *)
(* Wrap[arg_] := wp[Hashify[arg],arg] *)
Wrap/:Unset[Literal[Wrap[arg_]]] := (wrapunset[Hashify[arg],arg];Null)
wrapunset[h_,arg_] := h/:wp[h,arg]=. /;ValueQ[wp[h,arg]]
(* Here is the old Unset code. It it more efficient, but
gives an error if the value is not already set. *)
(*
Wrap/:Unset[Literal[Wrap[arg_]]] := wrapunset[Hashify[arg],arg]
wrapunset[h_,arg_] := h/:wp[h,arg]=.
*)
Wrap/:SetDelayed[Literal[Wrap[arg_]],val_] :=
wrapsetdelayed[Hashify[arg],arg,val]
wrapsetdelayed[h_,arg_,val_] := h/: wp[h,arg] = val
End[]
EndPackage[]