Accesing memory

This is a discussion on Accesing memory within the C Programming forums, part of the General Programming Boards category; Hi, I am developing a program which priority is speed. The program is large and use a lot of datas. ...

  1. #1
    Registered User
    Join Date
    Feb 2008
    Posts
    145

    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

  2. #2
    C++まいる!Cをこわせ! Elysia's Avatar
    Join Date
    Oct 2007
    Posts
    22,171
    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.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.
    For information on how to enable C++11 on your compiler, look here.
    よく聞くがいい!私は天才だからね! ^_^

  3. #3
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    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
    Last edited by matsp; 04-18-2008 at 04:22 AM.
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  4. #4
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Quote Originally Posted by Elysia View Post
    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
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  5. #5
    C++まいる!Cをこわせ! Elysia's Avatar
    Join Date
    Oct 2007
    Posts
    22,171
    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 View Post
    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.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.
    For information on how to enable C++11 on your compiler, look here.
    よく聞くがいい!私は天才だからね! ^_^

  6. #6
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    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
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  7. #7
    C++まいる!Cをこわせ! Elysia's Avatar
    Join Date
    Oct 2007
    Posts
    22,171
    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.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.
    For information on how to enable C++11 on your compiler, look here.
    よく聞くがいい!私は天才だからね! ^_^

  8. #8
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    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
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  9. #9
    C++まいる!Cをこわせ! Elysia's Avatar
    Join Date
    Oct 2007
    Posts
    22,171
    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.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.
    For information on how to enable C++11 on your compiler, look here.
    よく聞くがいい!私は天才だからね! ^_^

  10. #10
    Registered User
    Join Date
    Feb 2008
    Posts
    145
    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...

  11. #11
    C++まいる!Cをこわせ! Elysia's Avatar
    Join Date
    Oct 2007
    Posts
    22,171
    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 Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.
    For information on how to enable C++11 on your compiler, look here.
    よく聞くがいい!私は天才だからね! ^_^

  12. #12
    Registered User
    Join Date
    Feb 2008
    Posts
    145
    Quote Originally Posted by Elysia View Post
    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?

  13. #13
    C++まいる!Cをこわせ! Elysia's Avatar
    Join Date
    Oct 2007
    Posts
    22,171
    Quote Originally Posted by Kempelen View Post
    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.

    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.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.
    For information on how to enable C++11 on your compiler, look here.
    よく聞くがいい!私は天才だからね! ^_^

  14. #14
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    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!

  15. #15
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    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
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

Page 1 of 2 12 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. tools for finding memory leaks
    By stanlvw in forum C++ Programming
    Replies: 4
    Last Post: 04-03-2009, 11:41 AM
  2. Replies: 4
    Last Post: 01-13-2008, 01:14 AM
  3. Question regarding Memory Leak
    By clegs in forum C++ Programming
    Replies: 29
    Last Post: 12-07-2007, 12:57 AM
  4. Memory problem with Borland C 3.1
    By AZ1699 in forum C Programming
    Replies: 16
    Last Post: 11-16-2007, 10:22 AM
  5. Shared Memory - shmget questions
    By hendler in forum C Programming
    Replies: 1
    Last Post: 11-29-2005, 01:15 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21