[C] Pointers - what is the point?

[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