小编tts*_*ras的帖子

我正在阅读Agner Fog的优化手册，并且遇到了这个例子：

double data[LEN];

void compute()
{
    const double A = 1.1, B = 2.2, C = 3.3;

    int i;
    for(i=0; i<LEN; i++) {
        data[i] = A*i*i + B*i + C;
    }
}

Agner 指出，有一种方法可以优化此代码 - 通过认识到循环可以避免使用昂贵的乘法，而是使用每次迭代应用的“增量”。

我用一张纸来证实这个理论，首先......

...当然，他是对的 - 在每次循环迭代中，我们可以通过添加“增量”，基于旧结果计算新结果。该增量从值“A+B”开始，然后每一步增加“2*A”。

所以我们将代码更新为如下所示：

void compute()
{
    const double A = 1.1, B = 2.2, C = 3.3;
    const double A2 = A+A;
    double Z = A+B;
    double Y = C;

    int i;
    for(i=0; i<LEN; i++) {
        data[i] …

我最近在Python程序员面前发现了一个关于F#的演示文稿,看了之后,我决定自己实现"蚂蚁拼图"的解决方案.

有一只蚂蚁可以在平面网格上走动.蚂蚁可以一次向左,向右,向上或向下移动一个空间.也就是说,从单元格(x,y),蚂蚁可以进入单元格(x + 1,y),(x-1,y),(x,y + 1)和(x,y-1).蚂蚁无法访问x和y坐标的数字之和大于25的点.例如,点(59,79)是不可访问的,因为5 + 9 + 7 + 9 = 30,大于25.问题是:如果从(1000,1000)开始,蚂蚁可以访问多少个点,包括(1000,1000)本身？

我首先在30行OCaml中实现了我的解决方案,并尝试了它:

$ ocamlopt -unsafe -rectypes -inline 1000 -o puzzle ant.ml
$ time ./puzzle
Points: 148848

real    0m0.143s
user    0m0.127s
sys     0m0.013s

整洁,我的结果与leonardo在D和C++中的实现相同.与leonardo的C++实现相比,OCaml版本的运行速度比C++慢大约2倍.这是好的,因为leonardo使用队列来删除递归.

然后我将代码翻译成F# ......这就是我得到的:

Thanassis@HOME /g/Tmp/ant.fsharp
$ /g/Program\ Files/FSharp-2.0.0.0/bin/fsc.exe ant.fs
Microsoft (R) F# 2.0 Compiler build 2.0.0.0
Copyright (c) Microsoft Corporation. All Rights Reserved.

Thanassis@HOME /g/Tmp/ant.fsharp
$ ./ant.exe

Process is terminated due to StackOverflowException.
Quit …

我总是对学习新语言感兴趣,这一事实让我保持警惕,让我(我相信)成为更好的程序员.我征服Haskell的尝试来了又走 - 到目前为止两次 - 我决定是时候再试一次.第三次是魅力吧？

不.我重新阅读了我的旧笔记......并感到失望:-(

上次让我失去信心的问题很简单:整数的排列.即从整数列表到列表列表 - 列表的排列:

[int] -> [[int]]

这实际上是一个普遍的问题,因此用'a'替换上面的'int'仍然适用.

从我的笔记:

我先自己编码,然后成功.欢呼!

我将我的解决方案发送给我的一位好朋友--Haskell大师,通常有助于向大师学习 - 他告诉我这个,据我所知,"表达了语言的真正力量,使用通用设施来编码你的需要".所有这一切,我最近喝了kool-aid,让我们走吧:

permute :: [a] -> [[a]]
permute = foldr (concatMap.ins) [[]]
   where ins x []     = [[x]]
         ins x (y:ys) = (x:y:ys):[ y:res | res <- ins x ys]

嗯.让我们打破这个:

bash$ cat b.hs
ins x []     = [[x]]
ins x (y:ys) = (x:y:ys):[ y:res | res <- ins x ys]

bash$ ghci
Prelude> :load b.hs
[1 of 1] Compiling Main             ( b.hs, interpreted …

几年前,我通过动态编程解决了一个问题:

https://www.thanassis.space/fillupDVD.html

解决方案是用Python编写的.

作为拓展视野的一部分,我最近开始学习OCaml/F#.有什么更好的方法来测试水域,而不是直接将我用Python编写的命令式代码移植到F# - 并从那里开始,逐步向功能性编程解决方案迈进.

第一个直接端口的结果令人不安:

在Python下:

  bash$ time python fitToSize.py
  ....
  real    0m1.482s
  user    0m1.413s
  sys     0m0.067s

在FSharp下:

  bash$ time mono ./fitToSize.exe
  ....
  real    0m2.235s
  user    0m2.427s
  sys     0m0.063s

(如果您注意到上面的"mono":我在Windows下测试过,使用Visual Studio - 速度相同).

至少可以说,我......感到困惑.Python比F#运行代码更快？使用.NET运行时编译的二进制文件运行SLOWER而不是Python的解释代码？!？!

我知道VM的启动成本(在这种情况下为单声道)以及JIT如何改进Python等语言的东西,但仍然......我期望加速,而不是减速!

我也做错了吗？

我在这里上传了代码:

https://www.thanassis.space/fsharp.slower.than.python.tar.gz

请注意,F#代码或多或少是Python代码的直接逐行转换.

PS当然还有其他的好处,例如F#提供的静态类型安全性 - 但如果在F#下强制算法的结果速度更差......至少可以说,我很失望.

编辑:根据评论中的要求直接访问:

Python代码:https: //gist.github.com/950697

FSharp代码:https: //gist.github.com/950699

我在许多Python程序中都使用了yield,在很多情况下它确实清除了代码.我在博客上写了这篇文章,这是我网站的热门网页之一.

C#还提供了收益 - 它通过调用者端的状态保持来实现,通过自动生成的类来完成,该类保持状态,函数的局部变量等.

我目前正在阅读有关C++ 0x及其添加的内容; 在阅读有关C++ 0x中lambda的实现时,我发现它也是通过自动生成的类完成的,配备了存储lambda代码的operator().我心中形成了一个自然的问题:他们是为lambdas做过的,他们为什么不考虑支持"收益"呢？

当然,他们可以看到合作例程的价值......所以我只能猜测他们认为基于宏的实现(例如Simon Tatham的)是一个充分的替代品.然而,它们不是出于多种原因:被调用者保持状态,非重入状态,基于宏观(仅此一点是足够的理由)等.

编辑: yield不依赖于垃圾收集,线程或光纤.您可以阅读Simon的文章,看看我在谈论编译器进行简单的转换,例如:

int fibonacci() {
    int a = 0, b = 1;
    while (true) {
        yield a;
        int c = a + b;
        a = b;
        b = c;
    }
}

成:

struct GeneratedFibonacci {
    int state;
    int a, b;

    GeneratedFibonacci() : state (0), a (0), b (1) {}

    int operator()() {
        switch (state) {
        case 0:
            state = 1;
            while (true) { …

假设我有一个模板(称为ExampleTemplate),它带有两个参数:容器类型(例如list,vector)和包含的类型(例如float,bool等).由于容器实际上是模板,因此该模板具有模板参数.这是我必须写的:

#include <vector>
#include <list>

using namespace std;

template < template <class,class> class C, typename T>
class ExampleTemplate {
    C<T,allocator<T> > items;
public:
    ....
};

main()
{
    ExampleTemplate<list,int> a;
    ExampleTemplate<vector,float> b;
}

你可能会问什么是"分配器"的事情.好吧,最初,我尝试了显而易见的事情......

template < template <class> class C, typename T>
class ExampleTemplate {
    C<T> items;
};

...但遗憾的是我发现了分配器的默认参数......

   vector<T, Alloc>
   list<T, Alloc>
   etc

...必须在模板声明中明确地"保留".正如您所看到的,这会使代码变得更加丑陋,并迫使我重现模板参数的默认值(在本例中为分配器).

哪个是坏的.

编辑:问题不是关于容器的具体问题 - 它是关于"模板参数模板中的默认值",以上只是一个例子.答案取决于STL容器具有":: value_type"的知识不是我所追求的.想想一般问题:如果我需要在模板ExampleTemplate中使用模板参数C,那么在ExampleTemplate的主体中,我是否必须在使用它时重现C的默认参数？如果必须,那不会引入不必要的重复和其他问题(在这种情况下,C是STL容器,可移植性问题 - 例如"allocator")？

我喜欢F#; 我真的,真的.被"函数式编程"咬了之后,我强迫自己在有机会的时候使用它.事实上,我最近使用它(在一个星期的休假期间)来编写一个很好的AI算法.

但是,我尝试到目前为止(见与我第一次尝试一个SO问题在这里)似乎表明,虽然无疑是美丽的...... F#有我用过的所有语言中最慢的执行速度.

我在代码中做错了吗？

我在博客文章中详细解释了我的所作所为,在我的实验中,我看到OCaml和其他组的运行速度比F#快5到35倍.

我是唯一一个有这种经历的人吗？我觉得令人沮丧的是,我最喜欢的语言也是最慢的 - 有时到目前为止......

编辑:直接GitHub链接,代码以各种语言形式存在...

编辑2:感谢托马斯和丹尼尔,速度大大提高:

• 最大的速度提升:从"参考"转变为"可变"提供了高达30%的速度.
• 删除异常并使用while/flagChecks给了另外16%.
• 从歧视的工会转向枚举,又增加了5%.
• "内联"给出了0.5-1%

编辑3:Jon Harrop博士加入了战斗:60%的加速,使得ScoreBoard直接在"枚举"版本的数据上运行.现在,F#的命令版本运行速度比C++慢3-4倍,这对于基于VM的运行时来说是一个很好的结果.我认为问题解决了 - 谢谢你们!

EDIT4:在合并所有优化之后,这些就是结果(F#以命令式的方式达到C# - 现在,如果我只能做一些关于功能风格的话!)

• 真正的0m0.221s:那是C++
• 真正的0m0.676s:那是C#(命令式,C++镜像)
• 真正的0m0.704s:那是F#(命令式,C++镜像)
• 真正的0m0.753s:那是OCaml(命令式,C++镜像)
• 真正的0m0.989s:那是OCaml(功能)
• 真正的0m1.064s:那是Java(势在必行)
• 真正的0m1.955s:那是F#(功能)

几十年来我一直在和VIM合作,而且我已经非常精通了它.然而,我被Emacs's诱惑了org-mode,为了尝试它,我安装了Emacs和Evil.

Evil满足了我与VIM相关的大部分肌肉记忆,所以我继续我的测试org-mode- 并且遇到了我的第一个问题:当我在自己的窗口中生成Emacs(即emacs plan.org)然后TAB关键工作,打开和关闭我的计划部分就好了.但是,TAB当我在文本模式下使用Emacs时(即在我的XTerms中,通过"emacs -nw plan.org"),什么都不做.这是我最感兴趣的状态,因为我通常通过SSH连接在screen/tmux内部工作.

如果它与邪恶模式发生冲突,我不明白为什么 - 我不知道VIM正常模式下的任何TAB功能(这是我们在打开/关闭org-mode部分时所处的位置).

任何Emacs-guru在那里提出了为什么会发生这种情况的建议？

在阅读了Eli Bendersky 关于通过Python协同程序实现状态机的文章后,我想......

• 看他在Python3下运行的例子
• 并为生成器添加适当的类型注释

我成功完成了第一部分(但是没有使用async defs或yield froms,我基本上只是移植了代码 - 所以任何改进都是最受欢迎的).

但是我需要一些关于协同程序类型注释的帮助:

#!/usr/bin/env python3

from typing import Callable, Generator

def unwrap_protocol(header: int=0x61,
                    footer: int=0x62,
                    dle: int=0xAB,
                    after_dle_func: Callable[[int], int]=lambda x: x,
                    target: Generator=None) -> Generator:
    """ Simplified protocol unwrapping co-routine."""
    #
    # Outer loop looking for a frame header
    #
    while True:
        byte = (yield)
        frame = []  # type: List[int]

        if byte == header:
            #
            # Capture the full frame
            # …

执行摘要:如何在代码中指定OpenMP应该只为REAL内核使用线程,即不计算超线程的线程？

详细分析:多年来,我在空闲时间编写了一个仅限SW的开源渲染器(光栅化器/光线跟踪器).可以从这里获得GPL代码和Windows二进制文件:https: //www.thanassis.space/renderer.html 它在Windows,Linux,OS/X和BSD下编译并运行良好.

我上个月推出了一种光线追踪模式 - 生成的图片质量飙升.不幸的是,光线跟踪比光栅化要慢几个数量级.为了提高速度,就像我对光栅化器一样,我为光线跟踪器添加了OpenMP(和TBB)支持 - 以便轻松利用额外的CPU内核.光栅化和光线跟踪都很容易进行线程化(每个三角形工作 - 每像素工作).

在家里,凭借我的Core2Duo,第二核心帮助了所有模式 - 光栅化和光线跟踪模式的加速都在1.85x和1.9x之间.

问题:当然,我很想看到CPU的最高性能(我也玩"GPU",初步的CUDA端口),所以我想要一个坚实的基础进行比较.我把代码交给了我的一个好朋友,他可以使用16英寸,1500美元英特尔超级处理器的"野兽"机器.

他以"最重"模式运行它,光线跟踪模式......

......他的速度是我的Core2Duo的五分之一(!)

喘气 - 恐怖.刚刚发生了什么？

我们开始尝试不同的修改,补丁,......最终我们弄明白了.

通过使用OMP_NUM_THREADS环境变量,可以控制生成的OpenMP线程数.随着线程数从1增加到8,速度增加(接近线性增加).在我们越过8的那一刻,速度开始减弱,直到我的Core2Duo速度的五分之一,当使用所有16​​个核心时!

为什么8？

因为8是真实核心的数量.其他8个是...超线程的!

理论:现在,这对我来说是新闻 - 我看到超线程在其他算法中帮助很多(高达25%),所以这是出乎意料的.显然,即使每个超线程核心都有自己的寄存器(和SSE单元？),光线跟踪器也无法利用额外的处理能力.这引导我思考......

它可能不是缺乏处理能力 - 它是内存带宽.

光线跟踪器使用边界体积层次结构数据结构来加速光线三角形交叉.如果使用的芯超线程,则每个在一对"逻辑核"的,试图从在该数据结构不同的地方(即,在存储器中),以读 - 和CPU高速缓存(每对本地)完全捶打.至少,这是我的理论 - 任何建议都是最受欢迎的.

所以,问题是: OpenMP检测"核心"的数量并产生与之匹配的线程 - 也就是说,它包括计算中的超线程"核心".就我而言,这显然会导致灾难性的结果,速度方面.有谁知道如何使用OpenMP API(如果可能的话,可移植)只为REAL内核生成线程,而不是超线程的线程？

PS代码是开放的(GPL),可在上面的链接中找到,随时可以在您自己的机器上重现 - 我猜这将在所有超线程CPU中发生.

PPS原谅帖子的长度,我认为这是一种教育经历,想分享.