IBM Mainframe Forum

[FrankDCC]

Hi there I'm pretty new to Assmbler and I was wondering if anybody had some code laying around for a Bubble sort in ASM. I'm learning right now and would just like to see how everything works with the branches and comparisons!

[Robert Sample]

If you are learning HLASM, wouldn't it make more sense for you to WRITE a bubble sort (or quick sort) to learn from?

[FrankDCC]

I'm going to write one, I just want an example in case I get stuck. Plus I want to be able to compare my algorithm to someone who already knows how to write a bubble sort, this way I can gauge how mine is and where to improve on. I know three different high level languages and I have found this is the best way for me to learn and gauge my performance

[steve-myers]

This is about as minimal as you can get. The bad news is it uses the BXH and BXLE instructions, something beginners absolutely loathe. Registers 2, 3 and 5 are storage addresses. rather than index values, though it would be trivial to set registers 2 and 5 to 0 and 16 and do L 0,NUMBERS(2)/L 1,NUMBERS(3)

Select all

BUBBLE   CSECT
         USING *,12
         SAVE  (14,12)
         LR    12,15
         LA    2,NUMBERS
         LA    4,L'NUMBERS
         LA    5,LASTNUM
SORT0100 LR    3,2
SORT0200 BXH   3,4,SORT0500
SORT0300 L     0,0(,2)
         L     1,0(,3)
         CR    0,1
         BL    SORT0400
         ST    0,0(,3)
         ST    1,0(,2)
SORT0400 BXLE  3,4,SORT0300
         BXLE  2,4,SORT0100
         DC    H'0'
SORT0500 RETURN (14,12),RC=0
NUMBERS  DC    F'10,5,-5,30,20'
LASTNUM  EQU   *-L'NUMBERS
         END   BUBBLE

A very minor performance improvement can be made by changing BL SORT0400 to BNH SORT0400. The second BXLE always branches. Why?

[enrico-sorichetti]

http://rosettacode.org/wiki/Category:Sorting_Algorithms

[FrankDCC]

Here's my current code, how can I improve it?
TITLE 'SCORE ARRAY SCALER'

Select all

EX2    CSECT
R12      EQU   12           BASE REGISTER
R13      EQU   13           SAVE AREA POINTER
R14      EQU   14           RETURN REGISTER
* STANDARD ENTRY AND INITIALIZATION:
         STM   R14,R12,12(R13) SAVE REGISTERS
         BALR  R12,0        LOAD BASE REGISTER
         USING BASE,R12     DECLARE BASE ADDRESS AND REGISTER
BASE     ST    R13,SAVE+4   SAVE R13
         LA    R13,SAVE     R13 = ADDRESS OF SAVE AREA
* BEGIN PROCESSING ARRAY
         L     7,LIMIT
         LA    6,10
LOOP2    LA    1,0
         LA    4,4
LOOP     L     2,ARRAY(1)
         L     3,ARRAY(4)
         CR    2,3
         BNH   SKIP
         ST    2,ARRAY(4)
         ST    3,ARRAY(1)
SKIP     A     1,FOUR
         A     4,FOUR
         C     4,LIMIT
         BL    LOOP
         S     7,FOUR
         BCT   6,LOOP2
* STANDARD EXIT:           
DONE     L     R13,SAVE+4   RESTORE R13
         LM    R14,R12,12(R13)  RESTORE REGISTERS
         BR    R14          RETURN
* STORAGE:
ARRAY    DC    F'3'
         DC    F'12'
         DC    F'9'
         DC    F'23'
         DC    F'99'
FOUR     DC    F'4'
LIMIT    DC    F'40'
SAVE     DS    18F
         END   EX2

I apologize for the format!

[Robert Sample]

1. You've got 5 values, which requires 20 bytes. You have LIMIT set to 40 -- so you're not sorting what you think you're sorting.
2. Using register 1 is not a good idea -- registers 0, 1, 13, 14, 15 all have special purposes in HLASM and hence should NOT be used except for their special purpose.
3. Try changing the order of your values to ensure they are sorting correctly.
4. There's usually more than one way to do things in HLASM -- LA R4,4(R4) requires less memory access than A R4,FOUR.
5. As a result of #1, your value of FOUR does not remain 4 -- which has an impact on how register 7 changes value.

[FrankDCC]

Would it be possible to give me a code revision to see what I did wrong?

[steve-myers]

This will not work. I mainly doctored it to correct some of the issues Mr. Sample noted, particularly point 1. It does assemble cleanly. My little sample a couple of posts back uses a slightly different method to establish the array limits.

Mr. Sample's concern about the use of register 1 is something you should remember, but is not significant in your code. Any time you use an IBM macro you must assume registers 0, 1, 14 and 15 are going to be trashed. Most of my code uses these registers as short term work registers quite heavily. In most of my programs register 1 or register 15 is the most frequently referenced register. In a program I've been working on these last 2 weeks, a little over 1000 lines, register 1 has 158 references and register 15 has 206 references. The next most used register has 91 references.

Anyway, here is your doctored program -

Select all

         TITLE 'SCORE ARRAY SCALER'
EX2      CSECT
R12      EQU   12           BASE REGISTER
R13      EQU   13           SAVE AREA POINTER
R14      EQU   14           RETURN REGISTER
* STANDARD ENTRY AND INITIALIZATION:
         STM   R14,R12,12(R13) SAVE REGISTERS
         BALR  R12,0        LOAD BASE REGISTER
         USING BASE,R12     DECLARE BASE ADDRESS AND REGISTER
BASE     ST    R13,SAVE+4   SAVE R13
         LA    R13,SAVE     R13 = ADDRESS OF SAVE AREA
* BEGIN PROCESSING ARRAY
         L     7,LIMIT
         LA    6,COUNT
LOOP2    LA    1,0
         LA    4,L'ARRAY
LOOP     L     2,ARRAY(1)
         L     3,ARRAY(4)
         CR    2,3
         BNH   SKIP
         ST    2,ARRAY(4)
         ST    3,ARRAY(1)
SKIP     A     1,FOUR
         A     4,FOUR
         C     4,LIMIT
         BL    LOOP
         S     7,FOUR
         BCT   6,LOOP2
* STANDARD EXIT:
DONE     L     R13,SAVE+4   RESTORE R13
         LM    R14,R12,12(R13)  RESTORE REGISTERS
         BR    R14          RETURN
* STORAGE:
ARRAY    DC    F'3'
         DC    F'12'
         DC    F'9'
         DC    F'23'
         DC    F'99'
COUNT    EQU   (*-ARRAY)/L'ARRAY
FOUR     DC    A(L'ARRAY)
LIMIT    DC    A(L'ARRAY*COUNT)
SAVE     DS    18F
         END   EX2

Another thing about this code is the use of Assembler derived values. For example -

COUNT EQU (*-ARRAY)/L'ARRAY

*-ARRAY computes the number of bytes between the current value of the location counter and the value assigned to ARRAY; L'ARRAY directs the Assembler to use the length attribute of ARRAY. So COUNT is the number of words in ARRAY. Add another word, and the Assembler updates COUNT automatically. You see essentially the same thing in C from time to time:

int array[] = {3, 12, 9, 23, 99};
int count = sizeof(array) / sizeof(array[0]);

Mr. Sample's point 4 talks about replacing A 4,FOUR with LA 4,4(,0,4) to eliminate a storage reference. Storage, relative to computer instruction processing rate is s-l-o-w. In the 1990s, IBM added the first of the immediate instructions because they finally realized storage is s-l-o-w, though LA has been used for this purpose by Assembler guys for more than 40 years in spite of serious problems that have caught programmers by surprise more than once. Today we might use AHI 4,4 rather than LA. In the last 10 years IBM has added immediate instructions with 32 bit operands though most of us use them infrequently, if at all.

[FrankDCC]

This will not work. I mainly doctored it to correct some of the issues Mr. Sample noted, particularly point 1. It does assemble cleanly. My little sample a couple of posts back uses a slightly different method to establish the array limits.

Mr. Sample's concern about the use of register 1 is something you should remember, but is not significant in your code. Any time you use an IBM macro you must assume registers 0, 1, 14 and 15 are going to be trashed. Most of my code uses these registers as short term work registers quite heavily. In most of my programs register 1 or register 15 is the most frequently referenced register. In a program I've been working on these last 2 weeks, a little over 1000 lines, register 1 has 158 references and register 15 has 206 references. The next most used register has 91 references.

Anyway, here is your doctored program -

Select all

         TITLE 'SCORE ARRAY SCALER'
EX2      CSECT
R12      EQU   12           BASE REGISTER
R13      EQU   13           SAVE AREA POINTER
R14      EQU   14           RETURN REGISTER
* STANDARD ENTRY AND INITIALIZATION:
         STM   R14,R12,12(R13) SAVE REGISTERS
         BALR  R12,0        LOAD BASE REGISTER
         USING BASE,R12     DECLARE BASE ADDRESS AND REGISTER
BASE     ST    R13,SAVE+4   SAVE R13
         LA    R13,SAVE     R13 = ADDRESS OF SAVE AREA
* BEGIN PROCESSING ARRAY
         L     7,LIMIT
         LA    6,COUNT
LOOP2    LA    1,0
         LA    4,L'ARRAY
LOOP     L     2,ARRAY(1)
         L     3,ARRAY(4)
         CR    2,3
         BNH   SKIP
         ST    2,ARRAY(4)
         ST    3,ARRAY(1)
SKIP     A     1,FOUR
         A     4,FOUR
         C     4,LIMIT
         BL    LOOP
         S     7,FOUR
         BCT   6,LOOP2
* STANDARD EXIT:
DONE     L     R13,SAVE+4   RESTORE R13
         LM    R14,R12,12(R13)  RESTORE REGISTERS
         BR    R14          RETURN
* STORAGE:
ARRAY    DC    F'3'
         DC    F'12'
         DC    F'9'
         DC    F'23'
         DC    F'99'
COUNT    EQU   (*-ARRAY)/L'ARRAY
FOUR     DC    A(L'ARRAY)
LIMIT    DC    A(L'ARRAY*COUNT)
SAVE     DS    18F
         END   EX2

Another thing about this code is the use of Assembler derived values. For example -

COUNT EQU (*-ARRAY)/L'ARRAY

*-ARRAY computes the number of bytes between the current value of the location counter and the value assigned to ARRAY; L'ARRAY directs the Assembler to use the length attribute of ARRAY. So COUNT is the number of words in ARRAY. Add another word, and the Assembler updates COUNT automatically. You see essentially the same thing in C from time to time:

int array[] = {3, 12, 9, 23, 99};
int count = sizeof(array) / sizeof(array[0]);

Mr. Sample's point 4 talks about replacing A 4,FOUR with LA 4,4(,0,4) to eliminate a storage reference. Storage, relative to computer instruction processing rate is s-l-o-w. In the 1990s, IBM added the first of the immediate instructions because they finally realized storage is s-l-o-w, though LA has been used for this purpose by Assembler guys for more than 40 years in spite of serious problems that have caught programmers by surprise more than once. Today we might use AHI 4,4 rather than LA. In the last 10 years IBM has added immediate instructions with 32 bit operands though most of us use them infrequently, if at all.

Thank you very much for the helpful information and the updated code, first and foremost! The reason I have not been using the mentioned:
COUNT    EQU   (*-ARRAY)/L'ARRAY
FOUR     DC    A(L'ARRAY)
LIMIT    DC    A(L'ARRAY*COUNT)

is because I have not been taught how to do so yet, the only way I know how so far is the way I posted originally and I don't think I'm at liberty to skip ahead even if it's a better way. I do understand the point of using LA vs A though to eliminate a storage reference and will do so! Is there anyway you can "doctor" my code a bit more with the restrictive knowledge that I have / can use?