I would be surprised if a binary search could beat a linear search with
only five items in the list, which is the case in the example code
here. If usage of the function request codes were uniformly
distributed, the average number of list item comparisons with five items
for binary search would be 2.2 versus 3.0 for linear search, but each
comparison in the binary search requires slightly more control
instructions. I suspect the differences would be too minor in this case
to warrant the additional binary search logic complexity; and the
decision could be biased even more in favor of a linear search if some
function requests are used with greater frequency and the list were
ordered by frequency of expected usage, which could make the average
comparisons for linear search even less than for binary search. With 15
items and with a uniform request distribution, the advantage of binary
over linear search becomes 3.3 versus 8.0 average entry comparisons.
Since I doubt that each comparison pass of the binary search costs twice
as much, the break-even point could be expected to be lower than 15
items, but not as low as 5.
While modifying instructions within the actual program code would make a
routine non-re-entrant, this is not the case with the specific example
that started this thread. That example copies the instructions into a
passed data area and modifies and executes from there, and all other
stored data is in that same work area; so the PNBITMSK routine itself is
re-entrant and could be placed in read-only storage. Now if the calling
program does not dynamically acquire that passed storage area, or
inherit it from another routine that does, the entire application might
not be re-entrant, but that is not the fault of the instructions
dynamically generated by the PNBITMSK code.
Joel C. Ewing
On 04/29/2013 10:42 AM, John McKown wrote:
There is no architectural restriction about not modifying instructions
"on the fly". The z does not have the concept of "data" versus
"instruction" storage. But, IMO, it is an abomination. There are two
major reasons and one minor one. First, it causes a flush of the I
(and D?) cache. This impacts performance quite a bit. Second, it makes
the code not reentrant. And a minor point, due to not being reentrant,
is that the code cannot be placed in read-only memory. Rather than
modifying an instruction on the fly, I either use an EX of the
instruction, when possible; or I move a the template of the
instruction into a data area and EX that.
<reflection>
Reminds me of an interesting facet of the Xerox Sigma architecture.
All instructions were a full word in length. And the registers could
be address similar to the way the z does; but were also mapped into
memory locations 0..15 . So if you referenced memory location 0, you
actually accessed register 0. So you could construct an instruction in
register "n" <15 and then put a branch in register "n+1" (like a BR
15). You then did a branch to subroutine to register "n" to execute
the instruction. The Sigma didn't have an equivalent of the EX as I
recall. Kind of makes me wish that the z had an EXG which would EX a
single instruction created in single 64 bit Grande register. That
would work for _most_ instructions. Might even be more interesting if
the EXG looked at the opcode to determine if the instruction was in
the specified register or was in a Grande register (even-odd?) pair.
</reflection>
On Mon, Apr 29, 2013 at 10:06 AM, Paul Gilmartin <[email protected]> wrote:
On Mon, 29 Apr 2013 10:50:25 -0400, John Gilmore wrote:
It is not at all a bad subroutine. In many contexts the form of the
second argument would be gratuitously clumsy, but this routine was
(almost certainly) intended to be called from COBOL, and eight '0' or
'1' characters is appropriate for COBOL.
I would not myself have used assembler mnemonics, whicjh are not very
perspicuous for COBOL programmers, to identify which operation is to
be performed,;and linear search is not the best way to identify which
of them has been supplied; but these are quibbles.
I might have avoided the search entirely by providing separate entry
points for the various functions. It seems unlikely to me that a
programmer would want to choose at runtime which function to
perform.
Has the z nowadays any memory protection mode that forbids fetching
instructions from data storage? (Many other processors have such.)
But what's the break-even between linear search and binary search?
I suspect that it's at about a handful. And linear search is probably
friendlier to branch prediction logic than binary search.
-- gil
--
Joel C. Ewing, Bentonville, AR [email protected]
----------------------------------------------------------------------
For IBM-MAIN subscribe / signoff / archive access instructions,
send email to [email protected] with the message: INFO IBM-MAIN
