CODEWITHSUNDEEP
coptimizationdata-structures
upgrayedd
upgrayedd

Reputation: 129

C - Speed of Copying Data Structure Entirely vs Parts

I am working through "Data Structures and Program Design in C" by Kruse, Leung, and Tondo. Chapter 2, Section 2 presents a simple data structure (a list) and later asks the reader to write two different copy functions for the structure. The exercise in question is E2 and reads as follows:

Write functions that will copy one list to another list (as the structure type defined in the text). Use the following methods: (a) copy the entire structures; (b) use a loop to copy only the entries. Which version is easier to write? Which version will usually run faster, and why?

My question comes in with the last part of this exercise: "Which version will usually run faster, and why?". I am aware that copying the entire structure is faster, and my understanding suggests that this is because one can avoid the overhead of a loop. However, when I ran each I was surprised to find that copying the entire structure was not only faster but roughly 10x faster than copying each entry.

I was hoping someone may be able to explain to me why this is, or at least direct me to a source that could aid in my understanding. I tried reading through the assembly of the two functions I wrote, but my understanding of assembly is very basic at this point.

Thank you!

Relevant code:

#define MAXLIST 200 //maximum size of lists

extern void Error(const char *);

typedef struct coord_tag {
    int row;    //x
    int col;    //y
} Coord_type;

typedef Coord_type Entry_type;

typedef struct list_tag {
    int count;
    Entry_type entry[MAXLIST];
} List_type;

void Copy(List_type *lt, List_type *lf) //list "to" and list "from"
{
    if (lt == NULL || lf == NULL) {
        Error("list uninitialized");
    } else {
        *lt = *lf;
    }
}

void Copy2(List_type *lt, List_type *lf)
{
    if (lt == NULL || lf == NULL) {
        Error("list uninitialized");
    } else {
        int i;

        lt->count = lf->count;
        for (i = 0; i < lf->count; i++) {
            lt->entry[i] = lf->entry[i];
        }
    }
}

Upvotes: 0

Views: 240

Answers (1)

ldgabbay
ldgabbay

Reputation: 1183

You'd be surprised at how fast a straight memory copy can be! In assembly, there are instructions dedicated to fast memory copy. (e.g. REP MOVSB) Let's look at all the new interruptions the second copy introduces in each loop iteration:

  • i++
    • caches the original value of i
    • increments i in memory
    • finally returns the original value of i
  • lf->entry[i]
    • retrieves value of lf
    • retrieves value of i
    • adds i plus the offset of entry to lf
    • retrieves value at that address
  • lt->entry[i]
    • retrieves value of lt
    • retrieves value of i
    • adds i plus the offset of entry to lt
  • i < lf->count
    • retrieves value of lf
    • retrieves value of lf->count
    • retrieves value of i
    • compares i to lf->count

You can imagine why this would be 10x slower than an uninterrupted memory copy.

Upvotes: 1

Related Questions