I have to compare two larger objects for equality.
我需要比较两个更大的物体。
Properties of the objects:
对象的属性:
- Contain all their members by value (so no pointers to follow).
- 按值包含所有成员(因此不需要跟随指针)。
- They also contain some
stl::array. - 它们还包含一些stl::array。
- They contain some other objects for which 1 and 2 hold.
- 它们包含了1和2持有的其他对象。
- Size is up to several kB.
- 大小高达几个kB。
- Some of the
memberswill more likely differ than others, therefore lead to a quicker break of the comparison operation if compared first. - 有些成员可能比其他成员的差异更大，因此如果首先进行比较，将导致比较操作更快地中断。
- The objects do not change. Basically, the algorithm is just to count how many objects are the same. Each object is only compared once against several "master" objects.
- 对象不会改变。基本上，算法就是计算有多少对象是相同的。每个对象只与几个“master”对象进行一次比较。
What is the best way to compare these objects? I see three options:
比较这些对象的最好方法是什么?我看到三个选项:
- Just use plain, non-overloaded
operator==. - 只需使用普通的、非重载的运算符==。
- Overload
==and perform a member-by-member comparison, beginning with members likely to differ. - 重载==，并执行成员之间的比较，以可能不同的成员开始。
- Overload
==and view the object as a plain byte field and compare word by word. - 重载==，将对象视为一个普通的字节字段，逐字进行比较。
Some thoughts:
Option 1 seems good because it means the least amount of work (and opportunities to introduce errors).
Option 2 seems good, because I can exploit the heuristic about which elements differ most likely. But maybe it's still slower because built-in ==of option 1 is ridiculously fast.
Option 3 seems to be most "low-level" optimized, but that's what the compiler probably also does for option 1.
一些想法:选项1看起来不错，因为它意味着最少的工作量(以及引入错误的机会)。选项2看起来不错，因为我可以利用关于哪些元素最有可能不同的启发式。但是它可能还是比较慢，因为内建==选项1的速度快得可笑。选项3似乎是最“低级”的优化，但是编译器可能也对选项1进行了优化。
So the questions are:
所以,问题是:
- Is there a well-known best way to solve the task?
- 有一种众所周知的最好的方法来解决这个问题吗?
- Is one of the options an absolute no-go?
- 其中一个选项是绝对不允许的吗?
- Do I have to consider something else?
- 我还需要考虑别的事情吗?
2 个解决方案
#1
2
A good question.
一个很好的问题。
If you have some heuristic about which members are likely to differ - use it. So that overloading operator == and checking suspected members first seems to be a good idea.
如果你有一些关于哪些成员可能不同的启发式——使用它。因此，首先检查可疑成员的重载操作符==似乎是一个好主意。
About byte-wise comparison (aka memcmp and friends) - may be problematic due to struct member alignment. I.e. the compiler sometimes puts "empty spaces" in your struct layout, so that each member will have required alignment. Those are not initialized and usually contain garbage.
关于字节比较(即memcmp和friends)——由于结构成员对齐可能会有问题。例如，编译器有时会在结构布局中放置“空空间”，以便每个成员都需要对齐。它们没有初始化，通常包含垃圾。
This may be solved by explicit zero-initializing of your whole object. But, I don't see any advantage of memcmp vs automatic operator ==, which is a members-wise comparison. It probably may save some code size (a single call to memcpy vs explicit reads and comparisons), however from the performance perspective this seems to be pretty much the same.
这可以通过对整个对象的显式零初始化来解决。但是，我没有看到memcmp与automatic operator =的任何优势，这是一个成员间的比较。它可能会节省一些代码大小(对memcpy和显式读取和比较的一次调用)，但是从性能的角度来看，这几乎是一样的。
#2
4
Default == is fast for small objects, but if you have big data members to compare, try to find some optimizations thinking about the specific data stored and the way they are update, redefining an overloaded == comparison operator more "smarter" than the default one.
对于小对象，Default == =是快速的，但是如果您要比较大数据成员，请尝试寻找一些优化，考虑存储的特定数据以及它们的更新方式，重新定义重载的== =比较操作符比默认的更“智能”。
As many already said, option 3 is wrong, due to the fact that fields generally are padded to respect the data-alignment, and for optimization reason the bytes added are not initialized to 0 (maybe this is done in the DEBUG version).
正如许多人已经说过的，选项3是错误的，因为字段通常被填充以尊重数据对齐，而且由于优化的原因，添加的字节没有初始化为0(可能这是在调试版本中完成的)。
I can suggest you to explore the option to divide the check in two stages:
我可以建议您探索将检查分为两个阶段的选项:
- first stage, create some sort of small & fast member that "compress" the status of the instance (think like an hash); this field could be updated every time some big field changes, for example the elements of the stl-array. Than check frequently changed fields and this "compress" status first to make a conservative comparison (for example, the sum of all int in the array, or maybe the xor)
- 第一阶段，创建某种小型和快速的成员来“压缩”实例的状态(像散列一样思考);这个字段可以在每次大字段更改时进行更新，例如stl数组的元素。而不是检查频繁更改的字段和这个“压缩”状态，首先要做一个保守的比较(例如，数组中的所有整数的和，或者xor)
- second stage, use an in-deep test for every members. This is the slowest but complete check, but likely will be activated only sometimes
- 第二阶段，对每个成员进行深入的测试。这是最慢但完整的检查，但可能只在某些时候被激活
#1
2
A good question.
一个很好的问题。
If you have some heuristic about which members are likely to differ - use it. So that overloading operator == and checking suspected members first seems to be a good idea.
如果你有一些关于哪些成员可能不同的启发式——使用它。因此，首先检查可疑成员的重载操作符==似乎是一个好主意。
About byte-wise comparison (aka memcmp and friends) - may be problematic due to struct member alignment. I.e. the compiler sometimes puts "empty spaces" in your struct layout, so that each member will have required alignment. Those are not initialized and usually contain garbage.
关于字节比较(即memcmp和friends)——由于结构成员对齐可能会有问题。例如，编译器有时会在结构布局中放置“空空间”，以便每个成员都需要对齐。它们没有初始化，通常包含垃圾。
This may be solved by explicit zero-initializing of your whole object. But, I don't see any advantage of memcmp vs automatic operator ==, which is a members-wise comparison. It probably may save some code size (a single call to memcpy vs explicit reads and comparisons), however from the performance perspective this seems to be pretty much the same.
这可以通过对整个对象的显式零初始化来解决。但是，我没有看到memcmp与automatic operator =的任何优势，这是一个成员间的比较。它可能会节省一些代码大小(对memcpy和显式读取和比较的一次调用)，但是从性能的角度来看，这几乎是一样的。
#2
4
Default == is fast for small objects, but if you have big data members to compare, try to find some optimizations thinking about the specific data stored and the way they are update, redefining an overloaded == comparison operator more "smarter" than the default one.
对于小对象，Default == =是快速的，但是如果您要比较大数据成员，请尝试寻找一些优化，考虑存储的特定数据以及它们的更新方式，重新定义重载的== =比较操作符比默认的更“智能”。
As many already said, option 3 is wrong, due to the fact that fields generally are padded to respect the data-alignment, and for optimization reason the bytes added are not initialized to 0 (maybe this is done in the DEBUG version).
正如许多人已经说过的，选项3是错误的，因为字段通常被填充以尊重数据对齐，而且由于优化的原因，添加的字节没有初始化为0(可能这是在调试版本中完成的)。
I can suggest you to explore the option to divide the check in two stages:
我可以建议您探索将检查分为两个阶段的选项:
- first stage, create some sort of small & fast member that "compress" the status of the instance (think like an hash); this field could be updated every time some big field changes, for example the elements of the stl-array. Than check frequently changed fields and this "compress" status first to make a conservative comparison (for example, the sum of all int in the array, or maybe the xor)
- 第一阶段，创建某种小型和快速的成员来“压缩”实例的状态(像散列一样思考);这个字段可以在每次大字段更改时进行更新，例如stl数组的元素。而不是检查频繁更改的字段和这个“压缩”状态，首先要做一个保守的比较(例如，数组中的所有整数的和，或者xor)
- second stage, use an in-deep test for every members. This is the slowest but complete check, but likely will be activated only sometimes
- 第二阶段，对每个成员进行深入的测试。这是最慢但完整的检查，但可能只在某些时候被激活