Cel*_*tas 24 language-agnostic algorithm performance assembly swap
我知道不使用它们,但是有一些技术可以在不使用第三个变量的情况下交换两个变量,例如
x ^= y;
y ^= x;
x ^= y;
和
x = x + y
y = x - y
x = x - y
在课堂上,教授提到这些在20年前很流行,当时内存非常有限,至今仍在高性能应用中使用.这是真的？我对使用这种技术毫无意义的理解是:
那么是否有时间不与第三个变量交换？它更快吗？
相比之下,使用XOR的方法与使用+/-更快的方法相比？大多数架构都有一个加/减和XOR的单位,所以这并不意味着它们的速度都相同吗？或者仅仅因为CPU有一个操作单元并不意味着它们的速度都相同？
Erw*_*out 21
对于编写普通洗衣机固件的程序员来说,这些技术仍然很重要.许多类型的硬件仍然在Z80 CPU或类似产品上运行,通常不超过4K内存.在那个场景之外,正如你所说,知道这些算法"技巧"就像没有真正的实际用途一样好.
(我确实想说,尽管如此,那些记住并且知道这种东西的程序员经常会变成更好的程序员,甚至是"常规"应用程序,而不是那些不会打扰他们的"同行".正是因为后者经常采取这种行为.那种"记忆力足够大"的态度太过分了.)
gna*_*729 14
完全没有意义.这是为了表现出聪明才智.考虑到它在许多情况下(浮点,指针,结构)不起作用,是不可读的,并且使用三个相关操作,这将比仅交换值慢得多,它绝对没有意义并且表明实际上不聪明.
你是对的,如果它更快,那么优化编译器会在交换两个数字时检测到模式,并替换它.这很容易做到.但是编译器确实会注意到你交换两个变量并且根本不会产生任何代码,但之后会开始使用不同的变量.例如,如果你交换x和y,那么写一个+ = x; b + = y; 编译器可能只是将其更改为+ = y; b + = x; .另一方面,xor或加/减模式将无法识别,因为它非常罕见且不会得到改进.
Yes, there is, especially in assembly code.
Processors have only a limited number of registers. When the registers are pretty full, this trick can avoid spilling a register to another memory location (posssibly in an unfetched cacheline).
I've actually used the 3 way xor to swap a register with memory location in the critical path of high-performance hand-coded lock routines for x86 where the register pressure was high, and there was no (lock safe!) place to put the temp. (on the X86, it is useful to know the the XCHG instruction to memory has a high cost associated with it, because it includes its own lock, whose effect I did not want. Given that the x86 has LOCK prefix opcode, this was really unnecessary, but historical mistakes are just that).
Morale: every solution, no matter how ugly looking when standing in isolation, likely has some uses. Its good to know them; you can always not use them if inappropriate. And where they are useful, they can be very effective.
这样的结构对于PIC系列微控制器的许多成员都是有用的,这些成员要求几乎所有操作都通过单个累加器("工作寄存器")[注意,虽然这有时可能是一个障碍,但事实上它只是必需的每个指令编码一个寄存器地址和一个目标位,而不是两个寄存器地址,这使得PIC可以拥有比其他微控制器更大的工作集].
如果工作寄存器保存一个值并且必须将其内容与RAM的内容交换,则替代:
xorwf other,w ; w=(w ^ other)
xorwf other,f ; other=(w ^ other)
xorwf other,w ; w=(w ^ other)
将会
movwf temp1 ; temp1 = w
movf other,w ; w = other
movwf temp2 ; temp2 = w
movf temp1,w ; w = temp1 [old w]
movwf other ; other = w
movf temp2,w ; w = temp2 [old other]
三条指令,无额外存储,六条指令和两条额外寄存器.
顺便提一下,在希望制作另一个寄存器的情况下,另一个有用的技巧是保持其当前值或W的最大值,之后不再需要W的值.
subwf other,w ; w = other-w
btfss STATUS,C ; Skip next instruction if carry set (other >= W)
subwf other,f ; other = other-w [i.e. other-(other-oldW), i.e. old W]
我不确定有多少其他处理器有减法指令但没有非破坏性比较,但在这样的处理器上,技巧可能是一个很好的知道.
如果你想在内存或两个整个寄存器中交换两个完整的单词,这些技巧不太可能有用.如果你没有空闲寄存器(或者只有一个空闲寄存器用于存储器到存储器交换)并且没有可用的"交换"指令(比如在x86中交换两个SSE寄存器)或"交换"时,你仍然可以利用它们.指令太昂贵(如xchgx86中的寄存器存储器)并且无法避免交换或降低寄存器压力.
但如果您的变量是单个字中的两个位域,则修改3-XOR方法可能是一个好主意:
y = (x ^ (x >> d)) & mask
x = x ^ y ^ (y << d)
这个片段来自Knuth的"计算机编程艺术"第一卷.4A.秒.7.1.3.这y只是一个临时变量.要交换的两个位域都在x.mask用于选择位域,d是位域之间的距离.
你也可以在硬度证明中使用这样的技巧(以保持平面性).例如,请参阅此幻灯片中的交叉小工具(第7页).这是由教授在"算法下限"的最近讲座.Erik Demaine.