Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.sys.apple2.programmer > #2471 > unrolled thread

qsort for 65c02

Back to article view | Back to comp.sys.apple2.programmer

Contents

  qsort for 65c02 wssimms@gmail.com - 2016-03-10 07:34 -0800
    Re: qsort for 65c02 qkumba <peter.ferrie@gmail.com> - 2016-03-10 09:10 -0800
    Re: qsort for 65c02 gids.rs@sasktel.net - 2016-03-10 17:23 -0800
      Re: qsort for 65c02 gids.rs@sasktel.net - 2016-03-10 19:13 -0800
      Re: qsort for 65c02 "Michael J. Mahon" <mjmahon@aol.com> - 2016-03-10 19:37 -0800
        Re: qsort for 65c02 wssimms@gmail.com - 2016-03-10 21:37 -0800
          Re: qsort for 65c02 gids.rs@sasktel.net - 2016-03-11 12:43 -0800
            Re: qsort for 65c02 Michael J. Mahon <mjmahon@aol.com> - 2016-03-11 15:48 -0600
              Re: qsort for 65c02 gids.rs@sasktel.net - 2016-03-11 20:59 -0800
                Re: qsort for 65c02 gids.rs@sasktel.net - 2016-03-11 21:13 -0800
                  Re: qsort for 65c02 wssimms@gmail.com - 2016-03-11 21:19 -0800
            Re: qsort for 65c02 wssimms@gmail.com - 2016-03-12 07:15 -0800
              Re: qsort for 65c02 wssimms@gmail.com - 2016-03-12 07:25 -0800
              Re: qsort for 65c02 Michael J. Mahon <mjmahon@aol.com> - 2016-03-12 11:22 -0600
              Re: qsort for 65c02 gids.rs@sasktel.net - 2016-03-12 10:00 -0800
                Re: qsort for 65c02 Michael J. Mahon <mjmahon@aol.com> - 2016-03-12 14:09 -0600
                Re: qsort for 65c02 wssimms@gmail.com - 2016-03-12 22:17 -0800
                  Re: qsort for 65c02 Scott Hemphill <hemphill@hemphills.net> - 2016-03-13 09:03 -0400
                  Re: qsort for 65c02 gids.rs@sasktel.net - 2016-03-13 09:22 -0700
                    Re: qsort for 65c02 Michael J. Mahon <mjmahon@aol.com> - 2016-03-13 13:45 -0500
                      Re: qsort for 65c02 gids.rs@sasktel.net - 2016-03-13 19:01 -0700
                        Re: qsort for 65c02 wssimms@gmail.com - 2016-03-13 21:28 -0700
                          Re: qsort for 65c02 Michael J. Mahon <mjmahon@aol.com> - 2016-03-14 14:06 -0500
                        Re: qsort for 65c02 Michael Pohoreski <michael.pohoreski@gmail.com> - 2016-03-13 22:15 -0700
                          Re: qsort for 65c02 Michael J. Mahon <mjmahon@aol.com> - 2016-03-14 14:06 -0500
                        Re: qsort for 65c02 Michael J. Mahon <mjmahon@aol.com> - 2016-03-14 14:06 -0500
                  Re: qsort for 65c02 Michael J. Mahon <mjmahon@aol.com> - 2016-03-13 13:45 -0500
                    Re: qsort for 65c02 wssimms@gmail.com - 2016-03-13 15:46 -0700
                      Re: qsort for 65c02 Michael J. Mahon <mjmahon@aol.com> - 2016-03-14 14:06 -0500
    Re: qsort for 65c02 Michael Pohoreski <michael.pohoreski@gmail.com> - 2016-03-11 03:30 -0800
      Re: qsort for 65c02 gids.rs@sasktel.net - 2016-03-11 13:25 -0800
        Re: qsort for 65c02 Michael Pohoreski <michael.pohoreski@gmail.com> - 2016-03-14 16:24 -0700
          Re: qsort for 65c02 Michael J. Mahon <mjmahon@aol.com> - 2016-03-14 23:35 -0500
            Re: qsort for 65c02 gids.rs@sasktel.net - 2016-03-15 10:20 -0700
              Re: qsort for 65c02 Michael J. Mahon <mjmahon@aol.com> - 2016-03-15 17:30 -0500
            Re: qsort for 65c02 Michael Pohoreski <michael.pohoreski@gmail.com> - 2016-03-15 13:35 -0700
              Re: qsort for 65c02 gids.rs@sasktel.net - 2016-03-15 20:15 -0700
              Re: qsort for 65c02 gids.rs@sasktel.net - 2016-03-15 20:23 -0700
                Re: qsort for 65c02 Michael Pohoreski <michael.pohoreski@gmail.com> - 2016-03-16 10:33 -0700
                  Re: qsort for 65c02 wssimms@gmail.com - 2016-03-18 08:50 -0700
                    Re: qsort for 65c02 David Schmidt <schmidtd@my-deja.com> - 2016-03-18 12:37 -0400
                      Re: qsort for 65c02 wssimms@gmail.com - 2016-03-18 10:04 -0700
                    Re: qsort for 65c02 Michael Pohoreski <michael.pohoreski@gmail.com> - 2016-03-18 10:12 -0700
                      Re: qsort for 65c02 wssimms@gmail.com - 2016-03-18 10:33 -0700
                        Re: qsort for 65c02 Michael J. Mahon <mjmahon@aol.com> - 2016-03-18 13:01 -0500
                          Re: qsort for 65c02 wssimms@gmail.com - 2016-03-18 11:33 -0700
                            Re: qsort for 65c02 Michael J. Mahon <mjmahon@aol.com> - 2016-03-18 17:37 -0500
                    Re: qsort for 65c02 Michael Pohoreski <michael.pohoreski@gmail.com> - 2016-03-20 10:52 -0700
                      Re: qsort for 65c02 Michael J. Mahon <mjmahon@aol.com> - 2016-03-20 13:42 -0500
                        Re: qsort for 65c02 D Finnigan <dog_cow@macgui.com> - 2016-03-20 19:05 +0000
                          Re: qsort for 65c02 Michael J. Mahon <mjmahon@aol.com> - 2016-03-20 15:37 -0500
                        Re: qsort for 65c02 Michael Pohoreski <michael.pohoreski@gmail.com> - 2016-03-20 13:33 -0700
                          Re: qsort for 65c02 Michael J. Mahon <mjmahon@aol.com> - 2016-03-20 15:53 -0500
                      Re: qsort for 65c02 gids.rs@sasktel.net - 2016-03-20 18:40 -0700
                        Re: qsort for 65c02 Michael J. Mahon <mjmahon@aol.com> - 2016-03-21 01:40 -0500

Page 2 of 3 — ← Prev page 1 [2] 3  Next page →

#2505

> > There seems to be no shortage of applesoft programs, and some of the
> > ideas implemented in them have no assembly language counterpart.
> > 
> 
> Whaaaat?
> 
> Certainly there is an assembly language equivalent to *every* Applesoft
> program, so I'm not sure what you mean. 
> 
> Perhaps you mean that Applesoft's built-in support for floating-point and
> varying-length strings leads to small Applesoft programs that would be
> fairly large (and improbable) assembly language programs?


Floating point math is only one and not even the top one on my list.  It has more to do with arrays, screen displays, graphics programs and games, and whatever imagination the mind can conjur up.  Just like most people have libraries of programs in their collection, I am also collecting utilities and rewriting them into assembly.

Of all the years I have been programming, I have never come across a radix sort in any language and on any computer, other than this one little listing on a piece of crumpled magazine paper.  I'd like to get the article that I got it from now, just to read.

[toc] | [prev] | [next] | [standalone]

#2506

I remember learning bucket sort back I had my first intro to computer science class. Since then I haven't seen it used as such but it is very similar to a hashtable. In fact the code you presented basically is a hashtable where the first character of the string is the hash key.

[toc] | [prev] | [next] | [standalone]

#2512

<wssimms@gmail.com> wrote:
> I remember learning bucket sort back I had my first intro to computer
> science class. Since then I haven't seen it used as such but it is very
> similar to a hashtable. In fact the code you presented basically is a
> hashtable where the first character of the string is the hash key.
> 

True, though for sorting, order preservation is the goal, while for hashing
it's usually anathema. ;-)

The property of the radix sort that I find most interesting is that, unlike
virtually every other sort/merge algorithm, it never does a compare on a
key!
-- 
-michael - NadaNet 3.1 and AppleCrate II:  http://michaeljmahon.com

[toc] | [prev] | [next] | [standalone]

#2507

On Sunday, March 13, 2016 at 7:01:15 PM UTC-7, gid...@sasktel.net wrote:

> Of all the years I have been programming, I have never come across a radix sort in any language and on any computer, other than this one little listing on a piece of crumpled magazine paper.  I'd like to get the article that I got it from now, just to read.

In the games industry pre 2000 I've seen radix sort used in the days of software rendering to sort floats (polygon's vertices) in O(n) time.

The 3x memory space required makes it extremely slow on modern CPU's as the delta between CPU and Memory access speeds grew apart.

[toc] | [prev] | [next] | [standalone]

#2513

Michael Pohoreski <michael.pohoreski@gmail.com> wrote:
> On Sunday, March 13, 2016 at 7:01:15 PM UTC-7, gid...@sasktel.net wrote:
> 
>> Of all the years I have been programming, I have never come across a
>> radix sort in any language and on any computer, other than this one
>> little listing on a piece of crumpled magazine paper.  I'd like to get
>> the article that I got it from now, just to read.
> 
> In the games industry pre 2000 I've seen radix sort used in the days of
> software rendering to sort floats (polygon's vertices) in O(n) time.
> 
> The 3x memory space required makes it extremely slow on modern CPU's as
> the delta between CPU and Memory access speeds grew apart.
> 

3x seems a little extreme. I suppose it depends on the length of the
records compared to the length of a link. 

The only space required in addition to the items themselves is one link per
item. The bucket pointers (2 per bucket) are independent of the number of
items, and can be kept very reasonable by choosing a moderate number of
bits for the radix. 

In the common case of the input items already being a linked list, there is
no additional per item space needed, just two arrays of pointers with
length equal to the chosen radix. 
-- 
-michael - NadaNet 3.1 and AppleCrate II:  http://michaeljmahon.com

[toc] | [prev] | [next] | [standalone]

#2510

<gids.rs@sasktel.net> wrote:
>>> There seems to be no shortage of applesoft programs, and some of the
>>> ideas implemented in them have no assembly language counterpart.
>>> 
>> 
>> Whaaaat?
>> 
>> Certainly there is an assembly language equivalent to *every* Applesoft
>> program, so I'm not sure what you mean. 
>> 
>> Perhaps you mean that Applesoft's built-in support for floating-point and
>> varying-length strings leads to small Applesoft programs that would be
>> fairly large (and improbable) assembly language programs?
> 
> 
> Floating point math is only one and not even the top one on my list.  It
> has more to do with arrays, screen displays, graphics programs and games,
> and whatever imagination the mind can conjur up.  Just like most people
> have libraries of programs in their collection, I am also collecting
> utilities and rewriting them into assembly.
> 
> Of all the years I have been programming, I have never come across a
> radix sort in any language and on any computer, other than this one
> little listing on a piece of crumpled magazine paper.  I'd like to get
> the article that I got it from now, just to read.
> 

It's true that radix sort doesn't get much respect, but the microcomputer
world tends not to be very sort-obsessed (you seem like an exception ;-),
and transaction processing has made sorting less central to commercial data
processing. 

When sorting and merging were the heart of every batch processing "update"
app, there were literally hundreds of sort programs (and sort program
generators!). Knuth, in the "Sorting and Searching" volume (!) of "The Art
of Computer Programming" spends much of the volume on sorting methods, and
reduces them all to combinations of, IIRC, 28 different algorithms--all
categorized into their performance and space behaviors, their sensitivity
to initial key distributions, and their stability (ability to preserve
initial order among records having equal keys). 

I recommend Knuth as a reference for sorting algorithms (and for much else,
like searching and pseudorandom number generators).  

For most microcomputer applications, the numbers of records are small
enough that algorithm efficiency is not a critical factor, and most
programmers just do what they usually do, which is program the first
algorithm that comes to mind and, if it's not too bad, leave it. Optimality
is seldom a goal.  In fact, the vast majority simply call the library sort
subroutine, regardless of how suitable it is for their application. 

I applaud your interest in going beyond "it works" to measure and try to
improve your programs. 

I've been told that today it's more important to "get it out the door" than
to "get it right", and I regret the consequent loss of craftsmanship in
programming.  ;-(  Today, most commercial programmers are essentially
"scripting" on top of a very deep pile of libraries with almost no control
over the overall efficiency or size of what they are building. It's a
different world. 

That may explain some of the interest in 8-bit micros, where programming
"on the metal" is both possible and rewarding.  ;-)

Keep having fun!
-- 
-michael - NadaNet 3.1 and AppleCrate II:  http://michaeljmahon.com

[toc] | [prev] | [next] | [standalone]

#2501

<wssimms@gmail.com> wrote:
> I couldn't quite figure out AM and BM myself, so I changed them to FM
> (first character) and LM (last character).
> 
> You are right about the increased number of buckets playing a large role
> in the sort time. Of course that means an increased extra memory
> requirement but as long as your got the variable space to spare that's fine.
>

The range of the radix is determined by the range of key values, which is
not typically at the discretion of the sort algorithm, and the number of
bits of the key chosen for the radix, which, though chosen by the sort, is
usually strongly influenced by the processor architecture. 

In this case, an 8-bit byte is the natural unit, and any limitation on its
allowable range of values must be enforced before it can be relied upon.
This is a natural consequence of using it as an array index. 
-- 
-michael - NadaNet 3.1 and AppleCrate II:  http://michaeljmahon.com

[toc] | [prev] | [next] | [standalone]

#2504

You are correct but in this case, the choice of the values of the variables AM and BM dictates what subset of the ASCII character set is used to generate the to-be-sorted strings, which determines the number of possible first characters, and thus the number of buckets.

[toc] | [prev] | [next] | [standalone]

#2511

<wssimms@gmail.com> wrote:
> You are correct but in this case, the choice of the values of the
> variables AM and BM dictates what subset of the ASCII character set is
> used to generate the to-be-sorted strings, which determines the number of
> possible first characters, and thus the number of buckets.
> 

Right, for the benchmark program.

I was pointing out that I n an actual application, the key range is usually
already chosen. ;-)
-- 
-michael - NadaNet 3.1 and AppleCrate II:  http://michaeljmahon.com

[toc] | [prev] | [next] | [standalone]

#2481

Nice job!

Don't have any need for any sorting but always nice to have something in the toolbox for that rainy day -- which happens to be more often then not in Seattle :-)

[toc] | [prev] | [next] | [standalone]

#2484

On Friday, March 11, 2016 at 5:30:42 AM UTC-6, Michael Pohoreski wrote:
> Nice job!
> 
> Don't have any need for any sorting but always nice to have something in the toolbox for that rainy day -- which happens to be more often then not in Seattle :-)



Seriously?  :)

I use a sorting routine in about 30% of my programs I use or write.

Everything from Directories, garbage collection, spread sheets, data base, SRC creation, line cross-reference, variable cross-reference, Games with hi-scores, Games that require sorting cards, tiles or dice, and, dictionaries, word tables at the end of source code, word lists, even word processors (to sort word lists).

I even wrote a directory sorter that puts directories first, then system files, binary, basic, text and all others.

My life is all about being sorted.

Yep. If someone were to look in my closet, they would think it was a mess.  But it is actually sorted.  But not by socks or shirts or pants each in their own place.  It is sorted by having one pair of pants, one shirt and one pair of socks that go together, in once place.  (If you don't see the humor in this, it is time to go outside and get some sun :)

But, I think my point is, I think we all use sorting algorithms more than we realize.  And to be effective or efficient, sorting has to be fast.  Not like applesofts garbage collector.

Imagine the size of a list that a 1 Mhz apple computer can now handle with a sorting routine that is 3 times faster than the current fastest one that most programmers use.

That's it for now.  I have to go find something to sort through.

[toc] | [prev] | [next] | [standalone]

#2514

On Friday, March 11, 2016 at 1:25:47 PM UTC-8, gid...@sasktel.net wrote:
> On Friday, March 11, 2016 at 5:30:42 AM UTC-6, Michael Pohoreski wrote:
> > Nice job!
> > Don't have any need for any sorting but always nice to have something in the toolbox for that rainy day -- which happens to be more often then not in Seattle :-)
> Seriously?  :)

/Oblg.

O RLY?
Ya RLY!

http://www.aloha.net/~rbenson/O_Ya_rly.jpg

> I use a sorting routine in about 30% of my programs I use or write.

1. I'm a graphics / shader guy so sorting is not too high on the list.  

2. As someone who uses Data-Orientated-Design, as opposed to bloated OOP, sorting means you keep all your data _already_ sorted -- thus insertion sort, or merge sort does 99% of the job.

[toc] | [prev] | [next] | [standalone]

#2515

Michael Pohoreski <michael.pohoreski@gmail.com> wrote:
> On Friday, March 11, 2016 at 1:25:47 PM UTC-8, gid...@sasktel.net wrote:
>> On Friday, March 11, 2016 at 5:30:42 AM UTC-6, Michael Pohoreski wrote:
>>> Nice job!
>>> Don't have any need for any sorting but always nice to have something
>>> in the toolbox for that rainy day -- which happens to be more often
>>> then not in Seattle :-)
>> Seriously?  :)
> 
> /Oblg.
> 
> O RLY?
> Ya RLY!
> 
> http://www.aloha.net/~rbenson/O_Ya_rly.jpg
> 
>> I use a sorting routine in about 30% of my programs I use or write.
> 
> 1. I'm a graphics / shader guy so sorting is not too high on the list.  
> 
> 2. As someone who uses Data-Orientated-Design, as opposed to bloated OOP,
> sorting means you keep all your data _already_ sorted -- thus insertion
> sort, or merge sort does 99% of the job.
> 
> 

Excellent!  

The most efficient code is the code you avoid calling!  ;-)
-- 
-michael - NadaNet 3.1 and AppleCrate II:  http://michaeljmahon.com

[toc] | [prev] | [next] | [standalone]

#2516

> > 
> > O RLY?
> > Ya RLY!
> > 
> > http://www.aloha.net/~rbenson/O_Ya_rly.jpg
> > 
> >> I use a sorting routine in about 30% of my programs I use or write.
> > 
> > 1. I'm a graphics / shader guy so sorting is not too high on the list.  
> > 
> > 2. As someone who uses Data-Orientated-Design, as opposed to bloated OOP,
> > sorting means you keep all your data _already_ sorted -- thus insertion
> > sort, or merge sort does 99% of the job.
> > 
> > 
> 
> Excellent!  
> 
> The most efficient code is the code you avoid calling!  ;-)


That's because the least efficient code is still more efficient than the most efficient person entering the data and is sufficiently efficient.

[toc] | [prev] | [next] | [standalone]

#2518

<gids.rs@sasktel.net> wrote:
> 
>>> 
>>> O RLY?
>>> Ya RLY!
>>> 
>>> http://www.aloha.net/~rbenson/O_Ya_rly.jpg
>>> 
>>>> I use a sorting routine in about 30% of my programs I use or write.
>>> 
>>> 1. I'm a graphics / shader guy so sorting is not too high on the list.  
>>> 
>>> 2. As someone who uses Data-Orientated-Design, as opposed to bloated OOP,
>>> sorting means you keep all your data _already_ sorted -- thus insertion
>>> sort, or merge sort does 99% of the job.
>>> 
>>> 
>> 
>> Excellent!  
>> 
>> The most efficient code is the code you avoid calling!  ;-)
> 
> 
> That's because the least efficient code is still more efficient than the
> most efficient person entering the data and is sufficiently efficient.
> 

Hear, hear.  Some apps accumulate user-input records, then, after all the
records are input, sort them as the user waits...

Much better to insertion-sort each record as it's input, where the small
amount of time for the insert is unnoticeable. 

Of course, if they need to be sorted later on another key, that's where
efficiency matters. 
-- 
-michael - NadaNet 3.1 and AppleCrate II:  http://michaeljmahon.com

[toc] | [prev] | [next] | [standalone]

#2517

On Monday, March 14, 2016 at 9:35:46 PM UTC-7, mjm...@aol.com wrote:
> Excellent!  
> The most efficient code is the code you avoid calling!  ;-)

Yup, us graphic guys have a saying:

The fastest triangle to draw is the one you don't. :-)

[toc] | [prev] | [next] | [standalone]

#2519

On Tuesday, March 15, 2016 at 2:35:20 PM UTC-6, Michael Pohoreski wrote:
> On Monday, March 14, 2016 at 9:35:46 PM UTC-7, mjm...@aol.com wrote:
> > Excellent!  
> > The most efficient code is the code you avoid calling!  ;-)
> 
> Yup, us graphic guys have a saying:
> 
> The fastest triangle to draw is the one you don't. :-)

[toc] | [prev] | [next] | [standalone]

#2520

On Tuesday, March 15, 2016 at 2:35:20 PM UTC-6, Michael Pohoreski wrote:
> On Monday, March 14, 2016 at 9:35:46 PM UTC-7, mjm...@aol.com wrote:
> > Excellent!  
> > The most efficient code is the code you avoid calling!  ;-)
> 
> Yup, us graphic guys have a saying:
> 
> The fastest triangle to draw is the one you don't. :-)



What about all the time spent in deciding to not draw the triangle?

To draw a triangle, or to not draw a triangle?

Yuse graphic guys must spend hours deliberating that question.  :)

[toc] | [prev] | [next] | [standalone]

#2521

On Tuesday, March 15, 2016 at 8:23:54 PM UTC-7, gid...@sasktel.net wrote:
> What about all the time spent in deciding to not draw the triangle?

You don't do this on a per triangle basis as that would be stupidly expensive.  While you can't remove the overhead you certainly can minimize it.  That's why you do batching so you can amortize the cost. :-) i.e. Frustum Culling, Spatial Partitioning / Chunk Rendering, etc.

You also want to minimize the number of draw calls since the time spent in the OS + GPU Driver all add up.  Which is the biggest reason Vulkan, Metal, and DX12 are such big deals.


> To draw a triangle, or to not draw a triangle?
> Yuse graphic guys must spend hours deliberating that question.  :)

Try *decades*! This point (pardon the pun) literally has driven the graphics & games industry for decades for higher throughput with latency becoming less important. That's why we have things like Early Depth Test, Early Alpha Test, Early Stencil Tests, and rules of thumbs such as minimize state changes, sort by texture / shader, use render objects, etc.

Anyways, this is getting seriously OFF-TOPIC.  I guess everyone is bored. :-)   Sorry Sheldon, didn't mean to derail the thread.  

"All programming is an exercise in caching." - Terje Mathisen (famous optimization programmer)

[toc] | [prev] | [next] | [standalone]

#2535

No problem, I found the thread interesting enough.
I'd like to share more of what I'm doing but without context, most of what I could share now wouldn't make much sense.
By the way, when I start work on my virtual reality IBM 704 emulator, I'm commandeering you to help out with the graphics.

[toc] | [prev] | [next] | [standalone]

Page 2 of 3 — ← Prev page 1 [2] 3  Next page →

Back to top | Article view | comp.sys.apple2.programmer

csiph-web