[C] Pointers - what is the point?

[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!