Fred van der Windt observes and asks:
> That must be the simplest solution and probably the fastest as well.
Agreed. Very simple, very fast. I cannot think of anything that
would be either faster or simpler or even easier to code.
> But is there really no penalty for using so much storage?
Of course. There is the potential for a tremendous penalty.
Roughly 8 MB to 10 MB for a "covers all possibilities" (as they
are known) hash table approach vs. 0.5 GB for the simple-to-code
and fast-to-run approach (about 50 times as much storage). It
will take a lot of time (mostly elapsed) to touch that number
of storage frames (most of it in assigning page frames).
I cannot imagine an application where 0.5 GB would not be
available, but that is possible. If the distribution of
keys is truly "random" (as asserted), then it could be the
case (when a million unique keys are actually presented)
that 1 out of every 4096 (2**32/2**20) bits get turned on.
4096 bits is 512 bytes, so EVERY page in the 0.5 GB would
have to be accessed (assigned a real page frame, zeroed,
and then ultimately have 8 bits in it somewhere turned on).
As an experiment, on a lightly loaded z10-EC LPAR, with no
storage constraints (sufficient free frames to immediately
assign the number of frames accessed), I ran three programs:
(1) - STORAGE OBTAIN 512 MB (128K pages).
- Access every 1024th page (that is, 128 pages.
Used 00.00 seconds CPU (as reported by SMF) in 0.01
seconds of elapsed time (as calculated from SYSLOG).
On a repeated run, the elapsed time (as calculated
from SYSLOG messages) was 0.00 seconds.
This is the expected scenario for this "simple"
algorithm when a hundred unique keys are presented
for evaluation.
(2) - STORAGE OBTAIN 512 MB (128K pages).
- Access EVERY page (that is, 131,072 pages).
Used 00.17 seconds CPU (as reported by SMF) in 7.44
seconds of elapsed time (as calculated from SYSLOG).
Repeated runs were made. The elapsed time was never less
than 7.36 seconds, nor longer than 7.52 seconds. The CPU
time as reported by SMF was always 0.17 seconds.
This is the worst case scenario for this "simple"
algorithm when approximately a million unique keys
are presented for evaluation.
(3) - STORAGE OBTAIN 16 MB (4K pages).
- Access EVERY page (that is, 4,096 pages).
Used 00.01 seconds CPU (as reported by SMF) in 0.01
seconds of elapsed time (as calculated from SYSLOG).
Repeated runs were made. The elapsed time was never less
than 0.01 seconds, nor longer than 0.02 seconds. The CPU
time as reported by SMF was always 0.01 seconds.
This would be the typical profile for a hash table
solution.
Now you should see why the harder-to-code hash table
algorithm is much superior. Yes, it is slower. But not,
IMHO, sufficiently slower to matter to anyone.
--
WB
