你见过的最核心的优化是什么？

Question

你见过的最核心的优化是什么？

我不是在谈论算法的东西(例如使用quicksort而不是bubblesort),而我不是在讨论像循环展开之类的简单事情.

我在谈论硬核的东西.像Tiny Teensy ELF,Mel的故事 ; 几乎所有在demoscene,等等.

Answer 1

我曾经写过一个暴力RC5密钥搜索,一次处理两个密钥,第一个密钥使用整数流水线,第二个密钥使用SSE流水线,两个密钥在指令级交错.然后将其与管理程序结合使用,该程序在系统中的每个核心上运行代码实例.总的来说,代码运行速度比原始C版本快25倍.

我是维护者,这是一个宠物项目.评论很好,我将两个管道的代码放在他们自己的列中,以便更容易理解. (10认同)
"我将两个管道的代码放在他们自己的列中,以便更容易理解" - 很棒的主意.我想我永远不会想到这一点. (8认同)
如果可以,我会给你+2:一个用于代码,另一个用于双列代码.辉煌^ 2! (3认同)
是的,同样的...这实际上非常棒. (2认同)

Answer 2

Cra*_*rks 15

在我使用的一个(这里未命名的)视频游戏引擎中,他们重写了模型导出工具(将Maya网格变成游戏加载的东西),这样它实际上不会发出数据,而是实际发出精确的流渲染特定模型所必需的微指令.它使用遗传算法来找到在最小循环次数内运行的遗传算法.也就是说,给定模型的数据格式实际上是一个完美优化的子程序,用于渲染该模型.因此,将网格绘制到屏幕意味着将其加载到内存中并分支到其中.

(这不是用于PC,而是用于具有与CPU分离且并行的向量单元的控制台.)

Answer 3

sin*_*e j 10

在DOS的早期,当我们使用软盘进行所有数据传输时,也存在病毒.病毒感染不同计算机的一种常见方法是将病毒引导程序复制到插入的floppydisc的引导程序中.当用户将floppydisc插入另一台计算机并重新启动而不记得移除软盘时,病毒就会运行并感染硬盘启动器,从而永久感染主机PC.我被感染的一种特殊的令人讨厌的病毒被称为"Form",为了对抗这一点,我编写了一个具有以下功能的自定义软盘bootsector:

验证主机硬盘的bootsector并确保它没有被感染.
验证软盘引导扇区并确保它没有被感染.
如果病毒被感染,请从硬盘中删除病毒的代码.
如果按下特殊键,则将防病毒引导程序复制到另一张软盘的代码.
如果一切正常,则启动硬盘的代码,并且没有发现感染.

这是在bootsector的程序空间中完成的,大约440字节:)

我的伙伴最大的问题是显示非常神秘的消息,因为我需要所有代码空间.它就像"FFVD RM？",意思是"检测到FindForm病毒,删除？"

我很满意这段代码.优化是程序大小,而不是速度.装配中有两种完全不同的优化.

Answer 4

Gra*_*ers 9

我最喜欢的是通过整数运算的浮点反平方根.这是关于如何存储浮点值并且可以更快执行的一个很酷的小问题(即使执行1 /结果比股票标准平方根函数更快)或者产生比标准方法更准确的结果.

在c/c ++中,代码是:(来自维基百科)

float InvSqrt (float x)
{
    float xhalf = 0.5f*x;
    int i = *(int*)&x;
    i = 0x5f3759df - (i>>1);   // Now this is what you call a real magic number
    x = *(float*)&i;
    x = x*(1.5f - xhalf*x*x);
    return x;
}

我在invsqrts上运行了一堆时间(http://assemblyrequired.crashworks.org/2009/10/16/timing-square-root/).短故事是,`_frsqrte` - 所述SSE*标量*运算用于估计平方根倒数 - 比InvSqrt(),它是大于1.0 /`FSQRT`快6倍的速度的四倍.在PowerPC上,情况有所不同; 在那里,由于加载命中存储问题,InvSqrt()是一场彻底的灾难. (2认同)

Answer 5

j_r*_*ker 7

非常生物学优化

快速背景: DNA核苷酸三联体(A,C,G和T)编码氨基酸,这些氨基酸与蛋白质结合,蛋白质是大多数生物的组成部分.

通常,每种不同的蛋白质需要单独的DNA三联体序列(其"基因")来编码其氨基酸 - 因此例如长度为30,40和50的3种蛋白质总共需要90 + 120 + 150 = 360个核苷酸.然而,在病毒中,空间是非常宝贵的 - 因此有些病毒会重叠不同基因的DNA序列,因为有6个可能的"阅读框架"用于DNA到蛋白质的翻译(即从一个位置开始)可以被3整除;从3除以余数1的位置;或从3除以余数2的位置;再次相同,但反过来读取序列.)

为了比较:尝试编写一个x86汇编语言程序,其中300字节函数doFoo()从偏移量0x1000开始......另一个200字节函数doBar()从偏移量0x1001开始!(我为这次比赛提出一个名字:你比乙肝更聪明吗？)

这是硬核空间优化!

更新:链接到更多信息:

维基百科上的阅读框架表明,乙型肝炎和"大麦黄矮病毒"(一种植物病毒)都与阅读框架重叠.
维基百科上的乙型肝炎基因组信息.似乎不同的阅读框亚基产生表面蛋白的不同变异.
或者你可以谷歌搜索"重叠阅读框"
似乎这甚至可能发生在哺乳动物身上! 在第二个哺乳动物基因中广泛重叠的阅读框是玛丽莲科扎克2001年的一篇科学论文,该论文讨论了"广泛重叠阅读框"的大鼠"第二"基因.(这是相当令人惊讶的,因为哺乳动物的基因组结构为单独的蛋白质提供了足够的空间来分离基因.)我自己并没有超越摘要.

Answer 6

Luc*_*cas 7

几年前,我用65816汇编语言为Apple IIgs写了一个基于磁贴的游戏引擎.这是一台相当慢的机器,"在金属上"编程是哄骗可接受性能的虚拟要求.

为了快速更新图形屏幕,必须将堆栈映射到屏幕,以便使用一些特殊指令,允许用户仅在5个机器周期内更新4个屏幕像素.这并不是特别奇妙,在IIgs Tech Note#70中有详细描述.硬核位是我必须组织代码以使其足够灵活以成为通用库同时仍保持最大速度的方式.

我将图形屏幕分解为扫描线并创建了一个246字节的代码缓冲区来插入专门的65816操作码.需要246个字节,因为图形屏幕的每条扫描线宽80字,每端需要1个附加字以便平滑滚动.推送有效地址(PEA)指令占用3个字节,因此3*(80 + 1 + 1)= 246个字节.

通过跳转到对应于屏幕右边缘的246字节代码缓冲区内的地址并将BRanch Always(BRA)指令修补到紧随最左边单词后面的单词的代码中来呈现图形屏幕.BRA指令将带符号的8位偏移量作为其参数,因此它几乎没有跳出代码缓冲区的范围.

即便这样也不是太困难,但真正的硬核优化就在这里.我的图形引擎实际上支持两个独立的背景图层和动画图块,使用不同的3字节代码序列,具体取决于模式:

背景1使用推送有效地址(PEA)指令
背景2使用加载间接索引(LDA($ 00),y)指令,然后是推送(PHA)
动画磁贴使用加载直接页索引(LDA $ 00,x)指令后跟推送(PHA)

关键限制是65816寄存器(X和Y)都用于引用数据,不能修改.此外,直接页面寄存器(D)是基于第二背景的原点设置的,并且不能改变; 数据库寄存器设置为保存第二背景的像素数据的数据库,不能更改; 堆栈指针(S)映射到图形屏幕,因此不可能跳转到子程序并返回.

鉴于这些限制,我需要快速处理即将被推入堆栈的单词混合的情况,即一半来自背景1,一半来自后台2.我的解决方案是交换内存以获得速度.因为所有正常寄存器都在使用中,所以我只能使用程序计数器(PC)寄存器.我的解决方案如下:

定义一个代码片段,在与代码缓冲区相同的64K程序库中进行混合
为82个单词中的每个单词创建此代码的副本
存在1-1对应关系,因此代码片段的返回可以是硬编码的地址
完成!我们有一个硬编码的子程序,不会影响CPU寄存器.

这是实际的代码片段

code_buff:   PEA $0000            ; rightmost word (16-bits = 4 pixels)
             PEA $0000            ; background 1
             PEA $0000            ; background 1
             PEA $0000            ; background 1
             LDA (72),y           ; background 2
             PHA
             LDA (70),y           ; background 2
             PHA
             JMP word_68          ; mix the data
word_68_rtn: PEA $0000            ; more background 1
             ...
             PEA $0000
             BRA *+40             ; patched exit code

             ...                  
word_68:     LDA (68),y           ; load data for background 2
             AND #$00FF           ; mask
             ORA #$AB00           ; blend with data from background 1
             PHA
             JMP word_68_rtn      ; jump back
word_66:     LDA (66),y
             ...

Run Code Online (Sandbox Code Playgroud)

最终结果是接近最佳的阻击器,具有最小的开销,并且在具有1 MB/s存储器总线的2.5MHz CPU上以320x200的速度输出超过15帧/秒.

Answer 7

Mic*_*urr 5

迈克尔·阿布拉什(Michael Abrash)的" 汇编语言之禅 "(Zen of Assembly Language)有一些漂亮的东西,不过我承认我不记得我头脑中的细节.

实际上,似乎Abrash所写的一切都有一些漂亮的优化内容.

Answer 8

lep*_*pie 3

斯大林计划编译器在这方面相当疯狂。

归档时间：	17 年前
查看次数：	2120 次
最近记录：	13 年，4 月前