Linear search vs binary

[Dougie Lawson]

If I have a table of 3,500 entries of twelve bytes (I'm doing a compare of
eight bytes to find the entry I'm looking for and a check on a half word
marker for the end of the table to avoid running off the end) then is it
worth the pain of re-writing it as a binary search.

If it is worth the pain and does anyone have a sample binary search tucked
away.

The table is built into a CSECT at the bottom of my code. I can restructure
it if we need any special pointers to make a binary search work.

Dougie

[Rob van der Heij]

If you want to make it 4096 entries, you could step through the table with
binary search very cheap by shifting a mask on each pass. I would already
think about it with 35 entries... ;-)

[Bodoh John Robert [Contractor]]

I would use a hash table. It's much faster.

John

[Martin Truebner]

As Rob has already said- YES it is worth it

I say that too- worth it- here is my point.

assumptions:

1.) every instr is one unit (yes I know this is pretty simple but ...)

2.) random access pattern

----so here we go

a simple search is n instructions-

a binary search is +x instructions

for any number it needs exponent for next power of two

so for 50 entries you need
normal 25 times your loop
binay 6 (50 ---> 64 is 2**6)

so if your new code is 10 (=x)extra instructions (on top of 4 for n)

you are still better off doing it binary (4*25 vs: 6*(10+4))

now the big question: who is willing to post code?

--
Martin

Pi_cap_CPU - all you ever need around MWLC/SCRT/CMT in z/VSE
more at http://www.picapcpu.de

[Alan Atkinson]

Leaving aside hashing and suchlike, we've used this for a while in multiple places.
It's a ripoff of the C binsrch algorithm in the Tenenbaum data structures book, so there's nothing ~that~ proprietary about it.

I edited it to take out our specific stuff, so check carefully as I may have missed a variable.
I'm sure it's easy to rip apart from an elegance standpoint, but it does what it says on the tin well enough.
I removed all our site specific macros, so you should be able to adapt it easily enough.

***********************************************************************
* BINARY SEARCH FOR REQUESTED TABLE ENTRY *
* NTRY: R1: KEY TO FIND *
* EXIT: FULL: A(RECORD) - CC:EQ *
* FULL: A(INSERTION POINT) - CC:NEQ *
***********************************************************************
SPACE 1
BSRCH <use your favorite register preserving macro>
LR R4,R1 R4 = A(KEYARG)
L R5,=A(YOUR TABLE) R5 = A(START OF DATA)
L R0,=A(length of table) R0 = LENGTH OF DATA IN BUFFER
SRDL R0,32
*
LHI RF,l'single entry RF = LENGTH OF SINGLE ENTRY
DR R0,RF
CHI R1,6
BL SQSRCH LESS THAN 6 - DO SEQUENTIAL SEARCH
*
XR R0,R0 R0 = LOW
BCTR R1,0 R1 = HIGH
LHI RE,l'key-1 RE = L'KEY-1
*
BSRCH02 CR R0,R1 WHILE LOW <= HIGH
BH BSRCH04 R0 POINTS TO INSERTION POINT
*
LR R3,R0 R3 = MID
AR R3,R1
SRL R3,1 MID=(HIGH+LOW)/2
*
LR RF,R3
MH RF,ISKEYLN4
AR RF,R5 RF=A(TEST ENTRY)
*
EX RE,BSMTCH TRY TO MATCH KEY
BE BSXIT KEY == K(MID)
*
BL *+12
LA R0,1(R3) IF CC HIGH : LOW = MID+1
B BSRCH02
*
LR R1,R3 IF CC LOW : HIGH = MID-1;
BCTR R1,0
B BSRCH02
*
BSRCH04 LR RF,R0
MH RF,ISKEYLN4
AR RF,R5
B BSXIT
*
SQSRCH L RF,=A(YOUR TABLE)

L R1,=A(YOUR TABLE)
A R1,=a(l'table)
AHI R1,l'entry R1 = A(LAST ENTRY)
*
LHI R0,l'entry R0 = L'ENTRY
LHI RE,l'key-1 RE = L'KEY-1
*
SSRCH02 EX RE,BSMTCH TRY TO MATCH KEY
BNH BSXIT
BXLE RF,R0,SSRCH02
DC H'0'
*
BSMTCH CLC 0(0,R4),0(RF) COMPARE REQUESTED KEY WITH RECORD
*
BSXIT ST RF,FULL
<restore your registers>

[Paul Raulerson]

Guys- doesn't that depend - a lot - on how often the code is actually executed? A couple billion times a day makes it a no-brainer to do a binary search, a couple thousand times per day, perhaps just the opposite.

Paul


Typos courtesy of my iPhone and my fat fingers!

[Alan Atkinson]

Bad edit - sorry.

SQSRCH L RF,=A(YOUR TABLE)

L R1,=A(YOUR TABLE)
A R1,=a(l'table)
AHI R1,l'entry R1 = A(LAST ENTRY)

Should be

SQSRCH L RF,=A(YOUR TABLE)

L R1,=A(YOUR TABLE)
A R1,=a(l'table)

AHI R1,-l'entry R1 = A(LAST ENTRY)

The code's from 98. All our lengths are in literals and I added the immediate instructions when I amended it.
Type in haste, repent at leisure. Mea culpa.

[John Gilmore]

For match-seeking binary search Knuth's classical figure of merit for
an ordered table of n elements is

M(n) = 2[(n + 1)q + 2e] � n

in which q = floor[log2(n + 1)] and e = n - (2**q - 1).

Here q = 11, e = 3500 - 2047 = 1453, and thus

M(3500) = 2[3501 x 11 + 2 x 1453] - 3500 = 78324

For linear search of an ORDERED table, Knuth again, the best scheme
seeks 1) a glb on the search argument in the table and then 2) tests
it for a match. This scheme has

L(n) = 2n[(n + 1)/2 + 3n = n(n + 4)

Thus L(3500) = 3500 x 3504 = 12264000

Then

L(3500)/M(3500) = 12264000/78324 = 156.58.

Predictably, the logarithmic-time binary-search scheme is much better,
156 times better here, than the polynomial-time linear-search one for
non-trivial n.

If you are going to search this table at all frequently, the case for
using binary search is compelling; if not, maybe not.

John Gilmore, Ashland, MA 01721 - USA

[John Gilmore]

Perhaps also worth noting explicitly is that the linear-search scheme
done well is not significantly less complex than the binary-search
one.

[retired mainframer]

Obviously your data must be sorted for the question to be relevant. Is it
already sorted or is the cost of sorting it part of the difference?

If your search target is uniformly distributed against the key, then on
average a linear search will require 1750 iterations of your compare loop.
A binary search will require a constant 12 iterations regardless of
distribution.

Only you can decide if the savings in processing time is worth the cost to
make the change and the potential additional testing/maintenance effort due
to the added complexity.

:>: -----Original Message-----
:>: From: IBM Mainframe Assembler List [mailto:ASSEMBLER-
:>: LI...@LISTSERV.UGA.EDU] On Behalf Of Dougie Lawson
:>: Sent: Monday, October 21, 2013 4:32 AM
:>: To: ASSEMBL...@LISTSERV.UGA.EDU
:>: Subject: Linear search vs binary
:>:
:>: If I have a table of 3,500 entries of twelve bytes (I'm doing a compare

[Paul Gilmartin]

On 2013-10-21, at 07:13, John Gilmore wrote:

> Perhaps also worth noting explicitly is that the linear-search scheme
> done well is not significantly less complex than the binary-search
> one.
>

You've earlier advocated the value of comparison operands having
a ternary result. Of course this is available in (zSeries)
assembler. It might typically shorten a table search by one
iteration.

o What HLLs provide ternary comparison operators?

o Is an optimizing compiler likely to collapse two consecutive
comparisions with identical operands into a single comparison
operation followed by two conditional branches?

o In what langages does a comparison yield a ternary R-value; one
which could be assigned to a variable for future use?
(Assembler could be considered to provide this by storing the
condition code in the program mask.)

-- gil

[DASDBILL2]

It is not worth the pain of changing it if this code is only executed once a day.  It is absolutely essential to change it if this code is executed one thousand times per second, in disabled code, some other process is waiting for this code to finish, you hold a lock, etc., etc. etc.
In other words, ID. [1[
 
Bill Fairchild
Franklin, TN
 
[1] It Depends.

----- Original Message -----

From: "Dougie Lawson" <dl1...@gmail.com>
To: ASSEMBL...@LISTSERV.UGA.EDU
Sent: Monday, October 21, 2013 6:32:15 AM
Subject: Linear search vs binary

[Paul Gilmartin]

> ----- Original Message -----
>
> From: "Dougie Lawson" <dl1...@gmail.com>
> To: ASSEMBL...@LISTSERV.UGA.EDU
> Sent: Monday, October 21, 2013 6:32:15 AM
> Subject: Linear search vs binary
>
> If I have a table of 3,500 entries of twelve bytes (I'm doing a compare of
> eight bytes to find the entry I'm looking for and a check on a half word
> marker for the end of the table to avoid running off the end) then is it
> worth the pain of re-writing it as a binary search.
>
> If it is worth the pain and does anyone have a sample binary search tucked
> away.
>
> The table is built into a CSECT at the bottom of my code. I can restructure
> it if we need any special pointers to make a binary search work.
>

You need at least a pointer to the end of the table. Otherwise,
the preliminary scan for the end marker costs twice as much as
doing a linear search, on the average.

And the table needs to be sorted, but only once.

Unless there are dynamic insertions and deletions. If these are
frequent, a tree structure might be preferable.

-- gil

[John Gilmore]

The arithmetic function that mathematicians call signum, viz., for an
arithmetic expression x

signum(x) = -1, a < 0,
signum(x) = 0, a = 0,
signum(x) = +1, a > 0

is available as a BIF called sign in PL/I, where it is [almost always]
implemented in line. An analogous function is available for strings
in C, where it is implemented as a library subroutine. It has always
been available in FORTRAN in the form of the much deprecated but in
fact enormously useful arithmetic-IF statement

When it is implemented in statement-level procedural languages each
iteration of a binary search typically makes a second binary
comparison iff a first one fails. There is an optimal ordering of
these comparisons, which depends upon how middling subscript values
are calculated, but the details are probably TMI here.

For the modestly suboptimal case in which the search argument is
compared first with a current middling table element for equality, it
is clear that two comparisons---binary ones implemented at the
machine-code level as specialized ternary ones--are executed for all
but the last iteration of successful searches, of which there are n.

For most SLPL implementations Knuth's M(n) thus becomes something like

M*(n) = 2M(n) - n

The number of comparison operations--This number for the usual 2n + 1q
search arguments is Knuth's figure of merit for binary-search
schemes--is thus roughly doubled.
The availability of a ternary comparison is thus very important for
binary-search performance. (This issue is often, even usually, fudged
in programmjing texts for ideological reasons. Ternary-comparison
operations are judged to be 'unstructured', even 'anarchic' by many
academics. In fact some uses of them are and some are not; but this
distinction is judged oversubtle for their students.)

No optimizing compiler rhat I am familiar, including the current
shared C and PL/I optimizer, collapses sequences of binary comparisons
into a smaller number of ternary ones; and this would be difficult to
do in general, although compact special cases like those that occur
typically in binary-search routines are probably tractable.

[Dougie Lawson]

On 21 October 2013 13:34, Alan Atkinson <aatk...@mediaocean.com> wrote:

>
> MH RF,ISKEYLN4
>

Hi Alan,

Thanks for the code sample. I wasn't sure what value that ISKEYLN4 half
word should hold.

I found a really neat macro as part of IMS (member IMSORT in IMS.SDFSMAC)
which means I can easily build a static table that is quicksorted (by the
assembler) into alpha order. That's saved me a lot of work.

Regards, Dougie.

--
http://twitter.com/DougieLawson

[Alan Atkinson]

ISKEYLN4 is the length of an entire entry - 12 bytes in your case iirc.
I did say I may not have edited it as well as I might have.

-----Original Message-----
From: IBM Mainframe Assembler List [mailto:ASSEMBL...@LISTSERV.UGA.EDU] On Behalf Of Dougie Lawson
Sent: Monday, October 21, 2013 1:29 PM
To: ASSEMBL...@LISTSERV.UGA.EDU
Subject: Re: Linear search vs binary

[Gerhard Postpischil]

On 10/21/2013 1:06 PM, John Gilmore wrote:
> It has always
> been available in FORTRAN in the form of the much deprecated but in
> fact enormously useful arithmetic-IF statement

Which brings up the question of whether the trinary compare results
(e.g., CAS [Compare Accumulator to Storage] on the 704 and later
machines) was requested by the ForTran team, or whether they designed
the arithmetic IF because the hardware supported it?

Gerhard Postpischil
Bradford, Vermont

[John Gilmore]

John McCarthy, who for a time used CAS---as well as CAR and CADDR,
which survived---in LISP, thought that the instruction came first,
i.e., that the instruction was the model for the arithmetic-IF
statement. It is my guess that he was right, but it may now be too
late to resolve this particular chicken-egg conundrum. What is clear
is that the two were closely linked.

It is known, was indeed emphasized by Backus, is that he was much
concerned not to deprive 704 assembly-language programmers of
facilities they prized. His situation was very different from ours
today. He wanted to open up programming to others, but he crucially
needed to convince 704 assembly-language programmers of the
time---There were no others---that FORTRAN was not a performance dog;
and to this end he tried very hard to make analogues of the crucial
704 machine instructions available in FORTRAN.

I looked shortly after his death in 2007 to see if there were any oral-history
recordings of interviews with him, but found notjhing but some
sanitized, hagiographic IBM materials. There may now be more out
there, and I understand that there is a biography in the works.

[Gainsford, Allen]

> It is known, was indeed emphasized by Backus, is that he was much
> concerned not to deprive 704 assembly-language programmers of
> facilities they prized. His situation was very different from
> ours today. He wanted to open up programming to others, but he
> crucially needed to convince 704 assembly-language programmers of
> the time---There were no others---that FORTRAN was not a
> performance dog; and to this end he tried very hard to make
> analogues of the crucial 704 machine instructions available in
> FORTRAN.

Whereas nowadays IBM seem to add new instructions to support the programming languages!

[Robert A. Rosenberg]

At 06:27 -0700 on 10/21/2013, retired mainframer wrote about Re:
Linear search vs binary:

>If your search target is uniformly distributed against the key, then on
>average a linear search will require 1750 iterations of your compare loop.
>A binary search will require a constant 12 iterations regardless of
>distribution.

One trick that would make the binary search code simpler is to make
the table 4096 entries long not 3500 long. Place 298 low value
entries, then the 3500 live entries, and then 298 high values. This
will cause some wasted compares when you hit the padding low/high
values but you do not need to worry about how to spit the table in
half for each round (the size is always the prior power of 2).

[Paul Gilmartin]

I believe this is a fortiori true for FORTRAN's signum function
because that was a hardware instruction on the 704.

And that Wirth made cardinality a function in Pascal because it
was a machine instruction on the CDC 6600.

But that had disastrous consequences. Operator precedence in
Pascal is pernicious; I suspect that the reason is that Wirth
wanted not to allow more nonterminal symbols in the grammar
than could be represented in a bitset in a 60-bit word.

-- gil

[Paul Gilmartin]

On 2013-10-21 11:06, John Gilmore wrote:
>
> [signum] is available as a BIF called sign in PL/I, where it is [almost always]

> implemented in line. An analogous function is available for strings
> in C, where it is implemented as a library subroutine. It has always
> been available in FORTRAN in the form of the much deprecated but in
> fact enormously useful arithmetic-IF statement
>

(They seem to have borrowed the name from FORTRAN.)

One might consider implementing a dyadic signum as:

#define signum2( a, b ) ( ( ( a ) < ( b ) ) - ( ( a ) > ( b ) ) )

... in any language where TRUE==1 and FALSE==0. (Is this the case in
PL/I?)

Beware the shortcut:

#define signum2( a, b ) ( signum( ( b ) - ( a ) ) )

... which misbehaves for extreme values of a and b.

Alas, I know of no C implementation which reports integer overflow
of signed operands, although ANSI tolerates this behavior. I prefer
to be told of such exceptional conditions. (Didn't you say that PL/I
lately robbed programmers of that facility?) I find a few occurrences
of FPE_INTOVF buried in /usr/include.

-- gil

[John Gilmore]

PL/I was robbed of FIXEDOVERFLOW for binary fixed values. It is still
available for PL/I decimal fixed, i.e., packed decimal values.

The LE does in fact make a facility available for executing what is in
efffect an arbitrary SPM instruction; but it is documented so
poorly---It has been all but hidden---that it is difficult to use.
When binary FIXEDOVERFLOW is important I now do the arithmetic in an
assembly-language subroutine.

This a is a pity, a disagreeable consequence of the fact that much
PL/I implementation machinery is now shared with C; but it must be
conceded that there have been benefits too, e.g., for select groups
that are exact functional equivalents of licit C switch statements,
which are now better optimized than they once were.

[Paul Gilmartin]

On 2013-10-21 16:31, John Gilmore wrote:
> PL/I was robbed of FIXEDOVERFLOW for binary fixed values. It is still
> available for PL/I decimal fixed, i.e., packed decimal values.
>

> ...

>
> This a is a pity, a disagreeable consequence of the fact that much

> PL/I implementation machinery is now shared with C; ...
>
Truly a pity because reporting fixed overflow is entirely compatible
with the ANSI specification of C. I suspect some of the motivation
lies in LE library routines which carelessly generate fixed overflow,
smugly expecting it will be ignored, and which programmers lack the
ambition to correct.

Likewise, IBM's C some time ago made the invalid dereferencing of
NULL behave as a reference to "", in deference to pervasive misusage.

-- gil

[robin]

From: "John Gilmore" <jwgl...@gmail.com>
Sent: Tuesday, October 22, 2013 9:31 AM

> PL/I was robbed of FIXEDOVERFLOW for binary fixed values.

Use SIZE instead.

> It is still
> available for PL/I decimal fixed, i.e., packed decimal values.
>
> The LE does in fact make a facility available for executing what is in
> efffect an arbitrary SPM instruction; but it is documented so
> poorly---It has been all but hidden---that it is difficult to use.
> When binary FIXEDOVERFLOW is important I now do the arithmetic in an
> assembly-language subroutine.

Use SIZE instead. SIZE is raised for fixed binary overflow.

[Rob van der Heij]

Since the machine architectures that came to mind all have this 3-state
result after comparison, I expected the compiler to take advantage of it
when I write something like
if ( j < k ) m = -1;
else if (j > k) m = 1;
else m = 0;
return m;

A few surprises with gcc, like pretty dumb code without -O3 and then very
smart code with -O3 :-) and the result is below. What I considered
interesting is that we indeed have a single "CR" followed by the "JL" and
"JNLE" so the language allows me to express this situation properly. I
suppose the "LHI" at 062E is also done early to take advantage of the
pipeline?

(the setting of the scene is with R10 and R2 holding "j" and "k"
respectively')

80000628: 19 a2 cr %r10,%r2
8000062a: a7 44 00 1a jl 8000065e <main+0x6a>
8000062e: a7 28 00 00 lhi %r2,0
80000632: a7 34 00 0b jnle 80000648 <main+0x54>
80000636: e3 40 f1 10 00 04 lg %r4,272(%r15)
8000063c: b9 14 00 22 lgfr %r2,%r2
80000640: eb af f0 f0 00 04 lmg %r10,%r15,240(%r15)
80000646: 07 f4 br %r4
80000648: a7 28 00 01 lhi %r2,1
8000064c: e3 40 f1 10 00 04 lg %r4,272(%r15)
80000652: b9 14 00 22 lgfr %r2,%r2
80000656: eb af f0 f0 00 04 lmg %r10,%r15,240(%r15)
8000065c: 07 f4 br %r4
8000065e: a7 28 ff ff lhi %r2,-1
80000662: e3 40 f1 10 00 04 lg %r4,272(%r15)
80000668: b9 14 00 22 lgfr %r2,%r2
8000066c: eb af f0 f0 00 04 lmg %r10,%r15,240(%r15)
80000672: 07 f4 br %r4

[robin]

From: "Rob van der Heij" <rvd...@gmail.com>
Sent: Wednesday, October 23, 2013 8:12 PM

> Since the machine architectures that came to mind all have this 3-state
> result after comparison, I expected the compiler to take advantage of it
> when I write something like
> if ( j < k ) m = -1;
> else if (j > k) m = 1;
> else m = 0;
> return m;

It is sufficient to write:
return (sign(j-k) );

[John Gilmore]

Rob,

Interestingly, when I take your C example,

if ( j < k ) m = -1;
else if (j > k) m = 1;
else m = 0;
return m;

and rewrite it trivially modified in PL/I as

if j < k then m = -1;
else if j > k then m = 1;
else m = 0;
return (m);

I cannot reproduce your results.

[Rob van der Heij]

I understand. I don't even need a computer to do that :-) The "return" was
just to discourage the optimizer to throw away all the code because I
didn't use the result.

The thing that kept me awake briefly was whether the optimizer would
recognize that the shortcut and code a single compare with two branches
using the CC. I suppose my next attempt would have been a case statement
using sign()

Rob

[robin]

From: "Dougie Lawson" <dl1...@gmail.com>
Sent: Monday, October 21, 2013 10:32 PM

> If I have a table of 3,500 entries of twelve bytes (I'm doing a compare of
> eight bytes to find the entry I'm looking for and a check on a half word
> marker for the end of the table to avoid running off the end) then is it
> worth the pain of re-writing it as a binary search.
>
> If it is worth the pain and does anyone have a sample binary search tucked
> away.
>
> The table is built into a CSECT at the bottom of my code. I can restructure
> it if we need any special pointers to make a binary search work.

This may help:-

Array c has lower bound 0, upper bound n:
i = -1; k = n+1; /* pointers that always point beyond the smallest and largest values */
do while (i+1 < k);
m = isrl(i+k,1);
if c(m) > j then k = m;
else if c(m) < j then i = m;
else return (m); /* element found */
end;
return (-1); /* element not found. */

[Dougie Lawson]

Hi Alan,

I found some test data.

I found a ready written IMS macro to sort my test data (which was a real
bonus).

And I got your code sample to run and get the right answer.

Thank you - I owe you a virtual beer.

To all the other correspondents - thank you - a simple request has
generated some extremely lively discussion (from some of the usual
suspects).

Dougie

[robin]

From: "John Gilmore" <jwgl...@gmail.com>
Sent: Wednesday, October 23, 2013 10:02 PM

> Interestingly, when I take your C example,
>
> if ( j < k ) m = -1;
> else if (j > k) m = 1;
> else m = 0;
> return m;
>
> and rewrite it trivially modified in PL/I as
>
> if j < k then m = -1;
> else if j > k then m = 1;
> else m = 0;
> return (m);
>
> I cannot reproduce your results.

What does it produce (under highest optimisation) ?

[Paul Gilmartin]

What are the representations of boolean values in PL/I?
In Rexx, this could be written with no (explicit) branches
as:

m = ( j > k ) - ( j < k );

-- gil

[John Gilmore]

Boolean values are bits in PL/I.

Writing, say,

declare (a,b, d) signed binary fixed(63,0), signum signed binary fixed(7, 0),
(bigger, equal, smaller) aligned bit ;

permits either

d = a - b ;
select ;
when(d > 0) signum = +1 ;
when(d = 0) signum = 0 ;
when(d < 0) signum = -1 ;
end ;

or

d = a - b ;
bigger = (d > 0
equal = (d = 0) ;
smaller = (d < 0) ;

but nothing quite like your REXX construct is available.

[robin]

From: "Paul Gilmartin" <PaulGB...@aim.com>
Sent: Thursday, October 24, 2013 2:28 AM

>What are the representations of boolean values in PL/I?

A single bit.
True is 1, false is 0.

> In Rexx, this could be written with no (explicit) branches
> as:
>
> m = ( j > k ) - ( j < k );

In PL/I,
m = sign(j-k);

[robin]

What? Rexx's m = ( j > k ) - ( j < k );

would be exactly the same in PL/I.

However, you would never write it like that. It's just obfuscation.

simplest (and trivial-est) in PL/I is m = sign(j-k);

[Paul Gilmartin]

On 2013-10-23 17:26, robin wrote:
>
>> In Rexx, this could be written with no (explicit) branches
>> as:
>>
>> m = ( j > k ) - ( j < k );
>
> In PL/I,
> m = sign(j-k);
>

The objective was to synthesize sign() in a language such as
Rexx which, unlike PL/I, lacks it. I have occasionally gotten
flamboyant and coded such as:

X = copies( 'gubbins', A==B ) /* instead of: */

if A==B
then X = 'gubbins'
else X = ''

Clearly, I've been polluted by excessive exposure to CDC 6600,
whose programmers went to extremes to avoid branches which
might break pipelining.

On 2013-10-23 15:09, John Gilmore wrote:
> Boolean values are bits in PL/I.

> ...

> but nothing quite like your REXX construct is available.
>

IOW, PL/I provides no coercion from boolean (bit) values to
integer?

("[my] REXX construct"? It's conventional; I lay no claim
to originality.)

--- gil

[Paul Gilmartin]

On 2013-10-23 17:33, robin wrote:
>
> What? Rexx's m = ( j > k ) - ( j < k );
>
> would be exactly the same in PL/I.
>
> However, you would never write it like that. It's just obfuscation.
>
> simplest (and trivial-est) in PL/I is m = sign(j-k);
>

But beware: for extreme values of j and k this might result in
an undetected overflow (is this nowadays called an ON SIZE
condition?) and undesired results.

-- gil

[robin]

From: "Paul Gilmartin" <PaulGB...@aim.com>
Sent: Tuesday, October 22, 2013 1:42 AM

> On 2013-10-21, at 07:13, John Gilmore wrote:
>
>> Perhaps also worth noting explicitly is that the linear-search scheme
>> done well is not significantly less complex than the binary-search
>> one.
>>
> You've earlier advocated the value of comparison operands having
> a ternary result. Of course this is available in (zSeries)
> assembler. It might typically shorten a table search by one
> iteration.

How is that?

> o What HLLs provide ternary comparison operators?
>
> o Is an optimizing compiler likely to collapse two consecutive
> comparisions with identical operands into a single comparison
> operation followed by two conditional branches?
>
> o In what langages does a comparison yield a ternary R-value; one
> which could be assigned to a variable for future use?
> (Assembler could be considered to provide this by storing the
> condition code in the program mask.)

PL/I provides the COMPARE built-in function, that compares
two operands and delivers -1, 0, or +1.

[Kurt LeBesco]

I've been reading quietly and wondering how the dialog drifted off to rexx
and pl1 land. Can we get back on topic? Thanks

[robin]

----- Original Message -----
From: "Paul Gilmartin" <PaulGB...@AIM.com>
To: <ASSEMBL...@LISTSERV.UGA.EDU>
Sent: Thursday, October 24, 2013 10:43 AM
Subject: Re: signum


> On 2013-10-23 17:26, robin wrote:
>>

>>> In Rexx, this could be written with no (explicit) branches
>>> as:
>>>
>>> m = ( j > k ) - ( j < k );
>>
>> In PL/I,
>> m = sign(j-k);
>>

> The objective was to synthesize sign() in a language such as
> Rexx which, unlike PL/I, lacks it.

The KISS principle is worthy of more attention.
An IF construct is more obvious.

> I have occasionally gotten
> flamboyant and coded such as:
>
> X = copies( 'gubbins', A==B ) /* instead of: */

You have to be joking.

> if A==B
> then X = 'gubbins'
> else X = ''

> Clearly, I've been polluted by excessive exposure to CDC 6600,
> whose programmers went to extremes to avoid branches which
> might break pipelining.

You can't avoid branches, either implicit or explicit.

> On 2013-10-23 15:09, John Gilmore wrote:
>> Boolean values are bits in PL/I.
>> ...
>> but nothing quite like your REXX construct is available.
>>
> IOW, PL/I provides no coercion from boolean (bit) values to
> integer?

Conversion from boolean to integer is readily available in PL/I.

[Paul Gilmartin]

On 2013-10-23 17:54, Kurt LeBesco wrote:
> I've been reading quietly and wondering how the dialog drifted off to rexx
> and pl1 land. Can we get back on topic? Thanks
>

OK. Pure HLASM. I've long wondered why division by zero is permitted
in arithmetic expressions when otherwise overflows (even in division)
are reported as errors.

The only rationale I can think of (and a poor one) is that it was
initially an implementation oversight that was so rapidly codified
by use that when it was discovered no repair was feasible.

-- gil

[Alan Atkinson]

Glad you got some use out of it.
It's a pretty simplistic implementation, but sufficient for our needs.

Although based on how rapidly the discussion veered into other languages I thought I'd missed your point somehow.




Sent from my iPad

[robin]

From: "Paul Gilmartin" <PaulGB...@AIM.com>
Sent: Thursday, October 24, 2013 10:47 AM

Any overflow is detected.

And anyway, how do you think that J > K is computed?

The comparison is performed by subtracting K from J
(without changing either J or K, of course).

[Tony Harminc]

On 23 October 2013 19:43, Paul Gilmartin <PaulGB...@aim.com> wrote:
> I have occasionally gotten
> flamboyant and coded such as:
>
> X = copies( 'gubbins', A==B ) /* instead of: */
>
> if A==B
> then X = 'gubbins'
> else X = ''

That's a very APLish thing to do.

Tony H.

[Paul Gilmartin]

On 2013-10-23 17:51, robin wrote:
>>>
>> ... the value of comparison operands [operators -- gil] having

>> a ternary result. Of course this is available in (zSeries)
>> assembler. It might typically shorten a table search by one
>> iteration.
>
> How is that?
>

The search may be terminated early (however infrequently) on
discovering an exact match. But this requires an extra comparison
if ternary results are unavailable (as they are in assembler --
is that sufficiently on-topic?) The cost of that extra comparison
is unlikely to be offset by terminating the loop early (usually only
on the last iteration) if ternary comparisons are unavailable.

-- gil

[Kurt LeBesco]

Sounds like a plausible answer! My guess would be that IBM thought
assembler programmers sufficiently
Intelligent so as to avoid doing that!

[Paul Gilmartin]

On 2013-10-23 18:36, robin wrote:
>
> Any overflow is detected.
>
> And anyway, how do you think that J > K is computed?
>
> The comparison is performed by subtracting K from J
> (without changing either J or K, of course).

Why not use the Compare instruction? (As in Assembler
-- on-topic.)

-- gil

[robin]

From: "Paul Gilmartin" <PaulGB...@AIM.com>
Sent: Thursday, October 24, 2013 11:51 AM

That IS what a compare is (in hardware). C compares
by subtracting one operand from the other. (without changing
either operand).

[robin]

From: "Paul Gilmartin" <PaulGB...@AIM.com>
Sent: Thursday, October 24, 2013 11:30 AM

> OK. Pure HLASM. I've long wondered why division by zero is permitted

It is? According to my manual, the operation is suppressed,
and an exception occurs.

[Blaicher, Christopher Y.]

Never has been allowed. From the POPS for all integer divide instructions:

When the divisor is zero, or when the magnitudes of
the dividend and divisor are such that the quotient
cannot be expressed by a 32-bit signed binary integer,
a fixed-point-divide exception is recognized. This
includes the case of division of zero by zero.

For HFP divide it says:
When the divisor fraction is zero, an HFP-divide
exception is recognized. This includes the case of
division of zero by zero.

For BFP and DFP divide it says:
If the divisor is zero but the dividend is a finite number,
an IEEE-division-by-zero exception is recognized.
If the dividend and divisor are both zero, or if
both are infinity, regardless of sign, an IEEE-invalid operation
exception is recognized.

Chris Blaicher
Principal Software Engineer, Software Development
Syncsort Incorporated
50 Tice Boulevard, Woodcliff Lake, NJ 07677
P: 201-930-8260 | M: 512-627-3803
E: cbla...@syncsort.com

[Jon Perryman]

What arithmetic expression allows divide by 0?

Jon Perryman.

>________________________________
> From: Paul Gilmartin <PaulGB...@AIM.com>

[glen herrmannsfeldt]

From C28-6514-5 on bitsavers, on page 16:

"Division by zero is permitted and yields a zero result."

After that, (and presumably also earlier) it has to stay that
way as code (macros) might depend on that.

There is no reason given.

-- glen

[Rob van der Heij]

On 24 October 2013 02:43, Paul Gilmartin <PaulGB...@aim.com> wrote:

>
> The search may be terminated early (however infrequently) on
> discovering an exact match. But this requires an extra comparison
> if ternary results are unavailable (as they are in assembler --
> is that sufficiently on-topic?) The cost of that extra comparison
> is unlikely to be offset by terminating the loop early (usually only
> on the last iteration) if ternary comparisons are unavailable.
>

> From some code that I saw, it appeared that extra comparison was not to
improve performance but rather an assumed fix for using the wrong condition
for terminating the loop... But I have no right to speak after spending
several hours debugging a binary search and finding the input was not
sorted on that key ;-)

Rob

[Rob van der Heij]

I would be worried about (when the language permits it) x =
copies('gubbins', c=a==b)

No doubt a matter of style and experience, but I find if/then/else hard to
follow when reading. Especially when ident does not match the nesting. Once
you're familiar with the idioms, they reduce the amount of reading and
increase what you can oversee on a single screen or page.

Reducing the vocabulary does not make a coded algorithm easier to
understand. I you have no clue about binary search, then following the
if/then/else with your finger may not help you spot an error. Knowing the
language is the least of your concerns.

A popular one we use is this: return rc * (rc <> 12)
Or this (to assign defaults to missing arguments):
parse value subword(outf,1,3) subword('BUNDLE VMFPLC A', words(outf)+1)
with outf

Rob (almost Friday)

[robin]

From: "glen herrmannsfeldt" <g...@ugcs.caltech.edu>
Sent: Thursday, October 24, 2013 4:22 PM

> From C28-6514-5 on bitsavers, on page 16:

What manual is that; for what system, and what date?

[Rob van der Heij]

Ask someone for a web browser and type google.com ;-) OS assembler
language; 360, and december 1967

Many moons ago, a friend (who went to math school) showed me his scars and
explained that it were evil that compilers could optimize in such a way
that an attempt to divide by zero would go unnoticed. I believe most
languages now formally specify which parts of the expression may/will not
be computed when it can be avoided. Along the lines where you may write ( i
< n & table[i] > 0) without being concerned about stepping beyond your
table.

Rob

[Don Higgins]

All



I see discussion about optimizing the binary search, but I don't see any
discussion about optimizing linear search which might make it much faster
than binary depending on the search history. Putting the last key found at
front of most recently used list or just holding last found as a first test
may result in significant reduction in total search compares if there are
frequent repeat requests.



Don Higgins

d...@higgins.net

[robin]

From: "Rob van der Heij" <rvd...@gmail.com>
Sent: Thursday, October 24, 2013 9:35 PM

> Ask someone for a web browser and type google.com ;-) OS assembler
> language; 360, and december 1967

I have better things to do than do other people's research.

[DASDBILL2]

The Assembler language book does not describe how processor instructions work.  Processor instructions never have allowed division by zero.  The Assembler language book quote is describing how an arithmetic expression is evaluated at assembly time by the Assembler program.  This misconception is akin to finding a statement in a book about the XYZ compiler (where XYZ might be FORTRAN, PL/1, ALGOL/60, JOVIAL, APL, etc.) that says "division by zero is allowed if ...blah blah..." and then concluding that the processor itself has some kind of divide instruction which will not indicate an error if it attempts to use a divisor of zero.
The Assembler language book also describes Assembler language instructions such as SPACE, EJECT, PRINT NODATA, DSECT, etc.  These are also not processor instructions.  Without doing my homework, I would wager a large sum that somewhere in the beginning of the Assembler language book (introduction, prologue, whatever) is a statement that clarifies what the Assembler language book is not.
 
Bill Fairchild
Franklin, TN

----- Original Message -----

From: "Rob van der Heij" <rvd...@gmail.com>

[Rob van der Heij]

Sure, we made no assumption about the distribution of keys and searches and
assumed both random. In some cases you can generalize relevant information
about the distribution (like sorting an array that is already pretty good
sorted). But often it is more convenient to separate the two cases and
treat them separate using a bimodal distribution.

Your good suggestions sound like whether we want to split a search over N
items in two over M and N-M respectively (or M and N even, if N >> M). When
M < log(N) this is interesting, provided the hit ratio for [M] is high
enough and the cost to maintain the content of [M] is not too high. The
case with M=1 might provide interesting options because it can be
maintained fairly cheap (but makes it 1 + log(N) for the rest).

Rob

[Martin Truebner]

Robin,

>> What manual is that; for what system, and what date?

that was your question.

>> I have better things to do than do other people's research.

So you are not interested in any answer to your question I guess.

--
Martin

Pi_cap_CPU - all you ever need around MWLC/SCRT/CMT in z/VSE
more at http://www.picapcpu.de

[robin]

From: "DASDBILL2" <dasd...@comcast.net>
Sent: Thursday, October 24, 2013 10:44 PM

>The Assembler language book does not describe how processor instructions work.

Mine does. And most assembler langage books do also.

> Processor instructions never have allowed division by zero.

Some early processors did not detect division by zero, nor detected
overflow.

[John Gilmore]

Knuth's analysis of match-seeking binary search deals in an ordered
set of n keys

{k(1) < k(2) < . . . < k(i) < . . . k(n)}

and another set of 2n + 1 searches, viz.,

o one such that s < k(1), which fails,

o n - 1 such that k(i) < s < k(i+1),
i = 1, 2, . . . , n - 1, all of which fail,

o n such that s = k(j), j = 1, 2, . . ., n, all
of which succeed, and

o one such that s > k(n), which fails.

He shows that the total number of ternary comparisons required for
these 2n + 1 searches when his Algorithm B is used

M(n) = 2[(n + 1)q + 2e] � n,

with q = floor[log2(n + 1)] and e = n - (2^q - 1) ; and he shows that
this number is a minimum.

Knuth has also provided a recursive (dynamic programming) scheme for
constructing not tables but optimal explicit binary-search trees when
the frequencies of these 2n + 1 sets of search arguments are not
equal.

These classical results are in presented in volume 2 of TACP. They
are not really open to exception.

Departures from Knuth's assumptions are another matter. In very
different circumstances other schemes may be optimal. Even for them
some qualitative results have been established firmly. One of the
most important of these results is that match frequencies, counts of
the instances of s = k(i), alone are never adequate. Counts of the
frequencies of the n + 1 kinds of failures enumerated above are needed
too. Analyses based upon match frequencies alone have a long history
of yielding bad, suboptimal methods.


John Gilmore, Ashland, MA 01721 - USA

[Jon Perryman]

Paul Gilmartin said HLASM (not S360). The standard divide instructions get S0C9 when dividing by 0. Is it floating point that allows divide by 0? Is it the macro assembler SETA that allows it?

Jon Perryman.

----- Original Message -----
> From: Rob van der Heij <rvd...@gmail.com>
>

[John Gilmore]

Let us stipulate that z/Architecture divide instructions, all of them,
throw exceptions when a zero divisor is detected.

That said, things then get more complicated. These exceptions cannot
be disabled using SPM. There is no program-mask bit available for for
doing so. They can, however, be ignored more and less systematically.

Prototypically, I can write

ON ZERODIVIDE ;

in PL/I. This null on unit ensures that zero divides will be ignored
within its scope.

Moreover, there is now a functionally equivalent, albeit less
perspicuous, facility available via the LE in all IBM statement-level
languages that use it, i.e., for all of the usual suspects and even
for LE-compatible assembly language.

Paul Gilmartin and I do not always agree, but he knows all about
zero-divide exceptions. What he was asserting was not that these
exceptions do not occur but there are environments in which they are
ignored.

[Farley, Peter x23353]

Wow. I have occasionally been accused of using obscure, "unmaintainable" code in the name of efficiency, but that "gubbins" example and Rob's default parameter assignment parse make me look positively conservative.

Bravo! And thanks for showing us interesting concepts (assembler or not, I think concepts are not OT).

Peter

--

This message and any attachments are intended only for the use of the addressee and may contain information that is privileged and confidential. If the reader of the message is not the intended recipient or an authorized representative of the intended recipient, you are hereby notified that any dissemination of this communication is strictly prohibited. If you have received this communication in error, please notify us immediately by e-mail and delete the message and any attachments from your system.

[Tony Thigpen]

Now, I would like to see REAL assembler code for a binary search that
takes into consideration all the items being discussed and works for a
varying length tables, including an odd number of rows in the table.
To make it simple, assume:
R2 = @ first entry
R3 = @ last entry
R4 = length of each entry
R5 = @ of key to match
offset and length of key are EQUs KOFF and KLGH

Tony Thigpen

[David Cole]

At 10/23/2013 08:30 PM, Paul Gilmartin wrote:
>OK. Pure HLASM. I've long wondered why division by zero is permitted
>in arithmetic expressions when otherwise overflows (even in division)
>are reported as errors.
>
>The only rationale I can think of (and a poor one) is that it was
>initially an implementation oversight that was so rapidly codified
>by use that when it was discovered no repair was feasible.
>
>-- gil

For several of you that were confused by this, let me first point out
that Gill's question pertained to division allowed in the Assembler
at assembly time, not in runtime machine instruction execution.

More specifically, here are a couple of Assembler examples showing
what is allowed:
&ANSWER SETA 12/0
ANSWER EQU 12/0
In both cases, the assigned value is 0.

The reason that this useful is that this quirk can be exploited to
create, for example, a MAX or MIN function that is evaluated at
assembly time. (Maybe this has changed, but the last time I looked,
the Assembler did not offer native MAX and MIN functions.)

Here's how:

Below is some commentary from a macro of mine that needs to compute,
at assembly time, the size of a buffer that has to be big enough to
hold around 50 or so variations of a control block. Following that
commentary, I will try to translate this stuff into plainer English.

Note, the following will display best with a fixed pitch font. If
necessary, copy/paste it all into NOTEPAD for better readability.
Anyway, here it is:

*************************************************************
* *
* Required length of AUTOPARM. *
* *
* The following EQUs calculate the length that the *
* AUTOPARM, TWAPARM and RSTKPARM fields need to be in order *
* to hold the largest of the above defined parameter maps. *
* It does this by calculating the maximum of all AnnnnL *
* symbols, and it does that by repeatedly calculating the *
* maximum of a given AnnnnL symbol against the maximum of *
* all prior AnnnnL symbols. *
* *
* The computation is made possible by the following two *
* facts: *
* (1) The assembler defines x/0 to =0. *
* (2) All divisions are integral with no remainder or *
* fraction. *
* So each MAX computation looks like this: *
* *
* *
* oldmax oldmax [This is non-0 ] *
* newmax = ------ / ------ * oldmax [if and only if] *
* newlen newlen [oldmax=>newlen] *
* *
* newlen newlen [This is non-0 ] *
* + ------ / ------ * newlen [if and only if] *
* oldmax oldmax [newlen=>oldmax] *
* *
* newlen oldmax [This is non-0 ] *
* - 0 - ------ / ------ * newlen [if and only if] *
* oldmax newlen [newlen=oldmax ] *
* *
* Note, the " - 0 - " is present simply for spacing *
* reasons: Each of the following EQU statements is so long *
* that it has to be continued for a total of three lines. *
* The extra "-0" shifts the statement definition such that *
* no variable symbol name is broken by a continuation *
* character. This makes future editing somewhat easier. *
* *
*************************************************************
SPACE 3
ABEGIN EQU 1 STARTING POINT (CAN'T =0)
SPACE 1
AAD64Q EQU (ABEGIN/AAD64L)/(ABEGIN/AAD64L)*ABEGIN+(AAD64L/ABEGIN)/(|
AAD64L/ABEGIN)*AAD64L-0-(ABEGIN/AAD64L)*(AAD64L/ABEGIN)*|
ABEGIN
* MAX(1,AAD64L)
SPACE 1
AAFINQ EQU (AAD64Q/AAFINL)/(AAD64Q/AAFINL)*AAD64Q+(AAFINL/AAD64Q)/(|
AAFINL/AAD64Q)*AAFINL-0-(AAD64Q/AAFINL)*(AAFINL/AAD64Q)*|
AAD64Q
* MAX(AAD64L,AAFINL)
etc. etc. etc



Basically, in order to compute a maximum of two values you need to
add together three terms:
- One that equals the first value but only when it is high or equal.
- One that equals the second value but only when it is high or equal.
- One that adjusts for the doubling that occurs when both terms are equal.

For each of these terms, they must resolve to zero when their
particular criteria are not met. Two facts about assembly time
arithmetic are what makes this possible:
- The assembler permits n/0=0.
- Division results are always integers. Remainders are discarded.

Let's just look at the first of these terms from the above example:
(ABEGIN/AAD64L)/(ABEGIN/AAD64L)*ABEGIN [+...]

I'll translate this into something more readable:
(A/B)/(A/B)*A

Here's a better layout (better when your font is courier):
A/B
--- * A
A/B

To show what happens when A is low, I'll let A=2 and B=20:
2/20 0
---- * 2 becomes --- * 2 becomes 0*2 becomes 0.
2/20 0


To show what happens when A is high, I'll let A=70 and B=6:
70/6 11
---- * 7 becomes ---- * 7 becomes 1*7 becomes 7.
70/6 11


I'll leave it to you to work out the remainder of the computations.

IHTH,
Dave Cole

ColeSoft Marketing
414 Third Street, NE
Charlottesville, VA 22902
EADDRESS: dbc...@colesoft.com

Home page: www.colesoft.com
Facebook: www.facebook.com/colesoftware
YouTube: www.youtube.com/user/colesoftware

[John Gilmore]

Tony,

The code you want must address a number of additional issues.

Are the elements to be assembled into the table all of the same
length? If not, they must be padded with nuls, x'00', and not blanks,
x'40'|x'20', at table-assembly time to make them so.

Is the search argument shorter than the [padded out] table elements?
If so, it must be padded out with nuls at execution/search time to
make its length equal to that of the [padded out] table elements.

Would it perhaps be better---I think it would---to make the table a
self-defining one that contains the information required to search it?
A routine that can search any such table given invariant DSECTs for
it is a good notion.

Should the table have an eyecatcher? (I think it should.)

How should the middling subscript/element address be calculated?
(Hint. There are two different, correct ways to do this, which yield
slightly different decision trees. Moreover, both are notoriously
FIXEDOVERFLOW prone.)

Etc., etc. It will be interesting to see what if anything people post
for our delectation.

[Tony Thigpen]

I was thinking something more generic. The table description and layout
is outside the code. The code would be a generic branch and return routine.

How the table is loaded is also not part of the code. It could be done
at assemble time or at run time by reading a file.

Correctness of data is the responsibility of caller, not the routine.
The caller would be responsible to pad both the table and the search
argument in the same way.

Basically, a caller loads the 4 registers, branches to the binary
search, and upon return R15 has the address of the entry or 0 if not
found. Subroutine can modify R0, R1 and R15. If we need to, we can make
R4-R7 'modifiable'.

All entries will be fixed length. Can't really have variable length and
use a binary search. :-)

Tony Thigpen
-----Original Message -----

[Blaicher, Christopher Y.]

In a prior life, I have done a binary search with variable length data two ways. The better and easier way is using a vector of pointers to the data where the key is at a fixed offset with a fixed length. This method adds one more instruction per pass, but otherwise is just like any other binary search.

The second method used a binary chop of the data then scanned for the next entry. It was ugly, but it did its job. There are lots of limitations to it.

Chris Blaicher
Principal Software Engineer, Software Development
Syncsort Incorporated
50 Tice Boulevard, Woodcliff Lake, NJ 07677
P: 201-930-8260 | M: 512-627-3803
E: cbla...@syncsort.com

-----Original Message-----
From: IBM Mainframe Assembler List [mailto:ASSEMBL...@LISTSERV.UGA.EDU] On Behalf Of Tony Thigpen
Sent: Thursday, October 24, 2013 11:46 AM
To: MVS List Server 2

[Paul Gilmartin]

On 2013-10-24, at 04:35, Rob van der Heij wrote:

> Ask someone for a web browser and type google.com ;-) OS assembler
> language; 360, and december 1967
>

... which seems to take me to a bitsavers page, already discussed here.

> Many moons ago, a friend (who went to math school) showed me his scars and
> explained that it were evil that compilers could optimize in such a way
> that an attempt to divide by zero would go unnoticed. I believe most
> languages now formally specify which parts of the expression may/will not

> be computed when it can be avoided. ...
>
Pascal, with which I am most familiar (oh, damn! OT!), makes it
clear, if only by omission, that such constructs are syntactically
valid but should be reported at execution.

>> From: "glen herrmannsfeldt" <g...@ugcs.caltech.edu>
>> Sent: Thursday, October 24, 2013 4:22 PM
>>
>> From C28-6514-5 on bitsavers, on page 16:
>>

>> "Division by zero is permitted and yields a zero result."
>>>
>>> After that, (and presumably also earlier) it has to stay that
>>> way as code (macros) might depend on that.
>>>
>>> There is no reason given.
>>>

I don't see that it's so necessary to maintain compatibility
with all historic design blunders. Consider the relatively
recent detection and warnings of questionable address resolutions.
Similarly a warning could be issued for division by zero, even
as an error is reported for overflow.


On 2013-10-24, at 06:18, robin wrote:

> From: "DASDBILL2"
> Sent: Thursday, October 24, 2013 10:44 PM
>
>> The Assembler language book does not describe how processor instructions work.
>
> Mine does. And most assembler langage books do also.
>>

More to the point, it describes how the Assembler (HLASM) works,
and has done so since the earliest days, which is what I was
wondering about.

-- gil

[Robert A. Rosenberg]

At 13:52 +0200 on 10/24/2013, Rob van der Heij wrote about Re: Linear
search vs binary:

>On 24 October 2013 12:50, Don Higgins <d...@higgins.net> wrote:
>
>> I see discussion about optimizing the binary search, but I don't see any
>> discussion about optimizing linear search which might make it much faster
>> than binary depending on the search history. Putting the last key found at
>> front of most recently used list or just holding last found as a first test
>> may result in significant reduction in total search compares if there are
>> frequent repeat requests.
>>
>
>Sure, we made no assumption about the distribution of keys and searches and
>assumed both random. In some cases you can generalize relevant information
>about the distribution (like sorting an array that is already pretty good
>sorted). But often it is more convenient to separate the two cases and
>treat them separate using a bimodal distribution.

Using his Last Found trick, you can start at "Last Found" (bypassing
all the prior entries) if "Looking For" is greater than "Last Found".

[Robert A. Rosenberg]

At 12:45 -0400 on 10/24/2013, Tony Thigpen wrote about Re: Linear
search vs binary:

>All entries will be fixed length. Can't really have variable length and
>use a binary search.

That depends. If the table you are sorting is a table of pointers to
the actual data (and is ordered by the compare field), the entries
can be variable length so long as the compare field is fixed length
and is preceded by an entry length field. You use the pointer to find
the compare field of an entry and once you find the correct entry,
you back up to the location of the entry length and can then use the
entry.

[Tony Thigpen]

After a couple of posts about my post, I will go back to my point.

You can only binary search a fixed length table. If you create an index
table, the index table is the actual table being searched, not the
original table.

Now, Robert does have mention a neet trick where the fixed table
contains a refference pointer to the actual data to be compared. But,
the pointer table is still a fixed length table. :-)

You just can't binary search a variable length table.

Tony Thigpen

-----Original Message -----

[John Gilmore]

Tony writes that you just can't binary search a variable length table,
and this is certainly true if what he means is that you cannot search
a table the length of which changes while you are searching it.

You can, however, search a table that varies in length on different
occasions. How not?

[Tony Thigpen]

By variable length, I was talking about each ROW being variable length.
I.e, one row is 22 bytes, the next 10, the next 444.

Nothing to do with the number of rows in a table changing.

My original post stated:

"All entries will be fixed length. Can't really have variable length and
use a binary search."

Tony Thigpen

-----Original Message -----

[Paul Gilmartin]

On 2013-10-24 15:51, John Gilmore wrote:
> Tony writes that you just can't binary search a variable length table,
> and this is certainly true if what he means is that you cannot search
> a table the length of which changes while you are searching it.
>
> You can, however, search a table that varies in length on different
> occasions. How not?
>

I understand he meant a table containing entries of nonuniform lengths.


On 2013-10-24 15:43, Tony Thigpen wrote:> After a couple of posts about my post, I will go back to my point.
> ...
> You just can't binary search a variable length table.
>
Perhaps ...


On 2013-10-24 11:29, Blaicher, Christopher Y. wrote:
> ...

> The second method used a binary chop of the data then scanned for the next entry. It was ugly, but it did its job. There are lots of limitations to it.
>

Somewhat elliptical. I assume he means that from any point
in the table, which may be in the interior of an entry of
a priori unknown length, there's a method for locating the
beginning and end of that entry, perhaps a reserved character
such as BLANK, NUL, LF, ...

I think that should be feasible.

-- gil

[Evans, James R. (RET-DAY)]

I am out of the office until Monday 11/4/2013. I will read your note, as time permits, when I return to the office. If your e-mail is urgent and concerns a production issue/problem, please send your note to the 'GLO-RETS zOS Content' mailbox for attention.

Thanks!

[Alan Atkinson]

Someone at our place came up with a fairly slick solution for this about 30 years ago.
Design was to get around paging and a desire to not allocate multiple buffers for a dynamic table in a TP system. Another one we use daily.

One large block. Key data is pulled from the record and built into a sorted binary searchable table with entry length of key + 3 at the top of the buffer. Inserts move end of table down. The + 3 is the displacement to the rest of the record minus the key. First two bytes of record are length of non key portion.

This is inserted into the same block, filling from the bottom up. When the pointers intersect the table is full. We can reorganize if necessary at that point to fill holes from deletes.

Careful tuning means we don't hit this often.


We have one other that we use for very large tables that are fairly static and built mostly up front. We cache security info in it.

Here we build a sorted array but add space for a forward pointer. On completion we turn the array into a linked list with each pointer linked to the entry's neighbor.

Initial search is binary, but if pointer <> next then we traverse list for insert point. A CS is all it takes for an add - out of sequence stuff is shoved in next free slot in overflow.

That too works well for our use case.



Sent from my iPad

[Tony Thigpen]

> On 2013-10-24 11:29, Blaicher, Christopher Y. wrote:
>> ...
>> The second method used a binary chop of the data then scanned for
the next entry. It was ugly, but it did its job. There are lots of
limitations to it.
>>
> Somewhat elliptical. I assume he means that from any point
> in the table, which may be in the interior of an entry of
> a priori unknown length, there's a method for locating the
> beginning and end of that entry, perhaps a reserved character
> such as BLANK, NUL, LF, ...
>
> I think that should be feasible.
>
> -- gil

Yep, but so ugly. :-) And, so slow.

The math people would have to figure it out for sure, but I would almost
bet that such logic that Chris suggested would only be faster than a
linear search if the table is very large and the rows very short.

Tony Thigpen

-----Original Message -----

[Hall, Keven]

The assembler allows division by zero in arithmetic expressions whereas the instructions of the System/360 architecture do not.

Keven

-----Original Message-----
From: IBM Mainframe Assembler List [mailto:ASSEMBL...@LISTSERV.UGA.EDU] On Behalf Of glen herrmannsfeldt
Sent: Thursday, October 24, 2013 00:22
To: ASSEMBL...@LISTSERV.UGA.EDU
Subject: Re: Why is division by zero permitted?

From C28-6514-5 on bitsavers, on page 16:

"Division by zero is permitted and yields a zero result."

After that, (and presumably also earlier) it has to stay that way as code (macros) might depend on that.

There is no reason given.

-- glen

[Dave Wade]

Its been a while but bear with me and tell me if I am talking drivel...

I guess on a modern machine its not a problem, but on an older
environment with restricted memory and 4K page sizes then that is
going to be around 10 pages. If the data is paged out and item you are
looking for is in the first page a won't a binary search be the
slowest as it will cause three paging operations to occur.....

Dave

On 24 October 2013 11:50, Don Higgins <d...@higgins.net> wrote:
> All

>
>
>
> I see discussion about optimizing the binary search, but I don't see any
> discussion about optimizing linear search which might make it much faster
> than binary depending on the search history. Putting the last key found at
> front of most recently used list or just holding last found as a first test
> may result in significant reduction in total search compares if there are
> frequent repeat requests.
>
>
>

> Don Higgins
>
> d...@higgins.net

[robin]

From: "Tony Thigpen" <to...@vse2pdf.com>
Sent: Friday, October 25, 2013 3:45 AM

> All entries will be fixed length. Can't really have variable length and
> use a binary search. :-)

The code that I posted previously was for variable-length strings.

[robin]

From: "Tony Thigpen" <to...@vse2pdf.com>
Sent: Friday, October 25, 2013 8:43 AM

> After a couple of posts about my post, I will go back to my point.
>
> You can only binary search a fixed length table.

Nonsense.
The table for the code that I posted previouisly consisted
of varying-length strings.

> If you create an index
> table, the index table is the actual table being searched, not the
> original table.
>
> Now, Robert does have mention a neet trick where the fixed table
> contains a refference pointer to the actual data to be compared. But,
> the pointer table is still a fixed length table. :-)
>
> You just can't binary search a variable length table.

Rubbish. And the code to do it was written and published pre-1970.

[robin]

From: "Tony Thigpen" <to...@vse2pdf.com>
Sent: Friday, October 25, 2013 9:14 AM

> > On 2013-10-24 11:29, Blaicher, Christopher Y. wrote:
> >> ...
> >> The second method used a binary chop of the data then scanned for
> the next entry. It was ugly, but it did its job. There are lots of
> limitations to it.
> >>
> > Somewhat elliptical. I assume he means that from any point
> > in the table, which may be in the interior of an entry of
> > a priori unknown length, there's a method for locating the
> > beginning and end of that entry, perhaps a reserved character
> > such as BLANK, NUL, LF, ...
> >
> > I think that should be feasible.
> >
> > -- gil
>
> Yep, but so ugly. :-) And, so slow.

Binary search for verying-length strings is neither ugly nor slow.

[Tony Thigpen]

Repost the code. Nothing I still have in my inbox shows code to perform
a binary search of a table where each row occurrence can be any length.

Tony Thigpen

-----Original Message -----

[robin]

From: "Tony Thigpen" <to...@vse2pdf.com>
Sent: Friday, October 25, 2013 11:35 AM

> Repost the code. Nothing I still have in my inbox shows code to perform
> a binary search of a table where each row occurrence can be any length.

Array c has lower bound 0, upper bound n:
i = -1; k = n+1; /* pointers that always point beyond the smallest and largest values */
do while (i+1 < k);
m = isrl(i+k,1);
if c(m) > j then k = m;
else if c(m) < j then i = m;
else return (m); /* element found */
end;
return (-1); /* element not found. */

[robin]

From: "Savor, Tom" <Tom....@fisglobal.com>
Sent: Friday, October 25, 2013 11:40 AM


>Robin,
>Interesting....I would have said the same thing (if asked), that you can't have binary search on
>variable length keys.
>Is your code posted C+ ?? I don't know it at all.

The code is PL/I.

>How would you do this in Assembler ??

The original was in XPL, published in 1970 (but used well before that
in an unpublished earlier version).

In XPL, each string is accessed via descriptor that contains in a single word
the memory address and the length.

[Tony Thigpen]

> In XPL, each string is accessed via descriptor that contains in a single
> word
> the memory address and the length.

Your code is doing a binary search of the FIXED length POINTER table. It
is not doing a binary search of a table that has variable length rows.

As I said, any table with variable length rows requires the building of
a secondary table with fixed rows before a binary search can be used.

Tony Thigpen

-----Original Message -----

[robin]

From: "Tony Thigpen" <to...@vse2pdf.com>
Sent: Friday, October 25, 2013 12:16 PM

> > In XPL, each string is accessed via descriptor that contains in a single
> > word
> > the memory address and the length.
>
> Your code is doing a binary search of the FIXED length POINTER table.

No it's not. The code re-posted for you is PL/I. The storage for each element
is of a fixed size. Cariable C ios of type CHARACTER.
The code is performing a binary search of a string table.

In the original XPL code, the variable "C" is also of type CHARACTER.

> It is not doing a binary search of a table that has variable length rows.

Looks like it to me.

> As I said, any table with variable length rows requires the building of
> a secondary table with fixed rows before a binary search can be used.

No it doesn't.

[Tony Thigpen]

Convert your PLX code to assembler and you will see that you are binary
searching a pointer table that has fixed length entries.

Tony Thigpen

-----Original Message -----
From: robin

[robin]

From: "Tony Thigpen" <to...@vse2pdf.com>
Sent: Friday, October 25, 2013 10:05 PM

> Convert your PLX code to assembler and you will see that you are binary
> searching a pointer table that has fixed length entries.

In PL/I , each string value (= each element of an array) occupies exactly the same storage.

[Tony Thigpen]

As I don't know PL/I or PLX and this is the Assembler list, let's talk
assembler.

You stated that your code produced a binary search against a table where
each row was variable length.

I said binary search can't work on such a table.

So, produce the code in assembler.

Tony Thigpen

-----Original Message -----
From: robin

[Rob van der Heij]

On 24 October 2013 16:25, Farley, Peter x23353
<Peter....@broadridge.com>wrote:

Wow. I have occasionally been accused of using obscure, "unmaintainable"
> code in the name of efficiency, but that "gubbins" example and Rob's
> default parameter assignment parse make me look positively conservative.
>

Oh dear, I need to defend myself... As Paracelsus said "Alle Dinge sind
Gift.. " (Google for the rest) and even if you have something like
if/then/else that is simple to understand, when you have enough the result
gets complicated (like a 1000-line if clause)

Getting back to HLASM, I inherited macro that (simplified) starts like this:
MACRO
FOOBAR &A=,&B=,&C=
Now it needs to test that exactly one of the 3 parameters is being used,
and it does so using a cascade of simple AIF statement using ('&A' EQ ' ')
to verify that. This may have been trivial before, and got tedious when C=
was added. The error messages also introduced an ordering of the
alternatives that does not match the argument (eg "must not B when A is
specified" when invoked as FOOBAR B=1,A=3).

While I agree the following takes some creativity, it's basically not more
complicated and easier to maintain when you add another one...

LCLA &P
&P SETA K'&A+K'&B+K'&C
AIF (&P EQ 1).FOOX
MNOTE 8,'Foobar using &P of the A= B= C= options'
.FOOX ANOP ,

Rob

[Blaicher, Christopher Y.]

OK you two, Tony and Robin, you are looking at the same thing from two directions, I think.

Robin is saying each element, or structure, or entry, is the same length. The data stored in the element is variable in length.

So, Robin is right that you can binary search a table with variable length data, it just so happens each element in the table is the size of the largest, so Tony is right that it is easiest to search a fixed length table.

Or, at least that is what I am getting out of all this.

Chris Blaicher
Principal Software Engineer, Software Development
Syncsort Incorporated
50 Tice Boulevard, Woodcliff Lake, NJ 07677
P: 201-930-8260 | M: 512-627-3803
E: cbla...@syncsort.com

-----Original Message-----
From: IBM Mainframe Assembler List [mailto:ASSEMBL...@LISTSERV.UGA.EDU] On Behalf Of robin
Sent: Friday, October 25, 2013 7:13 AM
To: MVS List Server 2

[Tony Thigpen]

Maybe that explains the disconnect.

I am saying that all ROWs must be of equal length. Each row may contain
one or more fields. I did not say that the individual data fields in the
row must be fixed length.

In other words, each table occurance must be the same length.

Tony Thigpen

-----Original Message -----

[Paul Gilmartin]

On 2013-10-23, at 19:33, robin wrote:

> From: "Paul Gilmartin" <PaulGB...@AIM.com>
> Sent: Thursday, October 24, 2013 11:51 AM
>
>> On 2013-10-23 18:36, robin wrote:
>>>
>>> And anyway, how do you think that J > K is computed?
>>>
>>> The comparison is performed by subtracting K from J
>>> (without changing either J or K, of course).
>>
>> Why not use the Compare instruction? (As in Assembler
>
> That IS what a compare is (in hardware). C compares
> by subtracting one operand from the other. (without changing
> either operand).
>
I'm skeptical:

o How does it set the condition code?

o What happens if the values of J and K are so extreme
that the subtraction would result in overflow?
(I suppose I could imagine guard bits on the left.)

o How is Compare done for non-numeric operands, as by CLC?

-- gil

[Paul Gilmartin]

On 2013-10-24, at 00:41, Rob van der Heij wrote:

> On 24 October 2013 02:42, Tony Harminc <to...@harminc.com> wrote:
>
>> That's a very APLish thing to do.
>>
I'm sorry.

> No doubt a matter of style and experience, but I find if/then/else hard to
> follow when reading. Especially when ident does not match the nesting. Once
> you're familiar with the idioms, they reduce the amount of reading and
> increase what you can oversee on a single screen or page.
>
What about the HLASM TK SP Macros?

I coded yesterday for a test, growing out of an example I posted
on IBM-MAIN:
...
RC = BPXWDYN( 'alloc rtddn(DDX) rtdsn(DSX) rtvol(VLX) new delete' ,
word( 'dsn('userid()'.TEMP.LMTEST)' ,
'unit(VIO)', 1 ) ,
'dsorg(PS) recfm(V,B) lrecl(137) msg(WTP)' )
...

I can change the word number either to 1 for a DASD data set
or to 2 for VIO. Cleary I miss the facility of conditional
expressions in Rexx.

-- gil