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

Groups > comp.lang.c > #77065 > unrolled thread

qsort() function misunderstanding

Back to article view | Back to comp.lang.c

Contents

  qsort() function misunderstanding Alla _ <modelling.data@gmail.com> - 2015-11-24 01:48 -0800
    Re: qsort() function misunderstanding Richard Heathfield <rjh@cpax.org.uk> - 2015-11-24 10:32 +0000
      Re: qsort() function misunderstanding Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-11-24 11:08 +0000
        Re: qsort() function misunderstanding Richard Heathfield <rjh@cpax.org.uk> - 2015-11-24 12:03 +0000
          Re: qsort() function misunderstanding Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-11-24 16:12 +0000
      Re: qsort() function misunderstanding Alla _ <modelling.data@gmail.com> - 2015-11-24 03:33 -0800
        Re: qsort() function misunderstanding Richard Heathfield <rjh@cpax.org.uk> - 2015-11-24 12:05 +0000
          Re: qsort() function misunderstanding glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2015-11-24 13:52 +0000
            Re: qsort() function misunderstanding Ken Brody <kenbrody@spamcop.net> - 2015-11-24 10:01 -0500
          Re: qsort() function misunderstanding Alla _ <modelling.data@gmail.com> - 2015-11-24 06:04 -0800
            Re: qsort() function misunderstanding Richard Heathfield <rjh@cpax.org.uk> - 2015-11-24 14:16 +0000
        Re: qsort() function misunderstanding James Kuyper <jameskuyper@verizon.net> - 2015-11-24 07:32 -0500
          Re: qsort() function misunderstanding Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-11-24 16:43 +0000
            Re: qsort() function misunderstanding glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2015-11-25 05:58 +0000
              Re: qsort() function misunderstanding Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-11-25 11:34 +0000
                Re: qsort() function misunderstanding Richard Heathfield <rjh@cpax.org.uk> - 2015-11-25 12:45 +0000
                  Re: qsort() function misunderstanding Alla _ <modelling.data@gmail.com> - 2015-11-26 02:18 -0800
                    Re: qsort() function misunderstanding Richard Heathfield <rjh@cpax.org.uk> - 2015-11-26 10:45 +0000
                Re: qsort() function misunderstanding glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2015-11-25 14:46 +0000
            Re: qsort() function misunderstanding Alla _ <modelling.data@gmail.com> - 2015-11-25 00:51 -0800
              Re: qsort() function misunderstanding James Kuyper <jameskuyper@verizon.net> - 2015-11-25 08:12 -0500
                Re: qsort() function misunderstanding Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-11-25 14:02 +0000
                  Re: qsort() function misunderstanding James Kuyper <jameskuyper@verizon.net> - 2015-11-25 11:37 -0500
                    Re: qsort() function misunderstanding Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-11-25 17:36 +0000
    Re: qsort() function misunderstanding Malcolm McLean <malcolm.mclean5@btinternet.com> - 2015-11-24 03:30 -0800
      Re: qsort() function misunderstanding Alla _ <modelling.data@gmail.com> - 2015-11-24 03:48 -0800
        Re: qsort() function misunderstanding Malcolm McLean <malcolm.mclean5@btinternet.com> - 2015-11-24 06:29 -0800
      pre/post increments (was Re: qsort() function misunderstanding) Ken Brody <kenbrody@spamcop.net> - 2015-11-24 09:55 -0500
    Re: qsort() function misunderstanding Alla _ <modelling.data@gmail.com> - 2015-11-24 06:06 -0800
    Re: qsort() function misunderstanding Barry Schwarz <schwarzb@dqel.com> - 2015-11-24 07:33 -0800
    Re: qsort() function misunderstanding Keith Thompson <kst-u@mib.org> - 2015-11-24 09:04 -0800
      Re: qsort() function misunderstanding Richard Heathfield <rjh@cpax.org.uk> - 2015-11-24 17:17 +0000
        Re: qsort() function misunderstanding Geoff <geoff@invalid.invalid> - 2015-11-24 10:03 -0800
          Re: qsort() function misunderstanding Eric Sosman <esosman@comcast-dot-net.invalid> - 2015-11-24 13:31 -0500
            Re: qsort() function misunderstanding Geoff <geoff@invalid.invalid> - 2015-11-24 12:34 -0800
              Re: qsort() function misunderstanding Eric Sosman <esosman@comcast-dot-net.invalid> - 2015-11-24 16:02 -0500
                Re: qsort() function misunderstanding supercat@casperkitty.com - 2015-11-24 15:18 -0800
                  Re: qsort() function misunderstanding Chad <cdalten@gmail.com> - 2015-11-24 16:15 -0800
                    Re: qsort() function misunderstanding Malcolm McLean <malcolm.mclean5@btinternet.com> - 2015-11-24 23:51 -0800
              Re: qsort() function misunderstanding Alla _ <modelling.data@gmail.com> - 2015-11-25 01:01 -0800
                Re: qsort() function misunderstanding glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2015-11-25 12:53 +0000
                  Re: qsort() function misunderstanding supercat@casperkitty.com - 2015-11-25 10:15 -0800
                    Re: qsort() function misunderstanding glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2015-11-25 23:14 +0000
                      Re: qsort() function misunderstanding supercat@casperkitty.com - 2015-11-25 16:33 -0800
                        Re: qsort() function misunderstanding glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2015-11-26 08:18 +0000
        Re: qsort() function misunderstanding Ian Collins <ian-news@hotmail.com> - 2015-11-25 10:41 +1300
          Re: qsort() function misunderstanding Richard Heathfield <rjh@cpax.org.uk> - 2015-11-24 22:08 +0000
      Re: qsort() function misunderstanding Alla _ <modelling.data@gmail.com> - 2015-11-25 00:53 -0800
    Re: qsort() function misunderstanding Alla _ <modelling.data@gmail.com> - 2015-11-25 09:07 -0800

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

#77159

Alla _ <modelling.data@gmail.com> wrote:
 
>> As an instructor, I'd prefer to confine myself to answering the direct
>> questions, explain what the particular example is trying to show and
>> Socratically get the student to explain his own understanding and only
>> warn against name collisions when the student is surprised by one.
 
> Thank you. This is the approach that I would apply if I were 
> to help someone to get through the material (and actually did apply to 
> my employees, in my now "previous" life). 
> This is why I am not simply asking "Why and please explain", but I am trying
> to show how I read and interpret the code; and when being corrected and/or
> directed, I get much deeper understanding.
> No wonder Socratic method is widely used and praised.  

Many who post here have been doing C programming 10, 20, or even 
for 30 years. Some C features are a little unusual, and some have
a strange history behind them. It takes some time to really
understand C.

Even more, there are many things that C lets you do, but that you
shouldn't actually do.  Things that make programs less readable
by others, or even yourself next week, month, or year. These take
time to learn, and also some amount of practice.  (Naming your
function qsort() is one, when it isn't the C library routine, or
at least one with the same calling sequence.)

There are other languages that are commonly used for teaching 
courses like this. Often interpreted languages like Matlab/Octave,
perl, or python are used. For a compiled language, Java is popular.

For those previously doing assembly programming, C is fairly easy
to learn. C pointers have many features similar to the way
addressing is done in assembler. (Note that Java specifically
doesn't have some of those.) 

For those previously using other compiled languages, traditionally
Fortran or Pascal, more recently Java, C isn't so hard to learn.

Previous use of a higher level language such as Mathematica,
Matlab, Octave, or R isn't quite as good, but probably not so bad.

-- glen

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

#77176

On Wednesday, November 25, 2015 at 6:53:46 AM UTC-6, glen herrmannsfeldt wrote:
> Even more, there are many things that C lets you do, but that you
> shouldn't actually do.  Things that make programs less readable
> by others, or even yourself next week, month, or year. These take
> time to learn, and also some amount of practice.  (Naming your
> function qsort() is one, when it isn't the C library routine, or
> at least one with the same calling sequence.)

A bigger complication is that the name "C" is given to two families of dialects
with vastly different philosophies.

As originally conceived, C was a language which would make it possible for a
simple compiler to yield efficient code by allowing programmers to specify
things at a somewhat lower level than was typically allowed in other
languages.  A simple Pascal compiler given:

    For I:=0 to 99 do
      Array1[I] := Array2[I] + Array3[I];

would likely need to generate machine code equivalent to:

    for (int i=0; i<=99; i++)
    {
      int *p;
      int tv;
      p = (int*)((char*)Array2 + i*2);
      tv = *p;
      p = (int*)((char*)Array3 + i*2);
      tv += *p;
      p = (int*)((char*)Array1 + i*2);
      *p = tv;
    }

While a better compiler would be able to use loop induction for the address
calculations, such a compiler would require more computational resources than
a simple one.  C made it possible to write the code as:

    int *p1 = array1, *p2 = array2, *p3 = array3;
    i=100;
    do
      *p1++ = *p2++ + *p3++;
    while(--i);

and yield code that would run quickly without the compiler having to do any
sort of advanced analysis.

Over the years, the kinds of operations that machines can perform efficiently
have changed.  Some C dialects, especially those used for embedded-systems
programming, are driven by a philosophy that it's best to define behavior in
terms of operations performed on memory, and say that programmers can use
any algorithmic optimization techniques that would be applicable given such
a view.

Other dialects, however, take the viewpoint that it's better to say that if
a program uses constructs in ways that the language committee viewed as
"dubious", compilers should have no obligation to generate code that behaves
in any particular fashion.  The philosophy is that such rules will give good
compilers more opportunities to optimize code, and the value of such
optimizations will exceed the value of any optimizations a programmer could
produce.

Personally, I wish proponents of both philosophies could reconcile their
differences and realize that for different kinds of processors and
programming the relative costs to the programmer or compiler for semantic
concessions, and the value of those concessions to the other party, will
vary enormously, and adding a means within the language to indicate what
semantics are actually required would allow code to achieve even better
performance than is available under the present rules, while allowing the
full range of semantic possibilities that can be achieved with the "simple
compiler" philosophy.

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

#77192

supercat@casperkitty.com wrote:

(snip of what I wrote about readability)

> A bigger complication is that the name "C" is given to two families 
> of dialects with vastly different philosophies.
 
> As originally conceived, C was a language which would make it possible for a
> simple compiler to yield efficient code by allowing programmers to specify
> things at a somewhat lower level than was typically allowed in other
> languages.  A simple Pascal compiler given:

(snip of example indexing three arrays)
 
> While a better compiler would be able to use loop induction for the address
> calculations, such a compiler would require more computational resources than
> a simple one.  C made it possible to write the code as:
 
>    int *p1 = array1, *p2 = array2, *p3 = array3;
>    i=100;
>    do
>      *p1++ = *p2++ + *p3++;
>    while(--i);
 
> and yield code that would run quickly without the compiler having to do any
> sort of advanced analysis.
 
> Over the years, the kinds of operations that machines can perform efficiently
> have changed.  Some C dialects, especially those used for embedded-systems
> programming, are driven by a philosophy that it's best to define behavior in
> terms of operations performed on memory, and say that programmers can use
> any algorithmic optimization techniques that would be applicable given such
> a view.

More moved than changed. The things you say were done by big computers
at that time, but not small ones.

At least IBM S/360 has indexing modes that can easily do that,
and Fortran H was known to figure that out in only 256K or core.
(That is little ferrite doughnuts with wires through them.)

But more recently people working with Herucles wanted to run gcc
on MVS on emulated IBM S/370 with only a 16M address space, and
probably 8M left for the user program. But gcc won't run, at least
won't compile itself, in 8M. The art of small compilers is lost.

It doesn't take all that big a compiler to figure out array
indexing, though. 

> Other dialects, however, take the viewpoint that it's better to say that if
> a program uses constructs in ways that the language committee viewed as
> "dubious", compilers should have no obligation to generate code that behaves
> in any particular fashion.  The philosophy is that such rules will give good
> compilers more opportunities to optimize code, and the value of such
> optimizations will exceed the value of any optimizations a programmer could
> produce.

OK, I have agreed with this for a while now.
 
> Personally, I wish proponents of both philosophies could reconcile their
> differences and realize that for different kinds of processors and
> programming the relative costs to the programmer or compiler for semantic
> concessions, and the value of those concessions to the other party, will
> vary enormously, and adding a means within the language to indicate what
> semantics are actually required would allow code to achieve even better
> performance than is available under the present rules, while allowing the
> full range of semantic possibilities that can be achieved with the "simple
> compiler" philosophy.

For smaller processors, everyone uses cross compilers, so the need
for users to write optimal, and less readable, code is gone.

-- glen

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

#77196

On Wednesday, November 25, 2015 at 5:14:56 PM UTC-6, glen herrmannsfeldt wrote:
> supercat wrote:
> > As originally conceived, C was a language which would make it possible for a
> > simple compiler to yield efficient code by allowing programmers to specify
> > things at a somewhat lower level than was typically allowed in other
> > languages.  A simple Pascal compiler given:

> It doesn't take all that big a compiler to figure out array
> indexing, though. 

Of course.  FORTRAN compilers were doing it in the 1960s, though the
language required that array subscripts take certain particular forms.

> > Other dialects, however, take the viewpoint that it's better to say that if
> > a program uses constructs in ways that the language committee viewed as
> > "dubious", compilers should have no obligation to generate code that behaves
> > in any particular fashion.  The philosophy is that such rules will give good
> > compilers more opportunities to optimize code, and the value of such
> > optimizations will exceed the value of any optimizations a programmer could
> > produce.
> 
> OK, I have agreed with this for a while now.

I'm puzzled by why it was seen as better to cobble semantic restrictions
onto a language which was designed to allow for human-based optimization
techniques, rather than derive a language from C which could then have much
better-designed rules.  Consider, for example, how much more efficient a
lot of code could have been if there were directives to switch between
strict aliasing mode and anything-goes mode, and within a strict-aliasing-
mode zone there weren't any special rules about "character types" but there
was instead an explicit "__alias_barrier()" directive, such that writes
performed one way would be considered unsequenced relative to reads performed
another in the absence of an __alias_barrier() between the read and write.
That would allow a lot more compiler-driven optimizations than are possible
under current rules, but also allow a lot of human-driven optimizations that
are only possible under -fno-strict-aliasing.

> > Personally, I wish proponents of both philosophies could reconcile their
> > differences and realize that for different kinds of processors and
> > programming the relative costs to the programmer or compiler for semantic
> > concessions, and the value of those concessions to the other party, will
> > vary enormously, and adding a means within the language to indicate what
> > semantics are actually required would allow code to achieve even better
> > performance than is available under the present rules, while allowing the
> > full range of semantic possibilities that can be achieved with the "simple
> > compiler" philosophy.
> 
> For smaller processors, everyone uses cross compilers, so the need
> for users to write optimal, and less readable, code is gone.

I'm not sure how you figure that.  Of course someone targeting a micro with
256 bytes of RAM is going to use a cross-compiler, but humans often know
things about code's requirements which cannot be expressed in C, and such
knowledge may allow them to make optimizations which a compiler, no matter
how sophisticated, couldn't possibly make.  Further, humans will in many
cases know a lot more than compilers can about which parts of the code need
to run quickly, and which parts don't.

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

#77205

supercat@casperkitty.com wrote:
>> supercat wrote:
>> > As originally conceived, C was a language which would make it possible for a
>> > simple compiler to yield efficient code by allowing programmers to specify
>> > things at a somewhat lower level than was typically allowed in other
>> > languages.  A simple Pascal compiler given:

(snip, then I wrote)

>> It doesn't take all that big a compiler to figure out array
>> indexing, though. 
 
> Of course.  FORTRAN compilers were doing it in the 1960s, though the
> language required that array subscripts take certain particular forms.

The standard did say that, but allowing more general expressions was
likely the most common extension. The IBM S/360 compilers, including
Fortran H which for many years was the favorite optimizing compiler,
even allows for REAL subscripts.

I would sometimes translate BASIC programs to Fortran, with all 
variables being REAL. It is nice to use them for subscripts.

-- glen

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

#77128

Richard Heathfield wrote:
>
> So why did K&R name it qsort in the first place? Well, I'm only
> guessing, but it's quite likely that the standard library function has
> its origins in K&R (1, rather than 2, although I lack a K&R1 so I can't
> check that this code is also in that edition of the book). And, if that
> is the case, K&R would be quite within their rights to reason "we
> thought of it first, so it stays".

Well I still have my well worn original K&R and qsort is not used.  They 
present two versions of the "printd" function, one iterative and one 
recursive.

-- 
Ian Collins

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

#77131

On 24/11/15 21:41, Ian Collins wrote:
> Richard Heathfield wrote:
>>
>> So why did K&R name it qsort in the first place? Well, I'm only
>> guessing, but it's quite likely that the standard library function has
>> its origins in K&R (1, rather than 2, although I lack a K&R1 so I can't
>> check that this code is also in that edition of the book). And, if that
>> is the case, K&R would be quite within their rights to reason "we
>> thought of it first, so it stays".
>
> Well I still have my well worn original K&R and qsort is not used.  They
> present two versions of the "printd" function, one iterative and one
> recursive.

So much for that guess, then. Thanks for the feedback.

-- 
Richard Heathfield
Email: rjh at cpax dot org dot uk
"Usenet is a strange place" - dmr 29 July 1999
Sig line 4 vacant - apply within

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

#77152

On Tuesday, November 24, 2015 at 9:04:34 PM UTC+4, Keith Thompson wrote:
> Alla _ <modelling.data@gmail.com> writes:
> > Please, help me to understand the qsort function, which I publish below
> > my walkthrough. I have a few questions but I will ask them gradually, in
> > a hope that some might become clear on the way. 
> >
> > Consider an array v[] = {8,1,10,7,5}
> >
> >     void qsort(int v[], int left, int right)
> 
> Don't call your function qsort.  That's the name of a standard library
> function with a different declaration.  That might be causing problems
> for you; when you try to call your own function, the compiler might
> generate a call to the predefined qsort() -- with incorrect parameters.
> 
> If you're implementing the Quicksort algorithm, just call it
> "quicksort".
> 
>
Thank you. Yes, I have already understood that, but it wasn't the matter 
of choice initially - I copied the function, and its name, from K$R. 

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

#77171

The quicksort example given by K&R has no fancy programming features,
and demonstrates basic concepts, which are essential for
learning and understanding of C principles. 

Now the code in question is clear to me, and thus this question
is closed. 

[toc] | [prev] | [standalone]

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

Back to top | Article view | comp.lang.c

csiph-web