C - 完全复制数据结构与部分复制数据结构的速度

Question

我正在学习 Kruse、Leung 和 Tondo 所著的“C 语言数据结构和程序设计”。第 2 章第 2 节介绍了一个简单的数据结构(列表)，随后要求读者为该结构编写两个不同的复制函数。该练习是 E2，内容如下:

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?

我的问题来自本练习的最后部分:“哪个版本通常运行得更快，为什么？”。我知道复制整个结构更快，并且我的理解表明这是因为可以避免循环的开销。然而，当我运行每个条目时，我惊讶地发现复制整个结构不仅比复制每个条目更快，而且大约快 10 倍。

我希望有人能够向我解释这是为什么，或者至少引导我找到可以帮助我理解的来源。我尝试通读我编写的两个函数的汇编，但目前我对汇编的理解还很基础。

谢谢!

相关代码:

#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];
        }
    }
}

Answer 1

您会对直接内存复制的速度感到惊讶!在汇编中，有专门用于快速内存复制的指令。 (例如 REP MOVSB)让我们看看第二个副本在每次循环迭代中引入的所有新中断:

• 我++
  • 缓存 i 的原始值
  • 增加内存中的 i
  • 最终返回i的原始值
• lf->条目[i]
  • 检索 lf 的值
  • 检索 i 的值
  • 将 i 加上条目的偏移量添加到 lf
  • 检索该地址的值
• lt->条目[i]
  • 检索 lt 的值
  • 检索 i 的值
  • 将 i 加上条目的偏移量添加到 lt
• i < lf->计数
  • 检索 lf 的值
  • 检索 lf->count 的值
  • 检索 i 的值
  • 将 i 与 lf->count 进行比较

您可以想象为什么这会比不间断的内存复制慢 10 倍。