[C] Pointers - what is the point?

[Simon]

I am completely confused, pointers are just another name for some variable, I have read a couple of explanations and I'm still not getting why I would want to use them  .

[ataradov]

This is a very broad question. In short, the pointer IS a variable that points to some other variable. Not only they are useful, it is practically impossible to program without them.

A pointer can be made to point to some other location at any other place at time. This is a very valuable property.

[Simon]

but if i am pointing at another variable why not just use the variable?

[ataradov]

Because sometimes you don't know what you want to point to at compile time.

[rolycat]

Wikipedia provides a very good explanation of what pointers are and why they are useful here:

https://en.wikipedia.org/wiki/Pointer_(computer_programming)

[ataradov]

Imagine you have two big arrays with font data: "uint8_t font_a[1024];" and "uint8_t font_b[1024];". The user has a way to select one or the other.

Now you can write all your code like this:

Code: [Select]

  if (selected_a)
    byte = font_a[index];
  else
    byte = font_b[index];

or you can create a pointer and use that:

Code: [Select]

uint8_t *font = selected_a ? font_a : font_b; // This assignment only happens once when the user has changed the selected font

byte = font[index]; // The rest of the code does not care what font is selected, it just uses the provided data.


[wraper]

but if i am pointing at another variable why not just use the variable?

Try to make a function which does something with array (not single variable within array) without using pointers.

[Simon]

but if i am pointing at another variable why not just use the variable?

Try to make a function which does something with array (not single variable within array) without using pointers.

I've only just specified my first array, it was an easy way of having multiple locations to store values in from each ADC channel and be able to move from channel to channel by incrementing the variable used as an index.

[wraper]

but if i am pointing at another variable why not just use the variable?

Try to make a function which does something with array (not single variable within array) without using pointers.

I've only just specified my first array, it was an easy way of having multiple locations to store values in from each ADC channel and be able to move from channel to channel by incrementing the variable used as an index.

I was meaning returning value. When you pass array to function as an argument, you actually pass pointer to array, not array itself. You can also use pointers to variables as arguments and then modify them from within the function.

[Simon]

oh I might need to do that, any reason I can't just use the "array[index]" as a variable ?

[ataradov]

Use for what?

[Simon]

Anything. So I have an array full of ADC readings, I'll need to process them at some point.

[IonizedGears]

Pointers are just variables to store the address in memory in which other variables are stored.

Note that it is a common misconception that arrays are pointers. It is true that an array often decays into a pointer to the first variable stored in said array but there are some key differences between arrays and pointers.

First, a pointer not of the const type (note the difference between a pointer to a const variable and a const pointer to a variable) can be changed to point to another address in memory by simply storing a new address in the pointer variable. An array cannot be set to point to another location in memory and will always decay as a pointer to the first variable in said array. You can still use the decayed pointer address in pointer arithmetic, however.

Second, sizeof on an array will depend on the amount of elements in an array while sizeof on a pointer will return the size of a pointer variable.

Now for the use cases of pointers.

First, they are incredibly useful in cases where you want the called function to change the value of a non-global variable while not having to return a value.

Ex)

int main(void) {
   int x = 3;
   Int val = 2;

   setVariable(&x, val);
}

void setVariable(int* x, int newVal) {
    *x = newVal;
}

This example is too simple to actually warrant the its use but imagine how it might be useful for more complicated math routines.

Second, it's also really useful for speed and memory concerns. C is ALWAYS pass by value i.e. the parameters of a called function are always different from those that were used in it's call. Changing the value of newVal in the called function in the example above does not change the value of val in the main function because newVal is a new variable that was initialized on the call of setVariable. Things tend to get slower and slower as more and larger variables are sent as parameters to functions. This is especially critical in heavy programs or limited resource environments like embedded systems.

Pointers make things easier by sending one measly pointer  which will be initialized as a pointer in the called function that points to the same address because the value of the pointer (the address in memory of what is being pointed to) is what is passed. Arrays are good for this. The other type that pointers are useful for are structs which are basically just wrappers/envelopes for mutliple variables. Look them up if you aren't familiar, they're useful.

IX

[IanB]

I've only just specified my first array, it was an easy way of having multiple locations to store values in from each ADC channel and be able to move from channel to channel by incrementing the variable used as an index.

Actually, in C arrays and pointers are two sides of the same coin.

For example, if you write a[ i ] to access the i'th element of a, this is exactly the same as writing *(a+i)

What this means is: "take a (which points to the first element of the array), advance it by i elements, and then get the thing pointed to at that location".

[sokoloff]

If you use array[index], that works fine to pass a value IN to the function, but not out.

Pointers are the essence of C. Once they click, then you understand C, IMO.

Note that an array variable IS (mostly) a pointer. array[index] is the same as *(array + index).

[ttt]

Some good answers here already but saying pointers are not useful vs variables is equivalent to saying that impedance is not useful because it's just resistance. There is a little more to it ;-) In some ways a variable is just a special case of a pointer (or reference). Keep digging and at some point it'll click.

[bsudbrink]

Pointers are the essence of C. Once they click, then you understand C, IMO.

I would add that once you get this, you are well on your way to understanding machine language and you can then dispense with all of the "high level language" nonsense and program CPUs at the bare metal like god intended 

[Simon]

Keep digging and at some point it'll click.

I hope so

[Simon]

Pointers are the essence of C. Once they click, then you understand C, IMO.

I would add that once you get this, you are well on your way to understanding machine language and you can then dispense with all of the "high level language" nonsense and program CPUs at the bare metal like god intended 

em, no, really, not gonna happen.

[sokoloff]

C is pretty much portable assembly language already. It’s rare that I have to drop from C to asm to accomplish what I want. (Usually only in ISRs or similar to push registers or something.)

[bsudbrink]

C is pretty much portable assembly language already. It’s rare that I have to drop from C to asm to accomplish what I want. (Usually only in ISRs or similar to push registers or something.)

Agreed for the most part.  Depends on the CPU and the C compiler/toolchain that is available and how big of a PITA it is to get run code to the target.

[bsudbrink]

Pointers are the essence of C. Once they click, then you understand C, IMO.

I would add that once you get this, you are well on your way to understanding machine language and you can then dispense with all of the "high level language" nonsense and program CPUs at the bare metal like god intended 

em, no, really, not gonna happen.

If you were properly motivated and I could have a couple of hours of your undivided attention, I bet I could teach you 6502 or Z80 assembler.  Once you get one, you can then get any.

[madires]

A pointer is typically a link to a blob of memory. The blob of memory could be something like a simple character string or a complex structure with lots of data. If you place data in an array and want to sort the data you have to move the data around by copying the complete data sets. If you use a linked list instead (each data set is linked to the next one by a pointer) you only have to change the pointers when sorting. which is much faster than copying lots of RAM. This is only one example of the benefit of pointers.

[Jeroen3]

but if i am pointing at another variable why not just use the variable?

You are doing that with pointers. Except instead of the immutable name “foo”, you use a incrementable and changeable pointer to foo.

You can change the pointer to foo at runtime, without changing a single line of code.

This is all highly abstract, and I could dive into technical details. But let’s keep it simple.

Say have to write a function to display some text on a screen. You write some software to put “hello world” on the screen.
This works, and you feel great. Then you get asked to put another text on the screen.
You recompile, and it shows the other text.
You get asked again, and again. Eventually you’re sick of it, and you use a pointer for the text to show on the screen.
Now everyone can put in an address of where some text is stored that should be on the screen. You are no longer bothered by people requesting texts.

[rolycat]

If you wanted to process the elements of your array in a separate function, then you could use code like this (complete program):

Code: [Select]

#include <stdio.h>

void print_array(int *array, int size) {                        // function to print the elements of an array             
    for (int i=0; i<size; ++i) {
        printf("Array element %i: %i\n", i, array[i]);
    }
}

int main() {
    int main_array[] = { 5, 4, 3, 2, 1 };                       // create an array and fill it with values
    int array_size = sizeof(main_array)/sizeof(main_array[0]);  // calculate the number of elements
    print_array(main_array, array_size);                        // call a function to print the values
}



The function print_array() has two arguments, a pointer to an array and the number of elements in the array.

You could also specify the arguments like this; it's the same thing:

Code: [Select]

void print_array(int array[], int size) {

Notice that there is only one copy of the array, the definition of which is local to main(), but by passing a pointer you can access the elements in another function, using a different name for the array.

You could just make main_array[] a global variable and avoid using the arguments, but that's not a good idea in larger programs.

[IonizedGears]

A few notes for especially important for Embedded systems and other resource-limited environments:

Dereferencing pointers to access the memory that's being pointed to takes more time than directly using the variable.

Pointer size is usually dependent on the architecture of the system. Very important when pointers are 16 bits wide on an 8 bit architecture.

Accessing struct members takes time and having to dereference a struct first takes even more time on top of that.


Knowing these things is important if you're pinching cycles which has given me this rule of thumb:

Limit dereferencing as much as you can and especially limit it in the case of loops. You will have to optimize memory usage vs. time and it isn't as clear cut as one would like it to be.

Do not limit dereferencing to the point of seriously hurting readability unless you heavily document what is being done and why it was done that way. This one is a general rule of thumb but still very important.

IX

[Nominal Animal]

A lot of computational physicists with Fortran background ask the same question.  (There is a lot of physics code in F95, because it is easier to write efficient math/simulation code in Fortran for current processors, than it is to do the same in C.  Vectorization (using SSE2/AVX/AVX2/AVX512 in particular) is much easier for the Fortran compiler than it is to C compiler.

The first time you'll find the true utility of pointers is when you need runtime polymorphism (some variant of subtyping) in your data.

Think of a stack, that can contain different types of items, of varying sizes.  You could use an array of unions that can hold each type of item you want. But you could also make it a linked list of different structures. For example:

Code: [Select]

#include <stdlib.h>
#include <string.h>

enum {
    STACK_STRING = 0,
    STACK_INT,
    STACK_FLOAT
};

typedef  union stack_all   stack_all;

typedef  struct stack_any  stack_any;
struct stack_any {
    stack_any *next;
    char       type;
};

typedef struct {
    stack_any *next;
    char       type;  /* = STACK_STRING */
    char       value[];
} stack_string;

typedef struct {
    stack_any *next;
    char       type;  /* = STACK_INT */
    int        value;
} stack_int;

typedef struct {
    stack_any *next;
    char       type;  /* = STACK_FLOAT */
    float      value;
} stack_float;

union stack_all {
    stack_any    any;
    stack_string s;
    stack_int    i;
    stack_float  f;
};

static stack_any *stack = NULL;

static inline stack_any *pop(void)
{
    stack_any *item;

    if (!stack)
        return NULL;

    item = stack;
    stack = item->next;
    item->next = NULL;

    return item;
}

static inline void push(stack_any *item)
{
    item->next = stack;
    stack = item;
}

static inline int push_string(const char *s)
{
    const size_t  slen = (s) ? strlen(s) : 0;
    stack_string *item;

    item = malloc(slen + 1 + sizeof (stack_string));
    if (!item)
        return -1;

    item->next = stack;
    item->type = STACK_STRING;
    if (slen > 0)
        memcpy(item->value, s, slen);
    item->value[slen] = '\0';

    stack = (stack_any *)item;

    return 0;
}

static inline int push_int(int i)
{
    stack_int *item;

    item = malloc(sizeof *item);
    if (!item)
        return -1;

    item->next = stack;
    item->type = STACK_INT;
    item->value = i;

    stack = (stack_any *)item;

    return 0;
}

static inline int push_float(float f)
{
    stack_float *item;

    item = malloc(sizeof *item);
    if (!item)
        return -1;

    item->next = stack;
    item->type = STACK_FLOAT;
    item->value = f;

    stack = (stack_any *)item;

    return 0;
}
Now, the reason the stack = (stack_any *)item; lines are valid, and casting between any stack_ types is allowed, is twofold: First, all those types need to have the same common initial members. For a stack implemented via a linked list, that means the pointer to the next (older) item in the stack, and the type of the current item in the stack.  Second, the compiler needs to have union stack_all visible. It is an union of all those structure types with the same common initial members.  (A lot of C programmers are not aware that the visibility of the union type suffices; it is not necessary to use the union type at all. Simply having the union type visible, and the types having the same common initial members, due to C99 6.5.2.3p5, means you can cast a structure of any of those types to another of those types, and examine the common initial members. Cast to the correct type (used when assigning the fields) is needed to access the type-specific fields.)

(A similar (but older, pre-C99) mechanism was used in POSIX.1 and its predecessors (SVRv4, 4.4BSD) to describe socket addresses (struct sockaddr).  C99 standardized a way to implement those in a backwards compatible manner via this union mechanism; however, because of such a large body of existing code relying the same operation without having such an union visible, most C compilers do not actually need to have that union visible.)

In microcontrollers, you can sometimes see similar queues or stacks used, when commands/requests and results are processed asynchronously, and more than one can be "in flight" at the same time.

[IonizedGears]

A lot of computational physicists with Fortran background ask the same question.  (There is a lot of physics code in F95, because it is easier to write efficient math/simulation code in Fortran for current processors, than it is to do the same in C.  Vectorization (using SSE2/AVX/AVX2/AVX512 in particular) is much easier for the Fortran compiler than it is to C compiler.

The first time you'll find the true utility of pointers is when you need runtime polymorphism (some variant of subtyping) in your data.

Think of a stack, that can contain different types of items, of varying sizes.  You could use an array of unions that can hold each type of item you want. But you could also make it a linked list of different structures. For example:

Code: [Select]

#include <stdlib.h>
#include <string.h>

enum {
    STACK_STRING = 0,
    STACK_INT,
    STACK_FLOAT
};

typedef  union stack_all   stack_all;

typedef  struct stack_any  stack_any;
struct stack_any {
    stack_any *next;
    char       type;
};

typedef struct {
    stack_any *next;
    char       type;  /* = STACK_STRING */
    char       value[];
} stack_string;

typedef struct {
    stack_any *next;
    char       type;  /* = STACK_INT */
    int        value;
} stack_int;

typedef struct {
    stack_any *next;
    char       type;  /* = STACK_FLOAT */
    float      value;
} stack_float;

union stack_all {
    stack_any    any;
    stack_string s;
    stack_int    i;
    stack_float  f;
};

static stack_any *stack = NULL;

static inline stack_any *pop(void)
{
    stack_any *item;

    if (!stack)
        return NULL;

    item = stack;
    stack = item->next;
    item->next = NULL;

    return item;
}

static inline void push(stack_any *item)
{
    item->next = stack;
    stack = item;
}

static inline int push_string(const char *s)
{
    const size_t  slen = (s) ? strlen(s) : 0;
    stack_string *item;

    item = malloc(slen + 1 + sizeof (stack_string));
    if (!item)
        return -1;

    item->next = stack;
    item->type = STACK_STRING;
    if (slen > 0)
        memcpy(item->value, s, slen);
    item->value[slen] = '\0';

    stack = (stack_any *)item;

    return 0;
}

static inline int push_int(int i)
{
    stack_int *item;

    item = malloc(sizeof *item);
    if (!item)
        return -1;

    item->next = stack;
    item->type = STACK_INT;
    item->value = i;

    stack = (stack_any *)item;

    return 0;
}

static inline int push_float(float f)
{
    stack_float *item;

    item = malloc(sizeof *item);
    if (!item)
        return -1;

    item->next = stack;
    item->type = STACK_FLOAT;
    item->value = f;

    stack = (stack_any *)item;

    return 0;
}
Now, the reason the stack = (stack_any *)item; lines are valid, and casting between any stack_ types is allowed, is twofold: First, all those types need to have the same common initial members. For a stack implemented via a linked list, that means the pointer to the next (older) item in the stack, and the type of the current item in the stack.  Second, the compiler needs to have union stack_all visible. It is an union of all those structure types with the same common initial members.  (A lot of C programmers are not aware that the visibility of the union type suffices; it is not necessary to use the union type at all. Simply having the union type visible, and the types having the same common initial members, due to C99 6.5.2.3p5, means you can cast a structure of any of those types to another of those types, and examine the common initial members. Cast to the correct type (used when assigning the fields) is needed to access the type-specific fields.)

(A similar (but older, pre-C99) mechanism was used in POSIX.1 and its predecessors (SVRv4, 4.4BSD) to describe socket addresses (struct sockaddr).  C99 standardized a way to implement those in a backwards compatible manner via this union mechanism; however, because of such a large body of existing code relying the same operation without having such an union visible, most C compilers do not actually need to have that union visible.)

In microcontrollers, you can sometimes see similar queues or stacks used, when commands/requests and results are processed asynchronously, and more than one can be "in flight" at the same time.

Pretty neat but 8 bit microcontrollers, at least those from Microchip, don't have malloc due to the issues it could cause in a limited environment. There are ways of implementing the same design patterns without malloc and if you really wanted you could easily implement a pseudo-malloc if you really wanted.

I believe most 16 and 32 bitters support malloc, though.

IX

[emece67]

.

[nctnico]

Meanwhile I'd like to suggest to Simon to buy a good book about programming C for microcontrollers. Judging by his other questions he is using mostly 8 bit controllers and on those pointers are better to be avoided anyway because they are slow. On a typical 8 bit microcontroller it is faster to use global variables (*). In general it is good to avoid pointers because they offer a myriad of ways to shoot yourself in your feet and problems are hard to debug. Range checking when accessing arrays is highly recommended.

IMHO the way array variables are automatically pointers in C isn't very consequent. After all a 'regular' variable could be seen as an array with only one element. This tends to confuse people because you see things like this:

Code: [Select]

int a;
int b[2];
memset(&a, 0, sizeof(a));
memset(b, 0, sizeof(b));

* On 16 and 32 bit platforms pointers are much faster because (usually) the memory layout and/or instruction set are better suited to use pointers.

[Wilksey]

Simply because why pass by value, create multiple blocks of memory to store the same data when you can pass by reference (pointer) to address the variable by memory location.

If I had a 2048 byte array or even 1024 byte array of data and I didn't use pointers i'd soon run out of memory to copy the data into.

A pointer points to the first element of that array or data structure and you can do the rest, make sure you abide by boundary.

Function pointers are useful also.

[brucehoult]

I've only just specified my first array, it was an easy way of having multiple locations to store values in from each ADC channel and be able to move from channel to channel by incrementing the variable used as an index.

Actually, in C arrays and pointers are two sides of the same coin.

For example, if you write a[ i ] to access the i'th element of a, this is exactly the same as writing *(a+i)

What many people don't realise is it's also the same as  i[a]

BCPL wrote it as  a!i (or  i!a) which is closer to the truth but looks less like math.

[sleemanj]

* Dynamic memory allocation (reallocation)
* Linked lists, you can't do linked lists without a pointer (and dynamic memory allocation), circular buffers, FIFO stacks.... all need pointers to be efficient
* Pass by reference (although C++ & references are simpler here if you can do that)
* In C, strings, you really can't do strings without pointers, char * , or as mentioned char [] is virtually just a pointer
* Function pointers and jump tables
* Machine registers, those are all effectively pointers in C (eg in AVR land, volatile uint8_t *)
* In the AVR world, PROGMEM and EEMEM

[hamster_nz]

Pointers have many levels of understanding - and you can't get them all in one go, you need to build up level by level.

The first conceptual model for pointers is it is a nice "handle" to where some data is held. You can either use the data directly, or indirectly through the pointer (using the '*' operator). You can get the handle of any given bit of data with the '&' operator.

As C functions only return one value, and C functions are "pass by value" pointers are used to give functions the ability to update data that is outside of the function's scope.

Code: [Select]


int swap( int *a, int *b)
{
  int temp;
  temp = *a; // Save the value of 'a' in 'temp'
  *a = *b;     // Move 'b' into 'a'
  *b = temp; // update 'b' with the saved value in 'temp'.
}
...
   if(b < a)   // Put the lowest value in 'a'
     swap(&a, &b);
...

The next level is that the pointers are a handle to the first of a series of data - and you can do math on the pointer to access other items in the series.

Code: [Select]


int string_length(char *string) {
  int len = 0;
  while(*string != '\0') {
    len = len + 1;       // Could use the ++ operator too...
    string = string+1; // Move on to the next item
  }
  return len;
}
...
   char string[] = "My string";

   printf("String '%s' is %i characters long, excluding the terminating NULL\n",
            string, string_length(string));
...

The next level after that is that pointers can be the location of a structure holding multiple items, accessed using the "->" operator:

Code: [Select]

   struct Person {
      char name[100];
      unsigned age;
   };
   struct Person alice = {"Alice", 22};
   struct Person bob = {"Bob", 19};
....
   struct Person *person_ptr;
   person_ptr = &bob;  // Get the pointer to 'bob' in memory
...
   printf("%s is %i years old\n", person_ptr->name, person_ptr->age); // Print the person's details
...

The "glowing brain" level is when you use dynamic memory allocation to grab more memory at run time, allowing you to create and destroy structures like linked lists and trees, and process work with data where you don't know the size at compile time. The thing that does your head in about this is that the data structures used contain pointers that point to the data structure being defined:

Code: [Select]

struct ListItem {
   struct ListItem *next;  /* Address of next item in list */
   int value1;
   int value2;
}

Code to use this sort of thing becomes a familiar pattern:

Code: [Select]

struct ListItem *first_item;

int add_item_to_list(int value1, int value2) {
   struct ListItem *new_item;

   /* Allocate some memory */
   new_item = malloc(sizeof(struct ListItem));

   /* Detect if we were out of memory */
   if(new_item == NULL) 
     return 0;  /* Failed - out of memory */

   /* Clear out the entire block of memory */
   memset(new_item,0,sizeof(struct ListItem));

   /* Set the values in the item */
   new_item->value1 = value1;
   new_item->value2 = value2;
 
   /* Add to the linked list at the front */
   new_item->next = first_item;
   first_item = new_item;

   /* Successfully added item to the front of the list */
   return 1;
}

And somewhere off to the side is function pointers - these are pointer that hold the location of code and are used as callback functions, signal handlers and interrupt handling.

PS. Code most likely has many errors - was just typed in on the fly.

[brucehoult]

Pretty neat but 8 bit microcontrollers, at least those from Microchip, don't have malloc due to the issues it could cause in a limited environment. There are ways of implementing the same design patterns without malloc and if you really wanted you could easily implement a pseudo-malloc if you really wanted.

I believe most 16 and 32 bitters support malloc, though.

Saying that a processor supports (or doesn't support) malloc is pretty much nonsense. Malloc is just a function that manages a (hopefully large) array of bytes, chopping it up as requested, and keeping track of which parts are used and which parts are not.

What a processor might or might not support is "indirect addressing". If you've got indirect addressing (or the ability to run code from RAM, and modify it at runtime) then the programmer (or their library writer) can implement malloc.

If you don't have indirect addressing then you can't even have *arrays*.

Many early computers didn't have any form of indirect addressing. When the programmer wanted to work with an array or pointer they would modify the appropriate load or store instruction just before executing it. Pretty soon index registers were invented. This let you calculate a value into the index register and then have it added to the absolute address contained in the load or store instruction. Often the index register would be smaller than the full address size, making it not useful as a general pointer. This happened as recently as the 6502.

Fortunately, as they don't have program memory you can modify on the fly, even the smallest PIC10s support indirect addressing via the FSR and IND registers. Malloc wouldn't be very useful on them, since you only have 32 bytes of memory, but you could write it if you wanted.

[sleemanj]

Pretty neat but 8 bit microcontrollers, at least those from Microchip,

malloc etc works just fine with AVR libc

https://www.microchip.com/webdoc/AVRLibcReferenceManual/group__avr__stdlib_1ga4996af830ebe744d9678e5251dfd3ebd.html

Of course, dynamic allocation is to be avoided in low memory environments, but if you need to, go for it, carefully.

[ajb]

* Machine registers, those are all effectively pointers in C (eg in AVR land, volatile uint8_t *)

I'm not sure this really counts, since it's going to be a fixed numeric value *cast* to a pointer that is then dereferenced (something like "(*(volatile uint8_t *)0x25)" if you fully expand it), and accessing it should be exactly the same as accessing any other variable located at a fixed address, even though it uses pointer syntax behind the scenes.

In ARM and other processors you often have pointers to structs for peripherals, hence you wind up using lots of stuff like SPI2->DATA, which tends to make for nicer syntax than the AVR style, and means you can do things like store a pointer to a peripheral instance which can be handy for decoupling.  If you have a situation where you need to implement the same protocol on more than one interface, it's usually convenient to package up any state data or buffers into a struct for each protocol instance, and then pass a pointer to that struct into the functions that implement the protocol logic.  That struct can even contain a pointer to a USART or whatever to indicate which peripheral is associated with which protocol instance.  Or if those instances need to do slightly different things, you can store pointers to functions in the instance data.  This is really useful for supplying platform-dependent drivers to higher level libraries, especially libraries that may be used on different physical layers in the same application, for instance fatfs which may target both on-board flash and an SD card.

[Mechatrommer]

just as someone said... if you dont know whats its for, you dont need it.

[sleemanj]

* Machine registers, those are all effectively pointers in C (eg in AVR land, volatile uint8_t *)

I'm not sure this really counts,

Plenty of situations in which you need to pass registers around at runtime, pointers (and the address operator) are the way in which to do that...

Code: [Select]

  function doTheThingOnThisRegister(volatile uint8_t *TheRegister) { *TheRegister = ..... }
  doTheThingOnThisRegister(&DDRB);


[Leiothrix]

just as someone said... if you dont know whats its for, you dont need it.

That's a bit of a bad outlook on life though.

If you don't know what it's for -- find out.  Then you can make an informed decision as to whether you need it or not.

[T3sl4co1l]

Of interest:



Watch the series, hopefully it will prove illuminating.

Tim

[ajb]

Plenty of situations in which you need to pass registers around at runtime, pointers (and the address operator) are the way in which to do that...

My point was the fact that the IO register is declared as a pointer doesn't mean that it gets used as one (especially because the dereference is part of the #define in the AVR style!).  In your example you even show that you need to convert it back to a pointer via & before passing it as a reference, so syntactically that's no different than if the IO register were defined as volatile uint8_t foo instead of *((volatile uint8_t *)foo).  The pointer syntax is only used in the device header files to put the symbol at a particular address without having to do ugly things with the linker.

Sidenote: Using pointer syntax for things that aren't normally used as pointers can become significant in other situations, such as when a peripheral register needs to be cast to a different type in an assignment--some peripherals exhibit different behavior depending on the width of the access to a register, so you might need to force an 8-bit access on a 32-bit register to get the desired behavior.  Reading is no big deal, something like foo = (volatile uint8_t)(SPI2->DR) works fine, but (volatile uint8_t)(SPI2->DR) = foo does NOT work, because you can't cast an lvalue--unless you convert it to a pointer first, which leads to the silly-looking but quite useful *((volatile uint8_t *)(&SPI2->DR)) = foo, which works fine.

Unrelated to the above, but another situation pointers are useful is if you need to return more than one item from a function--for instance, you can have the function directly return the requested value in the usual way, but you can also pass it a pointer to a location where it might store an error code, or the number of bytes written, or something like that.

[NorthGuy]

Start from the beginning.

Every variable has 4 major attributes:

- address - where the variable is located at the memory
- size - how much memory it occupies
- content - what the memory stores
- type - how to interpret the content

Pointer is simply a variable that holds the address of another variable. You use pointers any time you need to remember where a particular variable is. If you know the address of a variable, you can get to the variable, fetch its content or replace the content with something new. The same as if you meet a girl, you need to write down her address so that you can find her in the future.

Even if you don't use pointers, variables still have addresses. You need the address to get to any variable. But if the address is known at the compile time, the compiler can find the variable without your help. If not, you must use pointers.

[Mechatrommer]

just as someone said... if you dont know whats its for, you dont need it.

That's a bit of a bad outlook on life though.

If you don't know what it's for -- find out.  Then you can make an informed decision as to whether you need it or not.

you like to keep busy. Congratulation i'm not that man enough... read on..

[BravoV]

Not an expert, example cases where pointer excels compared to array (assuming no constraint within small memory like MCU and the "link" it self cause no significant overhead to the overall memory usage).

Say "at run time", you need the bulk data stored which in the array (in OP's case) needs to be constantly resized either grow or shrink dynamically, linked list will beat array as the size is fixed.

Also at the sorted bulk data, manipulating like inserting/deleting data "in the middle" of the sorted bulk data, linked list will excels compared to array.

[T3sl4co1l]

* Machine registers, those are all effectively pointers in C (eg in AVR land, volatile uint8_t *)

I'm not sure this really counts, since it's going to be a fixed numeric value *cast* to a pointer that is then dereferenced (something like "(*(volatile uint8_t *)0x25)" if you fully expand it), and accessing it should be exactly the same as accessing any other variable located at a fixed address, even though it uses pointer syntax behind the scenes.

AVR GCC normally compiles such accesses (especially more than one access at a time) into literal pointer arithmetic (i.e., setting the X or Y registers to the base address, adding the offset and reading/writing SRAM there).  I forget if these are reduced to immediate addresses with heavy optimization.

It's a useful paradigm to understand a compiler as a translation tool, so that you can specify, in high level terms, what you want the output machine code to do.  Rather than writing it yourself, you tell it what to write.  In that sense, pointers are just another part of the tool at your disposal, and the point is to use them anywhere it makes your job easier, faster and more powerful.   Admittedly, this perspective isn't so useful to a beginner not familiar with instruction sets...

Tim

[JPortici]

Meanwhile I'd like to suggest to Simon to buy a good book about programming C for microcontrollers. Judging by his other questions he is using mostly 8 bit controllers and on those pointers are better to be avoided anyway because they are slow. On a typical 8 bit microcontroller it is faster to use global variables (*). In general it is good to avoid pointers because they offer a myriad of ways to shoot yourself in your feet and problems are hard to debug. Range checking when accessing arrays is highly recommended.

IMHO the way array variables are automatically pointers in C isn't very consequent. After all a 'regular' variable could be seen as an array with only one element. This tends to confuse people because you see things like this:

Code: [Select]

int a;
int b[2];
memset(&a, 0, sizeof(a));
memset(b, 0, sizeof(b));

* On 16 and 32 bit platforms pointers are much faster because (usually) the memory layout and/or instruction set are better suited to use pointers.

agree with every single word.
Other that i sometimes use pointers to variable or structures in my PIC18 firmwares, i can spare some cycles and it's better to have to keep/update/debug one function instead of every copy of the same. Also fewer lines to read and check

[newbrain]

Meanwhile I'd like to suggest to Simon to buy a good book about programming C

I left out the "for microcontrollers" part, but I think this is good advice to Simon.

Simon, I see you asking many disparate questions, from syntax to semantics to IDE use.
The forum is of course a great resource, and many are eager to help with high-quality answers, but some more structure and progression is IMHO needed.

IIRC you mentioned to have the K&R in another thread, I really think you should take the time to go through it, follow the examples and work out the exercises - even the banal ones - and make sure a topic is understood for good before proceeding.

The book is not MCU oriented, and will not help with IDE settings, but many things will get step by step clearer, and this will help having a better mental picture of the language, applicable to both embedded and hosted applications.

  I hope I don't sound too patronizing...

[Mechatrommer]

The book is not MCU oriented, and will not help with IDE settings..

there is the love to programming, there is the love to completing a project in due time. we know he's been in a serious professional business industry and been programing for a while but keep asking fundamental things recently, and complained how his sources are not for embedded programming he loved to. so i suspect he's into "learn if needed" basis. i have "C++ Nuts & Bolts: For Experienced Programmers" book. dont get scared by the term "Experienced" its not, the right term should be replaced with "Complete Guide", its the one i will grab if i forgot or got confused by the C/C++ syntaxes. its less than an inch thick, i think if i'm zero, i can complete the self-learnt course using the book alone in a month or so (and i have 5 childrens )...

only drawbacks is it lacks of practical and complete working examples let alone embedded, just examples needed to demonstrate the usage of each C/C++ keywords and syntaxes, from the basic pointers and arrays to the witchery of polymorphism, so we need some imagination there. the 2nd drawback is its heavily C++ oriented programming style with alot of "cout <<" that i hate, so you need to familiarize with C coding style and then differentiate which is C++ specific that cant be used in C style. if i'm like Simon i think i wont have trouble since i already have some basic experience programming C. fwiw.

[Nominal Animal]

don't have malloc

The code was just a quick example I whipped up to explain the logic. You don't need malloc() for pointers to be useful in the pattern shown.

For microcontrollers, you'd use a static array of structures per type; typically 2 or 3 elements. When not used, you'd set their type to e.g. UNUSED or other reserved type enum, so that instead of a malloc call, you just loop over the array to find an unused one.

If you consider a microcontroller that responds asynchronously to multiple requests -- say, reading digital temperature sensors, setting the duty cycle of some PWM outputs, and such --, a queue of such commands or requests makes a lot of sense. If you need different requests to have different priorities, you can implement that too with a binary heap, quite effectively. In that case, the elements just need two pointers (left and right), instead of one (next).  (The code is obviously different. In any case, a binary heap is surprisingly efficient to manage.  On the other hand, if you only have something like a dozen or so possible nodes, it won't matter much how you deal with them, as it is just a few cycles per node access.)

For Simon and others learning how to do C in an embedded or freestanding environment, it means that unless and until you need to implement such algorithms to really get the hardware working the way you want, you probably won't see the utility of pointers.

[jpanhalt]

but if i am pointing at another variable why not just use the variable?

I think you answered your own question.  Pointers keep track of where or what that variable is.

Sorry to come late to the party, but I do disagree with those who say pointers are almost useless for mid-range chips (specifically Microchip PIC devices).  Indirect addressing was introduced early on by Microchip with its FSR registers.  Current chips can access the entire range of program and RAM memory with them.  They are quite useful.   Microchip has seen that and introduced multiple FSRn's in its newest chips as well as instructions such as 'moviw' and 'movwi' with auto increment and decrement to facilitate use.  Moreover, if you run out of FSR's, you can create your own.   That can be used, for example in FIFO ring buffers where you may not want to tie up the FSR's.

[Mechatrommer]

...as well as instructions such as 'moviw' and 'movwi' with auto increment and decrement to facilitate use....

people who understand this, used it, get acquainted with it... will swear by the pointer and why they are necessary in some critical performance application. btw, pointer will enable the program logic to control many variables from only one variable (pointer) well isnt that confusing?

[brucehoult]

If you consider a microcontroller that responds asynchronously to multiple requests -- say, reading digital temperature sensors, setting the duty cycle of some PWM outputs, and such --, a queue of such commands or requests makes a lot of sense. If you need different requests to have different priorities, you can implement that too with a binary heap, quite effectively.

Point of order!

A heap doesn't require any embedded pointers at all. You only need an array to store the maximum number of elements, the address of the array, and a count of how many elements are currently present (or a pointer to the first free element).

If a node is at offset N from the start of the heap (zero based), then its children are at offsets 2N+1 and 2N+2, if those nodes are not >= the limit pointer.
 

[bd139]

This whole thread reminds me why we should teach computing from the bottom up.

[Simon]

The book is not MCU oriented, and will not help with IDE settings..

there is the love to programming, there is the love to completing a project in due time. we know he's been in a serious professional business industry and been programing for a while but keep asking fundamental things recently, and complained how his sources are not for embedded programming he loved to. so i suspect he's into "learn if needed" basis. i have "C++ Nuts & Bolts: For Experienced Programmers" book. dont get scared by the term "Experienced" its not, the right term should be replaced with "Complete Guide", its the one i will grab if i forgot or got confused by the C/C++ syntaxes. its less than an inch thick, i think if i'm zero, i can complete the self-learnt course using the book alone in a month or so (and i have 5 childrens )...

only drawbacks is it lacks of practical and complete working examples let alone embedded, just examples needed to demonstrate the usage of each C/C++ keywords and syntaxes, from the basic pointers and arrays to the witchery of polymorphism, so we need some imagination there. the 2nd drawback is its heavily C++ oriented programming style with alot of "cout <<" that i hate, so you need to familiarize with C coding style and then differentiate which is C++ specific that cant be used in C style. if i'm like Simon i think i wont have trouble since i already have some basic experience programming C. fwiw.

Serious? I'm never sure how serious my employer is but yes I tend to learn as I go. My experience so far is limited and has made minimal use of the cleverer things.

[Mechatrommer]

serious i mean military, if i recall correctly you involved in some military vehicle project, no?

[NivagSwerdna]

I am completely confused, pointers are just another name for some variable, I have read a couple of explanations and I'm still not getting why I would want to use them  .

I love these questions because everyone has an answer. 

You don't need to know about pointers you can let the magic happen.

int fred[10];

fred[0] = 123;   // Works

i = fred[0]; /// works

i = fred[j]; // works

That all works fine.  You can ignore any videos, ignore any books etc.

However one day you might be interested in passing a reference to one of the elements to a function rather than the whole array.... you could pass the whole array and an index or could pass a reference to the single element... e.g. &fred[2]

& gives you the address of the location of element fred[2].  Given an address you can get to the value by using *

So

int* interesting = &fred[2];
*interesting = 567;

is equivalent to fred[2] = 567

Now in C there are a few syntactic sugars in operation so... fred is actually short-hand for &fred[0] i.e. the address of the 0-th element of fred
Also at compile time the type of elements of an array is known so fred+3 takes into account the size of the fred elements.  i.e fred+3 and &fred[3] are equivalent.

Likewise pointer arithmetic works so...
int* interesting = &fred[2];
interesting++;
*interesting = 321;

sets the value of &fred[3]

Once you know the & and * operators you can apply them to anything.  So for example you can have a pointer to a function and then call it
(*fn)(args), which is useful for looking up functions at runtime... e.g. FSM implementations.

The underlying processor will be either using a pointer (the address) to a memory location or an internal register to hold a value. Machine operations for indirection using a register as an address are common place and efficient.

They are also dogs.... and a particularly cool, inbound aircraft warning system, one is described here... https://en.wikipedia.org/wiki/Judy_(dog)

[Nominal Animal]

A heap doesn't require any embedded pointers at all.

No, I meant with a queue or a binary heap where the nodes are of different types and sizes, similar to the stack structures in my example.  I take it you didn't read my previous post in this thread... 

To reword: Consider a microcontroller with various peripherals, connected to a computer, where some of the peripherals take a while to read/set. Rather than block for every single command/request, you can implement a priority queue using a binary heap, with each request or command being a separate node. These nodes can be statically allocated, typically 2 or 3 per type, depending on the peripherals configured.  One part receives incoming commands/requests, parses them, and adds to the queue. Another part of the code responds when commands/requests are fulfilled. Third part of the code decides which command/request to act upon next.

Such an approach is especially nice on microcontrollers with native USB interfaces, because the transfers are inherently asynchronous.  A lot of the serial port daemons I've seen don't really handle asynchronous communication, but expect to be able to write-then-read, one command/request at a time.  Which is fine if the round-trip time is short or you don't have many sensors.  When you do have many sensors or sensors that take a long time to respond, more complicated code is warranted; and that is the point where one finds algorithms and approaches where pointers are very useful, methinks.

[Maxlor]

When I learned programming a long time ago, I had a hard time wrapping my head around it. I thought I had gotten it, but got floundered later when having to do ** instead of just *, or wondered it is & instead of *, shouldn't the compiler know this is a pointer, yaddayadda, in other words, my understanding was not robust at all.

I then focused on x86 assembly. When I learned about how indirect adressing (with optional indexing) works, it finally clicked 100% for me, because at that point, all the abstractions and complexity had all been peeled away and I got to see what the CPU is actually doing. Maybe this learning approach works for you too.

(Note that the simple microcontrollers that one'd commonly program in ASM, say an 8-bit PIC, do not have the advanced addressing modes of the x86 architecture, so looking at those is not a substitute here.)

[NivagSwerdna]

(Note that the simple microcontrollers that one'd commonly program in ASM, say an 8-bit PIC, do not have the advanced addressing modes...)

Indirect Addressing: INDF and FSR

[newbrain]

(Note that the simple microcontrollers that one'd commonly program in ASM, say an 8-bit PIC, do not have the advanced addressing modes of the x86 architecture, so looking at those is not a substitute here.)

Ah, the good old days when 8 bitters had about as many addressing modes as address bus pins...

[NivagSwerdna]

(Note that the simple microcontrollers that one'd commonly program in ASM, say an 8-bit PIC, do not have the advanced addressing modes of the x86 architecture, so looking at those is not a substitute here.)

Ah, the good old days when 8 bitters had about as many addressing modes as address bus pins...

Indeed. http://www.obelisk.me.uk/6502/addressing.html

[bd139]

Zero page on the 6502 was awesome. Made me think of the CPU as a RISC processor with 256 memory mapped registers

[westfw]

    if you dont know whats its for, you dont need it.

Unfortunately, for C you end up needing to know something about pointers in order to be able to do anything with "strings."

    especially important for Embedded systems and other resource-limited environments:
    Dereferencing pointers to access the memory that's being pointed to takes more time than directly using the variable.

Um, that's not necessarily true.ARM in particular is really horrible at "directly accessing variables."On AVR, an "LD r1,Z+offset" instruction is the same speed and half the size of "LDS r1,variable"Even on an 8bit PIC, there significant advantages and no speed penalty for accessing memory via the INDFn registers (no Bank select register when trying to use data structures that span banks, as a biggie.)
(this supposes that the pointer itself is already set up, which a compiler should be doing efficiently.  But consider a sequence like:

Code: [Select]

// AVR code to initialize UART
UBRR0L = somediv;   // 3 words for each setting...
UBRR0H = highdiv;
UCSR0C = someval;
UCSR0B = someval2;
UCSR0A = someval3;
// 15 words total.
vs

Code: [Select]

uartp = &UART0;    // two words to initialize pointer
uartp->UBRRL = somediv;   // two words for each setting
uartp->UBRRH = highdiv;
uartp->UCSRC = someval;
uartp->UCSRB = someval2;
uartp->UCSRA = someval3;
// 12 words total.


[GeorgeOfTheJungle]

Page zero indexed indirect FTW.

[GeorgeOfTheJungle]

I am completely confused, pointers are just another name for some variable, I have read a couple of explanations and I'm still not getting why I would want to use them  .

*p is "another name" for a, but the pointer p is the address where a is stored, this:

Code: [Select]

#include <stdio.h>
int b= 66;
int main (void) {
    int a= 27;
    int* p= &a;
    printf(" a: %d\n",a);
    printf("*p: %d\n",*p);
    printf(" p: %p\n",p);
    printf("&a: %p\n",&a);
    p= &b;
    printf(" b: %d\n",b);
    printf("*p: %d\n",*p);
    printf(" p: %p\n",p);
    printf("&b: %p\n",&b);
    return 0;
}
Gives:

Code: [Select]


 a: 27
*p: 27
 p: 0x7fff5fbff8b4
&a: 0x7fff5fbff8b4
 b: 66
*p: 66
 p: 0x100001068
&b: 0x100001068


[brucehoult]

Zero page on the 6502 was awesome. Made me think of the CPU as a RISC processor with 256 memory mapped registers

Except the code density and speed sucked! Something as simple as adding or subtracting two 16-bit variables stored in ZP took 13 bytes of code (clc; lda $a; adc $b; sta $c; lda $a1+1; adc $b+1; sta $c+1) and 20 clock cycles. Compare that to 2-4 bytes of code and one clock cycle for variables stored in registers on anything from AVR to ARM to RISC-V to 68040/80486 or newer.

It's no wonder bytecode interpreters or threaded-code were so popular on those machines. Speed was even worse, but at least you could fit a decent amount of code into memory. Even Woz's ancient SWEET16 got that down to 3 bytes of code, and it integrated nicely with native code too.

[GeorgeOfTheJungle]

If at least X and Y had been 16 bits ...

[rhb]

I had to work on a FORTRAN internal read code which allowed user defined data formats.  Once the first record had been read, the format was fixed.  But doing it in FORTRAN required repeating all the conditional tests.

I wrote a C routine which constructed a table of pointers to the appropriate FORTRAN internal read function, the input buffer and the output buffer the first time it was called.  After the first call the function pointers were no longer null.  So instead of populating the table it simply executed the functions in the table until it hit a null function pointer.  This gave a 6x improvement in performance.  When you're processing ASCII files with several million records on an early 1990's computer, that's a very big improvement. Instead of waiting an hour, you had the result in 10 minutes.  A good excuse for a coffee break.

Get a copy of:

Expert C Programming: Deep C Secrets
Peter Van Der Linden
Prentice-Hall 1994

I think the best way to understand pointers is to study assembly, preferably on something like the 6502 or 6809.  Though the STM32 series and the MSP430 series will also do and are more readily available.

C is just barely above assembly language.  It's fundamentally a portable assembly language.  It separates the mental constructs from the implementation details. More recent versions of the standard have muddied that, but if you read K&R and the "Unix Programming Environment" by Kernighan and Pike it will become much more clear.  If yuo read the two volume set of Bell Labs Journal articles about Unix a lot of things will become obvious.

It's the same thing with esoterica such as caches and why certain memory access patterns have really bad performance that a minor change can speed up tremendously

The history of computing is actually very important to any work being done today.  I have seen the same mistakes repeated every 8-10 years.  it's really sad as a little understanding of history would prevent them.

Read "The Story of Mel", a Usenet posting by Ed Nather about Mel Kaye.  "Pointers?  We don't need no stinking pointers!  We know how the machine works."

[brucehoult]

If at least X and Y had been 16 bits ...

Like .. what was that chip the same people did at another company earlier? The company that sued them to stop making the socket-compatible 6501. Yeah. It had 16 bit X register and SP. And *two* accumulators. But no Y. Very similar instruction set.

Probably a superior chip if it hadn't been EIGHT times more expensive.

[GeorgeOfTheJungle]

The motorola 6800 you mean?

[brucehoult]

I think the best way to understand pointers is to study assembly, preferably on something like the 6502 or 6809.  Though the STM32 series and the MSP430 series will also do and are more readily available.

Agreed on the assembly language, but those chips are just needlessly like wrestling with an octopus these days .. as are the 8080/Z80/8088. The 6809 and 8088 less so than the others (and in fact they are remarkably similar to each other, once you get past Intel's ridiculous assembly language).

These days I'd recommend using one of the following, on linux -- native if available but otherwise a cross compiler/assembler, decent emulator (e.g. qemu), and binfmt_misc works great to let you write real, useful, programs that work as if they were native on your computer (just slower).

- AVR pretty great except for only having two registers that can dereference pointers, and of course more work to use 16 or 32 bit values.

- ARMv2 - ARMv4. Great except overly complex addressing modes, shifted 2nd operand, load/store multiple (but very useful!)

- Thumb1. Really great for beginners. Simplified ARM. Only small downside is about 4x more instruction encoding formats than ARM, and a few specialised instructions don't exist.

- PDP11. Really great for beginners. Problem is lack of modern tool support and old-style stack-based ABI.

- MIPSr2. Pretty great, except for the delay slots and slightly cumbersome conditional branches. Very clean instruction encoding. Much used in university programming courses through the 90s and 00s.

- RISC-V.  Really great. The advantages of MIPS without the problems. University courses and texts are switching to it. The only downside: encoding of literals & offsets inside instructions is not human-decodable.

[brucehoult]

The motorola 6800 you mean?

EXACTLY

[GeorgeOfTheJungle]

I still do 6502 assembly sometimes, just for fun. Not having any 16 bit register is a real PITA (*). The 65c02 was a disappointing upgrade, many mostly unneded additional opcodes that nobody wanted/asked for, and still no 16 bits nowhere.

(*) Strictly speaking it had one: the PC 

[GeorgeOfTheJungle]

Assembly? No no no, poor Simon, jeez, C is all he needs to learn about pointers!

http://publications.gbdirect.co.uk/c_book/chapter5/pointers.html

[brucehoult]

Assembly? No no no, poor Simon, jeez, C is all you need to learn about pointers!

http://publications.gbdirect.co.uk/c_book/chapter5/pointers.html

Call me thick, but 40 years ago when I was learning this stuff, I didn't understand it until I understood the machine code.

I always suspect that people who don't do it that way don't actually understand as well as they think they do!

[hamster_nz]

Assembly? No no no, poor Simon, jeez, C is all you need to learn about pointers!

http://publications.gbdirect.co.uk/c_book/chapter5/pointers.html

Call me thick, but 40 years ago when I was learning this stuff, I didn't understand it until I understood the machine code.

I always suspect that people who don't do it that way don't actually understand as well as they think they do!

Agreed - when you understand the lower layers under C machine code then lots of the of seeming arbitrary exceptions and gotchas and become understandable and obvious. Otherwises it is a bit like learning maths by rote.

<rant>
One thing I never got a good hand on was the number of days in a month.

That stupid rhyme where you can swap months around at random, why 28, 30, 31 days?

If I lost a few fingers to count on I would be stuffed.

At least leap days make sense, as it is a crude form of Digital Differential Analyzer...
</rant>

[westfw]

Quote

These days I'd recommend using one of the following

TI's MSP430 is about as close to a PDP-11 as you can get for less than $1, and I think it still qualifies as a "current" architecture.It looks like assembly would be pretty nice on it (and potentially useful, since they sell some Very Tiny (512B) chips), and you can get those LaunchPad boards for under $15, some with FRAM (which is also "interesting technology")
http://www.oocities.org/westfw/trip-report-msp430.txt (quite old; predates cheap, predates launchpad, predates FRAM)

[brucehoult]

Quote

These days I'd recommend using one of the following

TI's MSP430 is about as close to a PDP-11 as you can get for less than $1, and I think it still qualifies as a "current" architecture.It looks like assembly would be pretty nice on it (and potentially useful, since they sell some Very Tiny (512B) chips), and you can get those LaunchPad boards for under $15, some with FRAM (which is also "interesting technology")
http://www.oocities.org/westfw/trip-report-msp430.txt (quite old; predates cheap, predates launchpad, predates FRAM)

It's definitely decent. Twice the registers of the PDP11 (which was always a bit short), in exchange for  half the addressing modes. It's a bit annoying that the destination can only use half the addressing modes that you *do* have -- and in particular that you can't do register indirect for the destination but have to waste a word on a zero offset.

Super-H (especially SH4) is similarly PDP11-ish, but getting to 16 registers by keeping a full set of addressing modes, but using them only for (one operand of) MOV. All the arithmetic is register-to-register, RISC style. I think I find this preferable.

Both MSP430 and SH4 would be vastly better for learning assembly language than any 8 bit CPU (except AVR), anything ever designed by Intel, Thumb2 or Aarch64, SPARC, PowerPC. Many of those are fine CPUs and no problem at all if you've got a compiler to do the work. But manuals thousands of pages long are not good for assembly langauge programming, especially by beginners.

I shouldn't omit m68000 (forget the 020/040 additions). Also PDP11-ish, but this time getting 16 registers by specialising them into use as pointers or for arithmetic.

With that bit of sometime annoying asymmetry I think I'd put 68k on the same level as MSP430, and SH4 just above both. All are preferable to PDP11 or Thumb1 which are just a little bit too tight on usable registers (but at least Thumb gets PC, SP, LR out of the working registers).

There's quite a lot of good choices really :-)

[brucehoult]

<rant>
One thing I never got a good hand on was the number of days in a month.

That stupid rhyme where you can swap months around at random, why 28, 30, 31 days?
</rant>

Never had too much trouble with that. In the first seven months of the year odd number months have 31 days. In the last five months it's the even months that have 31. All the rest have 30, except February.

days = m&1 ^ m>7 ? 31 : m!=2 ? 30 : 28+leapShit(yr)

[JPortici]

Agreed - when you understand the lower layers under C machine code then lots of the of seeming arbitrary exceptions and gotchas and become understandable and obvious. Otherwises it is a bit like learning maths by rote.

Expecially obvious. Many of the things i see being repeated ad nauseam about pointers, safety and how to write better or more efficient C in general became obvious once i learned one instruction set that supported indirect addressing, which in my case was dsPIC. DLX came into my life some years later, i was doing dsPICs in high scool..

[GeorgeOfTheJungle]

That's all well and it's a Good Thing (TM): the more you know your CPU the better.

That said, IMO you don't need to know assembly, an ISA, and its addressing modes, to fully understand and be able to use pointers (and handles) in C, properly.

I beg to differ. Cordially 

[newbrain]

<rant>
One thing I never got a good hand on was the number of days in a month.

That stupid rhyme where you can swap months around at random, why 28, 30, 31 days?
</rant>

Never had too much trouble with that. In the first seven months of the year odd number months have 31 days. In the last five months it's the even months that have 31. All the rest have 30, except February.

days = m&1 ^ m>7 ? 31 : m!=2 ? 30 : 28+leapShit(yr)

Ah, those pesky Roman emperors, not only they wanted months with their name, they had to be 31 days long!

[tggzzz]

One thing I never got a good hand on was the number of days in a month.

That's easy and predictable - unlike seconds in a minute, hours in a day, months in a year, days in a year.

[GeorgeOfTheJungle]

One thing I never got a good hand on was the number of days in a month.

Hey, google "months knuckles trick" in youtube! 

[bd139]

I have no idea. I just look at the calendar on the computer. 

[GeorgeOfTheJungle]

I ~ always have to stop and think to get left and right, right.

[NorthGuy]

Call me thick, but 40 years ago when I was learning this stuff, I didn't understand it until I understood the machine code.

I always suspect that people who don't do it that way don't actually understand as well as they think they do!

That's why they want languages without pointers.

[T3sl4co1l]

If at least X and Y had been 16 bits ...

...You'd have had a Z80. Oh, and throw in some more registers while you're at it, oh and let's fix that ratty instruction set.... ahhhh.

Still bloody slow, but not a pain to write for.

Tim

[rhb]

The classic example for pointers is:

char* strcpy( char* to, char* from){

   char* ptr;

   ptr = to;

   while( *from ){
      *ptr++ = *from++;
   }
    *ptr = 0;
   return to;
}

Most CPU instruction sets have increment and decrement instructions.

It's important to note that C was created to simplify porting Unix from the PDP-7 to the PDP-11. Unix was not written entirely in assembly even on the PDP-7, but most other operating systems were.  Under the mistaken belief it was necessary to get good performance.

[rrinker]

I still do 6502 assembly sometimes, just for fun. Not having any 16 bit register is a real PITA (*). The 65c02 was a disappointing upgrade, many mostly unneded additional opcodes that nobody wanted/asked for, and still no 16 bits nowhere.

(*) Strictly speaking it had one: the PC 

 My first machine for direct machine language programming was the CDP1802 - 16 registers of 16 bits, with NONE of those pre-assigned to any function (you could make any of them the PC, on the fly, and you could make any the pointer index, on the fly - with the best instruction mnemonic ever in a micro - SEX). Next one I learned was Z80, when my TRS-80 owning best friend bought the Editor/Assembler and had no idea what to do with it. I later had a project in school on Apple IIs, where part of my program was just way too slow in BASIC so I figured I'd redo the slow part in assembly. It was trying to get all that to work that just made me hate the architecture of the 6502, and to this day I fail to see why so many love it.

[sokoloff]

I think a somewhat more canonical form is:

char *strcpy( char* to, const char* from){
    for (char *ptr = to; *ptr++ = *from++; )
        ;

    return to;
}

[Tomorokoshi]

I shouldn't omit m68000 (forget the 020/040 additions). Also PDP11-ish, but this time getting 16 registers by specialising them into use as pointers or for arithmetic.

With that bit of sometime annoying asymmetry I think I'd put 68k on the same level as MSP430, and SH4 just above both. All are preferable to PDP11 or Thumb1 which are just a little bit too tight on usable registers (but at least Thumb gets PC, SP, LR out of the working registers).

There's quite a lot of good choices really :-)

My first assembly language was with the 8085, but compared to that the 68K was a joy to program. Clean and crisp.

It's interesting to compare the architecture of 68K to IBM 360:

https://en.wikipedia.org/wiki/IBM_System/360_architecture#Features
https://en.wikipedia.org/wiki/Motorola_68000#Architecture

[rhb]

I think a somewhat more canonical form is:

char *strcpy( char* to, const char* from){
    for (char *ptr = to; *ptr++ = *from++; )
        ;

    return to;
}

possibly, but I was trying to explain this to a novice. 

However, I do not consider it good style as you have to pay close attention to the punctuation or it will be wrong. It also leads you into an area where the standard states the behavior is undefined or implementation dependent.   The compiler will generate almost exactly the same code for both versions.  And with optimization turned on they would probably both produce the same assembly.

[sokoloff]

Agreed on the last. There is nothing implementation dependent or language undefined in my sample above. (At least none that I'm aware of, of course.)

[GeorgeOfTheJungle]

That strcpy code makes one cringe, null terminated strings being what they are, not the best idea ever.

[Siwastaja]

I think pointers start making sense by a little bit of experience - no need to try to force yourself to learn more this concept "by the book". The "a-HA" moment will come, don't worry.

I think, for me it happened hand-in-hand with learning of code reuse and structure - and functions. You'll see it when you first time need a 1000 lines of copy-pasta switch-case where you do the same trivial thing with 1000 different data. There has to be a better way... This teaches you to think about data structures as well, instead of focusing on the instruction flow too much. Another super important aspect in programming!

Before that, the pointers came by when using any library functions, but that's a special case which doesn't teach you too much, and at least I ended up just copy-pasting example code without full understanding. You'll see the point when you first time need the pointers in your own code, completely, and any alternative would be a huge pain in the ass.

[GeorgeOfTheJungle]

And what a great footgun they are You wouldn't get to see the most splendid segmentation faults without them.

[rhb]

Read  section 6.5.16.1 on the simple assignment operator, "=".  The strcpy(3c) case is probably okay, but a minor variation of that style can result in trouble. The root cause is the type promotion rules.

I can't imagine why anyone would object to null terminated strings.  It's far less painful than enumerated strings which is the only other choice.  I've had to mix C & FORTRAN code, a *lot* of it.  Passing strings between the two languages is a huge headache.  And long strings in FORTRAN can become far too "interesting" for my tastes.

[westfw]

I shouldn't omit m68000

I left it out on purpose.  It's a fine architecture for learning assembly language, and there are even some reasonably priced "microcontroller-style" ("Coldfire") variants, but it's pretty much drifted off out of mainstream use and into a niche that isn't much used by beginners and hobbyists.  (Much as a Coldfire-based Arduino might be "neat", I can't quite justify putting in the effort to make it happen.)
How is x86 for assembly language programming these days?  Obviously all the bells and whistles of a full-blown GUI OS desktop system are a very deep end to jump in at, but that doesn't mean you can't "learn assembly language" using a subset in a CLI or debugging environment.  I'd just be a little worried that it TOO "CISC-y" (though it need not be taught that way, I guess.)(Alas, this is the crux of the matter.  Platforms for TEACHING assembly language, vs teaching an assembly language that is actually useful...)

[andyturk]

One thing I never got a good hand on was the number of days in a month.

That's easy and predictable - unlike seconds in a minute, hours in a day, months in a year, days in a year.

https://youtu.be/-5wpm-gesOY

[Nominal Animal]

That's easy and predictable - unlike seconds in a minute, hours in a day, months in a year, days in a year.

Who cares? That is exactly why C has mktime(), localtime(), and gmtime(). Just stuff the datetimes into struct tm structures (at noon if you are only interested in dates, and is_dst=-1 if you don't know if daylight savings time applies), and mktime() will not only normalize the fields but also give you the corresponding time_t: the number of seconds since Jan 1 1970 00:00:00 UTC (not counting any leap seconds; those are accounted for in the broken down struct tm, not in time_t AKA Unix time).

If you are doing any sort of date calculation yourself in hosted C, not using the above functions, you're doing it wrong. (Hosted meaning you have standard C library available.)

[rhb]

Actually, awk does a good job for dates in the example in the awk book by AWK.

[hamster_nz]

That's easy and predictable - unlike seconds in a minute, hours in a day, months in a year, days in a year.

Who cares? That is exactly why C has mktime(), localtime(), and gmtime(). Just stuff the datetimes into struct tm structures (at noon if you are only interested in dates, and is_dst=-1 if you don't know if daylight savings time applies), and mktime() will not only normalize the fields but also give you the corresponding time_t: the number of seconds since Jan 1 1970 00:00:00 UTC.

If you are doing any sort of date calculation yourself in hosted C, not using the above functions, you're doing it wrong. (Hosted meaning you have standard C library available.)

"the number of seconds since Jan 1 1970 00:00:00 UTC" - Are you sure of that?

There has been 27 leap seconds since 1970, and time_t doesn't know about any of them.

Code: [Select]

$ date  +"%s  %S"
1532045870  50
$ echo $((1532045870%60))
50

Unless take the time to understand what you are dealing with, you won't understand the assumptions that have been made on your behalf.

[Bassman59]

The classic example for pointers is

I was going to post exactly this example for Simon, but you beat me to it.

but I'll annotate it for him.

Code: [Select]

char* strcpy( char* to, char* from){

   char* ptr;
   ptr = to;
This is subtle. We create the temporary pointer ptr so we don't destroy our to variable.

Code: [Select]

   while( *from ){
The loop continues as long as *from is true. What does that mean?

Remember this is a string copy function. Strings in C are just an array of chars. The convention is that strings are always null-terminated; that is, the last byte in the string is always '\0', which has a numeric value of zero. And also in C, any integer which is zero is considered false, any non-zero value is true.

Now, remember, *from dereferences the pointer from. That is, it returns the value in the location pointed to by from. If the original string whose address is sent to the function (in from) is ABCD\0 then each time through the loop *from will be 'A', then 'B', then 'C', then 'D', then 0 (not the ASCII '0', the value 0). The first four are non-zero, therefore true, and the code in the loop executes and then we go back to the test. When *from is 0, that's false, so the loop exits.

Code: [Select]

      *ptr++ = *from++;
   }
This is classic C. Here's what happens. Note the precedence: the pointer dereference * is done before the post-increment ++.

*from is dereferenced, and you get a character (in example above, 'A', then 'B', etc). That character is put in the memory location pointed to by ptr.

Then the two pointers ptr and from are incremented.

Then the while() case is evaluated again, now using the new thing returned when from is dereferenced.

Code: [Select]

    *ptr = 0;
This null-terminates your destination string. Remember that the code in the loop incremented ptr after the character copy, so it is "looking" at the next place you can put a character. In this case, that next character is the terminator \0 and the string copy is done.

Code: [Select]

   return to;
}
The function has a char* return type, so it returns our result, a pointer to a character. In this case, we know that it is a pointer to the first character in a string. to is passed to us as a pointer to the destination string (assume that space for it exists, this function cannot know if that is true).

Remember at the start when we did the

Code: [Select]

ptr = to? We saved the destination pointer. If we had, instead, incremented to each time through the loop, when we returned it we would have sent the address of the last character in the string -- the null terminator. That's not useful, which is why we copied that address to a temporary and use the temporary for the copy and pointer increment.

This is really the most basic use of pointers, and if you grok this, you'll understand how pointers are generally useful.

[rhb]

@Bassman59

Thank you very much for your thorough explication (sorry, English lit major :-).    I just tossed a pebble in the general direction of the answer. You provided a very detailed explanation.  And it really is beautiful.

I get tremendous pleasure out of hearing people who understand in great depth how things work.  Even when I've known it for 20-30 years.  It gives me hope for the human race.

BTW  Do you play bass?  If so acoustic, electric or both?  I play guitar and harmonica.  Almost exclusively an Eastman 810 CE made in 2005.  Best decision I ever made. It completely transformed my playing  after some 30 years.

[Nominal Animal]

"the number of seconds since Jan 1 1970 00:00:00 UTC" - Are you sure of that?

Okay, I edited it for clarity. It is "the number of seconds since Jan 1 1970 00:00:00 UTC, if leap seconds were not applied" (as explained in the Unix time Wikipedia article).

Leap seconds are taken into calculation when you use one of the three functions I mentioned, in the broken down struct tm members, not in Unix time_t. (In particular, the tm_sec field can be 60, not just 0 to 59.)

[bsfeechannel]

I am completely confused, pointers are just another name for some variable, I have read a couple of explanations and I'm still not getting why I would want to use them

In C you don't understand things. You get used to them.

but if i am pointing at another variable why not just use the variable?

I've seen some books teach that a pointer is just an alias to a variable. Your question shows how this can be misleading.

[tggzzz]

That's easy and predictable - unlike seconds in a minute, hours in a day, months in a year, days in a year.

Who cares? That is exactly why C has mktime(), localtime(), and gmtime(). Just stuff the datetimes into struct tm structures (at noon if you are only interested in dates, and is_dst=-1 if you don't know if daylight savings time applies), and mktime() will not only normalize the fields but also give you the corresponding time_t: the number of seconds since Jan 1 1970 00:00:00 UTC (not counting any leap seconds; those are accounted for in the broken down struct tm, not in time_t AKA Unix time).

If you are doing any sort of date calculation yourself in hosted C, not using the above functions, you're doing it wrong. (Hosted meaning you have standard C library available.)

The latter is precisely the point I have had to make to implementors on more than one occasion

But your first paragraph is wrong; unix time doesn't take account of leap seconds.

Leap seconds cause serious problems in distributed systems that rely on timestamps, e.g. telecom, or high reliability distributed file systems.

As a result there have been serious attempts to redefine time in such a was as to avoid leap seconds.

[bd139]

Yep. See https://tools.ietf.org/html/rfc7164#section-3

[tggzzz]

I've seen some books teach that a pointer is just an alias to a variable. Your question shows how this can be misleading.

I rather like the Algol68 nomenclature....

An int is just that, no more, e.g. 59 is an int and unsurprisingly it cannot change during execution. In other words it is what most languages term a constant.

A ref int refers to an int, and can change during execution. In other words it is what most languages term a variable of type int.

A ref ref int refers to a ref int. In C this would be a pointer to an int.

[bd139]

Algol 68, much as many things it did, gets it right there. Also considers immutability explicitly up front.

I think the killer for pointers in C is sometimes the syntax used. Dereferencing a pointer to an int and incrementing it for example. Yuck. But it works.

[tggzzz]

Algol 68, much as many things it did, gets it right there. Also considers immutability explicitly up front.

The standard lament is that Algol68 is an improvement on most of its successors.

But it was too complex for the machines and compiler technology of the day (and random i/o devices lacking lowercase and punctuation characters). Hence the many subsets of the language.

[Psi]

Don't think of pointers as something that solves a problem, then try to figure out what that problem is and how it needs pointers. This kind of thinking is wrong and will confuse you.

Unless you're making your own OS you can get by without using any pointers.
It's just that pointers make some things sooo much easier and faster and more elegant than doing the same thing without using pointers.

Its like when you first learned about Arrays and how to use them, it opens up a word of possibilities.
Sure, you could write code without using arrays but damn would it be ugly.

One example where i used pointers recently was when writing data to a large RGB led display.
I had an array storing the color of all the pixels.  Timer interrupt code was reading the array and drawing the data on the LED pixels.
Some other code was updating the array with new text/images.
Now the problem is that sometimes it would be in the middle of adding an image to the array and the LED display would get updated when it was half drawn.

The solution for this is to double buffer it, have one array you only use for adding content and one array you only use for updating the LED display.  Then you can swap them around using pointers after you finish adding content.
A couple of pointers works well for this, you can have two pointers pDrawingImageBuffer and pActiveImageBuffer and quickly swap what array they actually point to.

This means your code that is updating the LED display can work with only one pointer and your code for drawing text/images can work only with the other pointer.
You can quickly swap what they point to around and none of those code blocks know any different.

[rhb]

Algol 68, much as many things it did, gets it right there. Also considers immutability explicitly up front.

The standard lament is that Algol68 is an improvement on most of its successors.

That should read Algol 60, not 68.  Algol 68 suffered from massive feature creep.

FWIW History is important here.  The predecessor to C, B, is available again on Unix V0 using a PDP-7 emulator.  So you can see first hand how Ken and Dennis were struggling to make system development easier.  They had worked on Multics for some time, so they were very familiar with the problem.

https://github.com/DoctorWkt/pdp7-unix

https://www.bell-labs.com/usr/dmr/www/bintro.html

[bd139]

This one always sticks in my head with Algol: http://cowlark.com/2009-11-15-go/

[brucehoult]

One example where i used pointers recently was when writing data to a large RGB led display.
I had an array storing the color of all the pixels.  Timer interrupt code was reading the array and drawing the data on the LED pixels.
Some other code was updating the array with new text/images.
Now the problem is that sometimes it would be in the middle of adding an image to the array and the LED display would get updated when it was half drawn.

The solution for this is to double buffer it, have one array you only use for adding content and one array you only use for updating the LED display.  Then you can swap them around using pointers after you finish adding content.
A couple of pointers works well for this, you can have two pointers pDrawingImageBuffer and pActiveImageBuffer and quickly swap what array they actually point to.

This means your code that is updating the LED display can work with only one pointer and your code for drawing text/images can work only with the other pointer.
You can quickly swap what they point to around and none of those code blocks know any different.

You could just as well make pDrawingImageBuffer and pActiveImageBuffer integers with value 0 or 1, and make your array:

RGB pixels[2][NPIXELS]

Anything you can do with pointers you can do with array indexes instead. Once the optimiser gets done with it the machine code will be virtually identical.

[bd139]

How do you implement a dynamic sized ring buffer with arrays?

[sokoloff]

Anything you can do with pointers you can do with array indexes instead. Once the optimiser gets done with it the machine code will be virtually identical.

Call malloc.
Write a function that calls a user-specified function.

[NorthGuy]

Anything you can do with pointers you can do with array indexes instead.

Of course. But it will be very tedious if your elements are of variable length.

Once the optimiser gets done with it the machine code will be virtually identical.

I wouldn't agree with that. To access an element of the array, the CPU must calculate the address of the element. It must multiply the index by the size of the element and add an offset. If you have a pointer, the calculation is not needed.

This may not be a problem if the CPU has scaled indexed addressing (e.g. [RAX*8 + offset] in i86), but if the element size is bigger or not a power of two, or CPU doesn't have adequate addressing modes, there may be substantial overhead.

If you try to implement linked lists through array indexes instead of pointers, the overhead of walking the list may be very substantial.

[tggzzz]

Anything you can do with pointers you can do with array indexes instead. Once the optimiser gets done with it the machine code will be virtually identical.

Only if every element is the same size and is known at compile time. Frequently neither of those conditions is true.

[Tepe]

For example, if you write a[ i ] to access the i'th element of a, this is exactly the same as writing *(a+i)

A fun effect of a[ i ] being syntactic sugar for *(a + i) is that because *(a + i) is the same as *(i + a) due to addition being commutative,  i[ a ] is the same as a[ i ].


Edit: An example

Code: [Select]

#include <stdio.h>

int main(void)
{
    char a[5];

    2[a] = 'a';
    printf("%c\n", a[2]);
    return 0;
}


[NorthGuy]

An example

Code: [Select]

#include <stdio.h>

int tepe_sum(int a, int b) {
  return &((void*)a)[b];
}

int main(void)
{
  printf("2 + 2 = %d\n",tepe_sum(2,2));
}


[T3sl4co1l]

You could just as well make pDrawingImageBuffer and pActiveImageBuffer integers with value 0 or 1, and make your array:

RGB pixels[2][NPIXELS]

Anything you can do with pointers you can do with array indexes instead. Once the optimiser gets done with it the machine code will be virtually identical.

Not quite -- the elements of pixels[a] are themselves arrays; that is, pixels is a pointer to an array of pointers to data!

Nested arrays are almost syntactic sugar, easily forgotten -- but one should always use array[x + y*WIDTH] when they mean it, and use nested arrays for other things.

It could be that, if link-time optimization is allowed, such that the as-written semantics no longer apply exactly -- a multidimensional array could be collapsed into a single one (even better, collapsed into a convenient width, if every last clock cycle is required, and possible additional memory usage is acceptable?).  I don't think this is within the realm of normal optimization though.

Hmm, I don't have a direct example for where nested arrays would be useful.  Dynamic arrays perhaps, like if you're doing a text editor as an array of strings?  You need some way to track the individual array lengths, of course (whether by null-terminated bytes, or an array of lengths).

Tim

[Nominal Animal]

Leap seconds cause serious problems in distributed systems that rely on timestamps, e.g. telecom, or high reliability distributed file systems.

Very true.

Linux kernels nowadays do support CLOCK_TAI. POSIX.1 clock_gettime(CLOCK_REALTIME, &timespec) reports the Unix time (similar to time(), but at a nanosecond resolution), which does NOT take leap seconds into account. However, clock_gettime(CLOCK_TAI, &timespec) reports the number of seconds since Epoch, including leap seconds, if the userspace is configured to handle leap seconds correctly.

(Basically, ntpd or whatever takes care of clock sync, needs to do an adjtimex() call, with .modes=ADJ_TAI and .constant=leapsecs where leapsecs is the number of leap seconds since 1970-01-01. When a leap second occurs, an adjtimex() call with .modes=ADJ_OFFSET|ADJ_TAI, .offset-=1000, .constant+=1 atomically steps back the Unix time by one second (simulating the extra second inserted), while incrementing the number of leap seconds, so that CLOCK_TAI stays monotonic. It can be done at any point during the leap second.)

Just for fun, I set the TAI offset to 27 by hand, so right now on my laptop, CLOCK_REALTIME = 1532102354.146984744 but CLOCK_TAI =  1532102381.146988316 (indicating 27 leap seconds since 1970-01-01). The difference in the fractional part is only due to the two clocks not being read simultaneously.  So, at least Linux does have the necessary kernel support; only the userspace part is lagging.

The only reason why time(), mktime(), localtime(), or gmtime() cannot be switched to CLOCK_TAI is that it might break backwards compatibility. Otherwise, it would be a very simple change to canonically handle even leap seconds correctly, with a time_t that did include leap seconds.

In practice, the leap second is addressed by ntp daemons by adjusting the clock rate; slewing. It usually takes about two or three days for the compensation cycle to be over, and during this time, the clock sync across machines tends to slip a bit more than usual.

[tggzzz]

Algol 68, much as many things it did, gets it right there. Also considers immutability explicitly up front.

The standard lament is that Algol68 is an improvement on most of its successors.

That should read Algol 60, not 68.  Algol 68 suffered from massive feature creep.

You are, of course, correct in both respects. The latter, as I mentioned earlier and bs139 omitted to quote, lead to the various Algol68 subsets.

[GeorgeOfTheJungle]

Code: [Select]

#include <stdio.h>
#include <stdint.h>

int main (uint32_t a, uint32_t b) {
    printf("2 + 2 = %ld\n", (char*)&a - (char*)&b);
}

[andyturk]

Not quite -- the elements of pixels[a] are themselves arrays; that is, pixels is a pointer to an array of pointers to data!

Saying it this way is misleading or maybe incorrect. There are no pointers *within* the memory occupied by "pixels", and there is no array of pointers implied by the declaration.

Code: [Select]

#include <stdio.h>
#include <stdint.h>

typedef int32_t RGB;
enum {NPIXELS=10};

RGB pixels[2][NPIXELS];
RGB *pixel_ptr = NULL;

int main() {
  printf("sizeof(pixels) = %lu\n", sizeof(pixels));
  printf("sizeof(pixels[0]) = %lu\n", sizeof(pixels[0]));
  printf("sizeof(pixels[0][0]) = %lu\n", sizeof(pixels[0][0]));
  printf("sizeof(pixel_ptr) = %lu\n", sizeof(pixel_ptr));
}

produces:

Code: [Select]

sizeof(pixels) = 80
sizeof(pixels[0]) = 40
sizeof(pixels[0][0]) = 4
sizeof(pixel_ptr) = 8


[Tepe]

Code: [Select]

#include <stdio.h>
#include <stdint.h>

int main (uint32_t a, uint32_t b) {
    printf("2 + 2 = %ld\n", (char*)&a - (char*)&b);
}

Making assumptions about the direction the stack grows, alignment, ...

[NorthGuy]

RGB pixels[2][NPIXELS]

Not quite -- the elements of pixels[a] are themselves arrays; that is, pixels is a pointer to an array of pointers to data!

No. It's just an array - 2*NPIXELS elements located in a linear fashion. You can access these linear (i,j) elements with

Code: [Select]

((RGB*)pixels)[i*NPIXELS + j]
If you try to use it as if it was a pointer to an array of pointers, such as

Code: [Select]

**(RGB**)pixels
Ka-boom!

However, when you access it, C may dereference the array to the pointer (depending on the context), so all these access the same element:

Code: [Select]

pixels[i][j]
(*(pixels+i))[j]
*(pixels[i]+j)
*((*(pixels+i))+j)

I each of these sentences, de-referencing happens twice - first "pixels" is dereferenced to the pointer to the array of RGB, then, after the indirection is applied, the second dereferencing converts the array of RGB into the pointer to RGB.

Thus, even though the

Code: [Select]

**pixels
is valid and is equivalent to

Code: [Select]

pixels[0][0]
"pixels" is not a pointer to a pointer.

[GeorgeOfTheJungle]

Code: [Select]

#include <stdio.h>
#include <stdint.h>

int main (uint32_t a, uint32_t b) {
    printf("2 + 2 = %ld\n", (char*)&a - (char*)&b);
}

Making assumptions about the direction the stack grows, alignment, ...

Killjoy...

Code: [Select]

#include <stdio.h>
#include <stdint.h>

int main (uint32_t* a, int b) {
    printf("2 + 2 = %d\n", (b= (char*)a - (char*)&a[1]) > 0 ? b : -b); }
[ x ] Fixed.

[ajb]

Not quite -- the elements of pixels[a] are themselves arrays; that is, pixels is a pointer to an array of pointers to data!

Saying it this way is misleading or maybe incorrect. There are no pointers *within* the memory occupied by "pixels", and there is no array of pointers implied by the declaration.

Multidimensional arrays do revert syntactically to pointers when you leave off a subscript, just like one-dimensional arrays do:

Code: [Select]

int foo[2][10] // array of two arrays of ten ints, equivalent in allocation to int[20]
foo[a][b]      // int
foo[a]         // pointer to int
foo            // pointer to an array of int [with size 10].
The syntax starts to get a little weird when you want to actually do anything with partially-subscripted mutlidimensional array names as pointers, though.  Given int (*bar)[10] = foo, you would access the values in the array pointed to by bar with (*bar)[a].   Usually easier to use a one-dimensional array and do the dimensional indexing explicitly unless you really want to be clear about the conceptual shape of the array for some reason.  Even then a one-dimensional array and a macro or helper function that calculates the index from coordinates is probably easier both to write and to read.

But anyway you never get a pointer-to-pointer (or pointer-to-array-of-pointer) this way, because there are no actual pointers allocated in memory--a multidimensional array of type[s₁][s₂]...[s_n] is equivalent to an array of type[s₁*s₂*...*s_n] in allocation.  If you want a pointer-to-pointer or pointer-to-array-of-pointer, you'd need to have pointer-to-whatever allocated in memory somehow:

Code: [Select]

int (* bar[2])[10] //array of 2 pointer to array of int [size 10]
bar                // pointer to array of two pointer to array of int

[Nominal Animal]

Here is a practical example of how very useful pointers can be.  However, it relies on dynamic memory management, so I'm not sure how relevant it is to the discussion here.

Dealing with matrices in C is not particularly fun.  The existing libraries range from cryptic (BLAS) to nice (GSL), but they're not exactly developer-friendly. To demonstrate how easy matrix manipulation and management could be in C, I developed the following structures:

Code: [Select]

typedef  double  matrix_data;

struct matrix_owner {
    long         refcount;
    size_t       size;
    matrix_data  data[];
};

typedef struct {
    int                  rows;
    int                  cols;
    long                 rowstep;
    long                 colstep;
    matrix_data         *origin;
    struct matrix_owner *owner;   
} matrix;
The idea is that a matrix describes the matrix, but a struct matrix_owner contains the matrix data.  The origin field always points to some data element in the owner; it is the element at row 0, column 0 (upper left corner) in that particular matrix.

To access matrix *m element at row r, column c , you use m->origin[r*m->rowstep + c*m->colstep]:

Code: [Select]

static inline matrix_data  get_matrix_element(matrix *m, const int row, const int col,
                                              const matrix_data  outside)
{
    if (m && row >= 0 && col >= 0 && row < m->rows && col < m->cols)
        return m->origin[row * m->rowstep + col * m->colstep];
    else
        return outside;
}

static void  set_matrix_element(matrix *m, const int row, const int col,
                                const matrix_data  value)
{
    if (m && row >= 0 && col >= 0 && row < m->rows && col < m->cols)
        m->origin[row * m->rowstep + col * m->colstep] = value;
}

For example, if you want m2 to be a transposed view to m1 (so that any changes in one are reflected automatically in the other), you simply do

Code: [Select]

    m2.rows = m1.cols;
    m2.cols = m1.rows;
    m2.rowstep = m1.colstep;
    m2.colstep = m1.rowstep;
    m2.origin = m1.origin;
    m2.owner = m1.owner;
    m2.owner->refcount++;

You can create row and column vector views to an existing matrix, diagonal vectors, and even block submatrix views.  Any regular rectangular view to an existing matrix is possible.  Similar to Unix hard links, all views to matrix data are treated equally.  (Note that that is not true with e.g. GSL, which has different types for matrices and views. Here, a matrix is a view to the data; there is no distinction between a matrix and a view to a matrix.)

Whenever you no longer use a matrix, you do need to discard it. However, the data it refers to is only discarded when no other matrix uses it:

Code: [Select]

static void  discard_matrix(matrix *m)
{
    if (m) {
        if (m.owner) {
            if (--(m.owner->refcount) < 1) {
                /* No longer needed; discard. */
                m.owner->size = 0;
                free(m.owner);
            }
        }
        /* Poison matrix; helps detect use-after-discard bugs. */
        m.rows = 0;
        m.cols = 0;
        m.rowstep = 0;
        m.colstep = 0;
        m.origin = NULL;
        m.owner = NULL;
    }
}

If one adds two pointers to struct owner, data allocations can be pooled, so that a complicated sub-calculation can be done using a dedicated "pool". When the result matrix is obtained, it is copied (using a deep copy, i.e. copying the data from the struct owner to a new one), and the entire pool can be discarded at once, not bothering with discarding individual temporary matrices.  (Such "allocation pool" approach is heavily used by e.g. the Apache HTTPD server. Each request has its own pool, and when completed, the entire pool is discarded. This reduces the risk of memory leaks significantly, without making the code too tedious to maintain.)

The runtime "cost" of this type of structure does not differ much from that of e.g. GSL's gsl_matrix in practice.  Yes, this one requires two multiplications per entry rather than just one, but signed integer multiplication is quite optimized in current architectures, and most matrix operations seem to be bottlenecked by cache and RAM speed, not ALU performance. On my Core i5-7200U, the "extra" multiplication seems to vanish in memory latencies in practical code.  The versatility and ease of use, in my opinion, is well worth the risk of a slight overhead anyway.

[T3sl4co1l]

It may be implementation dependent, or I'm confusing some C++ or other-language features with C arrays.  Here's an example, admittedly very much on the boundary of implementation dependency:
https://www.nongnu.org/avr-libc/user-manual/pgmspace.html

Tim

[brucehoult]

Anything you can do with pointers you can do with array indexes instead. Once the optimiser gets done with it the machine code will be virtually identical.

Call malloc.
Write a function that calls a user-specified function.

You can use an array to *write* malloc().  And then call it.

[brucehoult]

If you try to implement linked lists through array indexes instead of pointers, the overhead of walking the list may be very substantial.

Try it :-)

It's not. The memory access times dominate. Especially once your list is bigger than L1 cache.

[tggzzz]

This one always sticks in my head with Algol: http://cowlark.com/2009-11-15-go/

Amusing and not bad.

I particularly like the statement about Go "Most killingly of all, it's full of examples where they did not consult the literature." That has been a recurring problem with the C family; by contrast Gosling's original Java white paper was full of "X has been proven in M, and Y has been proven in N, and X and Y play nicely together thus...".

OTOH I think that your "On Go" page downplays the benefits of CSP channels too much.

[newbrain]

OTOH I think that your "On Go" page downplays the benefits of CSP channels too much.

Love CSP channels, my master thesis was an occam compiler...written in Pascal (+ASM x86).

[sokoloff]

Anything you can do with pointers you can do with array indexes instead. Once the optimiser gets done with it the machine code will be virtually identical.

Call malloc.
Write a function that calls a user-specified function.

You can use an array to *write* malloc().  And then call it.

That's why I said call malloc, not write it...

[tggzzz]

OTOH I think that your "On Go" page downplays the benefits of CSP channels too much.

Love CSP channels, my master thesis was an occam compiler...written in Pascal (+ASM x86).

Look at XMOS xC running on their xCORE processors. It is Occam and Transputers "Done Right" so they are commercially successful. Some of the technical team are the same, too.

Start with https://www.xmos.com/published/xmos-programming-guide and http://www.xmos.com/published/xcore-architecture-flyer?version=latest

[NorthGuy]

Try it :-)

It's not. The memory access times dominate. Especially once your list is bigger than L1 cache.

Tried it:

Code: [Select]

#include <stdio.h>
#include <windows.h>

#define LIST_SIZE 1000
#define WALK_COUNT 1000000

typedef struct sel{
  struct sel * next;
  char load[37];
} el, *pel;

el list[LIST_SIZE];

int main() {
  int i, v, before, after;
  pel c;
  setbuf(stdout,NULL);
 
  for (i = 0; i < (LIST_SIZE-1); i++) {
    list[i].next = list+i+1;
  }
 
  before = GetTickCount();
 
  for (v = 0; v < WALK_COUNT; v++) {
    c = list;
    for (i = 0; i < (LIST_SIZE-1); i++) {
      c = c->next;
    }
    c->load[0]++;
  }
 
  after = GetTickCount();
 
  printf("Count = %d\n",after - before);
}



Code: [Select]

#include <stdio.h>
#include <windows.h>

#define LIST_SIZE 1000
#define WALK_COUNT 1000000

typedef struct sel{
  int next;
  char load[37];
} el, *pel;

el list[LIST_SIZE];

int main() {
  int i, v, before, after;
  int c;
  setbuf(stdout,NULL);
 
  for (i = 0; i < (LIST_SIZE-1); i++) {
    list[i].next = i+1;
  }
 
  before = GetTickCount();
 
  for (v = 0; v < WALK_COUNT; v++) {
    c = 0;
    for (i = 0; i < (LIST_SIZE-1); i++) {
      c = list[c].next;
    }
    list[c].load[0]++;
  }
 
  after = GetTickCount();
 
  printf("Count = %d\n",after - before);
}

compiled with

Code: [Select]

Microsoft (R) C/C++ Optimizing Compiler Version 15.00.30729.01 for x64
(all default settings)

The pointer version scored 2995 on my old i5, while the array version scored 3775 - about 25% overhead. Not such a big difference, of course, but still.

The overhead doesn't seem to be related to compiler optimization. When I use

Code: [Select]

Microsoft (R) 32-bit C/C++ Optimizing Compiler Version 9.10 for 80x86
Copyright (C) Microsoft Corp 1984-1994.
the scores are a touch better - 2948 and 3760 respectively.

You can try it with GCC if you wish.

[rhb]

Look at XMOS xC running on their xCORE processors. It is Occam and Transputers "Done Right" so they are commercially successful. Some of the technical team are the same, too.

Start with https://www.xmos.com/published/xmos-programming-guide and http://www.xmos.com/published/xcore-architecture-flyer?version=latest

Thank you!   I never played with a Transputer, but I have and have read the manual for it and Occam.  I'll definitely have to look at this.

[westfw]

Quote

Anything you can do with pointers you can do with array indexes instead.

Yeah; I didn't like the strcpy() example for that reason; too easy to imagine doing the same thing with arrays (and more legibly.  though you do need to be able to trust your optimizer a bit more.)

But ... lets talk about passing those arrays to functions as arguments...It should be obvious that we don't want to copy the entire array(s) to and from storage that is local to the function, right?  They could have thousands of elements, and copying memory is slow.So instead, we pass the address of the beginning of the array (and maybe other info, like the total length or the size of an element, depending on the language.)Ta da!   that "address of the beginning of the array" is a pointer!Now that you have compiler internals that need to deal with "addresses of things", you might as well start looking into what you can do if you if you allow things other than plain arrays to access the same capabilities; access to more complex data structures, as a start - sort of like arrays whose element sizes are different from one another.

Quote

Anything you can do with pointers you can do with array indexes instead.

well, sure.  An array is essentially a chunk of virtual memory, and an array index is just a pointer within that limited scope...

[brucehoult]

The pointer version scored 2995 on my old i5, while the array version scored 3775 - about 25% overhead. Not such a big difference, of course, but still.

I deleted the Windows stuff and used "time" in bash with gcc 7.3 on a Kaby Lake Refresh i7:

-O	-O2	version
1.95	2.02	pointer
2.45	2.08	array

So, as I said "once the optimiser is finished with it" any difference is down in the measurement noise.

Even with -O the difference was, as you say, only 25%.

[NorthGuy]

-O	-O2	version
1.95	2.02	pointer
2.45	2.08	array

So, as I said "once the optimiser is finished with it" any difference is down in the measurement noise.

Interesting. The optimizer made the pointer version slightly worse

Would be interesting to compare your numbers to 1994 VC++, which may actually come up as a winner here (scored 2.95 here). Do you have Windows partition on this PIC? I can post the exec for you to try.

i7 Kaby Lake Refresh only beats my almost-10-years old i5 Sandy Bridge by 30%? May be I do not need a new PC ...

[bsfeechannel]

This whole thread reminds me why we should teach computing from the bottom up.

Challenge accepted.

You happily write:

Code: [Select]

int main(void)
{
int a = 0;
}

Under the hood what happens is:

Code: [Select]

<main>:
55                    push   ebp ; Save old base pointer
89 e5                mov    ebp,esp ; Old stack pointer is the new base pointer
83 ec 10              sub    esp,0x10 ; Reserve 16 bytes for registers and local variables
c7 45 fc 00 00 00 00 mov    DWORD PTR [ebp-0x4],0x0 ; Fill the first four bytes with zeros
c9                    leave ; Undo the first two lines
c3                    ret    ; Jump to the return address

In machine code your cherished variable "decays" to an implicit pointer indicated by the contents of ebp offset by four bytes (-0x4), the size of an int. The rest of the code deals with memory addresses.

So why use pointers? Because they're the default expedient in computing. Or perhaps the essence of it.

Variables, strings, arrays, structs, classes, etc., are high level abstractions that hide the task of memory manipulation. For better of for worse.

But C is a high level language, innit? So you don't get your hands dirty dealing with addresses directly.

You use the power of a high level language itself and store addresses in variables. Special variables called... pointers! Special for you and the compiler, but not for the machine. The source code below:

Code: [Select]

#include <locale.h>

int main(void)
{
int *a = NULL;
}

will render, surprise!, the same machine code as above:

Code: [Select]

<main>:
55                    push   ebp
89 e5                mov    ebp,esp
83 ec 10              sub    esp,0x10
c7 45 fc 00 00 00 00 mov    DWORD PTR [ebp-0x4],0x0
c9                    leave 
c3                    ret   

This is because incidentally the size of an address is the same size of an int in this machine: four bytes. And NULL is the same as (void *) 0. There's no indication that the same allocated memory space is going to take an address. That's a secret that only you and your compiler share. This is to show that pointers in C do not intrinsically point nor are aliases.

[brucehoult]

-O	-O2	version
1.95	2.02	pointer
2.45	2.08	array

So, as I said "once the optimiser is finished with it" any difference is down in the measurement noise.

Interesting. The optimizer made the pointer version slightly worse

The difference is getting close to measurement error .. or perhaps more pertinent, simply where the loop happens to start within a cache line, the grouping the instructions are dispatched in etc. The actual instructions generated are probably identical (I haven't checked).

Would be interesting to compare your numbers to 1994 VC++, which may actually come up as a winner here (scored 2.95 here). Do you have Windows partition on this PIC? I can post the exec for you to try.

I'm afraid I've never owned a machine running Windows.

i7 Kaby Lake Refresh only beats my almost-10-years old i5 Sandy Bridge by 30%? May be I do not need a new PC ...

This is only a 15W part, officially marketed as 1.9 GHz. It's in a NUC here but usually they are in "Ultrabooks".

In practice it's about 20% faster single-threaded than the full tower i7-6700 I had under my desk at Samsung, and maybe 3% slower than the 6700 with eight threads active, hitting the thermal limit etc.

Nevertheless I do find it quite useful as something I can literally put in my jeans pocket, and use anywhere I can borrow a monitor (or ssh in headless from my 2011 Sandy Bridge MBP). The attraction is in the portability not the speed.

[tggzzz]

Look at XMOS xC running on their xCORE processors. It is Occam and Transputers "Done Right" so they are commercially successful. Some of the technical team are the same, too.

Start with https://www.xmos.com/published/xmos-programming-guide and http://www.xmos.com/published/xcore-architecture-flyer?version=latest

Thank you!   I never played with a Transputer, but I have and have read the manual for it and Occam.  I'll definitely have to look at this.

You're welcome. Search this website for my moniker and xCORE or XMOS, and you'll see why I like the system. By system I mean hardware plus software plus toolset, and they way they are an integrated whole that allow you to do things that no other ecosystem can touch.

I'm far from being an expert user, but using it is remarkably easy and surprise free. The only snags I had to workaround were in my architectural design - which is my problem and nothing any tool could solve!

You can buy 32 core 4000MIPS chips with a 10ns "interrupt" latency (== hard realtime!)at Digikey https://www.digikey.co.uk/products/en?keywords=xmos

[GeorgeOfTheJungle]

-O	-O2	version
1.95	2.02	pointer
2.45	2.08	array

So, as I said "once the optimiser is finished with it" any difference is down in the measurement noise.

Interesting. The optimizer made the pointer version slightly worse

The difference is getting close to measurement error .. or perhaps more pertinent, simply where the loop happens to start within a cache line, the grouping the instructions are dispatched in etc. The actual instructions generated are probably identical (I haven't checked).

GCC optimizes the hell out of t_arrays.c (using indices), look:

jorge@unibody:~/kk$ gcc -O0 t_arrays.c
jorge@unibody:~/kk$ time ./a.out
1000000
real   0m3.226s
user   0m3.209s
sys   0m0.006s

jorge@unibody:~/kk$ gcc -O1 t_arrays.c
jorge@unibody:~/kk$ time ./a.out
1000000
real   0m0.009s
user   0m0.004s
sys   0m0.002s

jorge@unibody:~/kk$ gcc -O2 t_arrays.c
jorge@unibody:~/kk$ time ./a.out
1000000
real   0m0.007s
user   0m0.003s
sys   0m0.002s

jorge@unibody:~/kk$ gcc -O3 t_arrays.c
jorge@unibody:~/kk$ time ./a.out
1000000
real   0m0.007s
user   0m0.003s
sys   0m0.002s

jorge@unibody:~/kk$ gcc -O0 t_pointers.c
jorge@unibody:~/kk$ time ./a.out
1000000
real   0m3.215s
user   0m3.203s
sys   0m0.006s

jorge@unibody:~/kk$ gcc -O3 t_pointers.c
jorge@unibody:~/kk$ time ./a.out
1000000
real   0m1.410s
user   0m1.401s
sys   0m0.004s


t_arrays.c:

Code: [Select]

#include <stdio.h>

typedef struct sel {
    int next;
    int load[2]; } el, *pel;

#define LIST_SIZE 1000
#define WALK_COUNT 1000000
el list[LIST_SIZE+1];

int main (int i, int j, int c) {
    for (i= 0 ; i < LIST_SIZE ; i++) list[i].next= i+1;
    for (i= 0 ; i < WALK_COUNT; i++) {
        for (j= 0; j < LIST_SIZE; j++) c= list[j].next;
        list[c].load[0]+= 1; }
    printf("%d\n", list[c].load[0]); }
t_pointers.c:

Code: [Select]

#include <stdio.h>

#define LIST_SIZE 1000
#define WALK_COUNT 1000000
typedef struct sel {
    struct sel* next;
    int load[2]; } el, *pel;

el list[LIST_SIZE+1];

int main (int i, int j, el* c) {
    for (i= 0 ; i < LIST_SIZE ; i++) list[i].next= list+i+1;
    for (i= 0 ; i < WALK_COUNT ; i++) {
        for (j= 0, c= list ; j < LIST_SIZE ; j++) c= c->next;
        c->load[0]+= 1; }
    printf("%d\n", c->load[0]); }

[GeorgeOfTheJungle]

And, as you increase the payload size, t_pointers.c performs worse and worse. In the typedef put int load[6666]; instead of int load[2]; and then you get:


jorge@unibody:~/kk$ gcc -O0 t_arrays.c
jorge@unibody:~/kk$ time ./a.out
1000000

real   0m8.937s
user   0m8.930s
sys   0m0.005s
jorge@unibody:~/kk$ gcc -O3 t_arrays.c
jorge@unibody:~/kk$ time ./a.out
1000000

real   0m0.013s
user   0m0.005s
sys   0m0.004s
jorge@unibody:~/kk$ gcc -O0 t_pointers.c
jorge@unibody:~/kk$ time ./a.out
1000000

real   0m11.919s
user   0m11.908s
sys   0m0.007s
jorge@unibody:~/kk$ gcc -O3 t_pointers.c
jorge@unibody:~/kk$ time ./a.out
1000000

real   0m10.297s
user   0m10.287s
sys   0m0.006s

[GeorgeOfTheJungle]

A.k.a. the trap of the performance sweet spot 

[GeorgeOfTheJungle]

I can't imagine why anyone would object to null terminated strings.

1) Because you're mixing data and metadata.
2) Who says a string can't contain a null \0 ? Ritchie and Thompson. Amen.
3) There's no way to know its length, without traversing the whole damn thing.
4) Forget to end with a \0 and all hell breaks loose.
5) Put accidentally \0 in the data and it won't work but won't err either.

[NorthGuy]

GCC optimizes the hell out of t_arrays.c (using indices), look:

You're not actually walking the list. You replaced

Code: [Select]

c= list[c].next;
with

Code: [Select]

c= list[j].next;
thereby eliminating the walking completely.

[NorthGuy]

I'm afraid I've never owned a machine running Windows.

  I'll be that way starting from my next PC

[GeorgeOfTheJungle]

You're not actually walking the list. You replaced

Code: [Select]

c= list[c].next;
with

Code: [Select]

c= list[j].next;
thereby eliminating the walking completely.

Oh dear, so gcc -O1..3 is replacing the whole j loop with a single c= list[LIST_SIZE-1].next, right?

jorge@unibody:~/kk$ gcc -O0 t_arrays.c
jorge@unibody:~/kk$ time ./a.out
1000000
real   0m4.779s
user   0m4.769s
sys   0m0.002s

jorge@unibody:~/kk$ gcc -O3 t_arrays.c
jorge@unibody:~/kk$ time ./a.out
1000000
real   0m1.742s
user   0m1.733s
sys   0m0.004s

jorge@unibody:~/kk$ gcc -O0 t_pointers.c
jorge@unibody:~/kk$ time ./a.out
1000000
real   0m3.215s
user   0m3.203s
sys   0m0.006s

jorge@unibody:~/kk$ gcc -O3 t_pointers.c
jorge@unibody:~/kk$ time ./a.out
1000000
real   0m1.410s
user   0m1.401s
sys   0m0.004s

t_arrays.c:

Code: [Select]

#include <stdio.h>

typedef struct sel {
    int next;
    int load[2]; } el, *pel;

#define LIST_SIZE 1000
#define WALK_COUNT 1000000
el list[LIST_SIZE+1];

int main (int i, int j, int c) {
    for (i= 0 ; i < LIST_SIZE ; i++) list[i].next= i+1;
    for (i= 0 ; i < WALK_COUNT ; i++) {
        for (j= 0, c= 0 ; j < LIST_SIZE ; j++) c= list[c].next;
        list[c].load[0]+= 1; }
    printf("%d\n", list[c].load[0]); }
Note to self: if it seems too good to be true, it probably is.

[Nominal Animal]

It seems that a counterexample is in order: Verlet list, also known as neighbour list.

The practical implementation is a single honking big array. It lists the indexes of close-by particles, for each particle. Each subsequence in the array begins with the number of particles for that particle, followed with the neighbouring particle indexes. The subsequences are in order of particle indexes:
    ║ N_a │ a₁ │ a₂ │ ... │ a_Na ║ N_b │ b₁ │ b₂ │ ... │ b_Nb ║ N_c │ c₁ │ c₂ │ ... │ c_Nc ║
and so on, the above listing three subsequences in the array.  (I'm using 1-based indexing, because you see this most commonly in Fortran code.)

Why not use a linked list (of subsequences), using pointers? Why not have an array per particle?

The answer is simple: cache locality.

In a molecular dynamics simulation, the darned particles don't usually stay put.  Sure, if you have a solid block of some simulated matter, those atoms do stay in place; but simulating such a block is not very interesting.  If it melts, you have a big impact, or anything interesting, the atoms move quite a bit.  So, unless you do something radical that current simulators do not tend to do, and periodically rearrange the structures describing the particles location, velocity, and acceleration components (used by whatever predictor-corrector method is used to integrate the particle trajectories) to be sequential in memory, the particles you access will not be sequential in memory.

If you have the neighbour list as a single sequential array, you can process it linearly.  The neighbour list itself will have a relatively small cache footprint (your compiler can even produce very accurate prefetch instructions for it), leaving most of the cache for the scattered particle data.  One might think that because the particle data is already scattered in memory, it would not be so bad to have the neighbour list also scattered, but they'd be wrong: cache access patterns matter, a lot.

Furthermore, if a single simulation has fewer than 2³² = 4,294,967,296 particles, you can use 32-bit unsigned integers as particle indexes even on 64-bit architectures, "packing" the neighbour information even tighter, leaving even more of the cache for the scattered particle data. 
(In physics simulations using classical potential models, each atom typically has up to a few hundred neighbours, and a simulation up to a few million atoms per CPU core. To get any results, a LOT of time steps are needed, so to get results in reasonable time, the simulations tend to be distributed across a number of CPU cores, each core processing a subvolume of the entire simulation. Chemical simulations using potential models tend to differ, and I'm not very familiar with those.  Quantum mechanical simulations model the electron densities as fields, and are limited to a few hundred to a couple of thousand electrons, currently; and are much, much harder to distribute over many physical machines.)

In practice, the difference between neighbour lists where the sublists use pointers (either a linked list, and/or linked from each particle), and where the entire neighbour list is a single linear array, varies depending on how much the particles' data structures in memory reflect their neighbour relationships in the simulation, but the single linear array is always faster.

Does that mean that pointers are not useless?  Definitely not, I've already shown some examples of code that you cannot do efficiently with arrays (basically any data structure with members whose type and size varies).  Pointers and arrays are just tools provided by your programming language.  They have their uses, and your task as a programmer is to choose the appropriate tool (and algorithm!) when solving a particular problem.

If you haven't yet needed to use some tools, it means that either you have only worked on specific types of problems where that tool simply isn't needed to achieve an efficient solution, or that you don't know enough algorithms and approaches to solve the problems at hand.  I do like the saying that if all you have is a hammer, all problems start to look like nails; but with programming, the situation is more complex.  The problems are abstract, and it is hard to see whether you are using a proverbial "hammer" or a "screwdriver" to drive in a "screw"; you need experience with lots of different types of problems to learn to estimate that.

C is also a funny language in that because it is so low-levelish, programmers are often stuck in microbenchmarking irrelevant details.  There is absolutely no sense in comparing array-based and pointer-based linked list traversal, unless those lists contain real-world data, and the traversal obtains a real-world result.  That is because microbenchmarking does not prove anything practical: it is only a preliminary indicator.  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.

It is not rare to microbenchmark two implementations, say sort algorithms, and find that while the microbenchmark shows that one is faster than the other, in real world applications the opposite is true.  It is not always easy to explain why (although "memory and cache effects" are certainly at the core of it).  Even then, it is the real world performance that matters.  So, please, don't get too hung up on microbenchmarking, because its really is just a preliminary indication, not a proof of anything (except that microbenchmark itself).

Microcontrollers are even funkier, because there is so much variance between different types.  The one thing they have in common, tends to be the small amount of RAM used.  Therefore, when programming microcontrollers in C (or C++), one is probably more concerned about the total memory footprint -- the amount of memory needed to achieve the desired results --, than speed.

[tggzzz]

I'm afraid I've never owned a machine running Windows.

  I'll be that way starting from my next PC

Why wait? Ease the transition by dual-booting or a virtual machine.

[tggzzz]

C is also a funny language in that because it is so low-levelish, programmers are often stuck in microbenchmarking irrelevant details.  There is absolutely no sense in comparing array-based and pointer-based linked list traversal, unless those lists contain real-world data, and the traversal obtains a real-world result.  That is because microbenchmarking does not prove anything practical: it is only a preliminary indicator.  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.

Very true. It wasn't so true with PDP-11s, but C programmers all too often seem to think little has changed since then.

The other point about why microbenchmarking is pointless is that in normal-sized real programs there are many more possible interactions between different parts of the program - and doubly so when precompiled libraries are involved. The number of interactions rapidly makes it more difficult to globally optimise.

C/C++ is also particularly bad in this respect since the compiler has to presume pointer aliasing unless it can be proven not to exist. Since proof is arbitrarily difficult, it has to rely on every part of the code and libraries making the same correct declarations about aliasing and then not violating them. When, not if, a mistake is made, the resulting bugs are intermittent, difficult to spot, difficult to diagnose, and difficult to fix.

One way to reduce those problems is to copy everything, but that brings significant inefficiencies. And that is another reason why microbenchmarks are pointless.

[GeorgeOfTheJungle]

Exactly, and the cache effects can be seen here: all four below traverse arrays of the same size (# of elements), but in the first two the elements are ~ 100 kBytes each, in the last two a few bytes (int load[99999]; and int load[2]; of the struct).

jorge@unibody:~/kk$ gcc -O3 t_arrays.c
jorge@unibody:~/kk$ time ./a.out
1000000
real   0m12.106s
user   0m12.088s
sys   0m0.008s

jorge@unibody:~/kk$ gcc -O3 t_pointers.c
jorge@unibody:~/kk$ time ./a.out
1000000
real   0m10.898s
user   0m10.886s
sys   0m0.008s

jorge@unibody:~/kk$ gcc -O3 t_arrays.c
jorge@unibody:~/kk$ time ./a.out
1000000
real   0m1.671s
user   0m1.666s
sys   0m0.003s

jorge@unibody:~/kk$ gcc -O3 t_pointers.c
jorge@unibody:~/kk$ time ./a.out
1000000
real   0m1.328s
user   0m1.323s
sys   0m0.002s

[bsfeechannel]

There is absolutely no sense in comparing array-based and pointer-based linked list traversal,

I think the OP's question is brilliant and no one has managed to address it properly yet. Some try, others digress.

[Howardlong]

There is absolutely no sense in comparing array-based and pointer-based linked list traversal,

I think the OP's question is brilliant and no one has managed to address it properly yet. Some try, others digress.

I am not sure there is a straight answer.

Back when I was a young’un, I went from high level languages like Algol, Basic and Fortran, and in between all of those assembly language, where pointers were called indirect addressing, and fancier instruction sets like the Z80 and 6502 had indirect indexed addressing too.

Then I became a Pascal guy, where pointers are very definitely part of the language, but in a very much relaxed way, compared to C. I was happy, I knew what was going on under the hood.

Then came my immersion into C. This was a whole new ball game, mostly around the syntax, and that I really did find hard work. That was 30+ years ago and some of the more esoteric things, like passing an array of pointers to functions, I need to put my thinking cap on, but 99.999+% of the time it’s second nature.

While I agree it’s hard to grasp, there is some beauty in the syntax that allows you to get so close to the hardware.

My first C job was a baptism of fire into K&R C, some dude from Cornell, undoubtedly bloody clever, left a ton of (to me) undecipherable code, it was pointer city, with multiple side effects in single lines of code. Hard work for a Pascal bloke. Nowadays, apart from the odd weird pointer to array of pointers to array of pointers to function scenario, it’s second nature. I don’t seem to see those scenarios much these days though.

It does become second nature, but the learning curve is steep. Like the sibling you always hated as a child, you grow to love them.

[ajb]

I think the OP's question is brilliant and no one has managed to address it properly yet. Some try, others digress.

If the question is "why would I want to use pointers in C?" the answer is simple: because they make easier/cleaner/more efficient program constructs possible.  If you want to know why or how they do those things, well, that's why this thread is so long.  (Sometimes, especially as a beginner, you might use pointers just because that's what a library or peripheral (like DMA) requires of you.  That's as good a time as any to start learning!)

EDIT: I think part of the problem with this thread is that it often takes a fair amount of time and experience to grok pointers, so it's difficult to sum that up, and even if you do, it's not going to stick with a beginner until they develop some experience.  I think you really have to work through some programming problems to absorb the subject and get comfortable enough with the syntax that the notation is no longer such a barrier.  Side note: a really great resource, especially for beginners, is https://cdecl.org/, which translates C declarations into plain(ish) english, and vice versa.  It's especially great for the really wacky stuff, just note that it won't understand typedefed or stdint names.

[Nominal Animal]

How about this:

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

The qualified type information is only used at compile time, and is not recoverable at run time; it is not stored anywhere.
There are four qualifiers in C: const, volatile, restrict, and _Atomic. These govern how the data referred to by the pointer should be accessed. The type is of course the type of the target.  Because pointers can be indexed the same way as arrays can, the target can also be considered the first element in an array of such elements.

In a microcontroller, your C compiler could provide you with a mem[] array (on Harvard architectures like AVRs, you'd also need a flash[] or rom[] array, as the two address spaces are separate) which correspond 1:1 to the hardware.  Indexes to that array would act exactly like pointers, except you would need some other way to convey the type of the data at that point.  Or, in other words, pointers are indexes to such arrays, but also convey the qualified type of the data stored there.

Pointers do also have additional quirks like pointer arithmetic (incrementing a pointer by one does not change the memory index by one, but by the size of the target), but the qualified type information carried by the pointer is the key difference.

[ajb]

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

  I don't see how this constitutes a real difference in practice.  The index doesn't convey the type (qualified or otherwise, since it's just an integer), but the symbolic name of the array *does*, and if you aren't using a pointer, then you have have to be using said name to access the array data, and thus it will be accesses will be properly qualified.  A pointer to the array is in some ways more fragile in terms of maintaining the required access qualifications because it's quite easy to assign a location to a differently-qualified (or typed) pointer on assignment.  The compiler should issue a warning, but often an explicit cast is happening anyway, like creating a pointer from an int for some perfectly valid reason, and it's easy to make mistakes there.  That's not really an argument against pointers, but an argument for being careful with type qualifications, which you should do anyway!

[Nominal Animal]

I don't see how this constitutes a real difference in practice.

You do not see the trees for the forest, then.  Really.  If you think there is no difference in practice to labeling all trees in a forest, to labeling each tree according to their species, you just haven't needed a forest with varying species of trees before, I guess.  That is where the more complex and interesting abstract data types come in.  I've already shown a couple of examples of those, and they really do rely on the type information conveyed by each pointer, because each element, each "tree", can belong to one of many species.

Edited to add: the dangers of misusing pointers is not really relevant.  C is a language that happily lets you shoot your proverbial legs off if you want to.

[ajb]

I don't see how this constitutes a real difference in practice.

You do not see the trees for the forest, then.  Really.  If you think there is no difference in practice to labeling all trees in a forest, to labeling each tree according to their species, you just haven't needed a forest with varying species of trees before, I guess.  That is where the more complex and interesting abstract data types come in.  I've already shown a couple of examples of those, and they really do rely on the type information conveyed by each pointer, because each element, each "tree", can belong to one of many species.

If you're talking about allocating an array of some arbitrary type and then use elements of that array as different (or differently qualified) types, as in your neighbor list example, then that's a very specific pattern and a strange one to use in response to a beginner asking "what are pointers good for?".  Your post that prompted my response didn't indicate any of that context, so I assumed you were talking about the simple case of array vs pointer which has been a much larger subject of discussion in this thread.
 
Obviously there are cases where you need to manually arrange different data elements into memory (building/dissecting network packets, or a very specific performance optimization like in your case).  In other situations, compound data types are probably better handled as structs and abstract data types are probably better handled through tagged structures and unions.  The intent will be clearer, and you won't have to cast all over the place.

[GeorgeOfTheJungle]

WRT microbenchmarks, the fad is to say they're useless. Or to say so in public. But, then, in private, we all do them

[IanB]

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

[NorthGuy]

Exactly, and the cache effects can be seen here: all four below traverse arrays of the same size (# of elements), but in the first two the elements are ~ 100 kBytes each, in the last two two bytes (int load[99999]; and int load[2]; of the struct).

The minimum amount you can ever read from DDR3 DIMM in a half-burst is 32 bytes, and reading full-burst 64 bytes is much faster than reading two half-bursts. Thus reading consecutive bytes saves a lot of time.

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.

[NorthGuy]

Why wait? Ease the transition by dual-booting or a virtual machine.

I have few Linux machines, and I'm porting my stuff gradually. I also have a Mac, and it seems Ok too, although it doesn't run Vivado I haven't made up my mind yet whether I want Linux or Mac, but Linux will probably win.

Windows 7 would be fine (I use it now), but Windows 10 is way beyond acceptable to me - I'll never going to use it, and I guess Microsofts are not backing away from their ideas.

[tggzzz]

WRT microbenchmarks, the fad is to say they're useless. Or to say so in public. But, then, in private, we all do them

That so-called "fad" has been true for several decades.

[Howardlong]

WRT microbenchmarks, the fad is to say they're useless. Or to say so in public. But, then, in private, we all do them

Absolutely, lf course we do. Microbenchmarking isn’t done to show how something will perform once integrated, it’s a gate to show that it works well enough during development and unit testing. If you’re not using representative datasets during your unit testing, then you’re just putting off the inevitable rework and wasting everyone’s time.

More importantly, if your algorithm is shit when microbenchmarked, what do you know, it’s still going to be shit on your representative datasets, and when system integrated. At least it’s been like that since the tooth fairy last left a coin under my pillow.

So any programmer worth a tny grain of salt and at least some pride in their work is going to do a quick smoke test to get some sort of indication, and if that turns out to be reasonable, rework if not, and then try it with representative test datasets.

Blanket rejection of microbenchmarking is akin to rejecting “measure twice, cut once”.

[Nominal Animal]

If you're talking about allocating an array

No. I meant that definition in bold as an answer to Simon's original question: Pointers - what is the point?.

WRT microbenchmarks, the fad is to say they're useless. Or to say so in public. But, then, in private, we all do them

I did not say they're useless. I said, microbenchmarking [provides] only preliminary results.  Preliminary results are useful, but they don't prove anything.  The microbenchmarks posted in this thread, for example, do not prove anything but the results of those particular microbenchmarks; you cannot extrapolate their results to real world tasks!

I personally run microbenchmarks to exclude poorly performing implementations, and also to find the scalability of an implementation. (You do that by running the microbenchmark with increasing data set size, to find out where the cache behaviour causes the sudden increases in run time used. Comparing those curves and step points between implementations that do the same operation/work on random data, or to the known cache hierarchy on that particular piece of hardware, is useful because it provides information about the scalability of each approach. So, in many ways, there is a third type of benchmarking, scalability testing, between microbenchmarks and real world benchmarks.)

[GeorgeOfTheJungle]

Ok. Pointers and C. What's important to say? Let me try:

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, all the pointers are of the same (~ small) size, regardless of the size or type of the data they point to.
d) As 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 often it's much faster (no need to duplicate big chunks of data).
d.2) Because often it requires much 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.

... ¿?

[GeorgeOfTheJungle]

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

Yes! 

[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...)

[bd139]

I dip out of this thread and come back and find Perl mentioned. No. Just no.

Back in 2004 I got a 3 month contract to port an application to .net from “unknown”. Unknown happened to be Perl + cgi + DBI + MySQL on a RH7 box they lost the password for. Everything running as root of course. The original maintainer was killed in a motorcycle accident, probably because his motorcycle was bodged up like the rest of his life. One of those places where you know they were relieved he was dead because they didn’t have to fire him for being a dick.

I took one look at the vomit which was write only and proceeded to rewrite the damn thing from the schema and the screenshots only.

Even the worst C doesn’t get anywhere near middle of the road Perl.

[NorthGuy]

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 :-(

Microchip's XC8 compiler, for every pointer, analyzes its uses,  and then assigns the size. So, each individual pointer has its own size.

[brucehoult]

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. 

Dude, chill. Code presented in a thread like this is sketches, not finished paintings. I make errors, you make errors, what's the problem? The discussion is about style.

[bsfeechannel]

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. 

The problem with this approach is that you turn a simple Q&A thread into a debate. Debates are fine. I like debates. But they're incompatible with Q&A. In the future, if other people come with the same kind of doubt, we won't be able to recommend this thread because the meaningful answers will be so buried in parallel discussions that it will be discouraging to read.

My suggestion is that on spotting those "programmers with a lot of experience" (by the way someone with a lot of experience is someone that made a lot of mistakes) giving "bad advice" to "new programmers" one counterargument be given maximum. If that is not enough let's create a new thread, invite everyone and debate that idea there.

[rx8pilot]

Enjoying this thread....joining.

[sokoloff]

Saw this amusing image today and was reminded of this thread...