« first day (78 days earlier)      last day (2780 days later) » 

user406009
3:38 AM
@LuisAverhoff It comes down to how the array is laid out in memory.
 
user406009
Let me see if I can find a good picture.
 
user406009
 
user406009
Oh, and the fact is true, but optimization settings mean the compiler might be able to transform from one version of the loop to another.
 
@Lalaland So if you were to do row major order, it would be more cache efficient because it would load that part of the array into the cache?
 
user406009
@LuisAverhoff Well, the thing is that you want to read close parts of the array together.
 
3:41 AM
and then when it jumped to the second row, it would do the same?
 
user406009
Note how m[0][0] and m[0][1] are close, but m[0][0] and m[1][0] are much further apart.
 
user406009
The slow version of the loop reads m[0][0], m[1][0], m[2][0], m[0][1], etc, etc.
 
user406009
Note how all the array accesses are not that close together.
 
But still, you have to access each cell and so wouldn't you always have at most one miss in the cache?
 
user406009
CPU will usually cache a whole line of data at once.
 
user406009
3:43 AM
Like when you read m[0][0], it will read and cache the stuff nearby as well. m[0][1] etc etc.
 
user406009
m[0][0] and m[1][0] are far enough away that m[1][0] will not be cached, but m[0][0] and m[0][1] are close enough that m[0][1] will be cached after reading m[0][0].
 
So it all goes back to spatial locality.
I see
 
user406009
Yep. And in C everything is "row major" for what it's worth.
 
and C couldn't do both
row and column
order
is that possible?
 
user406009
It is possible, but it would require some changes to how arrays are done/implemented.
 
user406009
3:46 AM
In C, a 2d array is simply an array of arrays, so there is less flexibility so it has to be row major.
 
user406009
@LuisAverhoff Of course, there is nothing preventing you from writing a custom matrix class which manually stores an array in column order.
 
Ok I see. So if you were to flatten a 2D array, it would just be one long 1D array in a row.
 
user406009
Yes.
 
that is why it is much easier to do row major order.
 
user406009
Well, it's all sorta arbitrary and shouldn't matter too much.
 
3:50 AM
and is this why quicksort is cache efficient because when it partitions, it makes use of all nearby elements in the array that the cpu stores in the cache?
 
user406009
As long as you remember which one your specific matrix is stored in.
 
user406009
@LuisAverhoff Yeah.
 
Besides making use of spatial and temporal locality, how else can you code that makes good use of the cache?
 
user406009
Those are the two main things IIRC. I'm not really an expert on this subject, but one other technique is trying to shrink the amount of data you are processing so more of it can fit in cache.
 
user406009
Using smaller integer sizes. Or integers instead of strings, etc.
 
3:56 AM
Ok I have another question in regards to reference variables and pointers.
hold on
My question lies within this link paste.ofcode.org/AwAYfFYRjckAwwXWAEvmZm
oops ignore the /.
 
user406009
The issue is that you are creating a temporary copy when you do int badInt = getInt();
 
user406009
If you do int& badInt = getInt(); to avoid the copy, the segmentation fault goes away.
 
what do you mean temporary copy?
 
user406009
Now the reason why you get a segmentation fault with the original code is because int badInt is stored on the stack. And you can't use delete on something stored on the stack.
 
didn't I allocate memory on the heap?
 
user406009
4:07 AM
Yes, but the copy is allocated on the stack.
 
user406009
@LuisAverhoff The reason why you have a temporary copy is because when you do int foo = whatever, you are creating a new variable foo.
 
user406009
@LuisAverhoff You are right, I should be more specific. It's not really a temporary copy. It's just that badInt is a copy of the return value of getInt();
 
how does adding an ampersand stop it from becoming a copy?
 
user406009
Because now badInt is a reference.
 
user406009
Here is a simple example to keep things straightforward:
 
user406009
4:10 AM
int a = 3;
int b = a;
int& c = a;
 
user406009
b will create a copy of a.
 
user406009
c will just refer to a.
 
user406009
&b will be equal to the address of b (which is different from &a).
 
Alright I think I got it.
 
user406009
Note that this sort of code would be considered very bad style. Returning references to things that the user has to delete is very awkward and dangerous.
 
user406009
4:11 AM
It makes it very easy to cause memory leaks.
 
now if instead I was returning a pointer from the function, then I would not have a problem referencing and deleting the pointer.
 
user406009
@LuisAverhoff Well, if you make the same copy int badInt = *getInt();, you would have the same issue.
 
no not that
 
user406009
But you are right if you do int& badInt, or int* badInt you will not have an issue.
 
I mean this int *badint = geInt();
 
user406009
4:14 AM
Yeah, that would be fine.
 
So even if you allocate memory to a variable in a function, if you deference it and return it, it is just as bad as returning a local variable because when you deference a pointer and return it(return *x), it gets treated as a local variable correct? In other words, you return the value and not the address.
 
user406009
If the function is returning a reference return *x isn't an issue.
 
user406009
Your original int& getInt() (where you used new inside) was technically OK.
 
user406009
The problem was the that you were trying to free a copy which was stored on the stack.
 
user406009
Actually, if you are returning *x by value, it shouldn't be an issue either.
 
user406009
4:19 AM
As that copy of *x is self contained.
 
user406009
The main problem would be the memory leak of x.
 
Yes because x will be deallocated
and you would not have any way to delete it.
 
user406009
This is why most people try to use smart pointers like unique_ptr to clean up the memory for you.
 
is it good practice to set a pointer to null after deleting to avoid a dangling pointer?
 
user406009
@LuisAverhoff The main reason to set it to null is to catch use after free bugs where you try to use it after you delete it.
 
user406009
4:25 AM
But yeah, it's somewhat common practice if only for that reason.
 
user406009
But you should really try to use smart pointers where this isn't an issue at all.
 
user406009
There are only a couple of places where you should be manually newing or deleting things.
 
user406009
A very small number of places.
 
user406009
Anyways, I need to go to bed. Good night.
 
See you.
 

« first day (78 days earlier)      last day (2780 days later) »