UNIX Socket FAQ

A forum for questions and answers about network programming on Linux and all other Unix-like systems

You are not logged in.

  • Index
  • » C
  • » efficient equality comparison for 2d arrays

#1 2004-11-05 09:08 PM

socks
Member
Registered: 2004-09-27
Posts: 12

Re: efficient equality comparison for 2d arrays

What is the optimal way to test for equality between two 2D arrays?  I wrote some code that works but I don't know if it is optimal.  Could someone please post code that will run more efficiently than mine?  My comparision method is posted below:

Note: packet is a struct that contains a 2d array.  The 2D array called payload holds next hop info for a node and distance vector info.

int compare(packet  *array1, packet *array2, int row, int col)
{
  int result=1;
   int i, c;
   for(i=0; i<row; i++)
   {
     for(c=0; c<col; c++)
     {   
         if(array1->payload[i][c]!=array2->payload[i][c])
          {
           result=0;
           return result;
          }
     }
   }
return result;
}

Offline

#2 2004-11-05 10:35 PM

RobSeace
Administrator
From: Boston, MA
Registered: 2002-06-12
Posts: 3,829
Website

Re: efficient equality comparison for 2d arrays

If it's just strict exact equality in the entire array that you care
about, how about a simple memcmp()?  Ie:

int compare(packet  *array1, packet *array2, int row, int col)
{
    return (memcmp (array1->payload, array2->payload,
                                  sizeof (array1->payload[0][0]) * row * col));
}

Of course, if these are fixed-size non-dynamic arrays, you could
get away with dropping row and col args, and simply use
"sizeof (array1->payload)", too...

Offline

#3 2004-11-05 11:04 PM

socks
Member
Registered: 2004-09-27
Posts: 12

Re: efficient equality comparison for 2d arrays

Thanks. I just found out that memcmp and memcpy are very efficient methods because they were written in assembly is that true?  Other than using memcmp is there another way to optimize checking for equality between two 2D arrays (i.e. would mapipulating pointers so that the 2D array could be treated as a 1D array increase efficiency)?

Offline

#4 2004-11-06 07:32 PM

RobSeace
Administrator
From: Boston, MA
Registered: 2002-06-12
Posts: 3,829
Website

Re: efficient equality comparison for 2d arrays

Yes, generally, most decent libc's will have a very efficient
memcmp() and memcpy(), most likely written in highly optimized
assembly...  It's a pretty safe bet to assume you can't improve on
their efficiency, at least...

But, as for other methods not involving the use of optimized libc
functions...  Well, you might gain some slight efficiency by going
with your own pointer arithmetic instead of using indexing...  Ie.,
assuming "payload" is defined as a 2D array of ints:

int compare(packet  *array1, packet *array2, int row, int col)
{
    int *p1, *p2, *pend;
    p1 = (int*) (array1->payload);
    p2 = (int*) (array2->payload);
    pend = p1 + (row * col);
    for (; p1 < pend; p1++, p2++) {
        if (*p1 != *p2) return (*p1 - *p2);
    }
    return (0);
}

I wouldn't expect a very noticable increase in efficiency, though...
Though, if the arrays are fairly large and/or this comparison
function is called quite often, it might add up to a noticable amount...

Offline

#5 2010-10-22 03:21 AM

Andrew Phillips
Guest

Re: efficient equality comparison for 2d arrays

I only just stumbled upon this by accident but thought I should clarify some major problems with the replies as someone else might believe what is written here.

First in general you cannot use memcp() to compare 2-D arrays since there may be padding bytes at the end of each 1-D array.  The padding bytes may have garbage values which will prevent memcmp() from working.

BUT you can use it if any of these are true:
- padding is turned off (typically using #pragma pack(1)) - however this has performance penalties
- the element size is a multiple of the machine word size (or the current packing value set with #pragma pack) - ie there are no pad bytes
- array memory is cleared before use (eg, with calloc() or memset()) so padding bytes are always zero

Second you can often do a more efficient memory compare than memcmp if you have information about the alignment of the memory to compare.  For example, if the arrays were 4-byte aligned (whcih they probably are), then you could compare 32-bit values at a time and get close to 4 times the speed (at least 3 times).

Without getting too technical memcmp can't make any assumptions about alignment.  Of course, it could handle different alignment cases specially but in my experience most version of memcmp do not do this.  [Memcpy/memmove is a different matter as you don't have 2 pointers which may have different alignments as you do with memcmp.]

#6 2010-10-22 11:40 AM

i3839
Oddministrator
From: Amsterdam
Registered: 2003-06-07
Posts: 2,231

Re: efficient equality comparison for 2d arrays

The code posted shows clearly that it's an array of integers, so doing a memcmp() is fine,
there can't be any padding. Only way you can get padding in an array is when you have
an array of structures, which his not the case here.

Other than that, it's indeed a very good point to always keep padding in mind.

Some other remarks:

There are two kinds of padding: Padding within a structure, and padding between
array elements. For this particular use case disabling padding increases performance.
Having a structure that is a multiple of the word size is not sufficient because of the
above mentioned padding between structure members. Also, on 64 bits machines the
structures can be 64 bits aligned, so your structure has to be a multiple of 8 bytes,
not 4 to be sure there's no padding between the elements.

Memcmp() does keep alignment in mind, and does compare more than one byte at
a time. Glibc source code has this  to say about it:

/* The strategy of this memcmp is:

   1. Compare bytes until one of the block pointers is aligned.

   2. Compare using memcmp_common_alignment or
      memcmp_not_common_alignment, regarding the alignment of the other
      block after the initial byte operations.  The maximum number of
      full words (of type op_t) are compared in this way.

   3. Compare the few remaining bytes.  */

So it's not THAT easy to beat glibc's memcmp().

And in cases like this where it's very easy for gcc to figure out what you're doing,
it will most likely use it's own, faster, built-in memcmp optimised for exactly what
your doing at the moment (e.g. generate SIMD code).

One of the few cases where it can pay off to use your own thing instead of the
standard ones is when you're doing lots of comparisons on small memory chunks,
because the standard one is more optimised for big comparisons.

Offline

  • Index
  • » C
  • » efficient equality comparison for 2d arrays

Board footer

Powered by FluxBB