Working with 3D matrices

Discussion in 'C Programming' started by Frederic Soustra, Jan 30, 2006.

  1. Hi,
    I am trying to speed up some work I have to do with a 3D Matrix.

    If I am not mistaken, C is row major,
    hence the matrix
    A of size 2 x 2 x 2
    would be stored like this in memory:
    A[1][1][1],A[1][2][1],A[2][1][1],A[2][2][2],A[1][1][2],A[1][2][2],A[2][1][2],A[2][2][2]
    ?
    Am I correct, I need to work on Big 3D matrices, and I know that the way
    I traverse the matrices counts, which way is fastest? will gcc optimize
    this as to minimize the page jumps in memory?
    The matrix is declared using malloc so if A is n x n x d then i setup
    the matrix this way:

    A = (int***) malloc(n*sizeof(int));
    for(i = 0;i < n;i++){
    A = (int**) malloc(n*sizeof(int));
    for(j = 0;j < n;j++)
    A[j] = (int*) malloc(d*sizeof(int));
    }

    Is this a good way to declare the 3d Matrix? and am I traversing it
    correctly?

    Thank You for the help.

    Fred
     
    Frederic Soustra, Jan 30, 2006
    #1
    1. Advertising

  2. Frederic Soustra <> writes:
    > I am trying to speed up some work I have to do with a 3D Matrix.
    >
    > If I am not mistaken, C is row major,
    > hence the matrix
    > A of size 2 x 2 x 2
    > would be stored like this in memory:
    > A[1][1][1],A[1][2][1],A[2][1][1],A[2][2][2],A[1][1][2],A[1][2][2],A[2][1][2],A[2][2][2]
    > ?


    Um, not even close.

    First, C arrays are 0-based, not 1-based.

    Yes, C arrays are stored in row-major order. For

    int A[2][2][2];

    the order in memory would be:

    A[0][0][0]
    A[0][0][1]
    A[0][1][0]
    A[0][1][1]
    A[1][0][0]
    A[1][0][1]
    A[1][1][0]
    A[1][1][1]

    > Am I correct, I need to work on Big 3D matrices, and I know that the
    > way I traverse the matrices counts, which way is fastest? will gcc
    > optimize this as to minimize the page jumps in memory?


    Any relationship between the order in which you traverse the array and
    performance is implementation-specific; the language says nothing
    about it. If you want to know about optimizations performed by gcc,
    try one of the gnu.gcc.* newsgroups.

    > The matrix is declared using malloc so if A is n x n x d then i setup
    > the matrix this way:
    >
    > A = (int***) malloc(n*sizeof(int));
    > for(i = 0;i < n;i++){
    > A = (int**) malloc(n*sizeof(int));
    > for(j = 0;j < n;j++)
    > A[j] = (int*) malloc(d*sizeof(int));
    > }
    >
    > Is this a good way to declare the 3d Matrix? and am I traversing it
    > correctly?


    You haven't shown us the declaration of A.

    There are several ways to create a 3-dimensional array: an array of
    arrays of arrays, an array of arrays of pointers to arrays, and so
    forth. What you're doing here doesn't look right. You should never
    cast the result of malloc(). If A is an int***, it doesn't make sense
    to point it to something of size (n*sizeof(int)).

    Read question 6.16 in the C FAQ, at <http://www.c-faq.com/>. Then
    read the rest of section 6, then read the rest of the FAQ. If you
    still have questions, feel free to come back.

    --
    Keith Thompson (The_Other_Keith) <http://www.ghoti.net/~kst>
    San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
    We must do something. This is something. Therefore, we must do this.
     
    Keith Thompson, Jan 30, 2006
    #2
    1. Advertising

  3. Keith Thompson wrote:
    > Frederic Soustra <> writes:
    >
    >>I am trying to speed up some work I have to do with a 3D Matrix.
    >>
    >>If I am not mistaken, C is row major,
    >>hence the matrix
    >>A of size 2 x 2 x 2
    >>would be stored like this in memory:
    >>A[1][1][1],A[1][2][1],A[2][1][1],A[2][2][2],A[1][1][2],A[1][2][2],A[2][1][2],A[2][2][2]
    >>?

    >

    Thx, I was still thinking in matlab mode.
    >
    > Um, not even close.
    >
    > First, C arrays are 0-based, not 1-based.
    >
    > Yes, C arrays are stored in row-major order. For
    >
    > int A[2][2][2];
    >
    > the order in memory would be:
    >
    > A[0][0][0]
    > A[0][0][1]
    > A[0][1][0]
    > A[0][1][1]
    > A[1][0][0]
    > A[1][0][1]
    > A[1][1][0]
    > A[1][1][1]
    >
    >
    >>Am I correct, I need to work on Big 3D matrices, and I know that the
    >>way I traverse the matrices counts, which way is fastest? will gcc
    >>optimize this as to minimize the page jumps in memory?

    >
    >
    > Any relationship between the order in which you traverse the array and
    > performance is implementation-specific; the language says nothing
    > about it. If you want to know about optimizations performed by gcc,
    > try one of the gnu.gcc.* newsgroups.
    >
    >
    >>The matrix is declared using malloc so if A is n x n x d then i setup
    >>the matrix this way:
    >>


    >>A = (int***) malloc(n*sizeof(int));
    >>for(i = 0;i < n;i++){
    >> A = (int**) malloc(n*sizeof(int));
    >> for(j = 0;j < n;j++)
    >> A[j] = (int*) malloc(d*sizeof(int));
    >>}
    >>
    >>Is this a good way to declare the 3d Matrix? and am I traversing it
    >>correctly?

    >
    >
    > You haven't shown us the declaration of A.
    >
    > There are several ways to create a 3-dimensional array: an array of
    > arrays of arrays, an array of arrays of pointers to arrays, and so
    > forth. What you're doing here doesn't look right. You should never
    > cast the result of malloc(). If A is an int***, it doesn't make sense
    > to point it to something of size (n*sizeof(int)).
    >
    > Read question 6.16 in the C FAQ, at <http://www.c-faq.com/>. Then
    > read the rest of section 6, then read the rest of the FAQ. If you
    > still have questions, feel free to come back.
    >


    Thank you for pointing me to the FAQ,
    so according to the FAQ this is a correct setup for the 3D Matrix:

    int*** A = (int***) malloc(n*sizeof(int**));
    for(i = 0;i < n;i++){
    A = (int**) malloc(n*sizeof(int*));
    for(j = 0;j < n;j++)
    A[j] = (int*) malloc(d*sizeof(int));
    }
    and if I read your example of how it is stored in memory then,
    it is completely inneficient to build the matrix this way if i am
    traversing it in the following manner:
    for(l = 0; l < d; l++){
    for(i = 0;i <n;i++){
    for(j = 0;j < n;j++){
    /* do stuff with A[j][l]
    }
    }
    }

    Again correct me if I am wrong:
    If I traverse this matrix using l, then i then j as the indices then my
    declaration should look like this:


    int*** A = (int***) malloc(d*sizeof(int**));
    for(i = 0;i < d;i++){
    A = (int**) malloc(n*sizeof(int*));
    for(j = 0;j < n;j++)
    A[j] = (int*) malloc(n*sizeof(int));
    }


    Again thank you for pointing me to Q6.16, I had gone through the others
    but had not seen 6.16.

    Thanks a lot.

    Fred
     
    Frederic Soustra, Jan 30, 2006
    #3
  4. [...]

    >>> The matrix is declared using malloc so if A is n x n x d then i setup
    >>> the matrix this way:
    >>>

    >
    >>> A = (int***) malloc(n*sizeof(int));


    as Keith pointed out, never cast return of malloc
    are you using C++ compiler?
    if so then replace malloc with new

    >>> for(i = 0;i < n;i++){
    >>> A = (int**) malloc(n*sizeof(int));
    >>> for(j = 0;j < n;j++)
    >>> A[j] = (int*) malloc(d*sizeof(int));
    >>> }
    >>>


    here the same

    > and if I read your example of how it is stored in memory then,
    > it is completely inneficient to build the matrix this way if i am
    > traversing it in the following manner:
    > for(l = 0; l < d; l++){
    > for(i = 0;i <n;i++){
    > for(j = 0;j < n;j++){
    > /* do stuff with A[j][l]
    > }
    > }
    > }


    just as idea, you could do

    int dim1, dim2, dim3;
    int * large = malloc(sizeof(int) * dim1*dim2*dim3);

    inline int access_large(int i, int j, int k)
    { return large + i*dim2*dim3 + j*dim3 + k; }

    you can also provide DEBUG_ARRAY mode and check the ranges
    whether i,j,k are valid

    Regards, Daniel
     
    =?ISO-8859-1?Q?Sch=FCle_Daniel?=, Jan 30, 2006
    #4
  5. const int dim1 = 10, dim2 = 20, dim3 = 5;
    int * large = malloc(sizeof(int) * dim1*dim2*dim3);

    inline int * access_large(int i, int j, int k)
    { return large + i*dim2*dim3 + j*dim3 + k; }

    *acces_large(0,0,0) = 10;
    int xyz = *acces_large(0,0,0);
     
    =?ISO-8859-1?Q?Sch=FCle_Daniel?=, Jan 30, 2006
    #5
  6. In article <m2pDf.1905$> Frederic Soustra <> writes:
    > Thank you for pointing me to the FAQ,
    > so according to the FAQ this is a correct setup for the 3D Matrix:
    >
    > int*** A = (int***) malloc(n*sizeof(int**));
    > for(i = 0;i < n;i++){
    > A = (int**) malloc(n*sizeof(int*));
    > for(j = 0;j < n;j++)
    > A[j] = (int*) malloc(d*sizeof(int));
    > }


    This is not a three-dimensional array. A three-dimensional array would
    have the type "array of array of array of int". Your array has type
    "array of pointer to array of pointer to array of int".

    > and if I read your example of how it is stored in memory then,


    It is completely irrelevant. In the above example (with n = 2) you
    can not be sure that A[0][0][1] is followed by A[0][1][0].

    > it is completely inneficient to build the matrix this way if i am
    > traversing it in the following manner:
    > for(l = 0; l < d; l++){
    > for(i = 0;i <n;i++){
    > for(j = 0;j < n;j++){
    > /* do stuff with A[j][l]
    > }
    > }
    > }


    With your definition it is indeed extremely inefficient. When you
    have a true 3-dimensional array it may be inefficient, but that
    depends on how the cache of your processor works.
    --
    dik t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland, +31205924131
    home: bovenover 215, 1025 jn amsterdam, nederland; http://www.cwi.nl/~dik/
     
    Dik T. Winter, Jan 31, 2006
    #6
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. mkokelma

    split matrices

    mkokelma, Oct 21, 2004, in forum: VHDL
    Replies:
    5
    Views:
    757
    mkokelma
    Oct 22, 2004
  2. tommy

    matrices

    tommy, Dec 3, 2004, in forum: C++
    Replies:
    3
    Views:
    588
    Victor Bazarov
    Dec 3, 2004
  3. Prototipo

    Dynamic array of matrices

    Prototipo, Nov 1, 2003, in forum: C Programming
    Replies:
    3
    Views:
    436
  4. Nils Wagner
    Replies:
    1
    Views:
    485
    David M. Cooke
    Oct 22, 2004
  5. George Sakkis

    Sparse matrices

    George Sakkis, Sep 27, 2005, in forum: Python
    Replies:
    0
    Views:
    421
    George Sakkis
    Sep 27, 2005
Loading...

Share This Page