https://github.com/StanfordPascal/Pascal/blob/master/srceval/avltree.pas
this is the Stanford Pascal variant of the AVLSRCH function which
retrieves a value
from an AVL tree and optionally inserts it there, if it cannot be found.
When calling
AVLSRCH, another function AVLCOMP is passed as a parameter (this is old
Pascal technique);
AVLCOMP is used to compare the key data type of the AVL tree nodes
(which may vary, of course,
for different AVL trees); AVLCOMP is supposed to return an integer like
C memcmp,
this way controlling the insertions into the AVL tree.
The C variant is similar (passing a function pointer for the comparison
function).
IIRC, I took the code from a Niklaus Wirth textbook (written in the 1970s)
and extended it for practical use.
Kind regards
Bernd
Am 23.02.2022 um 23:44 schrieb Bernd Oppolzer:
I use AVL trees all the time for fast searches;
I have routines written in Pascal and ANSI-C.
No need to worry about hash collisions and other problems,
and the AVL technique keeps the B-trees always balanced with
a very simple algorithm.
https://en.wikipedia.org/wiki/AVL_tree
invented 1962 by two Soviet mathematicians. That's all I need,
my swiss knife for all sort of searching problems.
Kind regards
Bernd
Am 23.02.2022 um 23:08 schrieb Charles Mills:
If you are writing in C++ then the B-tree is all implemented for you,
and it is a d@mned fast implementation.
std::map
Charles
-----Original Message-----
From: IBM Mainframe Assembler List
[mailto:[email protected]] On Behalf Of Tom Harper
Sent: Wednesday, February 23, 2022 1:00 PM
To: [email protected]
Subject: Re: SRST vs. SRSTU
Gary,
Now that we know that you are implementing a key/data structure, we
can provide more help.
Vector instructions are impressive for searching for strings but
that’s not really what you’re doing here.
B-trees can be used, but are non-trivial to implement.
Your best bet is a dynamic hash table of size of an appropriate
Mersenne Prime. The fastest effective way to hash your key is using
the CKSM instruction. Although fast, it does produce more synonyms
than other hash techniques.
If the size of your structures are unknown ahead of time, you might
consider starting out with a small hash table and then if the ratio
of keys to entries exceeds a threshold, rehash entries to the next
higher Mersenne Prime. If you know you will never have more than a
certain number of entries, you can just make a structure that size
and skip the dynamic option.
In any case, if you are multi-threading, you will need to serialize.
Inserting and deleting keys is not difficult and neither is the basic
lookup.
If you have the option of writing in C, GLib already has this
function implemented.
Either way, it can be a fun exercise.
Tom Harper
Phoenix Software International
Sent from my iPhone
On Feb 22, 2022, at 7:24 PM, Gary Weinhold <[email protected]> wrote:
Thanks to all. From the responses so far and my experience I'm
inclined to believe SRST is hardware and probably SRSTU is millicode
(perhaps based on SRST for the first byte) and we must look for
another technique.
My original thought was that we would use a serial search until the
number of keys exceeded some threshold and then build and maintain
the 2-byte hash table and switch to SRSTU, based on naively
expecting its performance to be comparable to SRST up to some number
of keys and significantly better than SRST when the number of
entries exceeded some multiple of 256.
We are experimenting with other techniques, but we can't change that
the keys are added and deleted dynamically, are continually
accessed, and the total number of entries varies significantly in
different applications. I guess it's time to look at vector
instructions and possibly B-trees.
Gary
Gary Weinhold
Senior Application Architect
DATAKINETICS | Data Performance & Optimization
Phone:+1.613.523.5500 x216
Email: [email protected]
Visit us online at www.DKL.com
E-mail Notification: The information contained in this email and any
attachments is confidential and may be subject to copyright or other
intellectual property protection. If you are not the intended
recipient, you are not authorized to use or disclose this
information, and we request that you notify us by reply mail or
telephone and delete the original message from your mail system.
--------------------------------------------------------------------------------
This e-mail message, including any attachments, appended messages and
the
information contained therein, is for the sole use of the intended
recipient(s). If you are not an intended recipient or have otherwise
received this email message in error, any use, dissemination,
distribution,
review, storage or copying of this e-mail message and the information
contained therein is strictly prohibited. If you are not an intended
recipient, please contact the sender by reply e-mail and destroy all
copies
of this email message and do not otherwise utilize or retain this email
message or any or all of the information contained therein. Although
this
email message and any attachments or appended messages are believed
to be
free of any virus or other defect that might affect any computer
system into
which it is received and opened, it is the responsibility of the
recipient
to ensure that it is virus free and no responsibility is accepted by the
sender for any loss or damage arising in any way from its opening or
use.
