[C] Pointers - what is the point?

[Nominal Animal]

Here is an example of how that definition,

A pointer differs from indexing an array in that a pointer also conveys information on the target: the qualified type of the target.

can be very useful in practice: sorting data using the C library qsort() function.

Let's say you have an array of points, say

Code: [Select]

typedef struct {
    int x;
    int y;
}  point;that you want to sort primarily by increasing y, and points with the same y coordinates in decreasing x.  All you need to do is write a comparison function,

Code: [Select]

static int compare_points(const void *ptr1, const void *ptr2)
{
    const point *const  p1 = ptr1;
    const point *const  p2 = ptr2;

    if (p1->y < p2->y)
        return -1; /* Ascending in y */
    else
    if (p1->y > p2->y)
        return +1; /* Ascending in y */
    else
    if (p1->x < p2->x)
        return +1; /* Descending in x */
    else
    if (p1->x > p2->x)
        return -1; /* Descending in x */
    else
        return 0;
}
and possibly a wrapper function around qsort() to make the calling easier:

Code: [Select]

void sort_points(point *const array, const size_t count)
{
    if (array && count > 1)
        qsort(array, count, sizeof array[0], compare_points);
}

Here, we use a pointer with unspecified/unknown/no target type to refer to the array.  The void type is special; you cannot dereference it (because the target type is unspecified/unknown), but you may cast it to any other (object) pointer type.

Internally, qsort() only knows the start address of the array, how large each element is in bytes (third parameter), and a function it can call to determine if two elements are in ascending order (< 0), equal (0), or in descending order (> 0).  It uses an internal facility similar to memmove() to swap array elements when needed. It does not need to know what those elements mean, only how they are ordered.  Nifty!

It is very difficult to do the same with array indexing, as evindenced by a lack of a similar routine in Fortran. (Even sortqq provided by Intel Fortran only works on one-dimensional arrays of base types, not on derived types.)

Of course, the main factor is the comparison function pointer, which allows the one qsort() function to be used with any type one can imagine, as long as the type has a fixed size, and a comparison function. (If your data type has variable length, for example because it has a flexible array member, you'll typically sort an array of pointers to elements of that type. Which is okay; the comparison function then just receives two pointers to pointers to data.)

Did anyone notice that Simon has long since disappeared from this thread?

I've really tried to help here; it's a pity if the effort is in vain. 

[westfw]

In practice, our processors (aside from most microcontrollers with built-in SRAM) tend to be bound by memory bandwidth, and cache effects; and memory organization and cache usage depends on the dataset used.

Ah, well.  In the last several years, I haven't much programmed anything without built-in SRAM and (at most) pitiful cache.  Although I'd bet that they don't actually have enough memory to work on problems where "subtle" cache effects make a noticable difference.  (ok, I did remind Adafruit that their new CM4 core ought to actually turn the cache ON, and that improved some benchmark performance quite a bit, running stuff like Dhrystones, Python, and Lisp. https://github.com/adafruit/ArduinoCore-samd/issues/37 )
I would bet that outside of some relatively rare data analysis programs, most of the "poor performance" that users actually SEE is more due to bad coding and poor choice of algorithms at a very coarse level, rather than more subtle "The algorithm I chose causes poor cache utilization.")
And the reason you should learn to use pointers is that most of the good algorithm implementations, whether you get some pre-written or write it yourself) will probably end up using pointers.

[brucehoult]

Code: [Select]

static int compare_points(const void *ptr1, const void *ptr2)
{
    const point *const  p1 = ptr1;
    const point *const  p2 = ptr2;

    if (ptr1->y < ptr2->y)
        return -1; /* Ascending in y */
    else
    if (ptr1->y > ptr2->y)
        return +1; /* Ascending in y */
    else
    if (ptr1->x < ptr2->x)
        return +1; /* Descending in x */
    else
    if (ptr1->x > ptr2->x)
        return -1; /* Descending in x */
    else
        return 0;
}


Omg :-)

Code: [Select]

static int compare_points(const void *ptr1, const void *ptr2)
{
    const point *const  p1 = ptr1;
    const point *const  p2 = ptr2;
    if (p1->y - p2->y) return p1->y - p2->y;
    return p1->x - p2->x;
}

You could make a tmp for p1->y - p2->y if you wanted, but the compiler will do that for you well enough.

e.g. on RISC-V 64:

Code: [Select]

0000000000000000 <compare_points>:
   0: 415c                lw a5,4(a0)
   2: 41d8                lw a4,4(a1)
   4: 00e78563          beq a5,a4,e <.L2>
   8: 40e7853b          subw a0,a5,a4
   c: 8082                ret

000000000000000e <.L2>:
   e: 4108                lw a0,0(a0)
  10: 419c                lw a5,0(a1)
  12: 9d1d                subw a0,a0,a5
  14: 8082                ret

Or, on ARMv7:

Code: [Select]

00000000 <compare_points>:
   0: 6843      ldr r3, [r0, #4]
   2: 684a      ldr r2, [r1, #4]
   4: 4293      cmp r3, r2
   6: bf11      iteee ne
   8: 1a98      subne r0, r3, r2
   a: 680b      ldreq r3, [r1, #0]
   c: 6800      ldreq r0, [r0, #0]
   e: 1ac0      subeq r0, r0, r3
  10: 4770      bx lr
  12: bf00      nop

Well, I'm not sure predicating so many instructions is better than a branch, but anyway...

[Nominal Animal]

Omg :-)

Omg indeed. Your version only works if the x and y members of the point structure are ints. Mine was written for ease of understanding, and does not make that hidden assumption.

It also has a bug:

Code: [Select]

static int compare_points(const void *ptr1, const void *ptr2)
{
    const point *const  p1 = ptr1;
    const point *const  p2 = ptr2;
    if (p1->y - p2->y) return p1->y - p2->y;
    return p1->x - p2->x;
}
It sorts ascending in both x and y. You'd need return p2->x - p1->x; to match the behaviour. (Then again, I had written ptr1/ptr2 in my example code instead of p1/p2, so who cares.)

I call yours premature optimization, because correct operation should be achieved first, and only then such optimizations implemented (and their implicit assumptions documented in comments to the code).

[brucehoult]

Omg :-)

Omg indeed. Your version only works if the x and y members of the point structure are ints. Mine was written for ease of understanding, and does not make that hidden assumption.

Int or long or short or char or bool, yes. You'd need to do something different for floating point types. Or further structured types, but you can handle those with the same technique recursively.

It also has a bug:

It sorts ascending in both x and y. You'd need return p2->x - p1->x; to match the behaviour. (Then again, I had written ptr1/ptr2 in my example code instead of p1/p2, so who cares.)

Ahh .. yes, I missed that subtlety that you returned +1 and -1 in the opposite order. I checked that the *tests* were the same for x and y.

Just goes to show how difficult yours is to understand :-)  (NEVER trust the comments!)

I call yours premature optimization, because correct operation should be achieved first, and only then such optimizations implemented (and their implicit assumptions documented in comments to the code).

I think it's easier to verify correctness of mine. You spotted and corrected my error very easily.

I like perl even better. In C syntax it would be:

Code: [Select]

return
  p1->y <=> p2->y ||
  p2->y <=> p1->y;

I notice that C++20 is adding the <=> operator.

I don't know whether they're planning to make it work nicely with || but I hope so, as user-defined overloads of operator|| are not as useful as the built-in one.

[bsfeechannel]

If you want to know why or how they do those things, well, that's why this thread is so long.

I confess that I was disconcerted by the OP's question. Having been initiated in the "art" of programming via assembly many many moons ago, pointers seemed so natural that I just got used to them. I never stopped to think about the reason for their existence.

But I did a little research and found that the real culprit for all this mess is a bloke called Harold W. (Bud) Lawson.

Pointers were invented because people at IBM wanted PL/I to be written (bootstrapped) in PL/I. That required the use of linked lists for the compiler. Lawson was called to implement that feature and, after some head scratching, came with the concept of the pointer variable. People liked the feature, extended it to other complex data and expanded to other uses already approached to the point of exhaustion in previous posts in this thread. Later people realized that the power of raw pointers could cause harm in the wrong hands. So other languages were created with sophisticated techniques where pointers were still used but hidden from the programmer, made optional, or disguised as second class citizens with other names.

If I could give a definite answer to the OP now, I would say that in a language as frugal as C, it is not viable to create complex data structures without pointers.

Then I would recommend reading chapters 5 and 6 of "C Programming Language, 2nd Edition" by K&R and, if he got really interested in being proficient, "Understanding and Using C Pointers" by Richard Reese.

And further (but short) readings:
Harold Lawson, "Reflexions on the History of Computing: Preserving Memories and Sharing Stories". 2012: 75
Paul. W. Abrahams, "Advances in Computers", Volume 9.  1969 : 78
Harold W. (Bud) Lawson: 2000 Computer Pioneer Award
Pointer (computer programming)
Development of C language

[mikerj]

c) Unlike other variables, all the pointers are of the same (~ small) size, regardless of the size or type of the data they point to.

That's a dangerous assumption, it certainly wasn't the case for the old HiTech PIC compiler which could have different size pointers for different memory types.

[GeorgeOfTheJungle]

c) Unlike other variables, all the pointers are of the same (~ small) size, regardless of the size or type of the data they point to.

That's a dangerous assumption, it certainly wasn't the case for the old HiTech PIC compiler which could have different size pointers for different memory types.

 

[ x ] Fixed.

a) A pointer is a variable that contains a memory address.
b) You can always use a pointer to refer to any piece of data, just need to know its address.
c) Unlike other variables, pointers are ~ small in size, regardless of the size or type of the data they point to.
d) Arguments in C are passed by copy. Often it's better to say "the data that's there" (a pointer) than to duplicate and pass a copy of the data to the callee:
d.1) Because it's faster (no need to duplicate big chunks of data).
d.2) Because it requires less memory (no need to duplicate big chunks of data).
d.3) Because when the callee receives a pointer, it can use it to r/w the source data.
d.4) Because when the callee receives a duplicate copy, it can't r/w the original data, only the copy.

Gentlemen, what else would you add?

[sokoloff]

It also has a bug:

It sorts ascending in both x and y. You'd need return p2->x - p1->x; to match the behaviour. (Then again, I had written ptr1/ptr2 in my example code instead of p1/p2, so who cares.)

Ahh .. yes, I missed that subtlety that you returned +1 and -1 in the opposite order. I checked that the *tests* were the same for x and y.

Just goes to show how difficult yours is to understand :-)  (NEVER trust the comments!)

@Nominal's was neither hard to understand, nor was the plain English spec hard to understand:

Let's say you have an array of points, say

Code: [Select]

typedef struct {
    int x;
    int y;
}  point;that you want to sort primarily by increasing y, and points with the same y coordinates in decreasing x.

I call yours premature optimization, because correct operation should be achieved first, and only then such optimizations implemented (and their implicit assumptions documented in comments to the code).

I think it's easier to verify correctness of mine. You spotted and corrected my error very easily.

I agree that code brevity is a positive quality in general. Yes, your error was easy to spot and correct.

[Nominal Animal]

Int or long or short or char or bool, yes.

Actually, it only works for types smaller than int; it will not work correctly for even all int values. (I only just realized/remembered this myself.)

Consider the following results, when a, b, and their differences are restricted to 32-bit two's complement integers:
    a = 536870911      b = -536870912     a-b = 1073741823     b-a = -1073741823
    a = 1073741823     b = -1073741824    a-b = 2147483647     b-a = -2147483647
!   a = 2147483647     b = -2147483648    a-b = -1             b-a = 1           
*   a = -2147483648    b = 2147483647     a-b = 1              b-a = -1         
    a = -1073741824    b = 1073741823     a-b = -2147483647    b-a = 2147483647 
    a = -536870912     b = 536870911      a-b = -1073741823    b-a = 1073741823 
Note the line I marked with !: a > b but a - b < 0.
Similarly on the line I marked with *: a < b but a - b > 0.
This occurs because the difference between two values between MIN and MAX, inclusive, is between (MIN - MAX) and (MAX - MIN), inclusive.

For twos complement signed int type, for uniform random coordinates, the result will be incorrect 25% of the time! (In other words, for uniform random a and b, 25% of the time a < b but a-b > 0, or a > b but a-b < 0. Test it by all means; no need to trust my word on this. Although I just did verify it numerically (because even I don't trust my word alone).)

So, your version does NOT work correctly for all int coordinates. It only works correctly for all inputs for types smaller than int; usually short and char.

You spotted and corrected my error very easily.

Only because I've learned to see such errors in real life code.  I definitely dislike the hidden gotchas in yours; we both missed the range issue!

(It is much harder to see errors in ones own code, though. I usually need a sleep in between, before I can trust my own code even a little bit. And even then I'm very suspicious... Okay, paranoid.)

I notice that C++20 is adding the <=> operator.

I don't think the <=> operator is any clearer than using the ternary operator:

Code: [Select]

static int compare_points(const void *ptr1, const void *ptr2)
{
    return ((const point *)ptr1)->y < ((const point *)ptr2)->y ? -1 :
           ((const point *)ptr1)->y > ((const point *)ptr2)->y ? +1 :
           ((const point *)ptr1)->x < ((const point *)ptr2)->x ? +1 :
           ((const point *)ptr1)->x > ((const point *)ptr2)->x ? -1 : 0;
}
GCC at least will generate the exact same code for this.  (In fact, if you enable optimizations, even my original code compiles to the same machine code, on GCC-5.4.0 for x86-64 and GCC-4.9.3 for ARM.)

Now, if you don't mind me, I shall go back to my dark corner and try not to worry how many others have been bitten by that bug (i.e., assuming that a-b<0 iff a<b or a-b>0 iff a>b, when the result is of the same type as a and b).

[GeorgeOfTheJungle]

I think, in this case, the difference imposed by the load size is so dramatic because the motion through data is sequential. C compiler doesn't predict the next read, but the CPU can detect the access pattern and pre-fetch the data. It wouldn't be this dramatic if the elements being accessed were spread randomly over the array.

Ten thousand elements of 100k each is 1 GB. Randomly peeking all over a gigabyte sounds like mission impossible for the caches to me. But if you've got ten thousand cache lines, and only peek at ten thousand different places, the same ten thousand all the time, it should work, shouldn't it?

[brucehoult]

Int or long or short or char or bool, yes.

Actually, it only works for types smaller than int; it will not work correctly for even all int values. (I only just realized/remembered this myself.)

Yes, this is true. The input range should be restricted to +/- 1 billion for 32 bit integers (more precisely -1073741824 to 1073741823)

It all depends on the problem specification.

You could use a saturating subtract, for example on ARM you can use QSUB.

[brucehoult]

Code: [Select]

static int compare_points(const void *ptr1, const void *ptr2)
{
    return ((const point *)ptr1)->y < ((const point *)ptr2)->y ? -1 :
           ((const point *)ptr1)->y > ((const point *)ptr2)->y ? +1 :
           ((const point *)ptr1)->x < ((const point *)ptr2)->x ? +1 :
           ((const point *)ptr1)->x > ((const point *)ptr2)->x ? -1 : 0;
}


Too much to write .. too much to read.

At least do:

Code: [Select]

#define CMP(a,b) (a)!=(b) ? ((a) < (b) ? -1 : 1)

static int compare_points(const void *ptr1, const void *ptr2)
{
   const point *p1 = ptr1, *p2 = ptr2;
   return
     CMP(p1->y, p2->y) :
     CMP(p2->x, p1->x) :
     0;
}


[GeorgeOfTheJungle]

Are you two playing got you!

[andyturk]

c) Unlike other variables, all the pointers are of the same (~ small) size, regardless of the size or type of the data they point to.

That's a dangerous assumption, it certainly wasn't the case for the old HiTech PIC compiler which could have different size pointers for different memory types.

Any architecture that has different sized pointers for different types is a bad architecture.

[IanB]

c) Unlike other variables, all the pointers are of the same (~ small) size, regardless of the size or type of the data they point to.

That's a dangerous assumption, it certainly wasn't the case for the old HiTech PIC compiler which could have different size pointers for different memory types.

Any architecture that has different sized pointers for different types is a bad architecture.

Is this referring to "near" pointers and "far" pointers?

[bsfeechannel]

a) A pointer is a variable that contains a memory address.
b) You can always use a pointer to refer to any piece of data, just need to know its address.
c) Unlike other variables, pointers are ~ small in size, regardless of the size or type of the data they point to.
d) Arguments in C are passed by copy. Often it's better to say "the data that's there" (a pointer) than to duplicate and pass a copy of the data to the callee:
d.1) Because it's faster (no need to duplicate big chunks of data).
d.2) Because it requires less memory (no need to duplicate big chunks of data).
d.3) Because when the callee receives a pointer, it can use it to r/w the source data.
d.4) Because when the callee receives a duplicate copy, it can't r/w the original data, only the copy.

Gentlemen, what else would you add?

e) Pointers allow the creation of complex data structures like linked lists, arrays, queues, trees which are essential for systems programming. Systems programming being the very reason why pointers before, and the C language later, were created in the first place.
f) Pointers are mandatory for dynamic memory allocation, when you need to create, destroy, enlarge or shrink objects after your program is already compiled and running. Why would you want that? Because sometimes the existence of these objects depend on an interaction with the user and cannot be predicted when you write a program, for instance.
g) If you're dealing with memory-mapped hardware, you need pointers to access explicitly addressed chunks of memory.

[mikerj]

c) Unlike other variables, all the pointers are of the same (~ small) size, regardless of the size or type of the data they point to.

That's a dangerous assumption, it certainly wasn't the case for the old HiTech PIC compiler which could have different size pointers for different memory types.

Any architecture that has different sized pointers for different types is a bad architecture.

Is this referring to "near" pointers and "far" pointers?

Yes, though I think the qualifiers weren't needed in later versions as the compiler checked all assignments and sized the pointer accordingly (either 8 or 16 bits).  It's been quite a while since I used PICC though.

[ajb]

Here is an example of how that definition,

A pointer differs from indexing an array in that a pointer also conveys information on the target: the qualified type of the target.

can be very useful in practice: sorting data using the C library qsort() function.

qsort is a good example of things that are easier with pointers and the utility of void types, but your example still doesn't support your bolded claim.  It's the implicit cast when you assign the pointer-to-void to a pointer-to-struct point that provides the information about the target type, a pointer-to-void by definition has no associated target type information.  And anyway, this isn't really a helpful answer to Simon given how much leeway C gives you to use arrays with pointer syntax and vice versa.  You could implement a qsort that passes a void pointer to the beginning of the array and a pair of indices to the compare function and then use array indexing to get to the required values in the comparison and it would work just as well.  It wouldn't be as pretty, but not because there's somehow inherently less information in a subscripted array than in a pointer.

[NorthGuy]

qsort is a good example of things that are easier with pointers and the utility of void types, but your example still doesn't support your bolded claim.

My qsort uses two functions:

Code: [Select]

int compare(int a, int b);
void swap(int a, int b);

This way it can sort practically anything and it doesn't use pointers.

[ajb]

My qsort uses two functions:

Code: [Select]

int compare(int a, int b);
void swap(int a, int b);

This way it can sort practically anything and it doesn't use pointers.

The only way both of those things can be true with the given prototypes is if you are sorting an array that is accessible to both functions.  That would mean that you can only ever sort that one array, unless those functions actually share a reference to an array, in which case now you *are* using a pointer even if you use array indexing to access it.  Your two functions could look exactly the same either way, but in the first case they access an offset from a fixed address while in the second they have to retrieve a stored address and then access an offset from that.  C just happens to hide that difference because the syntax for arrays and pointers is largely interchangeable.

[Nominal Animal]

Yes, this is true. The input range should be restricted to +/- 1 billion for 32 bit integers (more precisely -1073741824 to 1073741823)

In C, that would be INT_MIN/2 to INT_MAX/2.  It is a horrible footgun, in other words.  I'm pretty sure there are users (of possibly your code?) bitten by that unstated limitation.

It is also pretty nasty response to compare an implementation with such limits to one without, and then just brush away the issue with a nonchalant "It all depends on the problem specification."  I for sure hope I will never have to rely on software you have written.

Are you two playing got you!

No.  I just absolutely hate programmers with a lot of experience, who give out bad advice, leading new programmers to directions that yields just more crap software into the world.  It seems that that type of people have one universal factor: they will never ever admit an error.  They also seem to think "correctness" is something someone else can work out afterwards; their work is to get the "product" out there as soon as possible.

The reason software and device firmwares are so crap today, is a direct consequence of programmers having the same attitude as brucehoult here.  I just can't help but fight against that kind of crap.  It seems to be my hobby, I guess. 

[NorthGuy]

C just happens to hide that difference because the syntax for arrays and pointers is largely interchangeable.

Even though in C arrays and pointers may be used the same way, it doesn't mean that the arrays are pointers or pointers are arrays.

[westfw]

Any architecture that has different sized pointers for different types is a bad architecture.

Is this referring to "near" pointers and "far" pointers?

And "bank switched" (in multiple forms.)  Especially with Harvard architectures.
Many an 8-bit CPU will have different sized pointers for data and for code (64k RAM address space, 256k Flash program address space.)I think avr-gcc currently has 16, 24, and 32bit "pointers" in use :-(

[hamster_nz]

I like perl even better. In C syntax it would be:

Code: [Select]

return
  p1->y <=> p2->y ||
  p2->y <=> p1->y;

I notice that C++20 is adding the <=> operator.

I don't know whether they're planning to make it work nicely with || but I hope so, as user-defined overloads of operator|| are not as useful as the built-in one.

Ah, Perl the language with so many ways to express yourself that nobody can understand anybody else's code.

It is somehow fitting that C++ is now adding operators from Perl.... I wonder if it will it get $_ and =~ too?

(I guess we have Perl's fluidness to thank for Python's rigidness...)