An interesting Speed Comparison

[cas]

Hi Carsten and Pengwin-

 

I've added a whole bunch of duplicates and an even bigger batch of records with fields of parantheses.

 

I'll test the file and send it out.

 

-Larry

 

Cool. I haven't had much time during the weekend, but I'll try to continue on this this week.

 

Carsten

[+Larry]

Hi Carsten-

 

I ran the BXE version with the updated data file, and got 16.11 minutes with DMA on, and 11.00 minutes with DMA off, or a 31.7% improvement. I've tried to implement a BGET strategy (BXE has that, also), but the results are ugly. I'll be interested to see how you do it in TBXL. I end up with lots of subscripting that just *eats* time. As an alternative, I'm also thinking about a way to effectively use RGET which allows BXE to get fixed length records. That might be less cumbersome. (?) -Larry

[+Larry]

Hi Carsten-

 

I ran the BXE version with the updated data file, and got 16.11 minutes with DMA on, and 11.00 minutes with DMA off, or a 31.7% improvement. I've tried to implement a BGET strategy (BXE has that, also), but the results are ugly. I'll be interested to see how you do it in TBXL. I end up with lots of subscripting that just *eats* time. As an alternative, I'm also thinking about a way to effectively use RGET which allows BXE to get fixed length records. That might be less cumbersome. (?) -Larry

 

Ahh! A flash of inspiration -- I thought of a better way to work with BGET segment...

-Larry

[cas]

Hi Carsten-

 

I ran the BXE version with the updated data file, and got 16.11 minutes with DMA on, and 11.00 minutes with DMA off, or a 31.7% improvement. I've tried to implement a BGET strategy (BXE has that, also), but the results are ugly. I'll be interested to see how you do it in TBXL. I end up with lots of subscripting that just *eats* time. As an alternative, I'm also thinking about a way to effectively use RGET which allows BXE to get fixed length records. That might be less cumbersome. (?) -Larry

 

Ahh! A flash of inspiration -- I thought of a better way to work with BGET segment...

-Larry

 

Hi,

 

I have an indea for an "Hack": Scan you favorite DOS for the comparison for the Atari EOL (155, $9b), patch the DOS at the beginning of the program with the PC EOL (10, $0A), and use INPUT #1,S$ from basic (which uses BGET internally, or CIO TXT Record Read), and patch it back later. Same can be done when writing the file.

 

Carsten

[+Larry]

Hi,

 

I have an indea for an "Hack": Scan you favorite DOS for the comparison for the Atari EOL (155, $9b), patch the DOS at the beginning of the program with the PC EOL (10, $0A), and use INPUT #1,S$ from basic (which uses BGET internally, or CIO TXT Record Read), and patch it back later. Same can be done when writing the file.

 

Carsten

 

That's an interesting idea! I've pretty much now given up on the direct use of BGET. I've implemented enough of it to know that by the time you do all the incrementing and checking to make sure you are still within the BGET data segment, it is no faster (and probably slower) than using GET from the ramdisk. Perhaps you will be more successful.

 

Another possibility is to re-write the whole data file before processing it (within the program), converting the CR/LF's to 155's. I wrote a ML CR/LF converter routine quite a few years ago that re-writes a file from a ramdisk in just a few seconds. Using INPUT #1... should be incredibly faster. Now to see if I can find my original code...

-Larry

[+Larry]

(snip...)

Another possibility is to re-write the whole data file before processing it (within the program), converting the CR/LF's to 155's. I wrote a ML CR/LF converter routine quite a few years ago that re-writes a file from a ramdisk in just a few seconds. Using INPUT #1... should be incredibly faster. Now to see if I can find my original code...

 

Well, this looks much more promising. I adapted my CR/LF converter, and it will read/convert/write the entire 700+ sector data file in apx. 12 seconds!

I had thought about doing this previously, but it seemed like a lot of work! I guess this has motivated me. Perhaps under 5 minutes (total) is possible?

-Larry

[+Larry]

Well, this looks much more promising. I adapted my CR/LF converter, and it will read/convert/write the entire 700+ sector data file in apx. 12 seconds!

I had thought about doing this previously, but it seemed like a lot of work! I guess this has motivated me. Perhaps under 5 minutes (total) is possible?

-Larry

 

By converting the CR/LF's to 155's, I was able to shave off another 5 minutes from the processing time.

Times now with Basic XE are DMA on: 11.3 minutes DMA off: 7.4 minutes. The Turbo Basic compiled version should be a little faster yet.

But unless there is some tricky way to find the duplicates, this is about the end of the road (at least in Basic).

-Larry

[+Larry]

By converting the CR/LF's to 155's, I was able to shave off another 5 minutes from the processing time.

Times now with Basic XE are DMA on: 11.3 minutes DMA off: 7.4 minutes. The Turbo Basic compiled version should be a little faster yet.

But unless there is some tricky way to find the duplicates, this is about the end of the road (at least in Basic).

-Larry

 

I guess "it's not over 'til it's over." While thinking about the search for duplicate records, it occurred to me that I was searching as if the records were unsorted. So I would have to search from the current position in the file to the end for each comparison. That would be about 90,000 comparisons. But since the records are sorted by then, all I need do is compare adjacent records. Apx. 900 comparisons instead of 90,000. That was huge.

So the almost-final times for BXE are down to DMA on: 4.2 minutes; DMA off: 2.9 minutes.

It's come a long way from the 60+ minutes of one of the first versions!

 

After I get things cleaned up a bit, I'll post the times for TBXL and Atari 8K Basic.

 

-Larry

[devwebcl]

finally, which sort method are you using guys?

I have read in the thread about shell , radix, insertion, but finally any final implementation at all?

 

--devwebcl

[cas]

finally, which sort method are you using guys?

I have read in the thread about shell , radix, insertion, but finally any final implementation at all?

 

--devwebcl

 

I have implemented Bubble Sort, Shell Sort and Comp Sort, Shell Sort being the fastest on the dataset.

 

Carsten

[Nukey Shay]

Here's a crazy idea-- just load the whole thing into an Excel spreadsheet and be done with it.

 

Of course it's silly and stupid to work with old, obsolete computers like the A8 theses days ---- that's why we do it!

 

lol

Without interest in classic systems, this site probably wouldn't exist

[+Larry]

finally, which sort method are you using guys?

I have read in the thread about shell , radix, insertion, but finally any final implementation at all?

 

--devwebcl

 

Basic XE has built-in commands for SORTUP and SORTDOWN. But they don't specify in the manual how it's implemented (shell, etc.).

 

IIRC, the ML sort used in the TB and Atari 8k Basic versions is supposedly a variant of the Shell sort.

 

When I originally wrote this program, I switched from TBXL to BXE because of the ease/speed of sorting and true string arrays in BXE. I also really like the OSS "Supercarts," because you can turn them off (and on) from Dos, so you can effectively "remove or attach them" without having to physically pull/insert the cart.

 

-Larry

[+Stephen]

I find this topic fascinating. Great example of why many times human optomization will beat a compiler hands down.

 

Stephen Anderson

[devwebcl]

Basic XE has built-in commands for SORTUP and SORTDOWN. But they don't specify in the manual how it's implemented (shell, etc.).

 

Probably the BXE sort implementation is faster (not tested) however I made the Insert Sort for TBX, maybe you would like to try out:

 

10 REM INSERTION SORT
40 DIM A(10)
50 A(0)=2
60 A(1)=1
70 A(2)=78
72 A(3)=34
76 A(4)=89
77 A(5)=11
78 A(6)=18
80 A(7)=45
81 A(8)=62
82 A(9)=83
90 N=10
100 FOR I=1 TO N-1
120   T=A(I)
145   J=I-1
150   WHILE J>=0
180	 IF A(J)<=T THEN EXIT 
190	 A(J+1)=A(J)
205	 J=J-1
210   WEND 
220   A(J+1)=T
240 NEXT I
1000 FOR X=0 TO N-1
1010   PRINT A(X)
1020 NEXT X

 

this algorithm is supposed to be faster for small sets.

 

Kind Regards,

 

--devwebcl

[+Larry]

Basic XE has built-in commands for SORTUP and SORTDOWN. But they don't specify in the manual how it's implemented (shell, etc.).

 

Probably the BXE sort implementation is faster (not tested) however I made the Insert Sort for TBX, maybe you would like to try out:

 

(snip...)

 

Thanks, I will check it out.

 

Here are the final times (with the standard data file):

 

Atari Basic: DMA on 8.58 min DMA off 5.92 min

Turbo Basic XL DMA on 4.25 min DMA off 2.93 min

Basic XE DMA on 4.36 min DMA off 3.03 min

 

All times are accurate to +/- .1 min. They do vary slightly from run-to-run. The TBXL program still has a bug when executing my ML CR/LF converter. For some reason, it refuses to convert the first 2 sets of CR/LF. I finally gave up trying to find this bug, instead adding the times of the two parts of the program. I'm still positive that the times shown above are *very* accurate. I don't have the source code for the ML routine anymore, and I'm sure it would shed some light on the bug. The converter works perfectly under Atari Basic and BXE. Perhaps at a later date I'll disassemble the routine and sort it out.

 

I'd like to thank Carsten for his interest in this which prompted me to "dig a little deeper" to find improvements. I'm sure that I wouldn't have looked any further than I already had. And thanks for the input and suggestions from other folks, also.

 

-Larry

[Allas]

You forgot the fast BASIC ADVANCED.

 

And maybe with compiled versions.

Edited February 3, 2007 by Allas

[+Larry]

You forgot the fast BASIC ADVANCED.

 

And maybe with compiled versions.

 

Sorry, this is the end of the road, at least for now.

 

-Larry

[cas]

 

 

Here are the final times (with the standard data file):

 

Atari Basic: DMA on 8.58 min DMA off 5.92 min

Turbo Basic XL DMA on 4.25 min DMA off 2.93 min

Basic XE DMA on 4.36 min DMA off 3.03 min

 

 

Sorry for my bad performance in delivering my FORTH version. My day job sends me around the world and I'm not finding some spare time to finish the FORTH version, however, I'll do it as soon as possible.

 

Carsten

today from Bangalore, India

[+Larry]

You forgot the fast BASIC ADVANCED.

 

And maybe with compiled versions.

 

In case I get motivated again (or perhaps someone else will?), I am familiar with ADVAN BASIC and CTH FAST BASIC. Are you referring to one of these?

 

I don't have much experience with either one, but I remember that FAST BASIC is quite compatible with Atari 8K, while ADVAN BASIC is not so compatible.

Porting it to Atari Microsoft BASIC would also be interesting, but a big job (since it is so different than A8K). Perhaps after the current "burn-out" subsides...

-Larry

[+Larry]

For those who may have read this thread previously -- I was still not satisfied that I could not get the Turbo Basic XL version of the program working properly with the "improved program" nor a TBXL compiled version to work at all. So I decided to re-write the program from scratch and as nearly as possible have one "FITS-ALL" version. The only exceptions are adding a "FAST" command to Basic XL and Basic XE and using a watch for the elapsed time for the ABC compiler version (which didn't affect the execution time, anyway). So here are the times -- fastest to slowest (screen ON):

 

Turbo Basic Compiled: 1.05 minutes

ABC Compiler: 1.67 minutes (timed by watch)

Turbo Basic XL: 2.11 minutes

Basic XE: 2.19 minutes (FAST command)

Basic XL: 2.80 minutes (FAST command)

CTH Fast Basic: 3.70 minutes

Atari 8K Basic: 5.07 minutes (slowest, as usual!)

 

The results are about what I'd expect. Basic XL is interesting in that in some applications, it is just about as slow as Atari 8K Basic, and sometimes (like here) it is substantially faster. These times are not directly comparable with the previous times -- a different file was processed for these tests.

 

Now, I think I'm finally done!

 

-Larry

Edited June 19, 2008 by Larry