SPOJ#15 The Shortest Path

原題:SHPATH

题意很简单,但是因为测试数据非常庞大,非常容易超时。推荐使用Dijkstra+BinaryHeap的算法,不过我的程序是没有通过的,Python写的代码光是读取数据就要用8s,并且即使读取结束,也总会运行时错误。

在tutorial组的题目中有一个Turtle’s Shortest Path TSHPATH,题目完全一样,测试数据也一样,除了时间限制很宽松,可以用来测试程序是否正确。

我后来编写了C版本的Dijkstra+BinaryHeap的代码,却总是WA,而用我自己特地生成的随机数据进行测试结果却完全正确(对比了问牛人要来的代码运行的结果)。

下面是我的代码,如果有牛人路过,希望能指出其中的错误:

Python版(我记得有些许小错误,因为某些数据和C版本不一致),C版本

gengraph测试数据生成脚本,不过可能会产生孤点。

在SpiderMonkey中产生可调用的对象

我应该对标题做一个更详细的解释:用C语言在SpiderMonkey中产生一个在JavaScript中可以当成函数被调用的对象,换句话说,就是一个非Function的对象,在JavaScript中可以被当成Function进行调用。例如,我有一个Hash对象,当我在var h = new Hash()之后,可以直接调用h(key),h并非一个函数对象,却可以以这种函数调用的方式来获取键key对应的值。

首先,必须要在创建这个Hash类的结构时,将JSClass中的”call”字段设置为相应的函数,如下:

现在,这里有一个很关键的问题便是如何在SpiderMonkey调用call_hash函数的时候,能够让call_hash函数知道被调用的对象(callee)是谁。然而,Mozilla的官方文档并没有对此作出任何解释。于是我在邮件列表中问了这个问题,有人给出了一个很特别的技巧——引擎调用call函数的时候,argv[-2]便是被调用者本身。


在把玩了Spidermonkey一段时间之后,我还是打算放弃spidermonkey,虽然这是一个很成熟很强大的脚本引擎,但是他的API还是有些混乱的,从本文的这个问题的解决方案就可以看得出来。

提领类型双关的指针将破坏强重叠规则

最近复习C/C++,今日用APR编写了一个生产/消费模型的小程序。结果出现了这样一个奇怪的警告:“提领类型双关的指针将破坏强重叠规则”,让我大惑不解,特此和大家讨论一下。

我用的是gcc 版本 4.2.3 (Ubuntu 4.2.3-2ubuntu7) 线程模型:posix。出现警告的这段是这样的:

虽然可以运行无误,但该警告还是让我比较无奈,最后我改成了如下:

因为很久没有写C,在这里,我的问题是:

  1. 什么叫做“提领类型双关的指针”?
  2. 什么是“强重叠规则”?
  3. 为什么会破坏?
  4. 破坏之后会引发什么问题?

希望有C/C++达人能解决我这些疑问,谢谢。

附源代码:main.c

Windows上配置Code::Blocks + wxWidgets

27号晚上我问一个做共享软件的朋友Lazaru(基于FreePascal的跨平台IDE,类似于Delphi)做桌面软件如何,他推荐用Code::Blocks,说Nightly Build已经很稳定,正式版很快就发布了,接着果然28号就发布了正式版。

本文内容来自Code::Blocks wiki上的WxWindowsQuickRef,本文内容并非按照原文完全逐字逐句的翻译。

Code::Blocks是一个跨平台的C++IDE,支持Windows、Linux、MacOSX。同时他还支持各种不同的编译器,如GNU/MinGW C/C++,VC++ 6.0/2003/2005/2008,Borland C++,Digital Mars等等各种不同的编译器。

经过14个组员长达2年对Code::Blocks的全部重写,终于发布了正式版8.02,这个版本更包括了对构建基于wxWidgets的跨平台GUI程序的支持,堪比Visual C++。

wxWidgets则是一个十分优秀的跨平台的GUI框架,用其编写的C++应用程序可以十分方便地迁移到不同的系统上去。

Code::Blocks + wxWidgets两个同是支持跨平台的IDE和框架,使得跨平台的编程非常方便。然而Code::Blocks虽然包含了对wxWidgets的支持,但是却没有包含wxWidgets的构建环境,我们必须手动进行配置。另外,Code::Blocks有一个安装包包含了MinGW的编译器,如果使用别的编译器,同样也需要自己进行相应的配置。

前提准备

编译器

你至少应该正确安装了免费的MinGW/GCC编译器或者是某种微软的编译器Express editions是免费的,但是你还需要安装Platform SDK)。如果是用MinGW/GCC,至少要准备gcc-core、gcc-g++、binutils、w32api以及mingw32-make包;同时,确保包含编译器可执行文件的目录(一般是C:\MinGW\bin)在Windows的PATH环境变量中。

如果选择MinGW/GCC编译器,可以在直接选择包含MinGW的Code::Blocks安装包,见下一节。

最新版的Code::Blocks

请下载最新的8.02发布版。尚未选择编译器可以选择包含MinGW的安装包

wxWidgets

你可以选择下载wxWidgets的源代码然后自己进行构建,或者是直接安装预编译的wxPack。

wxWidgets源代码

安装包较小,可以根据自己的需求进行自定义构建,但是需要花费长时间进行编译。如果不清楚编译选项,可能导致无法成功配置Code::Blocks。

目前推荐的wxWidgets的版本是2.8.7。点击此处下载wxWidgets 2.8.7源代码Windows安装包 (wxMSW-2.8.7-Setup.exe; 12.0 MB)。你也可以检查一下wxWidgets的下载页面看看有没有更新的稳定版下载。强烈建议你将代码安装到不带空格的路径中。必须保证盘中至少有300MB的剩余空间。

wxPack

虽然安装包达200MB,全部安装需要3G,但是包含了预编译的所有可能用到的库文件,而且包含VC和GCC的两种版本,可以不用去考虑构建选项了。

当前wxPack的稳定发布版是 v2.8.7.03,基于 wxWidgets 2.8.7。点击此处下载 wxPack v2.8.7.03 (wxPack_v2.8.7.03.exe, 236.9 MB)。你也可以查看wxPack下载页面看看有没有更新的稳定版下载。强烈建议将wxPack安装到没有空格的路径中。如果你选择只MSVC版本,应保证至少有700MB的剩余空间;如果只选择MinGW/GCC版本,则应保证至少有2.2GB的剩余空间。

提示

如果磁盘使用了NTFS格式,可以开启文件压缩功能,上述的目录在压缩后可以减少50%的空间占用。

编译wxWidgets

使用wxPack则可以跳过这一步。

打开命令行(在开始菜单中点击“运行”,输入cmd并回车)。如果使用的MSVC,你可以使用特定的用于设置环境变量的命令行。如果你使用的MSVC版本还要求你单独下载Platform SDK,确保全部包含了标准编译工具和Platform SDK中要用到的环境变量。

转到wxWidgets的构建目录,其中<wxWidgets>是源码所在路径,通常是C:\wxWidgets-2.8.7

执行构建命令,MinGW/GCC推荐的命令是:

MSVC推荐的构建命令是:

这个过程需要花很久,快的机器大概30分钟可以完成,慢的可能就需要几个小时了。

如果使用的GCC的版本较新,构建过程中可能会出现大量的警告。这样会明显导致构建过程变慢;你可以将错误信息重定向到文件中,在上述命令后面添加2> err.log,也可以通过2>nul直接禁止警告信息。

其中关于BUILD、SHARED、MONOLITHIC以及UNICODE选项的解释,请仔细参考文章后面关于wxWidgets的构建参数的解释,这些参数十分关键,他们直接定义了你所使用的基本的wxWidgets开发环境。你必须严格按照你的编译参数设置Code::Blocks的配置向导。

在Code::Blocks中创建wxWidgets项目

在Code::Blocks的起始页面中,选择“Create a new project”,也可以在File菜单中,选择“New” -> “Project…”。

找到并选择“wxWidgets project”,并创建,接下来会出现一个向导帮助进行wxWidgets项目的配置:

  1. 第一个页面是简介,可以选择以后跳过。
  2. 选择你要使用的wxWidgets版本。如果你是按照本文的过程配置的,那么你应该选择“wxWidgets 2.8.x”。
  3. 设置你的项目的名字的位置。
  4. 输入作者的信息(非必要)
  5. 选择自动代码和文件生成的选项。
  6. 选择wxWidgets的位置。强烈建议在此使用全局变量:输入“$(#wx)”(不包含引号)。如果你还没定义这个全局变量,那么全局变量对话框会出现,在Base Path中,选择你的wxWidgets安装路径。其他路径可以不用填。
  7. 为你的项目选择debug/release配置。推荐至少选择debug配置。
  8. 选择你的wxWidgets构建选项。必须和你构建wxWidgets时所使用的选项一致!如果你按照本文之前的方式构建的,应该将“wxWidgets Library Settings”下的全部三个选项选中。如果用的是wxPack,由于wxPack包含了各种不同的版本,所以你只需要选择你需要的选项。这个页面的另一个设置和wxWidgets的构建选项没有关系,你可以按照喜好来选择。如果,出于某种原因,你想使用调试版本的wxWidgets构建,选择“Configure Advanced options”然后在下一页选择“Use __WXDEBUG__ and Debug wxWidgets lib”。
  9. 如果需要,选择额外的库。一般应用的话应该无须选择其中任何一个。

构建并运行程序

接下来,就可以选择“Build and run”(F9)对程序进行构建并运行了。如果顺利,你的wxWidgets应用程序就会出现。如果出现了什么问题,你可以参考后面的常见问题。

wxWidgets编译选项简介

BUILD

BUILD控制wxWidgets构建调试版本(BUILD=debug)或者是发布版本(BUILD=release)。绝大多数情况下你只需要wxWidgets的发布版本就可以了,因为你应该不想要去调试wxWidgets自身,同时你依然可以通过链接wxWidgets的发布版本来构建你自己的程序的调试版本。

  • 调试构建wxWidgets会创建带有”d”后缀的库,例如”libwxmsw28d.a”、”wxmsw28d_gcc_custom.dll”。
  • 调试构建wxWidgets会在wxWidgets库的输出目录中创建”mswd” 或者 “mswud” 目录。
  • 发布构建wxWidgets创建的库没有”d”后缀,例如”libwxmsw28.a”、”wxmsw28_gcc_custom.dll”。
  • 发布构建wxWidgets会在wxWidgets库的输出目录中创建”msw” 或者 “mswu” 目录。

SHARED

SHARED控制wxWidgets是构建DLL(SHARED=1)还是静态库(SHARED=0)。利用构建的DLL,主程序构建时间较快,可执行文件更小。但是可执行文件加上wxWidgets DLL的总大小更大,但是不同的可执行文件可以使用同一个DLL。

  • wxWidgets的DLL构建会创建导入库(如 libwxmsw28.a)以及DLL文件(如wxmsw28_gcc_custom.dll)。你必须在发布你的程序的时候包含这个DLL。
  • wxWidgets的静态构建只会创建静态库(如 libwxmsw28.a),发布的时候也无须包含wxWidgets的DLL。

MONOLITHIC

MONOLITHIC控制是构建一个单一的库(MONOLITHIC=1)还是多个组件库(MONOLITHIC=0)。使用单一构建,项目的设置和开发会更加简单,如果你同时使用DLL构建的话,你只需要分发一个DLL文件。如果使用非单一构建(multilib),会构建出多个不同的库同时你可以避免将整个wxWidgets的基本代码链接到主程序,就可以去掉不需要的库。同时你也必须确保你选择了正确的组件库。

  • wxWidgets的单一构建仅会创建一个wxWidgets导入库(如libwxmsw28.a)以及一个DLL(如wxmsw28_gcc_custom.dll)。
  • wxWidgets的多库(multilib)构建会创建多个导入库(libwx28_base.a等)以及多个DLL文件。
  • 无论何种wxWidgets构建,都会创建额外的静态库(如libwxexpat.a、libwxjpeg.a等)。这些库对于wxWidgets的DLL构建一般是不需要的,但是当使用静态构建的时候,则是必须的。

UNICODE

UNICODE控制wxWidgets以及你的程序是否使用支持Unicode的宽字符串。大多数Windows 2000或更高系统上的应用程序都应该支持Unicode。早期的Windows版本不一定有Unicode支持。你应该总是使用wxWidgets的_("string")_T("string")宏来确保硬编码的字符串编译时是正确的类型。

  • wxWidgets的Unicode(UNICODE=1)构建将会创建带有”u”后缀的库,例如”libwxmsw28u.a”、”wxmsw28u_gcc_custom.dll”。
  • wxWidgets的Unicode构建会在wxWidgets库的输出目录中创建”mswu”或”mswud”目录。
  • wxWidgets的ANSI(UNICODE=0)构建创建的库没有”u”后缀,例如”libwxmsw28.a”、”wxmsw28_gcc_custom.dll”。
  • wxWidgets的ANSI构建会在wxWidgets库的输出目录中创建”msw”或”mswd”目录。

常见问题

出现类似于”wx/setup.h: No such file or directory”的错误

你在构建选项中缺少了很重要的编译器搜索路径。首先确认你是否在运行wxWidgets项目向导的时候正确选择了wxWidgets的构建配置。如果重新运行向导并配置依然无效,那么打开你的项目的构建选项并给编译起的搜索路径中添加”$(#wx.lib)\gcc_dll\mswu“(这里假设是一个单一的Unicode DLL构建)。

出现类似于”cannot find -lwxmsw28u”的错误

构建选项中的链接库错了。首先确认你是否在运行wxWidgets项目向导的时候正确选择了wxWidgets的构建配置。如果重新运行向导并配置依然无效,确定你构建了什么库,并相应在构建选项中调整库的名字。

TCMalloc:线程缓存的Malloc

作者:Sanjay Ghemawat, Paul Menage

原文

翻译:ShiningRay

动机

TCMalloc要比glibc 2.3的malloc(可以从一个叫作ptmalloc2的独立库获得)和其他我测试过的malloc都快。ptmalloc在一台2.8GHz的P4机器上(对于小对象)执行一次mallocfree大约需要300纳秒。而TCMalloc的版本同样的操作大约只需要50纳秒。malloc版本的速度是至关重要的,因为如果malloc不够快,应用程序的作者就很有可能在malloc之上写一个自己的自由列表。这就可能导致额外的代码复杂度,以及更多的内存占用――除非作者本身非常仔细地划分自由列表的大小并经常从自由列表中清除空闲的对象。

TCMalloc也减少了多线程程序中的锁争用情况。对于小对象,几乎已经达到了零争用。对于大对象,TCMalloc尝试使用粒度较好和有效的自旋锁。ptmalloc同样是通过使用每线程各自的场地来减少锁争用,但是ptmalloc2使用每线程场地有一个很大的问题。在ptmalloc2中,内存可能会从一个场地移动到另一个。这有可能导致大量空间被浪费。例如,在一个Google的应用中,第一阶段可能会为其URL标准化的数据结构分配大约300MB内存。当第一阶段结束后,第二阶段将从同样的地址空间开始。如果第二个阶段被安排到了一个与第一阶段什?用的场地不同的场地,这个阶段不会复用任何第一阶段留下的的内存,并会给地址空间添加另外一个300MB。类似的内存爆炸问题也可以在其他的应用中看到。

TCMalloc的另一个好处是小对象的空间最优表现形式。例如,分配N个8字节对象可能要使用大约8N * 1.01字节的空间。即,多用百分之一的空间。而ptmalloc2中每个对象都使用了一个四字节的头,(我认为)并将最终的尺寸规整为8字节的倍数,最后使用了16N字节。

使用

要使用TCMalloc,只要将tcmalloc通过“-ltcmalloc”链接器标志接入你的应用即可。

你也可以通过使用LD_PRELOAD在不是你自己编译的应用中使用tcmalloc:

LD_PRELOAD比较讨巧,我们也不十分推荐这种用法。

TCMalloc还包含了一个堆检查器以及一个堆测量器

如果你更想链接不包含堆测量器和检查器的TCMalloc版本(比如可能为了减少静态二进制文件的大小),你可以接入libtcmalloc_minimal

概览

TCMalloc给每个线程分配了一个线程局部缓存。小分配可以直接由线程局部缓存来满足。需要的话,会将对象从中央数据结构移动到线程局部缓存中,同时定期的垃圾收集将用于把内存从线程局部缓存迁移回中央数据结构中。

overview

TCMalloc将尺寸小于<=
32K的对象(“小”对象)和大对象区分开来。大对象直接使用页级分配器(一个页是一个4K的对齐内存区域)从中央堆直接分配。即,一个大对象总是页对齐的并占据了整数个数的页。

连续的一些页面可以被分割为一系列小对象,而他们的大小都相同。例如,一个连续的页面(4K)可以被划分为32个128字节的对象。

小对象的分配

每个小对象的大小都会被映射到170个可分配的尺寸类别中的一个。例如,在分配961到1024字节时,都会归整为1024字节。尺寸类别这样隔开:较小的尺寸相差8字节,较大的尺寸相差16字节,再大一点的尺寸差32字节,如此类推。最大的间隔(对于尺寸 >= ~2K的)是256字节。

一个线程缓存对每个尺寸类都包含了一个自由对象的单向链表

thread heap

当分配一个小对象时:

  1. 我们将其大小映射到对应的尺寸类中。
  2. 查找当前线程的线程缓存中相应的自由列表。
  3. 如果自由列表不空,那么从移除列表的第一个对象并返回它。当按照这个快速通道时,TCMalloc不会获取任何锁。这就可以极大提高分配的速度,因为锁/解锁操作在一个2.8GHz Xeon上大约需要100纳秒的时间。

如果自由列表为空:

  1. 从该尺寸类别的中央自由列表(中央自由列表是被所有线程共享的)取得一连串对象。
  2. 将他们放入线程局部的自由列表。
  3. 将新获取的对象中的一个返回给应用程序。

如果中央自由列表也为空:(1) 我们从中央页分配器分配了一连串页面。(2) 将他们分割成该尺寸类的一系列对象。(4) 像前面一样,将部分对象移入线程局部的自由列表中。

大对象的分配

一个大对象的尺寸(> 32K)会被除以一个页面尺寸(4K)并取整(大于结果的最小整数),同时是由中央页面堆来处理的。中央页面堆又是一个自由列表的阵列。对于i < 256而言,第k个条目是一个由k个页面组成的自由列表。第256个条目则是一个包含了长度>= 256个页面的自由列表:

Page heap

k个页面的一次分配通过在第k个自由列表中查找来完成。如果该自由列表为空,那么我们则在下一个自由列表中查找,如此继续。最终,如果必要的话,我们将在最后一个自由列表中查找。如果这个动作也失败了,我们将向系统获取内存(使用sbrkmmap或者通过在/dev/mem中进行映射)。

如果k个页面的一次分配行为由连续的长度> k的页面满足了,剩下的连续页面将被重新插回到页面堆的对应的自由列表中。

跨度(Span)

TCMalloc管理的堆由一系列页面组成。连续的页面由一个“跨度”(Span)对象来表示。一个跨度可以是已被分配或者是自由的。如果是自由的,跨度则会是一个页面堆链表中的一个条目。如果已被分配,它会是一个已经被传递给应用程序的大对象,或者是一个已经被分割成一系列小对象的一个页面。如果是被分割成小对象的,对象的尺寸类别会被记录在跨度中。

由页面号索引的中央数组可以用于找到某个页面所属的跨度。例如,下面的跨度a占据了2个页面,跨度b占据了1个页面,跨度c占据了5个页面最后跨度d占据了3个页面。

在一个32位的地址空间中,中央阵列由一个2层的基数树来表示,其中根包含了32个条目,每个叶包含了 215个条目(一个32为地址空间包含了 220个 4K 页面,所以这里树的第一层则是用25整除220个页面)。这就导致了中央阵列的初始内存使用需要128KB空间(215*4字节),看上去还是可以接受的。

在64位机器上,我们将使用一个3层的基数树。

解除分配

当一个对象被解除分配时,我们先计算他的页面号并在中央阵列中查找对应的跨度对象。该跨度会告诉我们该对象是大是小,如果它是小对象的话尺寸类别是什么。如果是小对象的话,我们将其插入到当前线程的线程缓存中对应的自由列表中。如果线程缓存现在超过了某个预定的大小(默认为2MB),我们便运行垃圾收集器将未使用的对象从线程缓存中移入中央自由列表。

如果该对象是大对象的话,跨度会告诉我们该对象覆盖的页面的范围。假设该范围是[p,q]。我们还会查找页面p-1和页面q+1对应的跨度。如果这两个相邻的跨度中有任何一个是自由的,我们将他们和[p,q]的跨度接合起来。最后跨度会被插入到页面堆中合适的自由列表中。

小对象的中央自由列表

就像前面提过的一样,我们为每一个尺寸类别设置了一个中央自由列表。每个中央自由列表由两层数据结构来组成:一系列跨度和每个跨度一个自由对象的链表。

通过从某个跨度中移除第一个条目来从中央自由列表分配一个对象。(如果所有的跨度里只有空链表,那么首先从中央页面堆中分配一个尺寸合适的跨度。)

一个对象可以通过将其添加到他包含的跨度的链表中来返回到中央自由列表中。如果链表长度现在等于跨度中所有小对象的数量,那么该跨度就是完全自由的了,就会被返回到页面堆中。

线程缓存的垃圾收集

某个线程缓存当缓存中所有对象的总共大小超过2MB的时候,会对他进行垃圾收集。垃圾收集阈值会自动根据线程数量的增加而减少,这样就不会因为程序有大量线程而过度浪费内存。

我们会遍历缓存中所有的自由列表并且将一定数量的对象从自由列表移到对于得中央列表中。

从某个自由列表中移除的对象的数量是通过使用一个每列表的低水位线L来确定的。L记录了自上一次垃圾收集以来列表最短的长度。注意,在上一次的垃圾收集中我们可能只是将列表缩短了L个对象而没有对中央列表进行任何额外访问。我们利用这个过去的历史作为对未来访问的预测器并将L/2个对象从线程缓存自由列表中移到相应的中央自由列表中。这个算法有个很好的特性是,如果某个线程不再使用某个特定的尺寸时,该尺寸的所有对象都会很快从线程缓存被移到中央自由列表,然后可以被其他缓存利用。

性能备注

PTMalloc2单元测试

PTMalloc2包(现在已经是glibc的一部分了)包含了一个单元测试程序t-test1.c。它会产生一定数量的线程并在每个线程中进行一系列分配和解除分配;线程之间没有任何通信除了在内存分配器中同步。

t-test1(放在tests/tcmalloc/中,编译为ptmalloc_unittest1)用一系列不同的线程数量(1~20)和最大分配尺寸(64B~32KB)运行。这些测试运行在一个2.4GHz 双核心Xeon的RedHat 9系统上,并启用了超线程技术, 使用了Linux glibc-2.3.2,每个测试中进行一百万次操作。在每个案例中,一次正常运行,一次使用LD_PRELOAD=libtcmalloc.so

下面的图像显示了TCMalloc对比PTMalloc2在不同的衡量指标下的性能。首先,现实每秒全部操作(百万)以及最大分配尺寸,针对不同数量的线程。用来生产这些图像的原始数据(time工具的输出)可以在t-test1.times.txt中找到。

  • TCMalloc要比PTMalloc2更具有一致地伸缩性——对于所有线程数量>1的测试,小分配达到了约7~9百万操作每秒,大分配降到了约2百万操作每秒。单线程的案例则明显是要被剔除的,因为他只能保持单个处理器繁忙因此只能获得较少的每秒操作数。PTMalloc2在每秒操作数上有更高的方差——某些地方峰值可以在小分配上达到4百万操作每秒,而在大分配上降到了<1百万操作每秒。
  • TCMalloc在绝大多数情况下要比PTMalloc2快,并且特别是小分配上。线程间的争用在TCMalloc中问题不大。
  • TCMalloc的性能随着分配尺寸的增加而降低。这是因为每线程缓存当它达到了阈值(默认是2MB)的时候会被垃圾收集。对于更大的分配尺寸,在垃圾收集之前只能在缓存中存储更少的对象。
  • TCMalloc性能在约32K最大分配尺寸附件有一个明显的下降。这是因为在每线程缓存中的32K对象的最大尺寸;对于大于这个值得对象TCMalloc会从中央页面堆中进行分配。

下面,CPU时间的每秒操作数(百万)以及线程数量的图像,最大分配尺寸64B~128KB。

这次我们再一次看到TCMalloc要比PTMalloc2更连续也更高效。对于<32K的最大分配尺寸,TCMalloc在大线程数的情况下典型地达到了CPU时间每秒约0.5~1百万操作,同时PTMalloc通常达到了CPU时间每秒约0.5~1百万,还有很多情况下要比这个数字小很多。在32K最大分配尺寸之上,TCMalloc下降到了每CPU时间秒1~1.5百万操作,同时PTMalloc对于大线程数降到几乎只有零(也就是,使用PTMalloc,在高度多线程的情况下,很多CPU时间被浪费在轮流等待锁定上了)。

注意

对于某些系统,TCMalloc可能无法与没有链接libpthread.so(或者你的系统上同等的东西)的应用程序正常工作。它应该能正常工作于使用glibc 2.3的Linux上,但是其他OS/libc的组合方式尚未经过任何测试。

TCMalloc可能要比其他malloc版本在某种程度上更吃内存,(但是倾向于不会有其他malloc版本中可能出现的爆发性增长。)尤其是在启动时TCMalloc会分配大约240KB的内部内存。

不要试图将TCMalloc载入到一个运行中的二进制程序中(例如,在Java中使用JNI)。二进制程序已经使用系统malloc分配了一些对象,并会尝试将它们传递到TCMalloc进行解除分配。TCMalloc是无法处理这种对象的。

JavaScript = C + Lisp

作者: William Taysom

原文地址:http://www.jadetower.org/muses/archives/000307.html

翻译:ShiningRay

我在过去的几周内一直在写JavaScript代码——使用我们的对话框系统来个性化Mozilla。假设你要求:“嘿,电脑,我要教你如何在Amazon.com上找书。首先你象这样进入Amazon,然后在这里输入你要的书的名字。点击“Go”然后……”我的困难在于对Mozilla编码使我的对话框系统可以“看”浏览器中正在进行什么然后自己可以执行这些动作。

由于Mozilla中较高的层次是用JavaScript实现的。所以我一直在废寝忘食研究它(我的Rhino book里面全是我做的书签)我写的越多,我越觉得它像Lisp。

考虑以下代码:

这里SemTree是一个对象,它允许你从一个HTML DOM 树中选出某些你感兴趣的节点,去掉那些你不感兴趣的节点。(根本上说,这是一个TreeWalker 类的包装器。)若要建立一个 SemTree ,你要给出一个接受器。一个接受器只是一个判断给定节点是否能被接受的一个函数:

一旦有了一些基本的接受器和筛选器,很容易就可以定义组合筛选器──一种将筛选器以特殊形式组合起来的函数:

当它被调用的时候,以接受器作为参数,acceptAny返回一个新的接受器,可以接受只要是 disjuncts 能接受的那些给定节点 n。所以,semanticAccepter 中出现的acceptAny 能接受文本、链接、表单和链接中的图像。相反地,acceptOnlyIf只能接受被所有接受器组件接受的节点。acceptOnlyIf的定义类似于acceptAny

acceptOnlyIfacceptAny如此相似让我纳闷是否有一个通用的方法可以将任一个组合器(像否定、短路与、短路或)变成一个组合筛选器(象acceptNotacceptOnlyIfacceptAny)。的确有,但JavaScript不胜任这个任务。要完成这个,我们需要更强大的武器。

将函数的能力定义得和单子的功能一样微小

通过提供第一类型函数,JavaScript迈出了进入更广阔世界的第一步。而这个世界中最具影响的便是Haskell和它的一些变体。由于接受器告诉我们是否要接受一个节点,它们应该是一个从节点到布尔值的函数。在Haskell中,我们这样写:

这样,否定是一个布尔到另一布尔,合取和析取是从一个布尔的列表到一个单个布尔值,这样写:

组合接受器有类似的形式:

我们给semanticAccepter下的定义和JavaScript版的类似:

我们怎样定义一个类似acceptOnlyIf的组合器?Haskell没有像一些语言中的命令结构。取代的是递归:

由于某些原因,短变量名是Haskell中的标准。n是一个节点,a是一个接受器,as是一个接受器的列表。(以’s’结尾是代表某个变量是列表的标准形式。)你上面看到的定义是正确的,但我不常用这个方法。我会使用一个优美的小函数叫map

当传了一个函数和一个列表,map返回对列表中的每个元素执行函数后生成的列表。有了map后,acceptOnlyIf
就可以这样定义。

这里语法 (\a -> a n) 基本意思和JavaScript下面的一样:

整个acceptOnlyIf的定义本质上说明了,“给出一个节点n,找出每个接受器对n的值,然后返回这些值的合取值(和值AND)。”有了这种定义函数的优美方法之后,它们之间的相似之处立刻显现出来了:

这样,泛化就是一些琐碎的事了:

现在我们是否可以更进一步了呢?我们是否可以也将 not搞成 acceptNot呢?andnot的主要区别在于 and参数是一个布尔值的列表,而not只能针对单个布尔值。要更进一步泛化 liftCombiner,我们必须:

  1. 找出可以描绘出基本值和列表的共同特性的结构。
  2. 将这个结构应用到合成组合器的问题中.

Haskell 正好有我们所需要的。它称为单子Monad.

什么是单子?

之前就有人问过这个问题。单子到处可见。大多数结构和过程/进程像数据类型、函数、对象、、异常、I/O、副作用、同步、事务、分析器和编程语言,都可以接受单独的、原子的操作。组对(Pair)、元组(tuple)、列表、树、图——这些数据结构都有一个单子级的解释,是常常不止一个。由于是单子的东西太多了,所以很难对它们进行描述。不过我还是可以给你一个数学上的定义。但是正如“A continuation is the rest of the computation ”所说的,给出单子的定义只有在你已经对它有了一些感性的认识才有用。否则直接给出定义只会混淆你的观点。那先让我们研究一下这个谦虚的列表作为我们受到单子启发的途径。

检验结构有很多方法。其中一个方法是查看各部分是如何一起工作来组成整体的。当以这种方法分析列表的时候,我们发现它们是连接的解码:一个列表要么是空的要么是一个由一个head和一个tail组成的Cons(一种构造函数,返回一个新的列表)。head是一个列表的元素,tail则是列表的其它部分。

若要定义列表[1, 2, 3],我们这样写:To define the list [1, 2, 3], we write:

Haskell中的列表就是这样工作的。除了用[]代表 Nil和用: 代表 Cons。逗号可以用来分隔条目,可以写成这样:

链表有一个很长很有名的历史。不幸的是分解材料并不会显露出单子。

另一种分析列表的方法是通过研究它是如何和其它东西相关、进行交互的。Haskell提供了“class”机制根据和它们相关联的方法来定义对象。类似于抽象数据类型和接口:

这是一个看似完美的列表类,但它几乎没有从分解材料中抽象出什么东西。所有的方法,除了 map,都是特定于列表的逻辑结构的,map抓住了一个较抽象的概念。它将一个函数作为参数,然后返回一个被函数处理过新的列表。回忆一下 map 对定义 acceptAny acceptOnlyIf 起了多大的帮助?这很明确是个值得研究的函数。

还有哪些其它函数对列表作为一个独立于它特定实现和形态的数据结构来说是至关重要的呢?好吧,还应该有一个方法 unit来把一个单独的元素放入一个列表,而且我们还需要一个 join 来将一个列表的列表组成一个长的列表。这个类定义像这样:

以下是链表的实现:

这些方法一目了然:unit将参数放入列表,map对列表中的每个元素执行函数,join将一个列表的列表连成一串。让我们确定一下串连接符(++)的定义吧:

这些函数都十分简单而且十分有用。它们确实是列表的标准成分,但就好比火药一样,如果你把它们正确地组合起来,你就能引爆一些东西:一个单子。我们等不及这个式子了:

就是它了。两个函数:return将一些东西放入单子中,同时(>>=),称为“绑定”,将一个单子变成另一个。我们立即来看看单子到底能做什么。不过首先为了明确起见,我们先将我们的列表实现扩展成应用一个单子:

return定义和 unit一样:将它自己放入一个列表中。绑定 (>>=)将mapjoin 组合成一个操作。首先你将函数k映射到列表 ls ,然后由于 f返回一个列表的列表,你再用 join 将结果组成单个列表。

但单子这东西有什么好处呢?设想你想要将一个列表中的所有值和另一个列表中的值相加来产生一个大的列表:

JavaScript代码应该像:

应用了单子我们可以这样写:

代码看来很简练,但没什么特别的。幸运的是,由于单子是如此有用,所以更好的语法形式也出现很久了。我们应该这样写:

这称为“do notation做标记”为了明显起见。还有另一种变体,我个人喜欢叫“列表包含语法”或者“我无法相信这没有成为一个学说”:

不论哪种方法,都是所有的单子之上的一种较好语法。这种较好语法也许看上去像某种命令语言或什么蛇的东西(指Python语言──译注)。但我不接受其它替代语法,在Haskell中任何单子都能使用两者之一。

我们看看一个列表单子是如何工作的,但我们仅有的单子是 LinkedList。对于not,我们只需要一个直接变换值的单子就行了:一个一致单子。它不会对值做特殊的改变,仅仅直接返回值:

现在我们终于可以完整地定义 liftCombiner了:

现在“让组合器能工作在所有接受器上”的这个想法已经不难实现了:

最后的思考

今天我们看了如何处理组合的接受器(从节点到布尔的函数),组合器可以是任何单子。结果接受器也是单子。你认为是否有一种方法,可以让组合器组合任意单子和其它单子(除了接受器之外)?如果有,怎样做?如果没有,单子之间要有怎样的关联才能这样?

嵌入JavaScript引擎梗概教程

嵌入JavaScript引擎

梗概教程

作者:Brendan Eich

2000年2月21日

翻译:ShiningRay @ NirvanaStudio

如何启动VM并执行一个脚本

如果不使用任何错误检查这样:

JS_起头的返回指针的函数会返回空(null)

JS_起头的返回布尔值的函数会返回假(false)
(错误照例会被保存在一个JSBool变量ok中)。

如何从JavaScript中调用C函数

假设有个C函数叫diot,他在被调用时需要至少两个实参(如果调用者少提供了几个,JS引擎需要保证undefined值传给了那些缺少的参数):

然后把它和JS连接起来,你要写:

或者,如果你有一堆的本地函数要调用,你可以把它们放在一个表格中:

(最后,全为0的函数表示表格结束)并且用:

ok = JS_DefineFunctions(cx, global, my_functions);

如何从C中调用JavaScript函数(像“onClick”)

假设点击事件是发生在最顶层或者是有焦点的UI元素,位置为(x,y):

再次声明,我省略了错误检查(例如在调用之后检查!ok),同时我伪造了一些C的事件管理程序来模拟DOM的协议——如果他的处理程序返回假就取消这个事件。


原文地址:http://www.mozilla.org/js/spidermonkey/tutorial.html