Bruce develops and sells software for TRS-80 and MS-DOS/PC-DOS computers. You may reach him at T.N.T. Software Inc., 34069 Hainesville Rd., Round Lake, IL 60073.
A structure may be defined as a grouping of data items (characters, numbers, pointers, or other types) that can be treated as an entity by the programmer. Structures (or the largely equivalent Pascal records and Basic user-defined types) are enormously useful because they simplify and generalize the underlying program logic. Without structures, programs that could have been written cleanly and elegantly must be written with more of a "brute force" approach.
Still, a structure is commonly limited in one important way: The structure's components (and even the order of those components) must be defined at compile time, not at run time. This shortcoming often causes problems.
Consider, for example, a general sort program. The program should be able to handle an arbitrary number of keys, to work with all reasonable data types of whatever lengths, and to sort files far larger than available memory. Because the amount of available memory is not known in advance and will vary, the sort should use the fastest comparison algorithm(s) possible for the sake of efficiency.
If the programmer knew in advance about the order and the types of the keys in the file to be sorted, a structure that contains all of the keys would be easy to define. A comparison algorithm could then be written to take full advantage of the structure, and space could be allocated for as large an array as necessary. When no formal structure can be defined in advance, that approach is not possible.
In practice, most programmers allocate a block of memory at run time instead. That block of memory will be filled with the data to be sorted (all or part of each record). Another block of memory may hold pointers to the collection of keys for each of the records. Individual key values that belong to each record can be accessed by a fixed offset from that value.
In effect, the programmer gets the effect of a structure, without many of its benefits. To see how severe this disadvantage can become, consider the pseudocode for a sort on K keys in Example 1. The actual sorting algorithm is not important, so I've kept things as general as possible. I've assumed that two records are compared at some point, but that the action taken (swapping pointers, moving memory, and so on) does not matter.
loop while still records to sort
get new record
set x=1
loop while x <= K
determine the data type of key x
call the appropriate comparison
compare record a to record b on key x
if record a is less than record b
return result 'less than'
else if record a is greater than record b
return result 'greater than'
else return result 'equal'
end if
if result is 'less than'
take action and set x=K+1
else if result is 'greater than'
take action and set x=K+1
else increment x
end if
end loop (compare keys)
end loop (sort records)
For each key that is compared, the program looks up the data type and then calls the correct comparison. The comparison is passed either the two values or else the pointers to those values, and will probably return an integer value that will be examined in order to determine what action should be subsequently taken. If necessary, the process is repeated for each key.
If the structure is known in advance, only a pointer to the structure needs to be passed to the comparison algorithm (or the comparison can be done inline). The comparison does not need to look up the type of each key. Substantially fewer parameters need to be passed.
Suppose that there are ten 1-byte keys for two records, and that all but the last key are identical. In this case, the general method will require ten type comparisons, ten calls with two passed parameters and a return value, and nine incremented key pointers to compare each of two records.
In this scenario, a specific solution will pass two pointers, with one pointer passed to each of the two key structure members. Assuming that each key is of a different type, the ten type comparisons can be omitted. If all keys are of the same type, then nine calls (with two passed parameters and a return value) can also be omitted. Furthermore, if all keys are either a character byte or an unsigned byte, there is no need to explicitly increment any key pointers.
Although it is not likely that all keys will be either a character byte or an unsigned byte, it is common for two or more adjacent keys to be one of these bytes. The resulting smaller overhead can offer a substantial advantage, since many sorts require a large number of comparisons -- and, therefore, a large number of passed parameters. If one or more merge passes are required, any advantage is further magnified because even more comparisons will occur.
Nearly every modern processor contains a string comparison instruction, or at least a small set of instructions that can perform a string comparison at high speed. This capability is an obvious optimization, and all common compilers take advantage of it.
No common CPU-level instruction for the comparison of floating-point numbers, long integers, or other special data types exists. Such comparison routines are supplied by the compiler vendor. For some types of data, the routines can be quite slow.
To take advantage of efficient string comparisons, an ideal general-purpose sort might convert all data into ASCII string format. If that conversion can be made faster than the sum of 1) the type comparisons, 2) the additional calls to the comparison algorithms (and the corresponding stack usage), and 3) the time required to increment the key pointers (in this example, x=K+1), then the sort will run faster.
Let me emphasize that I'm not talking about converting floating-point numbers into strings of digits. That would waste memory and be time-consuming. By "converting to string format," I mean something much simpler--converting the various data types into a string of characters, so that when the characters are sorted in ASCII order, the data from which the string was derived is also sorted.
As an example of the technique, consider a 16-bit signed integer stored on an IBM PC-type machine. In that format, the most significant byte is on the right, and the sign is stored in the high-order bit (on = negative number) of that byte.
If integers were stored with the bytes reversed and with the sign bit complemented, then a string comparison would work. An ASCII-order sort of the converted data would create the same relative order as an integer sort.
There wouldn't be any merit to the conversion if the sort key were a single integer field, because integer comparisons are fast. If the sort were required to process several integer keys per record, however, there might well be an advantage. The conversion would take time, but afterwards, any comparisons would require only two parameters. The more comparisons, keys, and different data types, the stronger the incentive to convert.
If the data is converted, then the original data (or some kind of pointer to the original data) needs to be retained in order to output a sorted file at the end. In most cases, that step is not necessary--only the original record number is needed in order to output an index to the sorted records. Note, too, that if the record number is converted and included as the last sort key, and then unconverted at the end of the sort, the sort preserves the order of the original data where possible. This can be important when a file is read through an index, because disk head movement and drive wear are minimized, and throughput is improved. Whether or not this conversion is performed, the step of appending the record number to each collection of keys makes it impossible for any records to be "equal," and makes the sort logic even faster.
In most sorts, all but a few records are compared to another record at least twice (more if a merge pass occurs). Computational and hash-based sorts can beat this process, but only at the price of added complexity and additional assumptions about the data. Often, there are far more comparisons: A bubble sort of N records makes N-1 comparisons on the first pass alone, and can (in the worst case) make N(N-1)/2 comparisons before it finishes. That is an average of (N-1)/2 comparisons per record!
A sort that uses a binary search technique makes approximately log(N) comparisons to insert the Nth record, log (N-1) comparisons to insert the N-1st record, and log(1) comparisons to insert the first record. (All logarithms in this article are to the base 2.) For files of more than eight records, sorts based on a binary search average more than two comparisons per record. As a rough approximation, a sort of N records based on a binary search requires an average of log(N)-1 comparisons per record. For a larger number of records (from about 20 to at least 100,000), a better approximation is log(.737N)-1. Table 1 lists an approximate number of comparisons (computed by summing the logs of all values of N to 16 significant digits) and the improved estimate. Listing One shows the program that was used to generate the table.
Number of Comparisons Log(.737N)-1
Records Per Record
------------------------------------
1 0 -1.4402630
2 0.5 -0.4402636
3 0.861654 0.1446990
4 1.146241 0.5597370
5 1.381378 0.8816650
6 1.581976 1.1446996
7 1.757030 1.3670914
8 1.912401 1.5597370
9 2.052126 1.7296623
10 2.179106 1.8816653
100 5.247650 5.2035935
1000 8.529398 8.5255217
2000 9.526494 9.5255217
3000 10.110419 10.110483
4000 10.524916 10.525521
5000 10.846511 10.847449
6000 11.109319 11.110483
7000 11.331546 11.332876
8000 11.524065 11.525521
9000 11.693891 11.695446
10000 11.845814 11.847449
20000 12.845441 12.847449
30000 13.430272 13.432411
40000 13.845242 13.847449
50000 14.167128 14.169377
6000 14.430134 14.432411
70000 14.652506 14.654804
80000 14.845136 14.847449
90000 15.015049 15.017374
If there are N records, K keys per record, and all keys need to be compared in order to resolve matters, then a very good sort needs to make about 2KN individual key comparisons. A bubble sort could require about (N/2)KN comparisons. A sort based on a binary search needs roughly [log(.737N)-1]KN comparisons. Table 2 may make the results easier to comprehend.
# Records Very Good Sort Bubble Sort Binary Sort
---------------------------------------------------------
16 48 360 123
128 768 24,384 2,135
1,024 6,144 1,571,328 26,296
16,384 98,304 402,628,608 617,336
131,072 786,432 25,769,607,168 6,118,339
1,048,576 6,291,456 1,649,265,868,800 58,383,894
An attempt to sort a million records with a bubble sort would be a ridiculous exercise. If each comparison took 100 nanoseconds, the sort would take nearly two days, even with no other overhead. The binary search method would finish in about six seconds!
In practice there is a lot of overhead. The actual comparison involves memory accesses, register increment and decrement operations, stack usage, and various other instruction processing.
The relative time required to perform comparisons of different kinds varies by compiler, processor, data type, and possibly the memory locations involved and the memory model used. String comparisons are usually among the fastest available comparisons. (Integer-to-integer or byte-to-byte comparisons are normally the fastest.) That being the case, it is difficult to state precisely what advantage will be gained by converting raw data into strings. The only possible answer is, "it depends."
Generally speaking, though, if a string comparison is even slightly faster than an explicit comparison, then there is a point after which it becomes more efficient to convert. This point is reached when the number of comparisons vastly outweighs the number of conversions necessary for any reasonably large file.
Remember that conversion saves some time when comparisons are done. If nothing else, the fact that fewer separate calls are made, and fewer parameters are passed, makes the string comparison more efficient. This efficiency increases as more keys are added --this factor is quite important for a general-purpose sort. Table 3 shows a sort of 10,000 records on two keys, where the key-by-key sort calls a comparison procedure.
Conversion Sort Key-by-key Sort
---------------------------------------------------
Conversions 20,000 0
Comparisons 118,458 118,458 to 236,916
Type checks 20,000 one per comparison
Procedure calls 0 one per comparison
From this, it's clear that a key-by-key sort suffers in performance unless a relatively long time is needed in order to perform a conversion, few keys and few records exist, and the time required to do type checks and procedure calls is negligible. As we shall see, none of these conditions are likely to hold.
Regardless of the amount of time saved, the savings in code complexity are very real and obvious. Once the data is converted to string format, all subsequent comparisons are string-to-string, and are fast and easy to optimize. The savings in complexity can be even easier to appreciate if one or more of the keys must be sorted in descending order.
When a full "brute force" method is used to compare each key individually, a general sort must accommodate an extra flag for each key. The sort must also invert the result returned by the affected comparison algorithm, or else supply a different comparison (doubling the number of algorithms and lengthening the sort time) in order to return a correct result.
If the data is converted to strings, then a simple and fast XOR (with decimal 255) can be performed to invert the bits in each affected key. This step allows the use of a straight string comparison thereafter. Example 2 illustrates some pseudocode for a sort that uses conversion.
loop while still records to sort
get new record
convert keys for new record and append record number
compare record a to record b
if record a is less than record b
do appropriate action
else do something else
end if
end loop (sort records)
The bare logic is certainly simpler than the previous example, but the sort depends heavily upon the step of data conversion. In order to obtain the best performance, the conversion routines should be written in assembler.
I've written a set of such assembler routines for Microsoft data types. The routines are in Listing Two (CONVINT, to convert integers), Listing Three (CONVLONG, to convert long integers), Listing Four (CONVOF, to convert old floating-points), Listing Five (CONVNF, to convert IEEE floating-points), and Listing Six (INVERT, to XOR all bytes in a key with ASCII 255 for reverse-order sorts). Each of these conversion routines alters the actual data in memory. The size of the key data does not change.
Though the routines were written for use with Quick Basic 4.0, there should be little problem in altering them for use with other languages. A word of warning: the converted data may contain ASCII null characters, which will cause problems in the standard C strcmp library routine. C programmers should use a different (perhaps assembler-based) string comparison.
To test the worth of the conversion approach, I wrote a simple series of benchmarks in Quick Basic 4.5 and ran the resulting stand-alone .EXE file on my Tandy 4000 (80386, 16 MHz, no math co-processor). The benchmark program (shown in Listing Seven) is tedious but straightforward: It consists of a series of timing loops for each of a number of elementary operations. The time required to perform a bare loop was subtracted from each test. The times are presented in seconds per 100,000 operations, and averaged over five runs. The results are shown in Table 4.
TEST RESULTS
Operation Test Time (sec.)
-------------------------------------------------
Raw integer loop 0.11
Integer conversion 0.88
Long integer conversion 1.05
Old single float conversion 2.33
Old double float conversion 3.01
IEEE single float conversion 1.98
IEEE double float conversion 3.66
Invert 8 bytes 2.27
Compare two-byte strings 3.00
Compare two integers 0.34
Compare two four-byte strings 3.13
Compare two single floats 39.73
Compare two double floats 40.78
Compare two 8-byte strings 3.40
Compare two long integers 1.33
Compare two 20-byte strings 4.22
Compare two 20-byte strings (best?) 2.91
Three-integer-parameter call{*} 2.26
{*} Dummy call with three parameters passed and one
integer (constant) assignment in the subprogram.
All string comparisons were for strings that differed
in only the final byte, except for the "20-byte (best?)"
operation, where the strings differed in the first byte.
From this table, there seems to be only one case where data should not be converted: when the key or keys are integers or long integers. As we shall see, that's not necessarily true.
If the sort ever includes any floating-point keys, then a conversion is nearly mandatory--the time required for a conversion and a string comparison ranges from 5.11 to 7.06 seconds per 100,000 operations, while the time required for a floating-point comparison alone (even coded in-line) can be nearly eight times as large.
Other combinations are not so clear-cut, but are more instructive. If an integer comparison is not coded in-line (meaning that the comparison is a procedure call), then it takes at least 2.60 seconds per 100,000 operations (2.26 seconds for the procedure calls). 100,000 conversions and 100,000 comparisons take 3.88 seconds. As a result, if the key is a single integer, you might think it better not to convert. Again, though, the sheer number of comparisons may dominate.
Suppose that you need to sort 100,000 records, and you intend to use a method that relies upon a binary search. If there are two integer keys, then you will need to perform 200,000 conversions and about 1,516,704 comparisons, which together will take 47.26 seconds. A simple integer comparison on the first key (not coded in-line) will take at least 39.43 seconds. If the first keys are always identical, then a second integer comparison will take another 39.43 seconds. If the second comparison is required only 19.9 percent of the time, then the two methods will be equally fast. If the second comparison is needed more often, then the conversion method will save time.
These times are quite conservative. For unconverted integer variables, the actual comparison operation would never be as simple as shown in the benchmarks--rather than only one logical operation, there could be two (compare for less than, compare for greater than, and drop through for equality). The number of necessary operations depends upon the data. If two logical comparisons are necessary for each integer key (all data is in exactly the wrong order for the first logical test), then the simple comparisons will take an additional 5.16 seconds. This additional time makes the process of conversion and string comparisons nearly equivalent to an integer comparison, even for a single key. In addition, each unconverted comparison requires a type check, which is not necessary for converted data. The type check will take at least another 5.16 seconds (one logical operation per comparison), and possibly make a sort on a single integer key faster if the data is converted into string format first.
From the results determined in the previous table, it seems that a string comparison takes about 2.9 seconds, plus approximately .066 seconds per byte (per 100,000 comparisons). No single data comparison takes less time than the time required per byte, whether or not the comparison is coded in-line. The greater the number of bytes of keys, and the more comparisons performed, the more efficient a conversion to ASCII strings will be.
To see how beneficial conversion could be, consider the case of ten integer keys. Assume that the tenth key is always necessary, and that there are 100,000 records to sort. I'll compare a sort that uses data conversion against a sort that is coded to use in-line comparisons, no type checks, and two logical integer comparisons per key (no fair testing for key equality first). In other words, I'll test a hard-coded special sort written specifically for the integer data against a general sort that uses data conversion.
The conversion sort requires 1,000,000 conversions (time: 8.8 seconds), 1,000,000 type checks (time: 3.40 seconds, if the integer test is first), and about 1,516,704 20-byte string comparisons (64.0 seconds) for a total of 76.20 seconds. The hard-coded integer sort requires no conversions or type checks, but performs 30,334,084 logical comparisons (two comparisons per key for each of the ten keys for each record comparison) for a total of 103.1 seconds--about 62 percent more time. If the integer sort had used procedure calls, the sort time would have been increased by the performance of an additional 15,167,040 procedure calls (one call per key per comparison) to a total of 445.9 seconds--nearly seven times as long as the time required with conversion!
These results are interesting because they show that:
Data conversion can pay rather large dividends, especially for a general-purpose sort, but also for any other program that must compare data in a variety of formats. If procedure calls are used to perform a comparison, any algorithm that does not use conversion might be (at best) only slightly faster than an algorithm that does use conversion. If there are multiple comparisons per record, as well as procedure calls for each comparison, it is virtually certain that conversion will be faster. In any case that involves the comparison of floating-point formats, the process of conversion plus a string comparison will be far faster than a straight floating-point comparison.
Apparently, compiler writers have missed a chance to optimize floating-point comparisons. (Borland's Turbo Basic floating-point and string comparison times are not especially different from those of Microsoft's QuickBasic, and the long-integer comparison times are much longer). I hope that future Basic compilers offer more optimization, but that won't change the overall value of conversions when multiple keys are used--string comparison operations are just too fast per byte.
Try extending these results and conversion routines to other languages, non-Intel-based machines, and to other data types. I'd be interested to hear about any cases where data conversion does not prove effective in a general sort.
All source code for articles in this issue is available on a single disk. To order, send $14 95 (Calif. residents add sales tax) to Dr. Dobb's Journal, 501 Galveston Dr., Redwood City, CA 94063, or call 800-356-2002 (from inside Calif.) or 800-533-4372 (from outside Calif.). Please specify the issue number and format (MS-DOS, Macintosh, Kaypro).
_Language-Independent Dynamic Pseudostructures_
by Bruce Tonkin
[LISTING ONE]
Copyright © 1989, Dr. Dobb's Journal
DEFDBL A-Z
DIM i AS LONG
k = 1# / LOG(2#) 'convert to base 2
OPEN "o", 1, "c:temp"
FOR i = 1 TO 100000
t = t + LOG(i) * k
IF i MOD 10000 = 0 OR i < 11 OR i = 100 OR
(i < 10000 AND i MOD 1000 = 0) THEN
PRINT #1, i, t / i, (LOG(i * .737) * k) - 1
NEXT i
[LISTING TWO]
.MODEL MEDIUM
.CODE
PUBLIC convint
;convint written by Bruce W. Tonkin on 8-14-88 for use with QB 4.0 & MASM 5.0
;convint will convert a binary 2-byte integer passed as a string into
;a string with the bytes re-ordered so an ASCII-order sort will sort in
;numeric order. It is called with:
;call convint (x$)
;where x$ is the string to convint (in the current data segment).
;The routine does not check for a zero length of the passed string.
convint PROC
push bp ;save old BP
mov bp,sp ;Set framepointer to old stack
mov bx,[bp+6] ;bx points to string length, which we don't need
mov bx,[bx]+2 ;move the string address to bx
mov dh,byte ptr [bx] ;get first byte
inc bx ;point to next byte
mov dl,byte ptr [bx] ;get second byte
xor dl,080h ;invert the sign bit
mov byte ptr [bx],dh ;store first byte where second was
dec bx ;now for modified second byte
mov byte ptr [bx],dl ;store where first byte went
pop bp ;restore old base pointer
ret 2 ;clear 2 bytes of parameters on return
convint ENDP
END
[LISTING THREE]
.MODEL MEDIUM
.CODE
PUBLIC convlong
;convlong written by Bruce W. Tonkin on 8-14-88 for use with QB 4.0 & MASM 5.0
;convlong will convert a long integer passed as a packed 4-byte string into
;a string with the bytes re-ordered so an ASCII-order sort will sort in
;numeric order. It is called with:
;call convlong (x$)
;where x$ is the string to convlong (in the current data segment).
;The routine does not check for a zero length of the passed string.
convlong PROC
push bp ;save old BP
mov bp,sp ;Set framepointer to old stack
mov bx,[bp+6] ;address of string length isn't needed
mov bx,[bx]+2 ;move the string address to bx
mov dh,byte ptr [bx] ;get first byte
inc bx ;point to next byte
mov dl,byte ptr [bx] ;get second byte
inc bx ;point to third byte
mov ah,byte ptr [bx] ;get third byte
inc bx ;point to last byte
mov al,byte ptr [bx] ;get fourth and last byte
mov byte ptr [bx],dh ;store first byte in fourth spot
dec bx ;point to third spot
mov byte ptr [bx],dl ;store former second byte
dec bx ;point to second spot
mov byte ptr [bx],ah ;store former third byte
dec bx ;point to former first byte spot
xor al,080h ;invert the sign bit
mov byte ptr [bx],al ;and store the fourth byte where first was
pop bp ;restore old base pointer
ret 2 ;clear 2 bytes of parameters on return
convlong ENDP
END
[LISTING FOUR]
.MODEL MEDIUM
.CODE
PUBLIC convof
;convof written by Bruce W. Tonkin on 8-14-88 for use with QB 4.0 & MASM 5.0
;convof will convert a Microsoft Binary format floating-point number passed as
;a string into a string with the bytes re-ordered so an ASCII-order sort will
;sort in numeric order. It is called with:
;call convof (x$)
;where x$ is the string to convof (in the current data segment).
;The routine does not check for a zero length of the passed string.
convof PROC
push bp ;save old BP
mov bp,sp ;Set framepointer to old stack
mov bx,[bp+6] ;move the string length to cx
mov cx,[bx]
push si ;save si--used by routine
mov ax,cx ;copy cx into ax
dec ax ;subtract one from ax
shr cx,1 ;divide cx by two
mov bx,[bx]+2 ;move the string address to bx
push bx ;save that address
add bx,ax ;look at the end of the string
cmp byte ptr [bx],0 ;check the first byte
pop bx ;restore string pointer
jnz va ;last byte was not zero
mov byte ptr [bx],081h ;it was zero, so make first byte 129
dec cx ;and make all other bytes zero
inc bx ;point to next byte
vt: mov byte ptr [bx],0 ;clear it
inc bx ;point to next byte
loop vt ;decrement cx and loop until done
jmp vi ;then go to the end and restore registers
va: mov si,bx ;set up si to point to bytes to swap
add si,ax ;points to last byte of string
iv: mov dl,[bx] ;first byte of string to dl
mov dh,[si] ;second byte to dh
mov [bx],dh ;and save it
mov [si],dl ;swap two bytes to reverse order
inc bx ;point to next byte
dec si ;and get ready for corresponding byte to move
loop iv ;dec cx and repeat until all bytes were swapped
mov bx,[bp+6] ;restore the original string pointer
mov cx,[bx] ;length to cx
mov bx,[bx]+2 ;location in bx
;at this point, all the bytes in the string have been put in reverse order
mov ah,[bx] ;save first string byte into ah
inc bx ;point to second byte
mov al,[bx] ;second byte into al
dec bx ;now point to first byte again
mov dh,ah ;save copies
mov dl,al ;of both bytes
push cx ;save cx=length
mov cl,7 ;get ready to rotate
shl ah,cl ;move low bit left 7 positions for first byte
shr al,cl ;move high bit right 7 positions for second byte
pop cx ;restore count in cx
and dl,07fh ;mask high bit for byte two
add dl,ah ;low bit of byte one to high bit of byte two
shr dh,1 ;shift byte one right one bit
or dh,080h ;and turn high bit on for byte one
cmp al,1 ;check status of former high bit on byte two
jnz v ;high bit wasn't set
push bx ;save string pointer
xor dx,0ffffh ;invert first two bytes
inc bx ;point to second byte
inc bx ;point to third byte
dec cx ;decrement counter accordingly
dec cx
vv: xor byte ptr [bx],0ffh ;invert successive bytes three to end
inc bx ;point to next byte
loop vv ;decrement cx and repeat until done
pop bx ;restore string pointer
v: mov byte ptr [bx],dh ;save altered byte one
inc bx
mov byte ptr [bx],dl ;and byte two
vi: pop si ;restore si
pop bp ;restore old base pointer
ret 2 ;clear 2 bytes of parameters on return
convof ENDP
END
[LISTING FIVE]
.MODEL MEDIUM
.CODE
PUBLIC convnf
;convnf written by Bruce W. Tonkin on 8-13-88 for use with QB 4.0 & MASM 5.0
;convnf will convert an IEEE floating-point number passed as a string into
;a string with the bytes re-ordered so an ASCII-order sort will sort in
;numeric order. It is called with:
;call convnf (x$)
;where x$ is the string to convnf (in the current data segment).
;The routine does not check for a zero length of the passed string.
convnf PROC
push bp ;save old BP
mov bp,sp ;Set framepointer to old stack
mov bx,[bp+6] ;move the string length to cx
mov cx,[bx]
push si ;save si--used by routine
mov ax,cx ;copy cx into ax
dec ax ;subtract one from ax
shr cx,1 ;divide cx by two
mov bx,[bx]+2 ;move the string address to bx
mov si,bx ;set up si to point to bytes to swap
add si,ax ;points to last byte of string
iv: mov dl,[bx] ;first byte of string to dl
mov dh,[si] ;second byte to dh
mov [bx],dh ;and save it
mov [si],dl ;swap two bytes to reverse order
inc bx ;point to next byte
dec si ;and get ready for corresponding byte to move
loop iv ;dec cx and repeat until all bytes were swapped
mov bx,[bp+6] ;restore the original string pointer
mov cx,[bx] ;length to cx
mov bx,[bx]+2 ;location in bx
test byte ptr [bx],080h ;check the high-order bit of the first byte
jnz v ;high-order bit was set
xor byte ptr [bx],080h ;fix the first byte
jmp vi ;and done
v: xor byte ptr [bx],0ffh ;invert all the bytes in the string
inc bx ;next location
loop v ;dec cx and repeat until all bytes have been inverted
vi: pop si ;restore si
pop bp ;restore old base pointer
ret 2 ;clear 2 bytes of parameters on return
convnf ENDP
END
[LISTING SIX]
.MODEL MEDIUM
.CODE
PUBLIC INVERT
;INVERT written by Bruce W. Tonkin on 8-13-88 for use with QB 4.0 & MASM 5.0
;INVERT will xor all the bytes in a string, thus allowing it to be sorted in
;descending order. It is called with:
;call INVERT (x$)
;where x$ is the string to invert (in the current data segment).
;The routine does not check for a zero length of the passed string.
INVERT PROC
push bp ;save old BP
mov bp,sp ;Set framepointer to old stack
mov bx,[bp+6] ;move the string length to cx
mov cx,[bx]
mov bx,[bx]+2 ;put the string address into bx
iv: xor byte ptr [bx],0ffh ;convert the first byte
inc bx
loop iv ;decrement cx and repeat until done
pop bp ;restore old base pointer
ret 2 ;clear 2 bytes of parameters on return
INVERT ENDP
END
[LISTING SEVEN]
defint a-z
dim t!(17)
dim t$(17)
open"o",1,"bench.dat"
cls
t!(0)=timer
for i=1 to 100
for j=1 to 1000
next j
next i
t!(0)=timer-t!(0) 'time for bare loop
t$(0)="Raw integer loop"
d$=mki$(-13)
t!(1)=timer
for i=1 to 100
for j=1 to 1000
CALL convint(d$)
next j
next i
t!(1)=timer-t!(1) 'time for integer conversions
t$(1)="Integer conversion"
d$=mkl$(-130000)
t!(2)=timer
for i=1 to 100
for j=1 to 1000
CALL convlong(d$)
next j
next i
t!(2)=timer-t!(2) 'time for long integer conversions
t$(2)="Long integer conversion"
d$=string$(4,204)
t!(3)=timer
for i=1 to 100
for j=1 to 1000
CALL convof(d$)
next j
next i
t!(3)=timer-t!(3) 'time for old single-precision float conversion
t$(3)="Old single float conversion"
d$=string$(8,204)
t!(4)=timer
for i=1 to 100
for j=1 to 1000
CALL convof(d$)
next j
next i
t!(4)=timer-t!(4) 'time for old double-precision float conversion
t$(4)="Old double float conversion"
d$=mks$(-13.0405)
t!(5)=timer
for i=1 to 100
for j=1 to 1000
CALL convnf(d$)
next j
next i
t!(5)=timer-t!(5) 'time for IEEE single-precision float conversion
t$(5)="IEEE single float conversion"
d$=mkd$(-13.04050607)
t!(6)=timer
for i=1 to 100
for j=1 to 1000
CALL convnf(d$)
next j
next i
t!(6)=timer-t!(6) 'time for IEEE double-precision float conversion
t$(6)="IEEE double float conversion"
t!(7)=timer
for i=1 to 100
for j=1 to 1000
CALL invert(d$)
next j
next i
t!(7)=timer-t!(7) 'time for inverting 8 bytes
t$(7)="Invert 8 bytes"
a$="AB"
b$="AX"
t!(8)=timer
for i=1 to 100
for j=1 to 1000
if a$>b$ then j=j+1
next j
next i
t!(8)=timer-t!(8) 'time to compare two-byte strings
t$(8)="Compare two-byte strings"
a=100
b=200
t!(9)=timer
for i=1 to 100
for j=1 to 1000
if a>b then j=j+1
next j
next i
t!(9)=timer-t!(9) 'time to compare two integers
t$(9)="Compare two integers"
a$="ABCD"
b$="ABCX"
t!(10)=timer
for i=1 to 100
for j=1 to 1000
if a$>b$ then j=j+1
next j
next i
t!(10)=timer-t!(10) 'time to compare two 4-byte strings
t$(10)="Compare two four-byte strings"
a!=100.01!
b!=200.01!
t!(11)=timer
for i=1 to 100
for j=1 to 1000
if a!>b! then j=j+1
next j
next i
t!(11)=timer-t!(11) 'time to compare two single floats
t$(11)="Compare two single floats"
a#=100.01#
b#=200.01#
t!(12)=timer
for i=1 to 100
for j=1 to 1000
if a#>b# then j=j+1
next j
next i
t!(12)=timer-t!(12) 'time to compare two double floats
t$(12)="Compare two double floats"
a$="ABCDEFGH"
b$="ABCDEFGX"
t!(13)=timer
for i=1 to 100
for j=1 to 1000
if a$>b$ then j=j+1
next j
next i
t!(13)=timer-t!(13) 'time to compare two 8-byte strings
t$(13)="Compare two 8-byte strings"
a&=123456&
b&=123457&
t!(14)=timer
for i=1 to 100
for j=1 to 1000
if a&>b& then j=j+1
next j
next i
t!(14)=timer-t!(14) 'time to compare two long integers
t$(14)="Compare two long integers"
a$="ABCDEFGHIJKLMNOPQRST"
b$="ABCDEFGHIJKLMNOPQRSX"
t!(15)=timer
for i=1 to 100
for j=1 to 1000
if a$>b$ then j=j+1
next j
next i
t!(15)=timer-t!(15) 'time to compare two 20-byte strings
t$(15)="Compare two 20-byte strings"
a$="ABCDEFGHIJKLMNOPQRST"
b$="XBCDEFGHIJKLMNOPQRST"
t!(16)=timer
for i=1 to 100
for j=1 to 1000
if a$>b$ then j=j+1
next j
next i
t!(16)=timer-t!(16) 'best? time to compare two 20-byte strings
t$(16)="Compare two 20-byte strings (best?)"
t!(17)=timer
for i=1 to 100
for j=1 to 1000
call dummy(a,b,c)
next j
next i
t!(17)=timer-t!(17) 'time to make a call with three parameters
t$(17)="Three-integer-parameter call"
print t$(0),t!(0)
print #1,t$(0),t!(0)
for i=1 to 17
t!(i)=t!(i)-t!(0)
print t$(i),t!(i)
print #1,t$(i),t!(i)
next i
sub dummy(a,b,c) static
c=1
end sub