Re: SRST vs. SRSTU

[Seymour J Metz]

COMPASS was the assembler for all the sons of COS, including SCOPE.


--
Shmuel (Seymour J.) Metz
http://mason.gmu.edu/~smetz3


From: IBM Mainframe Assembler List [ASSEMBLER-LIST@LISTSERV.UGA.EDU] on behalf 
of Paul Gilmartin [0014e0e4a59b-dmarc-requ...@listserv.uga.edu]
Sent: Wednesday, February 23, 2022 7:43 PM
To: ASSEMBLER-LIST@LISTSERV.UGA.EDU
Subject: Re: SRST vs. SRSTU

On Feb 23, 2022, at 17:18:58, Seymour J Metz wrote:
>
> ASCENT? You ran SIPROS?
>
SCOPE; later KRRONOS (which MACE may have begotten, but MACE
refused the DNA test.)  SIPROS was widely perceived as dissipated
vaporware, but CERN proudly claimed to use it.
<https://secure-web.cisco.com/1VMuA8hrj7L0KgQKaZ28DmSKo5MFpxUfPU8X1ghfYcd27ya00JFAEw76cJZK33eyfWVYbRQJ2NZbIxXx1bkfm3ig9ekFx_zsldt0wXY8JqLJSo19uRXl6QRpdceVfeLBoJVnd3sX9Vd_qCLhlgwXC65obhT0VT-pn1ECZXBNXKDqkCTm3Ry1r_sbzwCcRgBUWXC-kroD-kRNTAZp-BEuH-bHGYVDWdEqoFrD1x_DZx31shkgp-Tobxy-DJ2b3ODQxZdXXMjc1DuCf2NI7lRxTzb6C5GOm3SmdNiTeWKDLhvOkchrouyZzTplnQRgf070OKLxrbKs5NDwGtOPTC1BEHRDw7AOrRDfygATu_ng31d__22tEJyPl5q9qyXrDicEMHFGUxh0wrvWPmxiv-_dilpooHs0oVF9-XgAWXLpOx7t8DoEXUHSEVBBUgaxqdwDN/https%3A%2F%2Fen.wikipedia.org%2Fwiki%2FCDC_6600>

What was the assembler that fused ASCENT and ASPER?

--
gil

Re: SRST vs. SRSTU

[Paul Gilmartin]

On Feb 23, 2022, at 17:18:58, Seymour J Metz wrote:
> 
> ASCENT? You ran SIPROS?
>  
SCOPE; later KRRONOS (which MACE may have begotten, but MACE
refused the DNA test.)  SIPROS was widely perceived as dissipated
vaporware, but CERN proudly claimed to use it.


What was the assembler that fused ASCENT and ASPER?

-- 
gil

Re: SRST vs. SRSTU

[Seymour J Metz]

ASCENT? You ran SIPROS?


--
Shmuel (Seymour J.) Metz
http://mason.gmu.edu/~smetz3


From: IBM Mainframe Assembler List [ASSEMBLER-LIST@LISTSERV.UGA.EDU] on behalf 
of Paul Gilmartin [0014e0e4a59b-dmarc-requ...@listserv.uga.edu]
Sent: Wednesday, February 23, 2022 7:14 PM
To: ASSEMBLER-LIST@LISTSERV.UGA.EDU
Subject: Re: SRST vs. SRSTU

On Feb 23, 2022, at 16:24:53, Charles Mills wrote:
>
> A little OT for an assembler list but in case anyone cares:
>
> https://www.cplusplus.com/reference/map/map/
>
> It is a C++ "template" function, which works kind of like an HLASM macro
> (*not* like a C macro, which is more like an HLASM SETC symbol). *Kind of*
> like: please no need for anyone to tell me it is not exactly the same.
>
But consider:
#define sum( x, y) ( ( x ) + ( y ) )

... C has polymorphic operators so this generates code appropriate
to its operand types.

> It "builds" code at compile time specific to your data types, much like some
> HLASM macro might generate an L if your data was in a fullword but an LH if
> it were in a halfword, or an LR or LHI for a register or a symbol.
>
That takes a lot of AIFs.  CDC ASCENT could do that with no conditionals
since register names were reserved symbols with types known to ASCENT.
A consequence was that CDC programmers found habitual PRINT GEN alien
since ASCENT could be trusted to DWIM -- no unintended register reference
when a programmer unwittingly used parentheses; no IHBINRRA.

--
gil

Re: SRST vs. SRSTU

[Paul Gilmartin]

On Feb 23, 2022, at 16:24:53, Charles Mills wrote:
> 
> A little OT for an assembler list but in case anyone cares:
> 
> https://www.cplusplus.com/reference/map/map/ 
> 
> It is a C++ "template" function, which works kind of like an HLASM macro
> (*not* like a C macro, which is more like an HLASM SETC symbol). *Kind of*
> like: please no need for anyone to tell me it is not exactly the same.
>  
But consider:
#define sum( x, y) ( ( x ) + ( y ) )

... C has polymorphic operators so this generates code appropriate
to its operand types.

> It "builds" code at compile time specific to your data types, much like some
> HLASM macro might generate an L if your data was in a fullword but an LH if
> it were in a halfword, or an LR or LHI for a register or a symbol.
>  
That takes a lot of AIFs.  CDC ASCENT could do that with no conditionals
since register names were reserved symbols with types known to ASCENT.
A consequence was that CDC programmers found habitual PRINT GEN alien
since ASCENT could be trusted to DWIM -- no unintended register reference
when a programmer unwittingly used parentheses; no IHBINRRA.

-- 
gil

Re: SRST vs. SRSTU

[Charles Mills]

A little OT for an assembler list but in case anyone cares:

https://www.cplusplus.com/reference/map/map/ 

It is a C++ "template" function, which works kind of like an HLASM macro
(*not* like a C macro, which is more like an HLASM SETC symbol). *Kind of*
like: please no need for anyone to tell me it is not exactly the same.

It "builds" code at compile time specific to your data types, much like some
HLASM macro might generate an L if your data was in a fullword but an LH if
it were in a halfword, or an LR or LHI for a register or a symbol.

Charles


-Original Message-
From: IBM Mainframe Assembler List [mailto:ASSEMBLER-LIST@LISTSERV.UGA.EDU]
On Behalf Of Charles Mills
Sent: Wednesday, February 23, 2022 3:18 PM
To: ASSEMBLER-LIST@LISTSERV.UGA.EDU
Subject: Re: SRST vs. SRSTU

I don't know the internals of the C++ std::map. I *suspect* it does not: if
you add sorted data you will end up with a very unbalanced tree. I could be
wrong. I used it extensively in my SIEM Agent and it worked like a charm,
but I never looked under the covers.

Charles


-Original Message-
From: IBM Mainframe Assembler List [mailto:ASSEMBLER-LIST@LISTSERV.UGA.EDU]
On Behalf Of Paul Gilmartin
Sent: Wednesday, February 23, 2022 2:47 PM
To: ASSEMBLER-LIST@LISTSERV.UGA.EDU
Subject: Re: SRST vs. SRSTU

On Feb 23, 2022, at 15:08:16, Charles Mills wrote:
> 
> If you are writing in C++ then the B-tree is all implemented for you, and
it is a d@mned fast implementation.
>  '
That would be nice.  I've played with the POSIX
tdelete, tfind, tsearch, twalk - manage a binary search tree
on various platforms and they appear not to balance the tree.
<https://pubs.opengroup.org/onlinepubs/9699919799/functions/tdelete.html#tag
_16_609>

-- 
gil

Re: SRST vs. SRSTU

[Charles Mills]

I don't know the internals of the C++ std::map. I *suspect* it does not: if
you add sorted data you will end up with a very unbalanced tree. I could be
wrong. I used it extensively in my SIEM Agent and it worked like a charm,
but I never looked under the covers.

Charles


-Original Message-
From: IBM Mainframe Assembler List [mailto:ASSEMBLER-LIST@LISTSERV.UGA.EDU]
On Behalf Of Paul Gilmartin
Sent: Wednesday, February 23, 2022 2:47 PM
To: ASSEMBLER-LIST@LISTSERV.UGA.EDU
Subject: Re: SRST vs. SRSTU

On Feb 23, 2022, at 15:08:16, Charles Mills wrote:
> 
> If you are writing in C++ then the B-tree is all implemented for you, and
it is a d@mned fast implementation.
>  '
That would be nice.  I've played with the POSIX
tdelete, tfind, tsearch, twalk - manage a binary search tree
on various platforms and they appear not to balance the tree.
<https://pubs.opengroup.org/onlinepubs/9699919799/functions/tdelete.html#tag
_16_609>

-- 
gil

Re: SRST vs. SRSTU

[Bernd Oppolzer]

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: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  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 
co

Re: SRST vs. SRSTU

[Paul Gilmartin]

On Feb 23, 2022, at 15:08:16, Charles Mills wrote:
> 
> If you are writing in C++ then the B-tree is all implemented for you, and it 
> is a d@mned fast implementation.
>  '
That would be nice.  I've played with the POSIX
tdelete, tfind, tsearch, twalk - manage a binary search tree
on various platforms and they appear not to balance the tree.


-- 
gil

Re: SRST vs. SRSTU

[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: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  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.

Re: SRST vs. SRSTU

[Tom Harper]

Gil,

Apologies as I missed the point of your question. Any prime will generally give 
a good distribution. But a Mersenne Prime allows you to avoid a divide. 

Tom

Sent from my iPhone

> On Feb 23, 2022, at 4:37 PM, Paul Gilmartin 
> <0014e0e4a59b-dmarc-requ...@listserv.uga.edu> wrote:
> 
>> On Feb 23, 2022, at 14:00:21, Tom Harper wrote:
>> 
>> 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. 
>> 
> Why a Mersenne Prime?  The first thing I find is:
> 
>The key is that you can compute x mod p really fast if p is a Mersenne 
> prime.
> 
> Is this a significant advantage on z hardware?
> 
> Are name/token services, IEANTCR/IEANTRT useful here?
> 
> -- 
> gil



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.

Re: SRST vs. SRSTU

[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: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  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.

Re: SRST vs. SRSTU

[Tom Harper]

Gil, it has nothing to do with hardware speed it just gives a better 
distribution of hash values. 

Sent from my iPhone

> On Feb 23, 2022, at 4:37 PM, Paul Gilmartin 
> <0014e0e4a59b-dmarc-requ...@listserv.uga.edu> wrote:
> 
>> On Feb 23, 2022, at 14:00:21, Tom Harper wrote:
>> 
>> 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. 
>> 
> Why a Mersenne Prime?  The first thing I find is:
> 
>The key is that you can compute x mod p really fast if p is a Mersenne 
> prime.
> 
> Is this a significant advantage on z hardware?
> 
> Are name/token services, IEANTCR/IEANTRT useful here?
> 
> -- 
> gil



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.

Re: SRST vs. SRSTU

[Paul Gilmartin]

On Feb 23, 2022, at 14:00:21, Tom Harper wrote:
> 
> 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. 
>  
Why a Mersenne Prime?  The first thing I find is:

The key is that you can compute x mod p really fast if p is a Mersenne 
prime.

Is this a significant advantage on z hardware?

Are name/token services, IEANTCR/IEANTRT useful here?

-- 
gil

Re: SRST vs. SRSTU

[Tom Harper]

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  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.

Re: SRST vs. SRSTU

[Dan Greiner]

Gary,

Aside from some minor differences with end-of-second-operand determination, 
SRST and STRTU do pretty much the same thing, and it doesn't take the CPU any 
longer to compare one byte versus two. So the only possible explanation that I 
can think of to account for the differences in performance is the possibility 
that your operands are not equivalently aligned, and the STSTU case is 
experiencing cache-miss or page-fault delays that don't occur with SRST.

I also agree with Ed Jaffe ... if you have the flexibility to use the vector 
instructions, string searches can be spiffed up quite a bit.

Re: SRST vs. SRSTU

[Gary Weinhold]

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.

Re: SRST vs. SRSTU

[Charles Mills]

I was going to say all of these same things ... plus

Consider two tables, one of "stable keys" and one of "new keys." Sort and
binary search the stable list; do a linear search on the additions.

You can pseudo-delete a key from the stable table by turning on a "deleted"
flag.

You might also consider a B-Tree that you update dynamically.

For either of these possibilities you need to consider frequency of update
versus frequency of lookup.

Charles


-Original Message-
From: IBM Mainframe Assembler List [mailto:ASSEMBLER-LIST@LISTSERV.UGA.EDU]
On Behalf Of Tom Harper
Sent: Tuesday, February 22, 2022 2:45 PM
To: ASSEMBLER-LIST@LISTSERV.UGA.EDU
Subject: Re: SRST vs. SRSTU

Gary,

The first thought that comes to mind is why not sort the table and use a
binary search?

If in fact the table is being updated and that is not practical, then your
options are a serial search (which you have ruled out) or a hash. 

As you may have guessed, SRST and SRSTU are almost certainly milli-coded
instructions and probably not very fast. 

Secondly, hash performance is highly dependent on the number of synonyms you
have. Considering how many entries in your table, this is a distinct
possibility. A full word makes for a large number of entries. The best hash
tables are of a size of a Mersenne Prime. Right now you are not using one. 

Lastly, obtain storage for your table in a one Mb page frame to minimize TLB
misses. 

Summary:

1 - If table is static, sort and use a binary search.

2 - Otherwise, create a hash table of a Mersenne Prime of size large enough
to avoid most synonyms. 

Tom Harper

Phoenix Software International 

Sent from my iPhone

> On Feb 22, 2022, at 5:09 PM, Gary Weinhold  wrote:
> 
> We are trying to optimize a search routine for keys in fixed length rows
in an unordered array.  As the number of rows in the array grows, a serial
search becomes relatively inefficient, so we looked for another technique.
We tried a SEARCH STRING (SRST) against a one byte hash of the key to see if
it could give us better performance.  The relative positive of the matching
byte in the SRST array was used to determine the location of the key in the
original array; if the keys match, the row is found; if they don't match, we
redrive the SRST.  At about 50 rows, SRST is more efficient than a serial
search so it justifies maintaining the hash array.
>  On the average, we assume the SRST would have to be redriven about
(n/256)/2 times, where n is the number of rows in the array.  This would not
be a big factor for several thousand rows, but as the number of rows went
into the tens of thousands, we tried Search String Unicode (SRSTU).  It
appears to be identical to SRST, except it compares 2-byte values (at 2-byte
boundaries). So we created a 2-byte hash and, using the same technique based
on relative position, tested for performance improvements compared to SRST
when the number of rows exceeded 1.  We thought that the reduction in
the number of redrives due to non-matching keys (on average,  (n/65536)/2)
would more than offset the hash array doubling in size.
> 
> Our preliminary results show SRSTU about taking about 50-60% more time for
15000 and 25000 rows.  That came as a surprise to us.  We will do more
testing.
> 
> Is there a possibility we are encountering a hardware vs. microcode
implementation of the instuctions?  Has anyone else tested the performance
of these instructions?
> 
> Regards, Gary
> 
> Gary Weinhold
> Senior Application Architect
> We are trying to optimize a search routine for keys in fixed length rows
in an unordered array.  As the number of rows in the array grows, a serial
search becomes relatively inefficient, so we looked for another technique.
We tried a SEARCH STRING (SRST) against a one byte hash of the key to see if
it could give us better performance.  The relative positive of the matching
byte in the SRST array was used to determine the location of the key in the
original array; if the keys match, the row is found; if they don't match, we
redrive the SRST.  At about 50 rows, SRST is more efficient than a serial
search so it justifies maintaining the hash array.
>  On the average, we assume the SRST would have to be redriven about
(n/256)/2 times, where n is the number of rows in the array.  This would not
be a big factor for several thousand rows, but as the number of rows went
into the tens of thousands, we tried Search String Unicode (SRSTU).  It
appears to be identical to SRST, except it compares 2-byte values (at 2-byte
boundaries). So we created a 2-byte hash and, using the same technique based
on relative position, tested for performance improvements compared to SRST
when the number of rows exceeded 1.  We thought that the reduction in
the number of redrives due to non-matching keys (on average,  (n/65536)/2)
would more than offset the hash array doubling in size.
> 
> Our preliminary results sh

Re: SRST vs. SRSTU

[Ed Jaffe]

On 2/22/2022 2:44 PM, Tom Harper wrote:

As you may have guessed, SRST and SRSTU are almost certainly milli-coded 
instructions and probably not very fast.


In our benchmark testing, SRST reined supreme as the fastest 
single-character linear search BY FAR until we discovered how to use the 
vector facility.



--
Phoenix Software International
Edward E. Jaffe
831 Parkview Drive North
El Segundo, CA 90245
https://www.phoenixsoftware.com/



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.

Re: SRST vs. SRSTU

[Tom Harper]

Gary,

The first thought that comes to mind is why not sort the table and use a binary 
search?

If in fact the table is being updated and that is not practical, then your 
options are a serial search (which you have ruled out) or a hash. 

As you may have guessed, SRST and SRSTU are almost certainly milli-coded 
instructions and probably not very fast. 

Secondly, hash performance is highly dependent on the number of synonyms you 
have. Considering how many entries in your table, this is a distinct 
possibility. A full word makes for a large number of entries. The best hash 
tables are of a size of a Mersenne Prime. Right now you are not using one. 

Lastly, obtain storage for your table in a one Mb page frame to minimize TLB 
misses. 

Summary:

1 - If table is static, sort and use a binary search.

2 - Otherwise, create a hash table of a Mersenne Prime of size large enough to 
avoid most synonyms. 

Tom Harper

Phoenix Software International 

Sent from my iPhone

> On Feb 22, 2022, at 5:09 PM, Gary Weinhold  wrote:
> 
> We are trying to optimize a search routine for keys in fixed length rows in 
> an unordered array.  As the number of rows in the array grows, a serial 
> search becomes relatively inefficient, so we looked for another technique.  
> We tried a SEARCH STRING (SRST) against a one byte hash of the key to see if 
> it could give us better performance.  The relative positive of the matching 
> byte in the SRST array was used to determine the location of the key in the 
> original array; if the keys match, the row is found; if they don't match, we 
> redrive the SRST.  At about 50 rows, SRST is more efficient than a serial 
> search so it justifies maintaining the hash array.
>  On the average, we assume the SRST would have to be redriven about (n/256)/2 
> times, where n is the number of rows in the array.  This would not be a big 
> factor for several thousand rows, but as the number of rows went into the 
> tens of thousands, we tried Search String Unicode (SRSTU).  It appears to be 
> identical to SRST, except it compares 2-byte values (at 2-byte boundaries). 
> So we created a 2-byte hash and, using the same technique based on relative 
> position, tested for performance improvements compared to SRST when the 
> number of rows exceeded 1.  We thought that the reduction in the number 
> of redrives due to non-matching keys (on average,  (n/65536)/2) would more 
> than offset the hash array doubling in size.
> 
> Our preliminary results show SRSTU about taking about 50-60% more time for 
> 15000 and 25000 rows.  That came as a surprise to us.  We will do more 
> testing.
> 
> Is there a possibility we are encountering a hardware vs. microcode 
> implementation of the instuctions?  Has anyone else tested the performance of 
> these instructions?
> 
> Regards, Gary
> 
> Gary Weinhold
> Senior Application Architect
> We are trying to optimize a search routine for keys in fixed length rows in 
> an unordered array.  As the number of rows in the array grows, a serial 
> search becomes relatively inefficient, so we looked for another technique.  
> We tried a SEARCH STRING (SRST) against a one byte hash of the key to see if 
> it could give us better performance.  The relative positive of the matching 
> byte in the SRST array was used to determine the location of the key in the 
> original array; if the keys match, the row is found; if they don't match, we 
> redrive the SRST.  At about 50 rows, SRST is more efficient than a serial 
> search so it justifies maintaining the hash array.
>  On the average, we assume the SRST would have to be redriven about (n/256)/2 
> times, where n is the number of rows in the array.  This would not be a big 
> factor for several thousand rows, but as the number of rows went into the 
> tens of thousands, we tried Search String Unicode (SRSTU).  It appears to be 
> identical to SRST, except it compares 2-byte values (at 2-byte boundaries). 
> So we created a 2-byte hash and, using the same technique based on relative 
> position, tested for performance improvements compared to SRST when the 
> number of rows exceeded 1.  We thought that the reduction in the number 
> of redrives due to non-matching keys (on average,  (n/65536)/2) would more 
> than offset the hash array doubling in size.
> 
> Our preliminary results show SRSTU about taking about 50-60% more time for 
> 15000 and 25000 rows.  That came as a surprise to us.  We will do more 
> testing.
> 
> Is there a possibility we are encountering a hardware vs. microcode 
> implementation of the instuctions?  Has anyone else tested the performance of 
> these instructions?
> 
> Regards, 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