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:ASSEMBLER-LIST@LISTSERV.UGA.EDU] On Behalf Of Tom Harper Sent: Wednesday, February 23, 2022 1:00 PM To: ASSEMBLER-LIST@LISTSERV.UGA.EDU 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 <weinh...@dkl.com> 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: weinh...@dkl.com > 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.
