Quick way to zero array

Discussion in 'C Programming' started by rocketman768@gmail.com, May 12, 2006.

  1. Guest

    Man, that title should be in a poem, but anyways...So, I have this
    program, and it has an array of 40 million elements. The problem is
    that I have a for loop that continually is doing stuff to this array,
    and for each iteration, I have to zero out the array. This is how I am
    currently doing it: // Zero out the lnscores for( count=0; count <
    chunksize; count++ ) lnscores[count] = 0; Is there no quicker way
    to do this? I know there must be a trick since this array is one big
    contiguous chunk of memory right?
    , May 12, 2006
    #1
    1. Advertising

  2. prax Guest

    memset( lnscores, 0, chunksize )
    prax, May 12, 2006
    #2
    1. Advertising

  3. Ben C Guest

    On 2006-05-12, <> wrote:
    > Man, that title should be in a poem, but anyways...So, I have this
    > program, and it has an array of 40 million elements. The problem is
    > that I have a for loop that continually is doing stuff to this array,
    > and for each iteration, I have to zero out the array. This is how I am
    > currently doing it: // Zero out the lnscores for( count=0; count <
    > chunksize; count++ ) lnscores[count] = 0; Is there no quicker way
    > to do this? I know there must be a trick since this array is one big
    > contiguous chunk of memory right?


    memset(lnscores, 0, chunksize * sizeof lnscores[0]);

    Assuming 0 is represented by 0... what type is lnscores?
    Ben C, May 12, 2006
    #3
  4. Vladimir Oka Guest

    opined:

    > Man, that title should be in a poem, but anyways...So, I have this
    > program, and it has an array of 40 million elements. The problem is
    > that I have a for loop that continually is doing stuff to this array,
    > and for each iteration, I have to zero out the array. This is how I
    > am
    > currently doing it: // Zero out the lnscores for( count=0; count <
    > chunksize; count++ ) lnscores[count] = 0; Is there no quicker
    > way to do this? I know there must be a trick since this array is one
    > big contiguous chunk of memory right?


    If your array has file scope you don't even have to zero it yourself.
    All such variables get zeroed at startup. Otherwise, declare it and
    initialise thus:

    int lnscores[WHATEVER_SIZE] = {0};

    If you have to re-zero it afterwards, you could use `memset()`.

    --
    Worlds are conquered, galaxies destroyed -- but a woman is always a
    woman.
    -- Kirk, "Conscience of the King", stardate unknown

    <http://clc-wiki.net/wiki/Introduction_to_comp.lang.c>
    Vladimir Oka, May 12, 2006
    #4
  5. Michael Mair Guest

    schrieb:
    > Man, that title should be in a poem, but anyways...So, I have this
    > program, and it has an array of 40 million elements. The problem is
    > that I have a for loop that continually is doing stuff to this array,
    > and for each iteration, I have to zero out the array. This is how I am
    > currently doing it: // Zero out the lnscores for( count=0; count <
    > chunksize; count++ ) lnscores[count] = 0; Is there no quicker way
    > to do this? I know there must be a trick since this array is one big
    > contiguous chunk of memory right?


    As you did not tell us what type lnscores has, there is no
    definite "quickest" way.
    If lnscores[count] = 0 means that all bits of lnscores[count] are
    set to zero, you can use memset() to zero out all bits.

    Otherwise, you can use memcpy():
    -zero out lnscores[0]
    -memcpy() lnscores[0] to lnscores[1]
    -memcpy() lnscores[0] and lnscores[1] to lnscores[2] and lnscores[3]
    ....
    -memcpy() lnscores[0], ..., and lnscores[16777215] to
    lnscores[16777215], ..., and lnscores[33554431]
    - Last step (no doubling):
    memcpy() lnscores[0], ..., and lnscores[6445567] to
    lnscores[33554431], ..., and lnscores[39999999]

    This _may_ be quicker than the loop itself. It may be slower if
    your compiler recognizes the "zero out" pattern and does something
    intelligent.

    Try it out and measure.

    Cheers
    Michael
    --
    E-Mail: Mine is an /at/ gmx /dot/ de address.
    Michael Mair, May 12, 2006
    #5
  6. shisheng li Guest

    if not all elements will be used, there are some methods to just zero out as
    fewer as needed
    <> wrote in message
    news:...
    > Man, that title should be in a poem, but anyways...So, I have this
    > program, and it has an array of 40 million elements. The problem is
    > that I have a for loop that continually is doing stuff to this array,
    > and for each iteration, I have to zero out the array. This is how I am
    > currently doing it: // Zero out the lnscores for( count=0; count <
    > chunksize; count++ ) lnscores[count] = 0; Is there no quicker way
    > to do this? I know there must be a trick since this array is one big
    > contiguous chunk of memory right?
    >
    shisheng li, May 12, 2006
    #6
  7. wrote:
    > Man, that title should be in a poem, but anyways...So, I have this
    > program, and it has an array of 40 million elements. The problem is
    > that I have a for loop that continually is doing stuff to this array,
    > and for each iteration, I have to zero out the array. This is how I am
    > currently doing it: // Zero out the lnscores for( count=0; count <
    > chunksize; count++ ) lnscores[count] = 0; Is there no quicker way
    > to do this? I know there must be a trick since this array is one big
    > contiguous chunk of memory right?
    >


    Why do you have to zero the array? Are you only doing something to a
    few elements at each iteration? While there may be a fast C function
    that zeros arrays, unless you have a parallel machine you can't zero
    all cells at once, so this is likely to be costly. I suggest you
    seek a better algorithm--for example, whenever you update an element
    in an iteration, before you leave that loop, zero that element, so
    the whole array returns to the zeroed state.

    --
    Julian V. Noble
    Professor Emeritus of Physics
    University of Virginia
    Julian V. Noble, May 12, 2006
    #7
  8. Himanshu Chauhan <> writes:
    > Julian V. Noble wrote:
    >> Why do you have to zero the array?

    >
    > Zeroing out any piece of allocated memory is necessary to avoid
    > unforeseen results, which are annoying most of the time.


    It's not always necessary. For example, if you can keep track of
    which elements of the array you're currently using, you don't have to
    worry about what's in the other elements. The best approach depends
    on what you're actually doing with the array.

    [...]
    > You can use "calloc" for allocating for the first time. It already
    > returns memory region fillled with zero. Then memset or bzero are also
    > good option.
    > I mostly use bzero for such things.


    calloc() and memset() will set the array contents to all-bits-zero.
    If you have an array of integers, it will set each element to 0. If
    it's an array of some pointer or floating-point type, it will
    *probably* do so, but it's no guaranteed (the language doesn't
    guarantee that a floating-point 0.0 is represented as all-bits-zero).

    bzero() is non-standard, and might not exist on all systems.

    It's not obvious that memset() will be faster than a loop explicitly
    setting each element to zero. You should measure the performance of
    the code.

    --
    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, May 12, 2006
    #8
  9. Flash Gordon Guest

    Himanshu Chauhan wrote:
    > Julian V. Noble wrote:
    >>
    >> Why do you have to zero the array?

    >
    > Zeroing out any piece of allocated memory is necessary to avoid
    > unforeseen results, which are annoying most of the time.


    Depends on whether all bits zero is a valid initialiser. It is not
    necessarily valid for floats, doubles or pointers.

    >> Are you only doing something to a
    >> few elements at each iteration? While there may be a fast C function
    >> that zeros arrays, unless you have a parallel machine you can't zero
    >> all cells at once, so this is likely to be costly. I suggest you
    >> seek a better algorithm--for example, whenever you update an element
    >> in an iteration, before you leave that loop, zero that element, so
    >> the whole array returns to the zeroed state.

    >
    > That's a good idea.
    >
    > You can use "calloc" for allocating for the first time. It already
    > returns memory region fillled with zero. Then memset or bzero are also
    > good option.
    > I mostly use bzero for such things.


    Why choose the non-standard bzero when there is a perfectly standard memset?

    > BTW, 40 million elements array, are u doing image processing or some
    > other kind of signal processing?


    Please don't use stupid contractions like u for you.
    --
    Flash Gordon, living in interesting times.
    Web site - http://home.flash-gordon.me.uk/
    comp.lang.c posting guidelines and intro:
    http://clc-wiki.net/wiki/Intro_to_clc

    Inviato da X-Privat.Org - Registrazione gratuita http://www.x-privat.org/join.php
    Flash Gordon, May 12, 2006
    #9
  10. Guest

    > BTW, 40 million elements array, are u doing image processing or some > other kind of signal processing? Close. I'm doing some quadratic field sieve work. The program is actually quite fast. I factored a 203-bit number in about 9 hours on a 2.8GHz P4. >> Why do you have to zero the array? It has to do with keeping a score (hence the name "lnscore") of the residues modulo n. I process 40 million each go-round and then look at the scores to see if they are high-enough to progress through the algorithm. I usually get 1,000 that pass out of 40 million residues which are then narrowed down to around 10 numbers that I am actually looking for. It will find these 10 in around 11 seconds. Granted, I actually have to find tens of thousands of these before I can factor anything. >> I suggest you >> seek a better algorithm--for example, whenever you update an element >> in an iteration, before you leave that loop, zero that element, so >> the whole array returns to the zeroed state. No, this will not work. I have thought about it, and there is just no way to do it. Like I said, my program spits out the scores into lnscores (this is actually the "sieve" part of the QFS...it's pretty fast), and then I must search through the scores to take out the best ones. Only then can I return everything to zero. Oh, and I tried using memset(), but it was not any faster than the loop I had, and it hung after one iteration. So, still looping for now. Thanks for all the replies. I didn't expect so many :)
    , May 12, 2006
    #10
  11. <> wrote in message
    news:...
    > > BTW, 40 million elements array, are u doing image processing or some

    > other kind of signal processing?


    <corrected header...>
    > "Julian V. Noble" <> wrote in message

    news:e42j9c$q9f$...
    >> I suggest you
    >> seek a better algorithm--for example, whenever you update an element
    >> in an iteration, before you leave that loop, zero that element, so
    >> the whole array returns to the zeroed state.


    > No, this will not work. I have thought about it, and there is just no way
    > to do it. Like I said, my program spits out the scores into lnscores
    > (this is actually the "sieve" part of the QFS...it's pretty fast), and

    then
    > I must search through the scores to take out the best ones. Only then
    > can I return everything to zero. Oh, and I tried using memset(), but
    > it was not any faster than the loop I had, and it hung after one

    iteration.
    > So, still looping for now. Thanks for all the replies. I didn't expect so

    many :)

    In regards to:

    > I must search through the scores to take out the best ones.


    You didn't read Keith's post. A simple approach (I'll mention a better one
    further down) is to use a second array of unsigned char. As you assign a
    value to elements in array lnscores[], set an "in use" indicator in the
    second array. Then you only need to clear and search through the in_use
    array to find valid lnscores[]. Let's say your array is 40 instead of 40
    million:

    unsigned long lnscores[40];
    unsigned char in_use[40];

    memset(in_use,0,40); /* clear in use array */

    /* in loop finding potential residues */
    lnscores[index]=somevalue;
    in_use[index]=1; /* all non-used in_use values are 0 */

    /* in loop searching for potential residues */
    if (in_use[index]) /* if not in use skip */
    {
    /* look at lnscores[index] */
    }

    This will reduce clearing 40 million large values to 40 million small
    values.

    Now that you (hopefully) understood that, a better approach is to hash
    function or stack to just store the indexes of values you modified. This
    would reduce the number of values you need to clear to the peak number of
    residues.


    Rod Pemberton
    Rod Pemberton, May 12, 2006
    #11
  12. Julian V. Noble wrote:
    >
    > Why do you have to zero the array?


    Zeroing out any piece of allocated memory is necessary to avoid
    unforeseen results, which are annoying most of the time.

    >Are you only doing something to a
    > few elements at each iteration? While there may be a fast C function
    > that zeros arrays, unless you have a parallel machine you can't zero
    > all cells at once, so this is likely to be costly. I suggest you
    > seek a better algorithm--for example, whenever you update an element
    > in an iteration, before you leave that loop, zero that element, so
    > the whole array returns to the zeroed state.
    >


    That's a good idea.

    You can use "calloc" for allocating for the first time. It already
    returns memory region fillled with zero. Then memset or bzero are also
    good option.
    I mostly use bzero for such things.

    BTW, 40 million elements array, are u doing image processing or some
    other kind of signal processing?

    cheers,

    --Himanshu

    --
    +-----------------------------------+
    | Himanshu Singh Chauhan |
    | MCA (Final Year) |
    | I.G. National Open University |
    | Delhi (India) |
    | |
    | Contact: |
    +-----------------------------------+
    Himanshu Chauhan, May 13, 2006
    #12
  13. daizisheng Guest

    aha
    there are more efficient methods
    u know TAOCP, by Knuth
    there is a mazing method as this:

    suppose the array u will use is A[N], where N maybe very large, such as 40
    Million
    then u just need another two array, such as B[N] & C[N], all of them are of
    integer type

    #define N (40 * 1024 * 1024)
    int A[N], B[N], C[N];
    int cnt = 0;

    //u just only need to reset the counter *cnt*

    //when u need to refer an element such as A
    //u first check
    int t = B;
    if(t >= 0 && t < N && C[t] == i) {
    //that's ok, this element has been accessed before, so it must be goood
    }else{
    //this element has not been initalized
    A = 0;
    C[cnt] = i;
    B = cnt++;
    }

    //so, this is really maybe the best, *when u need, u do that!*

    "Rod Pemberton" <> wrote in message
    news:e432h7$m1u$...
    >
    > <> wrote in message
    > news:...
    > > > BTW, 40 million elements array, are u doing image processing or some

    > > other kind of signal processing?

    >
    > <corrected header...>
    > > "Julian V. Noble" <> wrote in message

    > news:e42j9c$q9f$...
    > >> I suggest you
    > >> seek a better algorithm--for example, whenever you update an element
    > >> in an iteration, before you leave that loop, zero that element, so
    > >> the whole array returns to the zeroed state.

    >
    > > No, this will not work. I have thought about it, and there is just no

    way
    > > to do it. Like I said, my program spits out the scores into lnscores
    > > (this is actually the "sieve" part of the QFS...it's pretty fast), and

    > then
    > > I must search through the scores to take out the best ones. Only then
    > > can I return everything to zero. Oh, and I tried using memset(), but
    > > it was not any faster than the loop I had, and it hung after one

    > iteration.
    > > So, still looping for now. Thanks for all the replies. I didn't expect

    so
    > many :)
    >
    > In regards to:
    >
    > > I must search through the scores to take out the best ones.

    >
    > You didn't read Keith's post. A simple approach (I'll mention a better

    one
    > further down) is to use a second array of unsigned char. As you assign a
    > value to elements in array lnscores[], set an "in use" indicator in the
    > second array. Then you only need to clear and search through the in_use
    > array to find valid lnscores[]. Let's say your array is 40 instead of 40
    > million:
    >
    > unsigned long lnscores[40];
    > unsigned char in_use[40];
    >
    > memset(in_use,0,40); /* clear in use array */
    >
    > /* in loop finding potential residues */
    > lnscores[index]=somevalue;
    > in_use[index]=1; /* all non-used in_use values are 0 */
    >
    > /* in loop searching for potential residues */
    > if (in_use[index]) /* if not in use skip */
    > {
    > /* look at lnscores[index] */
    > }
    >
    > This will reduce clearing 40 million large values to 40 million small
    > values.
    >
    > Now that you (hopefully) understood that, a better approach is to hash
    > function or stack to just store the indexes of values you modified. This
    > would reduce the number of values you need to clear to the peak number of
    > residues.
    >
    >
    > Rod Pemberton
    >
    >
    daizisheng, May 13, 2006
    #13
  14. daizisheng Guest

    "daizisheng" <> wrote in message
    news:e43gda$6f7$99.com...
    > aha
    > there are more efficient methods
    > u know TAOCP, by Knuth
    > there is a mazing method as this:
    >
    > suppose the array u will use is A[N], where N maybe very large, such as 40
    > Million
    > then u just need another two array, such as B[N] & C[N], all of them are

    of
    > integer type
    >
    > #define N (40 * 1024 * 1024)
    > int A[N], B[N], C[N];
    > int cnt = 0;
    >
    > //u just only need to reset the counter *cnt*
    >
    > //when u need to refer an element such as A
    > //u first check
    > int t = B;
    > if(t >= 0 && t < N && C[t] == i) {

    sorry for a mistake
    the condition is
    if(t >= 0 && t < cnt && C[t] == i)
    > //that's ok, this element has been accessed before, so it must be goood
    > }else{
    > //this element has not been initalized
    > A = 0;
    > C[cnt] = i;
    > B = cnt++;
    > }
    >
    > //so, this is really maybe the best, *when u need, u do that!*
    >
    > "Rod Pemberton" <> wrote in message
    > news:e432h7$m1u$...
    > >
    > > <> wrote in message
    > > news:...
    > > > > BTW, 40 million elements array, are u doing image processing or some
    > > > other kind of signal processing?

    > >
    > > <corrected header...>
    > > > "Julian V. Noble" <> wrote in message

    > > news:e42j9c$q9f$...
    > > >> I suggest you
    > > >> seek a better algorithm--for example, whenever you update an element
    > > >> in an iteration, before you leave that loop, zero that element, so
    > > >> the whole array returns to the zeroed state.

    > >
    > > > No, this will not work. I have thought about it, and there is just no

    > way
    > > > to do it. Like I said, my program spits out the scores into lnscores
    > > > (this is actually the "sieve" part of the QFS...it's pretty fast), and

    > > then
    > > > I must search through the scores to take out the best ones. Only then
    > > > can I return everything to zero. Oh, and I tried using memset(), but
    > > > it was not any faster than the loop I had, and it hung after one

    > > iteration.
    > > > So, still looping for now. Thanks for all the replies. I didn't expect

    > so
    > > many :)
    > >
    > > In regards to:
    > >
    > > > I must search through the scores to take out the best ones.

    > >
    > > You didn't read Keith's post. A simple approach (I'll mention a better

    > one
    > > further down) is to use a second array of unsigned char. As you assign

    a
    > > value to elements in array lnscores[], set an "in use" indicator in the
    > > second array. Then you only need to clear and search through the in_use
    > > array to find valid lnscores[]. Let's say your array is 40 instead of

    40
    > > million:
    > >
    > > unsigned long lnscores[40];
    > > unsigned char in_use[40];
    > >
    > > memset(in_use,0,40); /* clear in use array */
    > >
    > > /* in loop finding potential residues */
    > > lnscores[index]=somevalue;
    > > in_use[index]=1; /* all non-used in_use values are 0 */
    > >
    > > /* in loop searching for potential residues */
    > > if (in_use[index]) /* if not in use skip */
    > > {
    > > /* look at lnscores[index] */
    > > }
    > >
    > > This will reduce clearing 40 million large values to 40 million small
    > > values.
    > >
    > > Now that you (hopefully) understood that, a better approach is to hash
    > > function or stack to just store the indexes of values you modified.

    This
    > > would reduce the number of values you need to clear to the peak number

    of
    > > residues.
    > >
    > >
    > > Rod Pemberton
    > >
    > >

    >
    >
    daizisheng, May 13, 2006
    #14
  15. Malcolm Guest

    "Flash Gordon" <> wrote
    >
    >> I mostly use bzero for such things.

    >
    > Why choose the non-standard bzero when there is a perfectly standard
    > memset?
    >

    If memset isn't fast enough, probably the only way is to go for a
    non-standard function.

    Actually bzero is probably just a slightly different memset(), but many
    machines have hardware for clearing memory buffers in parallel. There's no
    easy way to give an ANSI C interface to this sort of operation, but normally
    you would set the operation going, do something else, and then check a flag
    to see if it had completed.

    The other solution is to use an algorithm that doesn't require the array to
    be initialised.
    --
    www.personal.leeds.ac.uk/~bgy1mm
    Malcolm, May 13, 2006
    #15
    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. JKop
    Replies:
    11
    Views:
    856
  2. Zhiqiang Ye
    Replies:
    53
    Views:
    10,220
    Dan Pop
    Jun 28, 2004
  3. Gerard Flanagan
    Replies:
    3
    Views:
    432
    Terry Hancock
    Nov 19, 2005
  4. Christopher Benson-Manica

    Doubles and zero/negative zero

    Christopher Benson-Manica, Jun 30, 2004, in forum: C Programming
    Replies:
    4
    Views:
    659
    Walter
    Jul 1, 2004
  5. Replies:
    23
    Views:
    838
    Chris Thomasson
    Aug 29, 2007
Loading...

Share This Page