Accesing memory

Hi,
I am developing a program which priority is speed. The program is large and use a lot of datas. Many of them are stored as global variables.
I have read that global variables are slow access, as the processor don't store in the L2 cache. I have been thinking on it, but don't know exactly how to treat this issue. Most optimization techniques web pages I seen only give tips for speed code saving cycles, but none talk about accessing memory in an efficient way. I think this problem is not only for global variables, but all.
How can I address this problem? what are faster ways to access data.....
thx.
Best regards,
FS

Avoid global variables at all costs. And it's better to store data on the stack rather than on the heap, as well. Don't use a pointer for accessing data, if possibe, instead, use an index when iterating an array.
These are some small optimizations.
And global variables are still bad practice, so you may want to avoid them anyway.

Otherwise you might want to use a profiler to see bottlenecks in the app before prematurely optimizing things.

The L2 cache is part of the processor itself - and if it gets used or not used is decided by completely different things than what code your C compiler produces.

Global variables are cached just as much as local variables.

There are plenty of ways that you can make memory accessing more efficient, and of course, using caches efficiently is one of those things.

I should write up all I know about memory optimization as I have done quite a bit of research on that subject - but here's a summary:
1. Stuff that gets used together should be close together in memory (so don't use one array for your X, one for Y and one for Z coordinates in a 3D drawing application, use an array of X, Y, Z kept together) - that way, the cache will be loaded with the "other data" automatically, rather than having to drag in data from several different places.

2. Pay attention to read/modify/write loops, and try to use blocks where you read in, modify and write back a lump (say a few kilobytes at a time) of the data, storing the temporary results in a local variable. That way, the processor doesn't have to try to do both reads and writes "at the same time". This gets even better if you can use "non-temporal write" functionality that you can use (that means "bypass the cache when writing", as when you write data that you know you are not going to read again soon, it's better to NOT store it in the cache).

This is a paper written on the subject by Mike Wall at AMD, and he does know a thing or two about that.

Edit:
On the subject of global variables, what often happens is that the compiler will not be able to optimize the code quite as well as if you have local variables. For example:

Code:

---

#define SIZE 10000
int gVar[SIZE];
int func()
{
    int over5 = 0;
    int sum = 0;
    for(i = 0; i < SIZE; i++)
    {
        if (gVar[i] > 5)
            over5++;
        func2();
        sum += gVar[i];
    }
}

---

If the compiler can not determine that func2() is NOT accessing gVar in the above function, it can not keep gVar[i] in a register across the call to func2() - so it will have to re-read the memory again when it comes back from func2(), which can influence the execution time of the above function quite a bit.


--
Mats

Quote:

---

Originally Posted by Elysia

Avoid global variables at all costs. And it's better to store data on the stack rather than on the heap, as well. Don't use a pointer for accessing data, if possibe, instead, use an index when iterating an array.
These are some small optimizations.
And global variables are still bad practice, so you may want to avoid them anyway.

Otherwise you might want to use a profiler to see bottlenecks in the app before prematurely optimizing things.

---

Stack is unsuitable for storing LARGE amounts of data [more than about 1MB would blow most stacks].

But from a performance perspective, a global data is better than malloc'd data.

--
Mats

Global variables are evil, also in sense that some compilers, such as Visual C++ does not optimize them at all. It reads, performs some operation and writes back data directly.
Even if it did optimize it, it would have a hard time doing so because they can be accessed from everywhere at any time, which makes it a headache for the compiler to keep track of the variable sufficiently to optimize it.
Worse is if multiple threads were to write to the global variable. That could potentially hurt a lot. So global variables are definitely not a good thing for optimization.

Though i'll admit it may have curious effects when dumped in the L2 cache.
Perhaps the best way is simply to test your performance and use a profiler that can gather interesting data (for AMD, Codeanalyst does this).

Quote:

---

Originally Posted by matsp

Stack is unsuitable for storing LARGE amounts of data [more than about 1MB would blow most stacks].
But from a performance perspective, a global data is better than malloc'd data.

---

It's true that the stack isn't big enough to hold all data. This also implies to use it effectively and well since it's (potentially) faster to access data on the stack than via a pointer.

But from a compiler optimization perspective, a pointer can also point to memory shared by other components, so again, the compiler can't necessarily optimize it well.

--
Mats

Which comes around to using the stack whenever possible, to avoid bottlenecks where the compiler can't optimize well.
Another one is assume no aliasing (this would apply to Microsoft compilers), which I'm not quite what it does, but can help with compiler optimizations. But it requires the code to follow certain guidelines, however.

Yes, aliasing is where you have two pointers that (do or can) point to the same memory. If you assume that there is no aliasing, then the compiler can optimize memory access to memory via pointers, and store in registers in the local function. Here is an example where assuming no alias will break the code:

Code:

---

struct A
{
  int x;
  int y;
};

void func(struct a *A, struct A *b)
{
    b->x = a->x - a->y;
    a->x = b->x - b->y;    // if b == a, we have already changed a->x, and now get the wrong data.
}

int main()
{
  struct A a;
  func(&a, &a);
}

---

--
Mats

I think I'm actually going to experiment with aliasing and create a CDbgPtr to catch aliasing errors.
No aliasing might be a good way to optimize some things.

Basically, I am writting a chess engine.

Main problem is basically I only have four core functions:

search() -> recursive function to find best move
eval() -> function to evaluate current position with lot of data (king safety, mobility, pawn formation, etc....)
domove()
undomove()

Only four main functions, but handred of data
- positions of piezes, array of [64]
- color of piezes in position, again array [62]
- special bitboards (this are int of 64 bits to represent a special board conditions): where pawn are, bitboard of current squares near king, where white piezes are,...... I have newar 50 bitboards.....
- time management data (five or seven vars....)
- control vars (like current level, position is check, .....)
- other data like a stack where store all game move history, etc.

As you see, handreds of data for only 4!!! function. I can not copy to local vars because are so many datas than maybe I loose more time copying than working.

As a curiosity, my domove function make a new copy of current board position with memcpy and then change the new one with current move. Then undomove only has to point to last one (very few lines of code for this function). This, as I have read in a chess programming forum, is ineficcient. People has make a domove function which changes the current posicion, and undomove rechange to takeback (no memcpy trick). As I know, this is faster. My memcpy take lot of times to copy all vars...

Use pointers instead of copying all the data forth and back.
And yes, memcpy is slow because it needs to copy all the data. Use minimal changes if possible.

Quote:

---

Originally Posted by Elysia

Use pointers instead of copying all the data forth and back.

---

What is better? to have global pointers to global vars, or to pass pointer to global structs in functions parameter?

Maybe there is a better efficient way of organizing global data , i.e. struct grouping. is that better optimized for the compiler?

Quote:

---

Originally Posted by Kempelen

What is better? to have global pointers to global vars, or to pass pointer to global structs in functions parameter?

---

If this is the case, then removing the data as global is better. The more local data is, the better chance the compiler has to optimize it.

Quote:

---

Maybe there is a better efficient way of organizing global data , i.e. struct grouping. is that better optimized for the compiler?

---

Grouping things together in a struct might not be a bad idea as mats points out since it will mean data is close to each other.
However, it can still be done without making the actual data global.

Avoid globals. They will make a mess of maintaining the code.

You'll definitely want to check out the premier chess programming site:

http://64.68.157.89/forum/index.php

Particularly the Programming and Technical Discussion Forum. Regulars include World Chess Programming Champions and top competitors, and just amateurs, as well.

If you want to see how your chess program is (or is not) making progress, there are sites dedicated to testing amateur chess programs in tournaments, if they are stable enough to run well. Tom's Simple Chess Program (early versions), called just TSCP, used to be a standard program to test your own, against. Be warned though - Tom got a bit tired of his program being such a door mat for testing, and put in some strength in the later versions.

Have fun!

Sorting out your algorithm should be the first step.

Avoiding global variables, for the reason Elysia and I have stated (it makes the compiler better at optimizing the code) is a fair comment - but be aware that local variables are limited in size, so don't overdo it.

Have a read of the performance cpwiki:
http://cpwiki.sourceforge.net/Perfor...d_optimization

--
Mats

Quote:

---

Originally Posted by Adak

You'll definitely want to check out the premier chess programming site:

http://64.68.157.89/forum/index.php

Particularly the Programming and Technical Discussion Forum. Regulars include World Chess Programming Champions and top competitors, and just amateurs, as well.

If you want to see how your chess program is (or is not) making progress, there are sites dedicated to testing amateur chess programs in tournaments, if they are stable enough to run well. Tom's Simple Chess Program (early versions), called just TSCP, used to be a standard program to test your own, against. Be warned though - Tom got a bit tired of his program being such a door mat for testing, and put in some strength in the later versions.

Have fun!

---

Thx for the info. I'm a assidous reader of that forum. I'm a novice in this area, but is addictive and fun.
Best regards,