Create mod挺好的，就是配方不太和我心意。怎么办呢？自己动手丰衣足食。本文介绍如何使用Minecraft的Data pack特性来扩展游戏的配方系统。闲白最近看阿里云和腾讯云都在做活动。腾讯云那个轻量游戏主机看着不错，点开却是老用户与狗不得入内。于是只得选购了阿里云的个人99计划，2核心2GB内存3Mbps带宽，年付99元。说实话，没啥诚意，但又转念一想，99一年要啥自行车啊。买了服务器之后就发现，干点啥呢？做网页，那肯定要备案。以我的性格来说：案，狗都不备。所以想来想去，只能开个MC服务器了。但是2GB内存，实在是不够吃，我用尽毕生所学，在1.20.1上打了19个Forge模组。再后来发现内存真的不够用，所以自己加了700多块钱升级了一个2核4GB内存，有点肉疼，但当时也是上头了——我今天一定要让他跑起来。再后来又发现带宽不够，固定3Mbps带宽也就带3个人，所以后来我换成了按量付费，同时把安全组打开，就留下MC服务器的端口免得被打然后账单上天。好在固定带宽改成按量付费的时候还有退费，退的不多，不过还是那句话——99一年，要啥自行车啊。这些Mod都是我自己选的，因为我平时高版本都玩Fabric了，但这些Mod还是以Forge为主，所以就Forge了。这些mod除了优化，基本上都是种田相关的，最后还有个Create用来自动化一些东西。BiomesOPlenty-1.20.1-18.0.0.592.jarBookshelf-Forge-1.20.1-20.1.9.jarBotanyPots-Forge-1.20.1-13.0.24.jarBotanyTrees-Forge-1.20.1-9.0.11.jarChunky-1.3.136.jarFallingTree-1.20.1-4.3.4.jarFarmersDelight-1.20.1-1.2.4.jarKsyxis-1.2.2.jarNoChatReports-FORGE-1.20.1-v2.2.2.jarTerraBlender-forge-1.20.1-3.0.1.4.jarTravelersBackpack-1.20.1-9.1.12.jaralternate_current-mc1.20-1.7.0.jarcanary-mc1.20.1-0.3.3.jarcarryon-forge-1.20.1-2.1.2.7.jarcreate-1.20.1-0.5.1.f.jardynview-1.20.1-3.9.jarferritecore-6.0.1-forge.jarmodernfix-forge-5.13.0+mc1.20.1.jarstarlight-1.1.2+forge.1cda73c.jar其中Chunky是用来预先生成区块的，因为服务器只有两个核心，所以在不玩的时候提前生成好区块，之后跑图探索就会舒服一些。再就是NoChatReports，这个是我在高版本必备的mod。然后还有TravelersBackpack，我个人认为是一款非常强筋甚至有些OP的背包模组。至于BiomesOPlenty这种增加生物群系的模组就更不用说了——我MC正版都买了快10年了，那原版那点东西，能有意思吗（再就是BotanyPots和BotanyTrees这两个花盆模组，我感觉也是非常OP的：自动种田，只占用1格空间，自动兼容mod物品，不需要手动补种，不需要手动收获，放好种子放好土，它会自动收获放进箱子里，连自动化都省了，非常OP最后就是各种优化的mod，性能不够优化来凑。像是dynview，能够自动根据当前服务器的tick耗时来调节渲染距离和模拟距离。如果服务器性能还够吃，那就增大这些距离来提升玩家体验，如果性能不够吃了那就给这两个距离往下调，确保玩家不会因为服务器性能吃紧而卡顿。但玩着玩着，我发现这个Create模组和我看别人玩的不太一样：好像缺点东西。我之前看到Create模组时是在ilmango的ATFC系列，这个整合包针对Create模组增加了许多自定义的合成表，比如你可以从沙子、沙砾和石头这些方块中获得一些碾碎的矿物，然后通过水洗得到更多的矿物。虽然我觉得这些配方非常繁琐（但这也是这个系列的看点所在），但我觉得这种想法还是挺不错的，比起那些种植矿物和动物资源的模组，我觉得Create这种配方既能免去后期重复下矿的麻烦，又可以要求玩家付出一定的努力。可是我打开合成表一看：啊？怎么什么都没有？原来原版的Create只有一些很基础的配方，而我之前在视频中看到的都是整合包作者自己加的。那么问题来了，怎么加的呢？我知道可以通过写Mod来加，但是整合包作者好像也没有因为就单纯要加合成表就自己写Mod。后来我一查，原来从1.13开始Minecraft就有了data pack了，他的目的就是允许整合包作者来为整合包增加额外的游戏机制，不只是合成表。关于Data pack怎么做我就不多说了，主要就是写Json文件然后放到对应的文件夹里就是了。这一部分在wiki上全都有说，没说的自己去Google搜搜也就差不多了。这里主要想说说我对于这次拓展的思路。好多时候，实现，也就是所谓的编程或者将想法转化为现实的过程，都不是最重要的，反倒是设计更重要。所以我现在除了没有10年经验，剩下的和高级开发基本差不多了（首先我不想把事情搞得太复杂，因为服务器跑不起来，我这脑子也接受不了——我是来玩游戏的，不是来被游戏玩的，所以合成表争取要简单一些；其次就是要合乎逻辑，毕竟之前说了不能像种植矿物那样太过强力，所以要有一些设计自动化的压力；最后就是得合乎常理，比如说通过水洗或研磨沙子可以获得碾碎金属矿物，但是从沙子里洗出钻石就不太对劲了。正题所以我研究了一下Create自带的配方，然后借用了一些来自Biomes O' Plenty的方块，得到了以下结论。首先要说明，需要实现可再生的资源如下：铁、金、铜锌（Create）青金石，钻石，远古遗骸下届石英，紫水晶，红石，萤石在矿物的范畴里，煤炭不算，但这里我也加了关于它的配方，因为后面要用。至于绿宝石，它虽然是矿物资源之一，但它的主要获得途径是和村民交易，因此这里就不考虑它了，不然就太OP了。我在Create里面找到了一些可以生成这些资源的配方：红沙经过水洗有几率得到金粒红沙可以经过粉碎花岗岩得到花岗岩可以通过闪长岩和下届石英合成得到闪长岩可以通过原石和下届石英合成得到下届石英可以通过粉碎海晶砂粒得到，同时还有几率得到萤石粉海晶砂粒可以通过对青金石缠魂得到沙砾经过水洗有几率得到铁粒沙砾可以通过粉碎原石得到粉碎的生铁矿经过水洗有几率得到红石和铁粒粉碎的生铁矿可以通过粉碎铁矿石、绯红岩得到虽然找到了一些配方，但是这些配方的原料终究还是不可再生的。所以我们的需求就是创造新的配方，让他们形成闭环。为了方便阅读，我整理了一个图表，这里面涉及到相关原有的合成表（黑色线）和新加的合成表（蓝色线）。这里面标为绿色的就是原始材料，圆角矩形是中间产物，矩形是最终我们想要的产物。其中以木炭为原料的流程比较简单，我们先从这个开始。首先是使用动力辊压机压木炭，可以获得煤炭，这一步可以解释为将松散的木炭压实。然后利用原版的合成表将煤炭变成煤炭块，最后再用辊压机压煤炭块，煤炭块有2%的几率变成钻石，余下98%的几率会被消耗。余下的流程就全都是从原石开始的。首先是原石经过两次粉碎轮，分别变成沙砾和沙子。其中模组带了一个沙子可以洗出粘土的配方，所以水洗就不行了，只能用粉碎了。粉碎沙子有7%的概率产生铜粒、7%的概率产生锌粒、5%的概率产生青金石、5%的概率产生紫水晶碎片。其中两个金属粒是由Create模组提供的，九个金属粒合成一个金属锭。使用鼓风机放置在点燃的灵魂沙后面可以进行缠魂操作。对青金石进行缠魂有几率得到海晶砂粒。粉碎海晶沙砾有几率获得萤石粉和石英。使用原石和石英可以手动合成白色的闪长岩，闪长岩再次和石英合成可以得到花岗岩。通过粉碎花岗岩可以得到红沙，而红沙经过清洗可以得到原版的金粒，在之后就可以得到金锭了。关于铁我想了半天，如果说含铁量高的话，那肯定就是红沙了。但是红沙本身已经有个水洗的配方了，所以只能换一种配方了。在翻阅合成表的时候，我发现Create模组提供了一个叫做绯红岩的方块，它可以粉碎成铁粒和Create模组中的粉碎的生铁矿，后者经过清洗可以得到红石粉。那么我们只需要想办法创造出这个绯红岩就好了。既然是红的，又得是含铁，直接用原石和红色染料有点儿戏了。好在BiomesOPlenty在下届提供了一种叫做血液的液体。很显然，血是红的，也含铁，正好可以放在搅拌器里做。Forge里面一通液体是1000mBucket，我设计做一块绯红岩要消耗250mBucket和一块岩石，也就是4块岩石加一桶血，得到4块绯红岩。那么血怎么再生呢？血和水相遇会生成多孔肉块，这个类似刷石机，可以用多孔肉块和一桶水搅拌出一桶血。水从无限水来，多孔肉块可以做成刷石机的设计进行自动采集，这样血的供应也就解决了。最后还剩下一个远古遗骸。一开始我不打算做远古遗骸的合成路线，我觉得有些OP了。但我自己玩的时候挖矿全都交给baritone，所以本质上还是电脑自己挖矿。最后还是决定加上了。可是怎么加呢？我想了想，多孔肉块是BiomesOPlenty在下届新增的方块，如果把他加热可以转化成下届岩，也不是完全没有道理对吧。所以加热获得下届岩，然后通过清洗下届岩能够有0.1%的几率获得一块远古遗骸。至此，Minecraft里面的所有资源都可以被自动化生产了。之后的问题就是怎么在生存中设计自动化。后记别说，本来我以为做个Data pack，我也没加什么新机制，更没涉及命令那些复杂的东西，没啥可写的。不过最后发现，合成表的设计也不能胡来，虽然不能完全的讲究科学，同时还得避开原版的合成表。还得考虑这些流程能不能形成一个闭环，能不能实现原料的自动化供应之类的。如果你用CraftTweak模组，那可以实现对原版合成表的修改，但我不想加新mod了，除了服务器带不起来，每次加新mod都得给别人发新的客户端，十分麻烦总之这个合成表应该就是这种形态了。如果大家需要取用的话可以异步GitHub。
不知道出于何种原因，我突然决定自己造轮子。索性这个轮子造的好像还不是特别没用。本文将记述我从零开始使用Kotlin实现一个Bencode编解码库。前言Java和Kotlin（JVM）具有比较好的互操作性，即便没有给Kotlin设计的库，如果有相应的Java库，在Kotlin上也是可以直接调用的。在此之前我尝试过com.dampcake:bencode这个库，用起来感觉还不错，但它的操作是类似DOM那种，即所有写入和读出的数据全部存在内存里以供操作。这种操作方式固然简单好用，但是如果你有很多数据的话，你可能更希望采用接近XML SAX的方式。后者是基于流的解析方案，也就是说解析器一边读入数据，一边将解析出来的结果交给你的代码。你可以选择将他们收集起来组装成DOM，也可以选择即时处理然后回收。本文将考虑如何构建一个基于流的Bencode编解码库。BencodeBencode好像是一种不太常见的编码。考虑到早年间的XML，以及现在的Json，好像Bencode并没有什么用武之地？但作为一个P2P爱好者和版权左人，大名鼎鼎的BitTorrent协议就是用Bencode编码数据。这种编码形式以字符为基础，肯定不如ProtocolBuf这种二进制编码高效，同时它的结构比较简单，不太可能像XML或Json在功能上那么丰富（Bencode甚至不支持编码小数）。但从某种意义上来说，Bencode确实是最简单且紧凑的格式。举个例子。在Json中表示一个结构是这样的：{ "number": 1234, "string": "hahaha", "list": [ "string in list", 2345, [ "list in list!" ], { "name": "object in array!" } ], "obj": { "string": "An object", "list": [ "List in object!" ], "dict": { "num": 2345 } } }去掉所有多余的空格，一共是195个字符。如果表示成XML，那就更罗嗦了：<?xml version="1.0" encoding="UTF-8" ?> <root> <number>1234</number> <string>hahaha</string> string in list 2345 <2>list in list!</2> <name>object in array!</name> <obj> <string>An object</string> List in object! <dict> <num>2345</num> </dict> </obj> </root>XML需要295个字符，而且它还没有保留list in list的部分。这可能是我是用的Json到XML转换器有问题，也可能是XML并没有名且规定列表的格式。如果将上述数据转换成Bencode，那就显得紧凑了不少：d4:listl14:string in listi2345el13:list in list!ed4:name16:object in array!ee6:numberi1234e3:objd4:dictd3:numi2345ee4:listl15:List in object!e6:string9:An objecte6:string6:hahahaeBencode只要179个字符。而这段数据的所有文本内容需要125个字符（数字由对应的字符表示，且丢弃了所有结构信息）。当然，如果只从格式上看的话，Bencode不是那么的“人类友好”，但这无伤大雅，我对于Bencode的主要用途是简单地导入和导出结构化数据，而不必考虑给人看。说了这么多，不如我们来看看Bencode的编码规则。Bencode的编码规则比较简单：Bencode使用ASCII字符作为分隔符和元素对于数字，采用i42e的形式来编码，其中42是数字42对应的十进制字符串。数字不允许前导0（即00042是非法的）。负数使用-作为前缀，即i-42e，但不允许负0对于字节串（字节序列，并不一定是字符），采用4:spam的形式来编码。其中4表示这个字节串的长度，采用十进制字符串表示，冒号表示分割，随后spam是字节串的实际内容。Bencode并没有提及数据无法被编码成ASCII时应当如何处理，在一些具体实现中，人们主要采用UTF-8来应对其他字符，或使用ISO 8859-1来编码字节数据，亦或采用Base64等编码将字节串编码为ASCII字符串一个列表由l<content>e表示。一个具有字符串“spam”和数字42的列表应当被表示为l4:spami42ee。其中首个字符是小写字母L，不是数字1。列表内的元素类型不受限制。一个字典由d<content>e表示。在字典中，字符串作为键后面总是直接跟着值。所有键必须按照字典序进行排列。例如字典{"bar": "spam", "foo": 42应当被表示成d3:bar4:spam3:fooi42ee。字典的值的类型不受限制。通过上述这几条规则，基本上就没有Bencode表示不出来的结构。同时字典规定了键的排序，保证了编码结果的唯一性。流式编码上面说了半天编码，不如我们就从编码入手，看看怎么基于流来编码。编码器的输入往小了说就是那四个基本类型：整数、字符串、列表和字典，对应Java里面的BigInteger、String、List<*>和Map<String, *>。因为Bencode并没有规定整数的最大上限，因此使用BigInteger来存储整数。整数和字符串对于整数和字符串来说，流失编码好像没有太多的意义：除非一个整数或字符串占用了以G计算的内存，你可能需要流式处理，不然没有必要把他们拆开——就算拆开，字符串还好说，整数怎么拆呢？这个就需要看具体的应用场景了，而作为一个通用的库来说，我们没有办法提供一个不过度复杂同时还通用的机制。因此这两个元素没有什么流式不流式的说法。列表对于列表就不一样。这里我们通过循环的方式来模拟对列表内数据的访问和写入。如果我们有400万个Int，他们在内存中大约占用16MB的内存。如果我们将他们转换成BigInteger，都不使用List，就用最紧凑的数据，在128MB的内存限制（-Xmx128M）下，程序直接OOM了。 val array = IntArray(400_0000) { it } val list = Array(400_0000) { array[it].toBigInteger() } println(list.count())即便没有OOM，这个list所占用的额外内存也必须等待所有数据写完之后才会被垃圾回收——只要编码器还没写完，对于GC来说这个列表就是可达的，那么每一个元素都无法被回收，即便他们的一部分已经被写入了。好在Kotlin提供了Sequence这个东西。Sequence的好处就是可以根据需求（on-demand）产生数据。也就是说，我通过循环的方式统计个数，而每次我只需要一个数据，处理完成之后这个数据就可以被GC回收了。使用Sequence，整个程序只占用了22MB的内存： val array = IntArray(400_0000) { it } val seq = sequence { for (i in array) yield(i.toBigInteger()) } println(seq.count())我们只要使用Sequence，就可以保证数据只有被编码器需要的时候才会产生。这不就是流式处理吗？字典下面我们来看看字典。我们可以借鉴列表的经验，但是Sequence有一个问题：除非提供者保证，否则没法确保数据是有序的，而我们的字典在编码时要求键必须按照字典序排列。要么我们就接受用户的输入，如果检测到违反了字典序，就抛出异常；要么我们就想办法自己构建一个类似Sequence的Map。好在我并不是第一个遇到这种问题的开发者。在Java中就提供了Supplier这个接口，而Kotlin中也有Lazy这种能够提供延迟求值的工具。但最简单的还是一个Lambda：() -> T，只要我们将Map的类型设置成Map<String, () -> T>就可以了。但是这个T怎么取呢？我们的元素有BigInteger、String、List和Map，且不说前两个没有共同的父类，后两者还有泛型擦除的问题，很显然编译器并不能要求传入的List必须是List<String>，而不能是List<UUID>。在传统的Java开发中，这个时候我们就应该已经写出编码器的接口，同时还有BencodeSerializable接口了，但是我个人并不太喜欢接口满天飞。不过在这种情况下，接口可能是无法避免的：sealed interface BEntry { data class BInteger(val value: BigInteger) : BEntry data class BString(val value: String) : BEntry data class BList(val value: Sequence<BEntry>) : BEntry data class BMap(val value: Map<String, () -> BEntry>) : BEntry }由于我们接口下面的实现是已知的，毕竟Bencode中就规定了四种元素，因此完全可以使用密封类来修饰接口。这样，当我们使用BEntry作为when的参数时，编译器就会知道，这个参数只有四种可能的情况，而我们上面的T也就可以取值为BEntry了。编码器既然有了这个BEntry，我们就可以面向这个接口设计编码器了。我们的BencodeEncoder在构建时只需要一个Writer，这个对象负责处理字符的写入，而无需我们考虑字符集编码这些问题。关于成员函数，由于我们的BEntry设计的很清晰，因此只需要一个fun writeEntry(entry: BEntry): Unit就好了。为了方便维护，我们可以针对不同的类型设计不同的私有函数，将writeEntry作为一个集中分派的入口： fun writeEntry(entry: BEntry) = synchronized(writer) { when (entry) { is BEntry.BInteger -> writeBInteger(entry) is BEntry.BString -> writeBString(entry) is BEntry.BList -> writeBList(entry) is BEntry.BMap -> writeBMap(entry) } }这里我们对writer加了锁，这是避免在多线程使用时造成冲突。例如一个列表正在输入，另一个线程突然开始写字典了，很有可能就会得到类似字典把列表截断，而列表又把字典截断的情况。对于四种类型的写入也比较简单： private fun writeBInteger(entry: BEntry.BInteger) { writer.write("i") writer.write(entry.value.toString(10)) writer.write("e") } private fun writeBString(entry: BEntry.BString) { writer.write(entry.value.length.toString()) writer.write(":") writer.write(entry.value) } private fun writeBList(entry: BEntry.BList) { writer.write("l") entry.value.forEach { writeEntry(it) } writer.write("e") } private fun writeBMap(entry: BEntry.BMap) { writer.write("d") entry.value.keys.sorted().forEach { k -> writeBString(BEntry.BString(k)) writeEntry(entry.value[k]!!()) } writer.write("e") }像是字典的键，我们知道它的类型，就可以直接调用writeBString，而对于值，我们并不知道它的类型，因此较为writeEntry进行分派。Writer有了编码器，但好像还不太够：这个编码器只能面向我们的BEntry工作。如果用户想要编码一个Map，还必须得转换成我们的BEntry.BMap，有点麻烦。如果我们能直接编码Map对象，甚至任意的对象呢？我想到了两个思路。第一个思路比较简单粗暴：提供一个接口，让用户可以实现这个接口，从而提供一个BEntry出来：interface BencodeEncodable { fun encodeToBEntry(): BEntry }使用的时候看起来是这样的：data class Point( val x: Int, val y: Int ) : BencodeEncodable { override fun encodeToBEntry(): BEntry = BEntry.BMap(mapOf( "x" to { BEntry.BInteger(this.x.toBigInteger()) }, "y" to { BEntry.BInteger(this.y.toBigInteger()) } )) }第二个思路则相对灵活一些：在实例化Writer的时候提供一系列mapper，他们将对应类型的对象转换为BEntry。如果更进一步扩展这个概念，mapper可以把writer不认识的类型转换成它认识的类型。例如上面那个Point类的mapper可以是：val mapper = BencodeEncoderMapper<Point> { mapOf( "x" to it.x, "y" to it.y ) }你会发现这个Mapper的返回值并不是BEntry，而是一个Map<String, Int>。而我们的Writer可以把这个Map转换成对应的BMap：只需要将值映射为{ it.value }就可以了。而完成转换之后，这个mapper返回的map就会被丢弃，从而可以被垃圾回收。不过在Mapper中不能返回lambda，因为JVM在运行的时候比较难判断一个值到底应该被包装成lambda，还是要作为lambda放进Map。Kotlin在编译时并没有保证两个类型相同的Lambda对于JVM就一定是同一个类型的。因此同样都是() -> BEntry，他们可能是两个不同的类。当然，使用反射可以解决这个问题，查看一个对象是否具有invoke()的方法，并且返回值不是Unit或Nothing，但我本意是想避免这些黑魔法的。另外还需要注意这两种思路的细微差别。对于实现接口来说，因为BEntry要求使用Supplier，所以BEntry.BInteger(this.x.toBigInteger())这一行只有在写入了键x之后才会被调用，可以认为获取到的值就是最新值了。而Mapper虽然也是在写入时调用，在Writer调用完成后，便得到了一个快照（因为在JVM上，对于Int的赋值是值复制，不是引用复制），也就是说，在Writer调用完成后、Encoder写入完成前，无论原来的Point.x怎么变，写入的内容都不会变了（在Encoder中调用的Supplier实际上只返回一个Int，这个Int是mapper中对it.x的求值）。当然，如果对于数据类都是用不可变类型，那自然是极好的。如果涉及可变类型，那除了保证内存可见性之外，还要考虑将对象转换成BEntry的时机对于编码结果的影响。总之，在这个库里面我实现了这两种思路，如果是自己编写类的话，建议使用第一种；如果是别人的类，那么就可以考虑使用Mapper在序列化时自动转换。关于这部分的代码也比较简单，Writer的主要入口： fun write(obj: Any): Unit = encoder.writeEntry(mapToBEntry(obj))而负责转换的函数实际上就是一个lookup table： private fun mapToBEntry(obj: Any): BEntry = when (obj) { is BEntry -> obj is BencodeEncodable -> obj.encodeToBEntry() // for signed value, convert to long is Byte -> BEntry.BInteger(obj.toLong().toBigInteger()) is Short -> BEntry.BInteger(obj.toLong().toBigInteger()) is Int -> BEntry.BInteger(obj.toLong().toBigInteger()) is Long -> BEntry.BInteger(obj.toBigInteger()) // for unsigned value, convert to long so the value is same is UByte -> BEntry.BInteger(obj.toLong().toBigInteger()) is UShort -> BEntry.BInteger(obj.toLong().toBigInteger()) is UInt -> BEntry.BInteger(obj.toLong().toBigInteger()) // for ULong, it's bigger than long, thus turn it into string is ULong -> BEntry.BInteger(BigInteger(obj.toString())) // for chat and string, just write string is Char -> BEntry.BString(obj + "") is String -> BEntry.BString(obj) // for list, transform it to sequence is List<*> -> BEntry.BList(obj.asSequence().map { mapToBEntry(it!!) }) // for map, map the key to string and map value to BEntry is Map<*, *> -> BEntry.BMap(obj.mapKeys { if (it.key is String) it.key as String else it.key.toString() }.mapValues { { mapToBEntry(it.value!!) } }) // for general object, search mapper and apply the transform else -> ((mapper.find { it.canHandle(obj) } ?: error("Mapper not found: ${obj.javaClass}")) as BencodeEncoderMapper<Any>) .invoke(obj) .let { if (it is BEntry) it else mapToBEntry(it) } }关于Mapper的设计，也比较简单：interface BencodeEncoderMapper<T> { fun canHandle(obj: Any): Boolean fun invoke(obj: T): Any }这个canHandle是用来询问一个mapper实例能否处理这个类。因为运行时的泛型擦除，Writer除了知道这是一个Mapper之外，并不知道它所实现的泛型是什么，更不要说什么类型间的继承应该如何处理了——有时候子类可以按照父类处理，有时候子类需要它独有的处理方式。当然，每次实例化Mapper都需要写一个object : Interface { ... }都怪臃肿的，而且这个接口有两个函数，没法用SAM。但是啊，我们可以用同名函数来实现简化：inline fun <reified T> BencodeEncoderMapper(crossinline block: (T) -> Any) = object : BencodeEncoderMapper<T> { override fun canHandle(obj: Any): Boolean = T::class.java.isInstance(obj) override fun invoke(obj: T): Any = block(obj) }当然了，简化的代价就是要服从一些约定。这里关于能否处理的判断，是调用了泛型类的isInstance方法。得益于Kotlin的inline和reified，我们可以在内联函数中访问泛型的具体类型。这也是实现第二个思路的关键。如果要我在Java中实现类似的机制，我肯定要舍弃掉第二个思路——无论使写起来还是用起来，都太臃肿了。写到这里突然想到，使用Mapper可能会出现成环的情况。比如说一个类型A的Mapper返回了类型B，而类型B的Mapper又返回了类型A，这样不停的递归调用就会导致爆栈。不过话又说回来，这样成环肯定说明这家伙的数据类型设计的很不合理，总之不是我的锅就对了。解码说完了编码，再说说解码。你会发现说解码的时候我可没提流式。我在不同的设计方案中思考了半天，最终决定像编码那样提供两个层级的API。底层可以是流式的，但顶层就比较困难了。解码意味着要处理一系列的输入流，而若像编码那样使用Supplier按需解码，就需要解码器能够知道要跳过多少字符以便解析下一个元素，同时还能倒回某一处，在需要的时候解码以前跳过的内容。这对于Reader来说实在是强人所难了。但是这种限制并不意味着我们必须把一个元素完整的解析到内存中。我们可以根据当前的字符构造状态机啊！例如我们读到一个字符i，我们就知道下一个元素应该是一个整数；如果读到1~9中的一个，那么下一个肯定是字符串；类似地，如果读到l或者d，那么下一个肯定是列表或字典。而且他们的终止符都是成双成对的，只要输入的是合法的数据，就不会出问题。举个例子：data class Person( val name: String, val age: Int, val friends: List<Person>, val attributes: Map<String, String> )我们在读取的时候可以构建一个Builder，根据读到的内容填充builder。例如说：在开始之前应该预期一个字符d，因为对象将被处理成字典接下来应该预期字符1~9中的一个，因为字典中总是键值的顺序，而键是字符串根据读到的键，预期不同类型的数据例如读到了name，就应该预期一个字符串读到age，就预期一个整数如果是friends，那就调用处理List<Person>的函数，循环调用当前函数以读取Person列表，最后将读出的列表返回当遇到字符e的时候，检查这个Builder是否已经准备好build了。如果还有缺失数据，说明输入的有问题显而易见地，这是个递归结构。如果你怕爆栈的话，改成链表+循环也可以。但脑子尖的读者应该已经注意到了：这个friends对应的列表，并没有流式解析啊，反倒是只有最顶层的Person是流式解析，而它的内容倒都变成DOM形式了。对，你说得都对。这个问题我也思考了很久，最后得出来的结论就是以实际需求为准。我上面那个例子是根据输入还原对象，也就是说无论如何我们都是避免不了DOM形式的。但如果说你是想即时更新数据库，那相比之下就简单了不少：你只需要在读到id之前暂存数据，读到id之后直接采用多个UPDATE语句的形式，读一个就产生一条语句，然后丢弃结果。总之在这方面，我尽力了。如果一个对象不大的话，那么以对象为单位进行DOM形式的操作，而总体还是流式的话，我反正是能接受的。解码器关于解码部分的代码这里就不多说了，只介绍一下API。较为底层的API是BencodeDecoder，实例化时需要一个Reader来读入字符，它总共有如下方法： fun hasNext(): Boolean fun nextType(): BEntryType fun readInteger(): BigInteger fun readString(): String fun startList(): Unit fun startMap(): Unit fun endEntity(): Unit这其中，hasNext不必多说，就是看Reader是否已经被处理干净了。如果还没有，那么就读入一个字符。而后nextType则是根据当前读入的字符来判断类型。这里你会发现我没有用BEntry，一来是它的实现都不是Object，没法直接用，二来是解码时l和d表示列表和字典的开始，而e则单独表示一个实体的结束，没办法与四种类型对应。因此就额外引入了一个Type类，它也是密封接口，而它的实现，除了EntityEnd比较特殊，其他的都是BEntry的四个实现的companion object，也就是说我们可以直接写BEntry.BList来表示一个BEntryType，我觉得很是优雅。后面两个read就不用说了——直接读取对应类型的值，读完之后还要读入下一个字符，以便后续调用hasNext来判断。而至于列表和字典，这个start函数只是检查一下当前的字符是否正确。例如startList会检查当前字符是不是l，不是的话就会抛出异常，避免错误地开启列表。剩下的startMap和endEntity也是类似的操作。Reader而较高等级的API则提供了一种近似DOM方式的API：class BencodeReader( reader: Reader ) { fun hasNext(): Boolean fun nextType(): BEntryType fun readInteger(): BigInteger fun readString(): String fun readList(): List<*> fun iterateList(callback: Consumer<Any>) fun readMap(): Map<String, *> fun iterateMap(callback: BiConsumer<String, Any>) } 前两个就不多说了，唯一值得一提的就是nextType，因为读出来就是完整的对象，所以不存在EntityEnd这种类型。后面的各种read也不必多说，读出来就是对象。这里额外提供了两个iterate方法，为的是流式遍历顶层对象。比如说一个输入是几百万个小对象组成的列表，那么iterateList就会每次解析一个对象，然后交给callback处理，处理完成后再解析下一个。字典也是一样，每次解析一对键值，然后交给callback处理。后记至此这整个库的设计思路就介绍完了。这个库本身比较简单，不像Ktorm那种复杂的库。但碍于我没有设计库的经验，在设计的过程中考虑了好多有用的和没用的细节，以至于文章写起来很罗嗦。另外写文章的时候突然意识到一些问题，就把文章扔到一边修改代码去了，改完代码再接着写文章，难免会有些思路上的跳脱。好在这又不是出版书籍，有点问题就有点问题了。也许有经验的读者看到我这边文章会说：就设计一个编解码的库，这孙子怎么写的那么啰嗦，这不脱了裤子放屁吗？有的地方还狗屁不通，这写的啥啊这是？我奶奶用脚写的都比这好对，你说的都对，不爱看滚蛋。不过还是要感谢一下能耐心读到结尾的读者，感谢你们的耐心。关于这个库，我已经开源到了GitHub上，可以在JitPack上使用相应的制品。-全文完-
本文记述我使用Kotlin在JVM上实现Conway's Game of Life。游戏规则康威生命游戏并不是什么新鲜玩意儿了，它可以视作一个二维的棋盘，每一个格子被称为细胞（Cell），每一个细胞有两种状态：死亡或存活。每一轮迭代时，所有细胞同时更新状态，更新的规则如下：若细胞当前存活：当周围的存活细胞数量小于2时，这个细胞在迭代时死亡（因人烟稀少）当周围的存活细胞数量大于3时，这个细胞在迭代时死亡（因人口过剩）当周围有2个或3个存活的细胞时，这个细胞在迭代时继续存活若细胞当前死亡：当周围有且只有3个存活细胞时，这个细胞在迭代时复活（模拟繁殖）其他形况下，细胞继续保持死亡状态这个规则其实还挺简单的，并且它可以使用多线程进行运算。实现思路这个游戏的“世界”可以用一个二维数组表示，数组的元素就是一个布尔值，true表示存活，false表示死亡。每次更新细胞时先统计它周围的存活细胞，然后根据细胞的当前状态使用if else做判断，更新细胞状态。考虑到规则要求所有细胞同时更新，因此我们需要两个“世界”，一个表示当前的细胞状态，计算出下一状态后，将新的状态写入另一个世界，表示未来的状态。当所有细胞都产生了新状态后，交换这两个世界的指针，这样一来，未来的状态就成为了现在的状态，而原来的状态则成为记录未来状态的容器。不论使用什么语言，这种设计还都挺合理的对吧？在JVM上也一样，对吧？整体来说还挺对的，但有一些小问题。首先，JVM标准并没有规定一个布尔值应该占多少内存。可能是1比特，也可能是1字节，这完全取决于JVM的实现。如果JVM使用1比特，那么含有1024个元素的布尔数组的大小就是128字节；如果采用1字节表示一个布尔，那么同样大小的数组就要占用1KB。假如说我们要渲染一个1080P的康威游戏，1920乘以1080，一共是2073600（200万）个细胞，每个细胞占用1字节，这就是2MB的内存，而原本它可以只占用不到256KB的。当然了，好在JVM中其他类型的大小是固定的。你可以选择使用byte作为容器，这样一个byte就有8个bit，但鉴于kotlin的类型系统比较生硬，在做位运算的时候需要将byte转换成int，再将int转换为byte存回去，这样子很麻烦，所以我是用Int作为容器，每个Int可以存储32个比特，即便有浪费，也最多是最后一个Int没有完全使用，浪费的部分不超过4字节。熟悉BitSet的读者可能会说，诶呀，你说的这个不就是BitSet嘛！Java中提供了一个可变长度的BitSet，可以方便地做位运算。但这里还有一个问题：内存一致性。关于这一部分，最开始的构想是使用分段锁来保护不同位置，这样既保证了内存一致性，又保证不同位置的独写互不冲突。但是后来发现一个问题：写入一个状态需要读取九个状态，换句话说，如果读写都加锁（读需要加锁保证线程可以看到之前写的数据），那么更新一个细胞就要竞争10次锁，一旦竞争失败，synchronized关键字就会把竞争失败的线程转变为操作系统的阻塞态。这是非常耗费时间的。谈及多线程和内存一致性，包括我在内，第一反应可能都是用同步锁，无论是synchronized关键字还是同步代码块，总之，正确用锁就能保证安全。但是从性能角度来看，监视器锁可能是性能最差的（字节码中使用了monitorenter和monitorexit），因为它依赖于操作系统将竞争失败的线程阻塞，锁释放时再依赖操作系统唤醒线程。在这里，我们更新一个细胞需要读取9次，而每次都要竞争锁，如果竞争失败则需要在阻塞、唤醒上浪费时间。采用自旋锁（ReentrantLock）则能够避开线程调度。选好了锁，我们再想想，到底哪里需要锁？我们使用锁的目的就是利用它的顺序性，也就是所谓的happen before，即后进入锁的线程一定能够看到先前持有锁进程产生的修改——后来的线程在读取世界状态时，必须能够看到之前由多个线程计算出来的状态。可我们真的需要使用锁来保证这一点吗？除了锁，只读内存也是同步安全的，只读就是所谓的immutable，不可变对象。通过游戏规则可知，所有细胞必须同时更新，因此这不可能是就地更新，也就是说，我们从当前世界读取状态，然后将修改写入其他地方。如果当前世界是不可变的呢？这样一来，读取的时候我们就不需要锁了。读取的时候不需要锁并不意味着不需要锁了。上锁的时机从读取时提前到了创建对象时。计算下一步的状态仍然需要一个可修改的状态，我们仍然需要使用锁来写入，而读取的时候也需要锁来保证我们可以看到其他线程的修改。但如果我们在计算完成后抄写一份，我们只需要在这里上一次锁，然后将抄写的结果作为不可变对象使用，那么之后就不再需要上锁了。实现细节WorldMap“世界”的实现如下：package info.skyblond.pocog import java.util.concurrent.locks.ReentrantLock import kotlin.concurrent.withLock class WorldMap private constructor( val height: Int, val width: Int, private val data: Array<IntArray> ) { init { require(height == data.size) { "Height doesn't match the data" } val wordWidth = width / Int.SIZE_BITS + if (width % Int.SIZE_BITS == 0) 0 else 1 for (i in 1 until data.size) { require(data[i].size == wordWidth) { "Rows have different width" } } } operator fun get(x: Int, y: Int): Boolean { require(x in 0 until width) { "x out of bound" } require(y in 0 until height) { "y out of bound" } val wordIndex = x / Int.SIZE_BITS val wordOffset = x % Int.SIZE_BITS return data[y][wordIndex] and (1 shl wordOffset) != 0 } class Builder( private val width: Int, private val height: Int ) { // ...... } } 这里可以看到，WorldMap的底层还是一个data数组，但是整个实现中都没有写入数组的代码。没有修改，也就不需要同步，自然也不需要锁了。而为了方便构造实例，我们在内部实现了一个Builder： class Builder( private val width: Int, private val height: Int ) { private val wordWidth = width / Int.SIZE_BITS + if (width % Int.SIZE_BITS == 0) 0 else 1 private val data = Array(height) { IntArray(wordWidth) } private val locks = Array(height) { ReentrantLock() } operator fun set(x: Int, y: Int, newValue: Boolean) { require(y in 0 until height) { "y out of bound" } require(x in 0 until width) { "x out of bound" } val wordIndex = x / Int.SIZE_BITS val wordOffset = x % Int.SIZE_BITS locks[y].withLock { if (newValue) setTrue(wordIndex, wordOffset, y) else setFalse(wordIndex, wordOffset, y) } } private fun setTrue(wordIndex: Int, wordOffset: Int, y: Int) { val mask = 1 shl wordOffset data[y][wordIndex] = data[y][wordIndex] or mask } private fun setFalse(wordIndex: Int, wordOffset: Int, y: Int) { val mask = (1 shl wordOffset).inv() data[y][wordIndex] = data[y][wordIndex] and mask } fun build(): WorldMap { val result = Array(height) { IntArray(wordWidth) } for (i in data.indices) { locks[i].withLock { System.arraycopy(data[i], 0, result[i], 0, wordWidth) } } return WorldMap(height, width, result) } }这个Builder不是线程安全的：当最终调用build时，程序会依次获取每一行的锁，将当前的结果拷贝到一个数组里。如果此时其他行发生了修改，那么就无法保证一致性了。至于选用行锁，单纯是因为可重入锁不涉及阻塞和唤醒，竞争失败的代价很小，同时操作也仅仅是读取、位运算并赋值，没什么耗时操作，因此粗略的选用行锁不会带来太大的性能惩罚。游戏游戏本身也不难实现，这里定义了一些基础的功能：package info.skyblond.pocog import java.util.* import java.util.concurrent.CompletableFuture import java.util.concurrent.ForkJoinPool import java.util.concurrent.locks.ReentrantLock import kotlin.concurrent.withLock class ConwaysGame( val gameWidth: Int, val gameHeight: Int, val heightSubdivisionSize: Int, val parallelism: Int ) : AutoCloseable { private val lock = ReentrantLock() private val threadPool = ForkJoinPool(parallelism) val gameSize = gameWidth.toLong() * gameHeight.toLong() @Volatile private lateinit var cellStatus: WorldMap @Volatile private var nextCellStatus: WorldMap? = null fun reset(generator: (x: Int, y: Int) -> Boolean) { val builder = WorldMap.Builder(gameWidth, gameHeight) for (i in 0 until gameWidth) { for (j in 0 until gameHeight) { builder[i, j] = generator(i, j) } } cellStatus = builder.build() } fun countNeighbors(x: Int, y: Int): Int { var counter = 0 for (i in x - 1..x + 1) { for (j in y - 1..y + 1) { if (i == x && j == y) continue // count if in range if (i in 0 until gameWidth && j in 0 until gameHeight) { if (cellStatus[i, j]) counter++ } } } return counter } private fun updateCell(builder: WorldMap.Builder, x: Int, y: Int) { val currentStatus = cellStatus[x, y] val neighbor = countNeighbors(x, y) if (currentStatus) { // Any live cell with two or three live neighbours lives on to the next generation. // Any live cell with fewer than two live neighbours dies, as if by underpopulation. // Any live cell with more than three live neighbours dies, as if by overpopulation. builder[x, y] = neighbor in 2..3 } else { // Any dead cell with exactly three live neighbours becomes a live cell, as if by reproduction. builder[x, y] = neighbor == 3 } } private fun updateLine(builder: WorldMap.Builder, y1: Int, y2: Int) { // p1: top left, p2: bottom right for (j in y1 until y2.coerceAtMost(gameHeight)) { for (i in 0 until gameWidth) { updateCell(builder, i, j) } } } fun calculateNextTick(): Unit = lock.withLock { val builder = WorldMap.Builder(gameWidth, gameHeight) val futureList = LinkedList<CompletableFuture<Void>>() for (y in 0 until gameHeight step heightSubdivisionSize) { CompletableFuture.runAsync({ updateLine(builder, y, y + heightSubdivisionSize) }, threadPool).also { futureList.add(it) } } futureList.forEach { it.get() } nextCellStatus = builder.build() } fun useCellStatus( block: ((x: Int, y: Int, isNext: Boolean) -> Boolean) -> Unit ): Unit = lock.withLock { if (nextCellStatus == null) calculateNextTick() val func = fun(x: Int, y: Int, isNext: Boolean): Boolean = if (isNext) nextCellStatus!![x, y] else cellStatus[x, y] block.invoke(func) } /** * For debug only, make sure each cell is updated correctly. * */ fun checkResult() { useCellStatus { query -> // check result for (y in 0 until gameHeight) { for (x in 0 until gameWidth) { val current = query(x, y, false) val next = query(x, y, true) val nc = countNeighbors(x, y) if (current) { // current alive if (next) check(nc == 2 || nc == 3) { "($x, $y) should die, but alive, nc: $nc" } // still alive else check(nc < 2 || nc > 3) { "($x, $y) should alive, but die, nc: $nc" } // die next tick } else { // current die if (next) check(nc == 3) { "($x, $y) shouldn't alive, but did, nc: $nc" } // alive next tick else check(nc != 3) { "($x, $y) should alive, but didn't, nc: $nc" } // still die } } } } } fun swapToNextTick(): Unit = lock.withLock { // done update, swap status if (nextCellStatus == null) calculateNextTick() cellStatus = nextCellStatus!! nextCellStatus = null } override fun close(): Unit = lock.withLock { threadPool.shutdown() } }应该都比较直观。其中reset提供了一种设置游戏初始状态的方式，updateCell用于更新一个细胞，而updateArea则用于更新一个举行范围内的细胞。calculateNextTick函数根据创建实例的参数，分区域指派任务，这个任务由线程池执行，所有计算执行完毕后函数返回。接下来用户可以使用useCellStatus来访问细胞状态。你会发现这几个函数都是同步的，这是保证这些操作是互斥的/顺序的。换句话说，你得先等着状态计算完毕，才能使用状态，或者进行别的操作。同样地，你得等别人操作完了，才能通过swapToNextTick步进到未来。这里checkResult是一个调试用的函数，它通过检查当前和未来的状态来检查游戏是否正确更新了每一个细胞。正确性验证当然，代码写完了还得确保它能正确运行： val game = ConwaysGame(1000, 1000, 100, 23, 8) game.reset { _, _, -> Random.nextBoolean() } for (i in 0 until 1000) { game.calculateNextTick() game.checkResult() game.swapToNextTick() } game.close()这个代码会随机填充世界，并开始迭代。每次迭代都会检查程序的正确性。在这篇文章中，单元测试并不是主要内容，因此只要使用某种方法确认程序运转正确即可。如果实在不想写代码，将每次迭代的结果打印到终端，人肉检查也是可以的。性能调节单元测试不是重点，性能调节才是。你看，在创建Game实例的时候有很大的灵活性。除了世界的大小由用户指定之外，每个线程计算的区域大小，分配多少个线程，这些也要用户来指定。如果每个线程计算的区域太小，那么CPU资源就会浪费在给线程分配任务上；如果计算区域过大，那么线程得不到充分利用，就没法完全释放性能。此外，面积相同的情况下，行和列的尺寸对性能也会有影响（CPU缓存更偏好行）。此外，如果线程数太多，会加剧操作系统调度线程的压力，如果线程太少，那计算任务又分配不过来。而且最重要的是，调节这些参数不能凭感觉，那怎么办呢？我曾经在调试Minecraft服务器的性能的时候做过简单的性能测量，但那样笼统的性能测量在这里是不适用的。要知道，JVM在运行时是一个复杂的系统，除了不确定的垃圾回收之外，还有各种优化器会随时加入进来，将字节码优化成二进制指令。在这方面而言，Java程序并不是幂等的。那怎么办呢？实现JVM的那帮人也有相同的疑问，于是他们写了一个性能测量工具，叫做JMH。它主要用于“微基准测试”，也就是说，用于测量一些微小细节的性能的工具，例如测量i++和++i到底能差出几纳秒。我们当然不需要测量的那么精准，我们只需要这个框架帮我们排除JVM优化以及垃圾回收这些元素的影响。至于JMH框架的具体使用就不说了，这里放一个代码：package info.skyblond.pocog import org.openjdk.jmh.annotations.* import kotlin.random.Random open class TestBench { @State(Scope.Benchmark) open class ExecutionPlan { @Param("1", "10", "50", "100", "300") open var heightSubdivisionSize = 0 @Param("12") open var parallelism = 0 private val random = Random(1234) @Volatile lateinit var game: ConwaysGame @Setup fun setUp() { game = ConwaysGame( 600, 600, heightSubdivisionSize, parallelism ) game.reset { _, _ -> random.nextBoolean() } } @TearDown fun tearDown() { game.close() } } @Benchmark @Fork(1) @Warmup(iterations = 5) @BenchmarkMode(Mode.Throughput) fun conway(plan: ExecutionPlan) { plan.game.calculateNextTick() plan.game.swapToNextTick() } } 这里根据三个参数进行测试，分别是高度和线程数。测试的结果比较直观：高度为10和50时取得了较高的性能：每秒320步迭代。细化测试参数，将高度修改为：5、10、25、50、55，第二轮测试发现高度为25时性能最高。为了避免用户手动设置，可以按照面积恒定的原则来计算：上述测试中宽600，高25，每个线程计算15000个格子。当宽度变化时，可以根据15000÷宽度得到对应的高度：(15000 / gameWidth).coerceAtLeast(1)可视化？文章写到结尾，好像还没有谈及可视化。如果没有可视化，这玩意儿就只是在内存里的0和1。涉及到模拟的东西，它是一种动态的过程，所以我更希望能够以动图或视频的方式展现出来，而不是一堆数字编号的jpg图片。我本来是想用ffmpeg来一边模拟一边生成视频的，但是看起来这个工具好像只能接收图片输入。索性今天看到了一个叫做humble-video的Java库，能够将Java生成的BufferedImage编码成视频文件。在下一篇文章中，我将介绍如何使用这个工具来生成视频。-全文完-
本文将记述如何在JVM上使用Lua脚本。众所周知，JVM上运行的都是字节码，而要得到字节码，就离不开编译。而脚本的目的就在于不进行事先编译的情况下提供一个灵活的控制系统。谈及脚本语言，JavaScript和Python算是两个比较火的编程语言了，但是我认为他们都太复杂了，不够优雅。我心目中比较理想的脚本语言是Lua，它比较简单，而且能够面向特定领域。如果说Python是为了解决任何可以通过编程解决的问题而设计的，那么Lua可能就是为了解决某个特定领域中的问而设计的。例如大名鼎鼎的Cheat Engine，他就支持用户使用Lua脚本来操作程序的内存，或者将Lua脚本编译成机器指令插入到源程序中，这可比写汇编容易不少。除了Lua，似乎也可以为某一个特定领域创建一门语言，来自JetBrains的MSP工具就是为此而生。但是为此你需要自定义一套语法规则，相当于为了你的领域而单独创造一门编程语言，即便它非常简单。这对我来说有些因小失大了——引入脚本最初是为了简化开发，同时提供足够的灵活性，而为了达到这个目的要设计一个全新的语言，我想这对开发者、对用户的心智负担都不小。本文将记述我在JVM平台上使用Lua脚本的过程。LuaKLuaK是隶属于KorGE的Lua库，其旨在将LuaJ迁移到Kotlin上。其中KorGE是一个基于Kotlin的游戏引擎。但这个库看起来还在开发中，暂时没有可以使用的文档与制品。我个人比较期待这个库，但是目前还没有完工，只能寻求别的代替品了。Luaj经过一番搜索，我找到了一个有年头的库，LuaJ，有年头到什么程度呢？就是最后一次更新的时候（2019年3月，3.0.2发布），社区开发者没能联系上原作者，进而无法为Maven仓库上的制品进行更新。于是使用时只得将库下载到硬盘上进行使用。这让我想起了早年间我学习Java，还不会用maven、gradle这些工具时，就从网络上下载依赖的jar，让IDEA帮我管理依赖。总之，通过类似implementation(files("lib/luaj-jse-3.0.2.jar"))的语句就可以让gradle使用本地的jar依赖了。这个库在功能上还是比较丰富的：例如执行Lua脚本（使用库的API），提供脚本执行引擎（使用Java Scripting API），Lua解释器（将Lua脚本处理为语法树，使用Java访问语法树），Lua编译器（将Lua脚本编译成LuaVM的字节码），Lua到Java编译器（将LuaVM的字节码翻译成JVM字节码）。而以上所有内容都跟C代码没有任何关系——纯Java实现。当然了，本文的目标很简单：让Java能够为Lua脚本提供新的能力，并且在Lua脚本中调用Java提供的能力。经过一番查阅，LuaJ为扩展提供了较为方便的接口，其中比较重要的就是TwoArgFunction。从名字来看，这个抽象类似乎是描述了一个具有两个参数的函数，但LuaJ将其用作加载库的方式。具体来说，当我们在Lua脚本中require 'MyCustomLib'时，LuaJ会搜索classpath中所有实现了LuaFunction、并且具有默认构造函数（即无参数的构造函数）的类，如果找到了name为MyCustomLib，就把这个类当作一个函数来执行，其中第一个参数是模块名（modname，也就是MyCustomLib），第二个参数就是调用者的环境。通过操作环境可以在环境中注册库，之后的代码便可以调用我们的库了。需要注意的是，前文说的name并不是传统意义上的类名，而是Class.java中getName()返回的类名。因此对于info.skyblond.demo.lua.luaj包中的MyCustomLib类，他的name是info.skyblond.demo.lua.luaj.MyCustomLib。如果仅用MyCustomLib，LuaJ是找不到对应类的。这里我编写了一个简单的例子，展示了LuaJ提供的无参函数、单参函数、双参函数、三参函数和可变参函数：package info.skyblond.demo.lua.luaj import org.luaj.vm2.LuaFunction import org.luaj.vm2.LuaTable import org.luaj.vm2.LuaValue import org.luaj.vm2.Varargs import org.luaj.vm2.lib.* import java.math.BigDecimal import java.math.BigInteger import java.time.Duration class MyCustomLib : TwoArgFunction() { /** * Will be called when executing `require 'MyCustomLib'`. * Then the "MyCustomLib" will be the moduleName. * The env is the environment of that env. * And this func needs to return a [LuaTable]. * The key is func name, the value is [LuaFunction] * */ override fun call(modname: LuaValue, env: LuaValue): LuaTable { val library = tableOf() library.set("getMilli", GetMilliSecondFunc()) library.set("addOne", AddOneFunc()) library.set("longestStr", LongestStringFunc()) library.set("futureMilli", FutureMilliFunc()) library.set("hello", TestFunc()) env.set("MyCustomLib", library) return library } class GetMilliSecondFunc : ZeroArgFunction() { override fun call(): LuaValue { return LuaValue.valueOf(System.currentTimeMillis().toString()) } } class AddOneFunc : OneArgFunction() { override fun call(p0: LuaValue): LuaValue { // in Lua, int, double, long are all "number" return when (p0.typename()) { "number" -> { val number = p0.checknumber() number.add(1) } "string" -> { val str = p0.checkstring().tojstring().lowercase() if (str.contains(".") || str.contains("e")) { // decimal val result = str.toBigDecimal().add(BigDecimal.ONE) val er = result.toEngineeringString() val pr = result.toPlainString() if (er.length < pr.length) { LuaValue.valueOf(er) } else { LuaValue.valueOf(pr) } } else { // integer val result = str.toBigInteger().add(BigInteger.ONE) LuaValue.valueOf(result.toString()) } } else -> error("Invalid arg type: ${p0.typename()}") } } } class LongestStringFunc : TwoArgFunction() { override fun call(p1: LuaValue, p2: LuaValue): LuaValue { val str1 = p1.checkstring().length() val str2 = p2.checkstring().length() return if (str1 >= str2) p1 else p2 } } class FutureMilliFunc : ThreeArgFunction() { override fun call(p0: LuaValue, p1: LuaValue, p2: LuaValue): LuaValue { val currentMilli = p0.checkstring().tojstring().toLong() val number = p2.checkstring().tojstring().toLong() val offset = when (p1.checkstring().tojstring().lowercase()) { "millis" -> Duration.ofMillis(number) "seconds" -> Duration.ofSeconds(number) "minutes" -> Duration.ofMinutes(number) "hours" -> Duration.ofHours(number) "days" -> Duration.ofDays(number) else -> null }?.toMillis() return if (offset != null) { LuaValue.valueOf((currentMilli + offset).toString()) } else { error("Invalid duration type: $p1") } } } class TestFunc : VarArgFunction() { override fun invoke(args: Varargs): Varargs { // note: Lua start index from 1 for (i in 1..args.narg()) { val arg = args.arg(i) println("Arg#$i: $arg (${arg.typename()})") } return LuaValue.valueOf("Vararg result!") } } }这些代码都可以在Lua中被调用。测试用的Lua脚本如下：-- get Java lib loading in the env require 'info.skyblond.demo.lua.luaj.MyCustomLib' -- test normal print print('Hello world!') -- zero arg func print('GetMilli', MyCustomLib.getMilli()) -- one arg with multiple arg types print('AddOne', MyCustomLib.addOne(123)) print('AddOne', MyCustomLib.addOne(128.5)) print('AddOne', MyCustomLib.addOne('999999999999999999')) print('AddOne', MyCustomLib.addOne('1e-6')) -- two arg func print('LongestStr', MyCustomLib.longestStr('aa', 'bbb')) -- three arg func print('FutureMilli', MyCustomLib.futureMilli(MyCustomLib.getMilli(), 'days', 1)) -- var arg func print('VarArg', MyCustomLib.hello('str', 222, true))为了方便起见，我直接从字符串加载Lua脚本了：package info.skyblond.demo.lua.luaj import org.luaj.vm2.lib.jse.JsePlatform object TestLuajBasic { @JvmStatic fun main(args: Array<String>) { val globals = JsePlatform.standardGlobals() globals.load(MyCustomLib()) println(MyCustomLib::class.java.name) val chunk = globals.load("...Lua脚本...") chunk.call() } }这里为了确认类的名字，我打印了MyCustomLib::class.java.name。这一行println并不是执行代码必须的。执行结果如下：info.skyblond.demo.lua.luaj.MyCustomLib Hello world! GetMilli 1659595842222 AddOne 124 AddOne 129.5 AddOne 1000000000000000000 AddOne 1.000001 LongestStr bbb FutureMilli 1659682242233 Arg#1: str (string) Arg#2: 222 (number) Arg#3: true (boolean) VarArg Vararg result!嗯，目的达成。不过有些老代码确实让我耿耿于怀，这个库支持的Lua版本是5.2，而最新版已经到了5.4。虽然说功能很强大，但是通过GitHub来看，大部分代码都已经大约七八年没有更新了，最老的代码已经有12年之久。如果是业务代码到还无所谓，我比较担心的是将LuaVM字节码翻译成JVM字节码时，能否利用到最新的字节码（这部分相关的代码是2012年10月更新的，那时候Java7刚问世一年）。不过抛开这部分功能，Lua 5.2还是够用的，并且Java的一个好处就是能够保持代码不变，而仅通过升级JVM版本就能获得性能提升。并且得益于Java API的稳定性，这样的老代码能够完全兼容Kotlin并运行在Java17上。-全文完-
【代码札记】基于 Merkle DAG 的文件存储服务 P4 API接口 & SpringBoot初入门
上文中实现了一个简单的概念原型，但是每次要用都得打开IDEA改代码，给人一种不可靠的感觉。经过一番搜索，我发现IPFS也提供基于HTTP的接口，我决定仿照IPFS也弄一个HTTP API。虽然我是写Java的，可我从来没用过Spring相关的东西（Spring框架是一系列简化开发的库的合集，而当Spring这套框架变得愈加复杂时，人们构建了SpringBoot来简化Spring框架的使用）。我一直觉得对于个人的小项目来说用Spring过于庞大了，所以以前我比较青睐诸如Javalin和Ktor这样的框架，用于快速构建一个HTTP API，但是他们仅仅是一个提供HTTP API的库，当程序需要可配置性的时候，通常需要一个yml（我个人比较青睐这个格式作为配置文件）文件进行配置，于是解析配置、拉起服务等操作都需要我自己写代码。一个两个还行，等项目多了，或者说，一个项目里的配置多了起来，自己维护这一套代码就变得极其繁琐。最近我在考虑为这个系列做一个HTTP API，找了一圈，这些库虽然说小巧好用，但跑不掉自己要做好多铺垫/善后。最终还是找到了Spring，与几年前不同，现在可以直接通过官方的网页版交互式选择你需要的配件，然后自动生成项目模板。我一直不愿意碰Spring的原因之一就是它本身过于庞大，给人一种无从下手的感觉。至少SpringBoot在这方面减轻了我启动项目的痛苦。项目总览经过大约三四天的编码，我成功的将原来的代码迁移到SpringBoot框架中，其中重构了不少东西，并且大部分东西都搞成用Java编写了。SpringBoot对于Kotlin的支持还比较有限，一些东西和Kotlin混合起来之后会引发一些奇怪的问题，所以我比较青睐的做法是大部分基础设施使用Java编写，比如配置和数据库实体什么的，然后一些工具类或者数据模型使用Kotlin，后者在写法上会方便不少（尤其得益于data class及不严格要求一个public class独占一个文件）。通过大约上千次谷歌搜索，我终于让Gradle（with Kotlin DSL）、protobuf、lombok、SpringBoot和Kotlin能够在一个项目中融洽相处。现在的项目中有这么多文件：对比之下，原来的工程全部展开也只有这么一点文件：并且虽然这些组件可以在一个工程中和睦相处，但实际上lombok和Kotlin还是没有办法一起工作。因为Hibernate使用代理类来监测实体，而Kotlin默认的类和成员全都是final，因此使用Kotlin来编写数据库实体就不可避免的要滥用open关键字，同时Hibernate依赖setter来更新数据，因此数据库中具有不可变语义的列被声明为val时将会导致Hibernate无法为查询结果赋值，而声明为var就失去了Kotlin中不可变成员变量的优势。因此最终决定还是使用Java来编写数据库实体类，然后使用Lombok处理Getter和Setter。但是因为Kotlin要先于Java编译（否则Java编译时找不到Kotlin依赖），而此时Lombok的注解处理器来没有开始工作，因此使用@Getter和@Setter标注的类，这时候还没有对应的方法被生成。所以在Kotlin中没办法使用依赖Lombok的Java类。但好在需要Lombok的地方只有数据库实体，而与数据库相关的操作可以封装到由Java实现的服务里，通过巧妙的设计可以让Kotlin和Lombok互不见面，从而避免产生问题。项目结构在切换到SpringBoot之后我发现原来的一些设计并不能直接拿来用。在Spring中引入了控制反转（Invert of Control），即由框架调用你的代码。在传统的编程中都是你的程序调用框架来完成一些事情，比如你的程序调用Jackson或者Gson将一个字符串转换为一个对象，这个是控制。而在处理HTTP请求时，别人的代码调用你的代码，这个就有点反转控制的意思了。控制反转更严格的说法是基于对象的，在Java中所有的数据和操作都封装在对象中，因此当你的代码需要利用Jackson或者Gson做什么的时候，至少需要先实例化一个ObjectMapper或者Gson对象，然后拿着这个对象去做事。这个过程中你的代码控制这个对象如何实例化；在控制反转中，你的代码接受一个对象作为入参，而不必（也无法）控制这个对象在何时何地如何实例化的，只管用就是了。好在原来的程序中我设计了不少接口，所以迁移起来还是比较方便的。反转控制带来的好处就在于程序代码之间只经过接口约定，而不必假定对方是如何实现的。大多数情况下接口是一个相对比较强的约束（但没办法程序化的约定实现效果——程序员只能将要求的实现效果，诸如原子性，写在JavaDoc中并祈祷子类这样实现）。在重构后的设计中一共有三个服务：ProtoMetaService、ProtoStorageService和ProtoService。Meta和Storage都只面向不同的后端存储元数据和数据，并不关心这些数据如何去重，如何与其他数据联系起来，干就完了。元数据存储还好说，目前的同一实现是使用JPA在关系型数据库上提供持久化存储（不使用NoSQL的原因在于这东西没必要用NoSQL存，反正都已经SpringBoot了，RDB不可避免，索性就完全拥抱RDB了），配合Redis实现分布式锁，保证同一时间同一个键只有一个调用者可以修改（这样做的原因是为了拥抱Hibernate提供的ORM特性，同时不必自己写SQL，并且在Redis上竞争锁的性能会更高一些）。得益于JPA的抽象，元数据并不挑数据库，无论是MySQL还是PostgreSQL，只要能接到JPA上就可以，而分布式锁也就是一个Redis，没什么好挑的。而数据存储就不一样了，目前开发用只是将数据存在文件里，之后为了实用性需要接入AWS S3，或者为了花哨一些而接入IPFS。在面对不同的存储后端时只考虑如何读何如写，这种纯粹性能带来非常高的编码效率——试想一下不光要处理如何读如何写，还得面向不同的存储后端解决怎么去重/复用，想想就头皮发麻。至于数据切片、去重和重建，我把这些工作全都交给了ProtoService，它会利用Meta和Storage（当然，实现者也可以不用，他/她开心就好）来完成底层数据的存储而不必关心实现，只专注于如何去重，如何重建。还是那句话，设计的纯粹性能带来非常高的效率，虽然在上文中实现快速原型时大可不必如此，但从长期的可维护性来看，这样设计受益会更高（翻译：日后维护不会很痛苦）。关于其他SpringBoot的基建就不多赘述了——诸如JpaRepository、Entity描述什么的。这里简单说说给我眼前一亮的地方。还记得开头说的使用Jackson解析配置文件吗？SpringBoot能帮我把这部分自动化了，然后配合依赖注入，写程序真的太爽了。一个很现实的需求就是要根据不同的配置文件来决定使用哪一个存储后端。通过SpringBoot的自动配置就可以直接把枚举值写到application.yml里，然后对应的Java代码中加几个注解，配置文件里的值就能自动映射到对象中的成员变量上，最后通过依赖注入获取这个对象，然后解析内容构建对应的存储后端，把这个构建的对象返回给Spring。在之后这个对象（Bean）就可以注入到其他代码里作为存储后端使用。一气呵成，非常舒服，再也不用自己写代码解析yml了。接口设计上面吹了一波Spring的好处，但是我觉得还是得自己先不用Spring写几个项目，再去接触Spring才会有所感受，才能理解他这里面为什么要这么设计。对于接口方面，比起使用Javalin或者Ktor自己注册Handler，Spring的Controller让代码更加结构化（也就是MVC里面的C）。关于Proto的接口设计如下：/proto + /chunk | + Post: Upload chunk of data and get links to blob or list | + Get: Download chunk of data from a link to blob or list | + /tree | + Post: Create a tree obj from list of links | + Get: Get the list of links from a link to a tree obj | + /commit | + Post: Create a commit obj from the given info | + Get: Display the info of a link to commit obj | + /restore | + Post: Restore and return all involved blob object links from a list of links | + /status | + Get: Query the info of given links根据Proto已有的操作，chunk接口能够操作blob和list类型，用于读写整块数据。而tree和commit就分别操作树和快照对象。而restore则用于告诉存储后端恢复/准备某些proto以供读取，并返回这些proto涉及到的其他proto，如果选择不进行操作，该接口也可以单纯用于列出这个proto所涉及的子proto。最后status则是用于查询给定Proto的信息，比如类型、文件信息、存储状态等。之后还会有一个接口，面向用户界面提供一个类似文件系统的功能，然后利用前端调用proto接口进行数据的上传、修改等。项目地址由于我比较懒，并不想详细的总结什么东西，因此这篇文章写的也比较草率，放一个项目链接吧：GitHub。在这里可以看到这个项目的全部代码，并且可以看到我用了一些比较花哨的东西，比如OpenAPI之类的东西。目前代码量算是一半一半：总之这篇文章就先到这里了。周末突然发现这个月的更新还完全没写，于是赶紧摸了一篇。-全文完-
上文中讨论了关于Merkle DAG的一些基本概念和原理，本文将记述其具体实现。存储结构结合上文来看，本系列中Merkle DAG的使用方法还是更接近IPFS一些，于是我便参照IPFS的白皮书设计了一下。为了使数据具有统一的序列化标准，我使用了Protobuf。syntax = "proto3"; message AritegObject { // Type of this object AritegObjectType type = 1; // blob data content bytes data = 2; // list, tree and commit links // Note: commit link has fixed name: parent, link, author repeated AritegLink links = 3; // commit data AritegCommitData commit_data = 4; }AritegObject是所有Object的超集，它具有所有Object需要的字段，并且内置了一个type用来描述该Object是何种类型：enum AritegObjectType { BLOB = 0; LIST = 1; TREE = 2; COMMIT = 3; }这里一共设计了4个Object，与前文介绍的IPFS中的Object类型一样。另外IPFS中还定义了加密和签名的Object，用于IPNS，由于本文的目的是一个简单的文件存储服务，所以并不考虑对存储数据的处理（签名、加密等）。即便是要加，可以简单的在程序方面增加， 而不必修改底层设计。对于links，设计与IPFS的类似：message AritegLink { // name of the link string name = 1; // multihash of target bytes multihash = 2; }这里没有记录目标对象的大小，因为与IPFS不同，IPFS获取对象前无法知晓对象的大小，因此必须记录下来以供申请合适大小的缓冲区。而我们的系统将所有数据集中存储，因此给定一个目标的multihash，必定能够知道该对象的字节数目。对于commit类型的Object，使用一个专门的域来存储某次提交的信息，结构如下：message AritegCommitData { // type of committed object AritegObjectType type = 1; // unix timestamp of this uint64 unix_timestamp = 2; // commit message string message = 3; }逻辑结构基于上述存储结构，可以引申出4个逻辑结构，分别对应blob、list、tree和commit。抽象类为了适应Protobuf生成的类与四个逻辑结构能够相互转换，首先定义如下抽象类：package info.skyblond.ariteg.objects import info.skyblond.ariteg.AritegObject import info.skyblond.ariteg.AritegObjectType abstract class AbstractAritegObject { /** * Convert current instance to proto * */ abstract fun toProto(): AritegObject // If bytes are same, then they are same override fun equals(other: Any?): Boolean { if (this === other) return true if (other !is AbstractAritegObject) return false val thisBytes = this.toProto().toByteArray() val otherBytes = this.toProto().toByteArray() if (!thisBytes.contentEquals(otherBytes)) return false return true } // hash is the byte content override fun hashCode(): Int { return this.toProto().toByteArray().contentHashCode() } } abstract class AbstractAritegObjectCompanion<T>( protected val expectedType: AritegObjectType ) where T : AbstractAritegObject { /** * If the object is type * */ fun isTypeOf(proto: AritegObject): Boolean { return proto.type == AritegObjectType.BLOB } /** * Generate instance from proto. * */ fun fromProto(proto: AritegObject): T { require(isTypeOf(proto)) { "Expect ${expectedType.name} object but ${proto.type.name} object is given" } return toInstance(proto) } protected abstract fun toInstance(proto: AritegObject): T } AbstractAritegObject类描述了一个Object应该有哪些方法，由于里面覆盖了来自Any（Kotlin世界中的万物之父java.lang.Object）的equals和hashcode方法，统一利用其内容的字节进行比较，所以使用了抽象类。自从Java 8中给接口引入了默认方法之后，很大一部分情况下接口与抽象类在功能上可以相互替换了，但这里由于覆盖了来自其他类的方法，所以不能使用接口。由于使用Kotlin，所以Object的构造应当由静态工厂方法来担任，Object本身应当设计成不可变对象，这样之后的序列化到字节数组，以及多线程的使用会方便和安全许多。另外系统中的Object是通过其内容的哈希来索引，如果内容变了，那么内存中对该对象的引用和逻辑上哈希的引用出现了冲突，会带来额外的麻烦，所以Object本身不可变，由一个工厂方法负责构造，由一个成员方法负责将其转换为Protobuf的生成类，这样应该算得上是最优实践了。在Kotlin中没有static关键字，一般类中的静态方法是依靠companion object来实现的，因此还得针对compainion object设计一个抽象类，即AbstractAritegObjectCompanion<T>，泛型表示该伴生对象产生的Object类型，应当是AbstractAritegObject类的子类。这里没有使用接口的原因是其拥有一个protect修饰的成员变量，该变量记录本对象接受的Protobuf对象的类型，并在转换前进行检查，这样即可复用类型检查的代码（很显然你不希望在每个具体实现中检查传入的proto是不是拥有正确的type）。具体实现在有了如上两个抽象类之后，我们可以开始搞具体实现了。之前说过，所有的Object类应当是不可变的，Kotlin当中的data class较为方便的提供了这个特性。BlobObject的实现如下：data class AritegBlobObject( val data: ByteString ) : AbstractAritegObject() { companion object : AbstractAritegObjectCompanion<AritegBlobObject>(AritegObjectType.BLOB) { override fun toInstance(proto: AritegObject): AritegBlobObject { return AritegBlobObject(proto.data) } } override fun toProto(): AritegObject { return AritegObject.newBuilder() .setType(AritegObjectType.BLOB) .setData(data) .build() } }这里ByteString是Protobuf提供的对字节串的描述，相比字节数组，其本身具有不可变性，与String一样。AritegBlobObject自身实现了AbstractAritegObject，它只要实现toProto方法即可。其伴生对象实现了AbstractAritegObjectCompanion<AritegBlobObject>，只需要覆盖toInstance方法即可享受到转换前的自动类型检查。使用实例上述数据结构在代码中使用时如下图。最顶层的AritegCommitObject表示一个commit，内部除了有本次提交的相关信息之外，还有一个AritegLink作为指针，指示本次提交的根对象。本例中是一个AritegTreeObject，其内部有一系列AritegLink，每个代表一个子对象。子对象可以是其他tree，list或blob，而list的子对象可以是其他list或blob。本例中还给出了一个blob复用的情况：如果恰好存储了具有相同哈希的blob块，那么可以直接引用已有的数据，而不必再单独存储一份。如果只存储一份可能效果不明显，如果一个文件或目录有多个版本，目前所有S3的做法都是把旧版本复制一份单独收费，而使用这种文件切块的方式，则可以复用已有的块。假如一个20GB的文件改变的范围可以有一个blob描述，那么两个版本大小加起来只有20GB+1个blob，而S3则需要40GB。这种做法可以极大的减少开销。最顶层的对象只需要使用一个Base58编码的Multihash即可找到，便于人类查询。哈希碰撞由于整个系统使用数据的哈希作为索引，由于输入空间无限大（默认每个blob是256k，但不足256k的也可以单独程为要给blob，如果用户愿意，任意不同大小的blob相互组合也是合法的，这样一来扔进哈希函数的数据长度就是任意的，那么数据的内容也就是无限种情况），而输出空间只有固定大小（IPFS使用SHA256，我准备使用SHA3-512），回忆我们中学或小学时学到的抽屉原理，势必会有两个及更多个不同的输入对应同一个输出哈希，这种情况下，某一块的blob哈希重复，但内容不相同，文件势必会损坏，这种情况应该如何应对？技术上最简单的方法就是同时使用三种不同的哈希函数，由于两个哈希函数对于同一个输入同时碰撞的几率很小，可以认为是不可能事件，所以在AritegLink中存储三个哈希函数，每次读取读出三个数据，如果三个数据都相同，那么没有碰撞，万事大吉。如果有一个不同，则发生了碰撞，另外两个相同，选相同的两个作为读取的结果。这种解决方法将数据损毁的概率直接推向了不可能，但代价是同一份数据要以三个哈希存储三遍，付出三倍的存储代价。如果数据块的复用程度比较高，这种做法还有可能带来收益，但如果复用性较低，那么只会徒增存储成本。在IPFS社群中也有过类似的讨论。例如：「What to do in case of hash collision?」、「Hash collision/limitation in IPFS: is it possible?」、「IPFS collisions.」，以及SHA1被攻破的例子：「We have broken SHA-1 in practice.」。虽然最后一个例子很吓人——两个内容不同的PDF给出了相同的SHA-1哈希，但也只是个例。哈希碰撞在客观上确实存在，但和中彩票一样——你知晓它的存在，但很少遇见。而且就哈希函数的设计而言，一个好的哈希函数是无法预知输入与输出之间的关系，所以这种哈希碰撞完全是概率的（即，不是普遍现象）。系统中使用了Multihash存储不同哈希函数的结果，所以不同的哈希可以在系统中共存，因此在未来如果我们发现某个碰撞确实存在，那么可以简单的升级到一个更安全的哈希函数，虽然过程中可能需要重新对所有AritegLink涉及的数据重新计算哈希，但至少是可升级的，一个哈希函数的失效并不会给整个系统宣告死亡。至于上一篇文章开头问的，块复用有这么多好处，为什么没有人用？大概原因就是如此——虽然碰撞的概率很低，但谁也不想冒着数据损坏的风险来减少成本。这也是为什么大家都能够接受S3在开启版本控制时会收取多分费用的原因。
本系列将记述使用Merkle DAG实现一个文件存储服务。这个想法并非本人原创，在本文之前，以太坊、IPFS等去中心实现中都用到了类似的想法，但令人惊奇的是，竟然没有纯粹的将这个想法作为文件存储来实现的代码。可能是意义不大吧。本文作为整个系列的铺垫，将阐述这个需求的意义以及一些基本概念。Merkle DAG所谓Merkle DAG，其实分为两个部分：Merkle和DAG。DAG无需多说，是有向无环图的英文缩写。而Merkle是个人名，早年间他给这个东西注册了专利，所以才叫Merkle DAG或者Merkle tree。从技术上讲，Hash tree或者Hash DAG更直观一些。因为在这种有向无环图中使用了Hash来索引节点。最直观的理解就是把传统的DAG或者树中的指针全部替换成Hash。对于指针，它建立了节点（Node）与成员域（Field）之间的联系，即通过域中记录的指针（内存地址）可以找到一个节点，进而对该节点进行访问。但是指针中记录的内存地址与被指向的节点不具有唯一的对应关系，原则上同一个内存地址可以是任何节点，也可以不是节点。而Hash则具有相对唯一的对应关系，某个节点的Hash由其自身的内容决定，并且微小的改变都会使得Hash的计算结果与原来大相径庭（所谓的「雪崩效应」）。一个Merkle DAG节点可以抽象的标识成如下两种格式：public class MerkleNode<T> { final T data; final List<Hash> links; }public class MerkleNode<T> { final T data; final Set<Hash> links; }这两个区别是使用List存储Hash允许节点间维持相对顺序，而Set则不保证顺序。前者适用于表示大块数据（IPFS），后者适用于组织零碎节点（ETH）。其中links存储的是子节点的Hash。基于节点的定义，显而易见，Merkle DAG有三个特点。首先是整个DAG构建完成后即不可变，因为任何节点的改变，都导致自身Hash的变化，进而导致父节点内容改变，从而导致父节点的Hash变化，如此传播下去，最顶层的根节点的Hash也一定会改变（假定不会撞Hash）。第二个特点就是构造时必须自底向上构造，因为父节点要存储子节点的Hash，而子节点的Hash来源于自身的内容。因此构造时只有叶节点可以被最先计算Hash，然后逐级构造。第三个特点就是允许复用。这并非Merkle DAG的特点，一般的DAG也可以通过共享指针来复用节点，但基于Hash的复用允许我们更直接更自信的复用节点——相同的内容产生相同的Hash，考虑到撞Hash的可能性极小（或许压根儿不需要担心碰撞），我们完全可以认为Hash相同即内容相同。这也是基于内容寻址的核心想法。以上是Merkle DAG的原理，以下将利用IPFS和智能合约作为例子说明他们是如何使用这种DAG的。智能合约以太坊最近（一直）比较热门，它与比特币具有本质上的不同。比特币的核心是去中心分布式的账本，它使用节点度为1的Merkle DAG，实际上就退化成了使用Hash寻址的链表（这里省略了比特币的UTXO模型和挖矿的原理）。而以太坊除了要支持传统的交易之外，还希望引入能够根据条件自动执行的代码，即智能合约。简单回忆一下计算机组成原理，冯诺依曼结构的五大组成要素是：运算器、控制器、存储器、输入、输出。对于区块链来说，运算器和控制器由区块链虚拟机提供，存储器有区块链提供，表现为合约的存储区，该存储区为合约专属，本质上是区块链中的一块数据，表示合约的状态。输入输出则表现为调用合约时传入的参数，以及合约正常返回时的返回值。这样我们就可以实现一个简单的支持智能合约的区块链的。在以太坊中，运算器和控制器由EVM提供，即执行时以太坊节点根据实现约定的指令和行为对编译好的合约进行模拟执行（因为合约并不编译为x86或其他机器指令，而是EVM自定义的指令集），在调用合约时提供的参数作为输入，调用前的合约状态（合约存储区）作为存储器，用于存储持久化的数据（比如账户余额等），而合约结束后的返回值则作为输出发送给调用者。对于区块链节点来说，这个过程它只关心两个东西：调用前的合约状态和调用后的合约状态。要保证交易的可验证性，任何节点只要用同样的输入和同样的合约状态执行同样的合约代码，一定会得到同样的调用后的合约状态（假设其中不涉及预言机，Oracle，不是甲骨文）。而调用后的合约状态将在未来作为输入去验证后续的交易，至于输出，区块链节点并不关心。所以以太坊需要一种可靠并高效的机制来记录每个区块中所有合约的状态。于是就该轮到Merkle DAG出场了。在一个区块中，Merkle DAG表现为一个树，即每一个节点表示一个合约的存储区，这些存储区使用Hash寻址，组织成一棵树。但是有些合约不见得每个块都要变，于是利用DAG复用节点的原理，如果一个合约的存储区没有变，那就不要每个块都复制一遍，不如就直接用之前的状态。由于节点间不需要维护相对顺序，所以使用Set<Hash>就可以完成任务，并且在节点数量巨大的情况下，为了提高查找效率，还可以引入前缀树等优化手段。值得注意的是这里所说的并不完全是以太坊的工作机制，以太坊的每个区块中有三棵树，分别记录了世界状态、收据和交易。其中的数据结构根据实际需求有所变动，这里只是从解决需求和介绍Merkle DAG的角度泛泛而谈。下面有关IPFS的部分也一样，如果想要了解以太坊或IPFS的具体设计，不妨直接去阅读他们的白皮书。IPFSIPFS全称星际文件系统，旨在创建持久且分布式存储和共享文件的网络传输协议。它在文件存储的核心部分就是Merkle DAG。在IPFS中，最小的数据单位是Object：public class IPFSObject { final IPFSLink[] links; final byte[] data; } public class IPFSLink { final String name; final Multihash hash; final int size; }这是一种抽象的表示方法，可以看出这里的links和上面的List<Hash>类似，用以维护节点之前的相对顺序（毕竟数据块之前的顺序乱了，文件也有要不了了）。取决于各自的作用，Object有许多种分型。充当DAG中叶结点的是blob，它的特点是links为空，data是要存储的数据。在存储文件时，默认的切块大小是256KB，即每个blob的data域长度为256KB。将多个blob连起来，就变成了list，它所表示的数据即将其内部的blob和list按顺序拼接起来。它的data域指明了links中对应Object的类型（blob或list），links不具有name（因为没有意义）。默认情况下，一个list最多具有176个子节点。以上通过blob和list的组合可以实现存储任意大小的文件，对于文件夹，则可以使用tree。与list类似，data域存储Object类型，文件夹中的类型可以是blob（小于256KB的文件）、list（大于256KB的文件）和tree（子文件夹）。并且tree的links中的name即文件名或目录名。为了支持版本管理，IPFS还有一个commit类型的Object，由于Merkle DAG是不可变的，因此通过在commit中指向一个DAG的根节点，就相当于对这个DAG拍了个快照，之后无论数据怎么变动，commit永远指向这个快照所表示的状态，因此使用IPFS来实现Git也是有可能的。IPFS通过将上述不同种类的Object组织成Merkle Tree来灵活的表示任意大小的文件和文件夹，同时还具备版本控制功能。另外得益于基于内容寻址（也就是使用Hash索引节点），如果不同文件的某些切块重复，那么可以直接复用，从而节省空间。文件存储所以说回文章一开始的问题，为什么要用Merkle DAG（像IPFS一样）存储文件？文件存储对于IPFS来说并不是核心，它所要解决的问题是文件交换的效率。而我希望的是能够以这种方式存储/归档文件。谈起这种需求，大概还得从IBM Cloud说起。大约8月26日前后，我的IBM Cloud账号毫无征兆的被封了，于是痛失900GB数据，联系IBM Cloud无果（SoftLayer的客服就是逊），和其他人聊了聊，发现导致封号的原因可能是在他们家的云对象存储上存了大量的版权视频，因为我用那东西做备份来着，数据存放在美国，所以适用于美国的法律。现在我转到了AWS S3，因为他们家是最早一个做云服务的，所以我比较相信AWS的客服质量，只要封号之前告诉我一声就行了。但是为了避免发生类似的事情，同时希望能够借复用机制减少一些使用量（从价格上来说，我只用Glacier Deep Archive，其他的太贵），所以提出了这样的构想。在下一篇中我将介绍本项目的一些基本组件和相关数据结构。-全文完-
最近在用Java写智能合约，其中有一个静态字段是合约的管理员地址，这个地址用于鉴权，确保只有该地址能够对合约进行管理操作（升级、销毁等）。但是为了做到自动化测试，这个管理员地址在develop分支上是私链的，而实际部署的时候得换成公链上的另一个地址。前几天升级合约的时候忘记替换地址，直接把私链地址部署到了公开的测试网了。好在是测试网，问题不大，这要是主网就别玩了，重开吧。为了杜绝这样的后顾之忧，本文决定探索一种方法，能够一份代码按照使用情况填入不同的地址来生成合约，避免将地址写死在代码里产生问题。背景具体来说，这个区块链是Neo N3区块链，其中Java的语言支持由Neow3j这个库提供。这个库允许开发者使用任意JVM语言开发合约，并根据最终编译的Java字节码生成Neo的可执行合约。因此上文提到的合约就是使用Java开发的，没有用Kotlin的原因就是怕翻车。典型的合约管理员地址是将其作为一个静态字段实现的：public class TestContract { static Hash160 CONTRACT_OWNER = addressToScriptHash("NR9pwfToFHHYti4RY1dLP3wGr4waSGn7NH"); }其中NR9pwfToFHHYti4RY1dLP3wGr4waSGn7NH是用于测试的地址，其私钥随着代码一并公开到GitHub仓库，显然这种公开的钱包地址并不适宜作为公链的管理地址使用，但对于自动化测试来说，让程序获取到地址的私钥并进行自动调用，这可比手工测试轻松多了。其中的addressToScriptHash函数是Neow3j编译器提供的一个本地方法，它没有具体实现，而是在编译为合约的时候，由编译器将里面的字符串解读为NeoVM能够理解的钱包地址。这种方法最直观，官方的教程也是这样写的。看起来没什么问题，但涉及到实际使用和开发，就如同我所说的，自动化测试要求密钥开放，而实际部署要求密钥必须保密，如果在开发和部署两个分支上频繁修改这个地址，不美观且麻烦，最重要的是一旦忘记，会导致很大的安全隐患。另一个解决方法是在合约中获取当前网络的MagicNumber来判断网络类型，由合约自动决定使用哪一个地址。由于每个网络的魔数都是固定的，并且公共测试网和主网的数字都是固定不变的，这种方法相对可行，但额外的代码会给执行阶段带来额外的手续费（NeoN3的智能合约是按指令收费的），并且同时写两个地址，并不美观，也不优雅。解决为了美观优雅，我决定探索ObjectWeb ASM库，这个库用于直接操作底层的Java字节码。谈及Java，我的印象总是诸如“抽象”、“不关心底层硬件”、“面向Java虚拟机”之类的，所以我们在编写Java的时候只需要关注逻辑上的实现，而不必关心这套代码是否会在不同架构的CPU上有不同的行为。而能够支持这种功能得，正是Java虚拟机和Java字节码的配合，所有运行在Java虚拟机上的语言，包括Java、Kotlin，最终都要编译成Class文件。而这个Class文件中就包含了即将执行的Java字节码，可以理解为面向Java虚拟机的汇编语言。字节码初探以如下类为例：package info.skyblond.jvm.asm; public class ASMTargetClass { static Pair<String, String> target = genPair("Something", "Nothing"); String local = "local"; static String staticDirect = "staticDirect"; private static Pair<String, String> genPair(String s1, String s2) { return new Pair<>(s1, s2); } }其中的Pair<>是这个类：package info.skyblond.jvm.asm; public class Pair <T, U>{ private final T first; private final U second; public Pair(T first, U second) { this.first = first; this.second = second; } public T getFirst() { return first; } public U getSecond() { return second; } }编译ASMTargetClass会得到文件ASMTargetClass.class，和其他可执行文件一样，我们可以直接用16进制编辑器打开它看内容，这种方法可以但是并不推荐。在Linux下我们会使用readelf之类的工具来查看可执行文件的信息。对应的，我们可以使用javap命令查看编译好的class文件：javap -c path/to/class/file其中-c表示我们要反汇编，这样我们就能在控制台中看到结果了，另外如果使用IDEA的话，可以安装ASM Bytecode Viewer这个插件，直接在IDEA里面查看。除了字节码之外，插件还会进行额外的处理，比如查询字节码版本，字段的访问控制，将常量拼接到字节码中。这里我们只关心字节码：public class info.skyblond.jvm.asm.ASMTargetClass { static info.skyblond.jvm.asm.Pair<java.lang.String, java.lang.String> target; java.lang.String local; static java.lang.String staticDirect; public info.skyblond.jvm.asm.ASMTargetClass(); Code: 0: aload_0 1: invokespecial #1 // Method java/lang/O bject."<init>":()V 4: aload_0 5: ldc #2 // String local 7: putfield #3 // Field local:Ljava/lang/String; 10: return static {}; Code: 0: ldc #6 // String Something 2: ldc #7 // String Nothing 4: invokestatic #8 // Method genPair:(Ljava/lang/String;Ljava/lang/String;)Linfo/skyblond/jvm/asm/Pair; 7: putstatic #9 // Field target:Linfo/skyblond/jvm/asm/Pair; 10: ldc #10 // String staticDirect 12: putstatic #11 // Field staticDirect:Ljava/lang/String; 15: return }可以看到，反编译给出了三个变量和两个函数。三个变量正是我们在代码中定义的，而两个函数，好像都不太像我们定义的那个genPair()，仔细观瞧得话，可以发现Code那一节正是对象的<init>方法，也就是在JVM创建对象后真正用来初始化对象的代码。首先它调用了Object的<init>方法，毕竟Object是万物之父嘛。然后通过ldc将常量池中的#2压入栈（在此之前还通过指令aload_0将this压入了栈），随后putfield就将常量池中#3代表的局部变量赋值为刚刚压入栈的#2。而后面的static {}，就是初始化类的代码，这个代码只有在类被加载的时候才会执行。比如先从常量池加载了#6和#7，然后调用了一个static方法，之后又把这个栈顶（也就是刚刚调用的那个方法的返回值）赋值给#9，再从常量池中加载#10，付给静态变量#11，最后返回。结合后面的注释来看，这个注释是javap自动生成的，在ldc指令后面它标出了加载的值，比如最后一个ldc #10，加载的正是我们写在代码里的字符串staticDirect。但是我们写的genPair方法还是没有找到。如果我们在javap命令中添加-private标志，就可以看到这个方法了：public class info.skyblond.jvm.asm.ASMTargetClass { // ... private static info.skyblond.jvm.asm.Pair<java.lang.String, java.lang.String> genPair(java.lang.String, java.lang.String); Code: 0: new #4 // class info/skyblond/jvm/asm/Pair 3: dup 4: aload_0 5: aload_1 6: invokespecial #5 // Method info/skyblond/jvm/asm/Pair."<init>":(Ljava/lang/Object;Ljava/lang/Object;)V 9: areturn // ... }实际上，如果我们使用刚刚提到的插件，会得到更友好的输出：// class version 55.0 (55) // access flags 0x21 public class info/skyblond/jvm/asm/ASMTargetClass { // compiled from: ASMTargetClass.java // access flags 0x8 // signature Linfo/skyblond/jvm/asm/Pair<Ljava/lang/String;Ljava/lang/String;>; // declaration: target extends info.skyblond.jvm.asm.Pair<java.lang.String, java.lang.String> static Linfo/skyblond/jvm/asm/Pair; target // access flags 0x0 Ljava/lang/String; local // access flags 0x8 static Ljava/lang/String; staticDirect // access flags 0x1 public <init>()V L0 LINENUMBER 3 L0 ALOAD 0 INVOKESPECIAL java/lang/Object.<init> ()V L1 LINENUMBER 5 L1 ALOAD 0 LDC "local" PUTFIELD info/skyblond/jvm/asm/ASMTargetClass.local : Ljava/lang/String; RETURN L2 LOCALVARIABLE this Linfo/skyblond/jvm/asm/ASMTargetClass; L0 L2 0 MAXSTACK = 2 MAXLOCALS = 1 // access flags 0xA // signature (Ljava/lang/String;Ljava/lang/String;)Linfo/skyblond/jvm/asm/Pair<Ljava/lang/String;Ljava/lang/String;>; // declaration: info.skyblond.jvm.asm.Pair<java.lang.String, java.lang.String> genPair(java.lang.String, java.lang.String) private static genPair(Ljava/lang/String;Ljava/lang/String;)Linfo/skyblond/jvm/asm/Pair; L0 LINENUMBER 8 L0 NEW info/skyblond/jvm/asm/Pair DUP ALOAD 0 ALOAD 1 INVOKESPECIAL info/skyblond/jvm/asm/Pair.<init> (Ljava/lang/Object;Ljava/lang/Object;)V ARETURN L1 LOCALVARIABLE s1 Ljava/lang/String; L0 L1 0 LOCALVARIABLE s2 Ljava/lang/String; L0 L1 1 MAXSTACK = 4 MAXLOCALS = 2 // access flags 0x8 static <clinit>()V L0 LINENUMBER 4 L0 LDC "Something" LDC "Nothing" INVOKESTATIC info/skyblond/jvm/asm/ASMTargetClass.genPair (Ljava/lang/String;Ljava/lang/String;)Linfo/skyblond/jvm/asm/Pair; PUTSTATIC info/skyblond/jvm/asm/ASMTargetClass.target : Linfo/skyblond/jvm/asm/Pair; L1 LINENUMBER 6 L1 LDC "staticDirect" PUTSTATIC info/skyblond/jvm/asm/ASMTargetClass.staticDirect : Ljava/lang/String; RETURN MAXSTACK = 2 MAXLOCALS = 0 }除了字节码之外，插件还会帮我们添加上对应的行号、栈最大大小和局部变量最大个数等信息，同时还会将常量池中#x的引用替换成实际的内容，比如LDC #10变成了LDC "staticDirect"。ASM入门这样一来我们就能够对应上了，如果要修改某一个常量的值，我们只需要修改对象初始化，或者类初始化时的代码，让ldc加载一个不同的常量就可以了。改动的方法有两种：一种是修改常量池，指令不变；另一种是新增一个常量，然后让指令加载新的常量。对于ASM库来说，它提供了两种面向对象的访问方式，一种叫做Visitor API，另一种叫做Tree API。两种API各有优劣，而对于我们的需求来说，两种API都可以胜任。Visitor APIVisitor API以遍历的思想实现：例如我们要将一个class中的字符串常量替换，产生一个新的class，那么我们需要定义一个Visitor，决定在遇到各种事件时执行什么动作，而新的class就在遍历时产生了。例如遇到普通的方法或函数，我们原封不动的复述这个方法或函数，而一旦遇到我们要修改的函数，我们就替换成自己的Visitor；当遇到其他指令的时候我们复述这个指令，而一旦遇到LDC指令，我们就检查原来加载的值是不是我们要替换的，是就替换成新的值，不是就复述这个指令，写到新的class中去。代码如下：package info.skyblond.jvm.asm; import org.objectweb.asm.*; import java.io.IOException; import java.lang.reflect.Field; import java.lang.reflect.InvocationTargetException; import static org.objectweb.asm.Opcodes.ASM9; public class VisitorDemo extends ClassVisitor { public VisitorDemo(ClassVisitor cv) { super(ASM9, cv); this.cv = cv; } @Override public MethodVisitor visitMethod(int access, String name, String descriptor, String signature, String[] exceptions) { MethodVisitor mv = cv.visitMethod(access, name, descriptor, signature, exceptions); if (name.equals("<clinit>")) { return new MethodVisitor(ASM9, mv) { @Override public void visitLdcInsn(Object value) { if ("Something".equals(value)) value = "Replace!"; super.visitLdcInsn(value); } }; } return mv; } public static void main(String[] args) throws IOException, InstantiationException, IllegalAccessException, NoSuchMethodException, InvocationTargetException { String className = ASMTargetClass.class.getCanonicalName(); ClassReader reader = new ClassReader(className); ClassWriter writer = new ClassWriter(reader, ClassWriter.COMPUTE_MAXS); VisitorDemo visitor = new VisitorDemo(writer); reader.accept(visitor, ClassReader.EXPAND_FRAMES); byte[] classData = writer.toByteArray(); Class clazz = new MyClassLoader().defineClass(className, classData); Object personObj = clazz.getDeclaredConstructor().newInstance(); Field targetField = clazz.getDeclaredFields()[0]; targetField.setAccessible(true); Pair<String, String> p = (Pair<String, String>) targetField.get(personObj); System.out.println(p.getFirst()); System.out.println(p.getSecond()); System.out.println(ASMTargetClass.target.getFirst()); System.out.println(ASMTargetClass.target.getSecond()); } }首先我们通过继承ClassVisitor来实现我们自己的Visitor。这个Visitor使用ASM9标准，这里我用的库是org.ow2.asm:asm:9.2。ClassVisitor提供了许多可以覆盖的方法，比如VisitField、visitMethod之类的方法，他们分别在访问成员和方法时被调用，由于我们的目标是<clinit>方法，也就是类初始化时的代码，因此这里只覆盖了visitMethod。 @Override public MethodVisitor visitMethod(int access, String name, String descriptor, String signature, String[] exceptions) { System.out.println("Visit method: " + name); MethodVisitor mv = cv.visitMethod(access, name, descriptor, signature, exceptions); if (name.equals("<clinit>")) { return new MethodVisitor(ASM9, mv) { @Override public void visitLdcInsn(Object value) { if ("Something".equals(value)) value = "Replace!"; super.visitLdcInsn(value); } }; } return mv; }在这个方法中，首先我们先用外部的ClassVisitor进行访问，访问结果存在mv变量里，随后判断，如果方法的名字是<clinit>，那我们就返回一个自己创建的MethodVisitor，这个Visitor的默认行为由刚刚的mv提供，我们只覆盖处理Ldc指令的逻辑，即覆盖了visitLdcInsn方法，在这个方法中，我们判断value和字符串“Something”是否一致，如果一致就把它的值就改为“Replaced!”，然后调用父类的默认实现（这里的默认实现是ClassWriter，稍后讲解main的时候会说，它的默认行为就是在访问时把访问的指令写到新的class里，即复述）。随后就是主函数。 String className = ASMTargetClass.class.getCanonicalName(); ClassReader reader = new ClassReader(className); ClassWriter writer = new ClassWriter(reader, ClassWriter.COMPUTE_MAXS); VisitorDemo visitor = new VisitorDemo(writer); reader.accept(visitor, ClassReader.EXPAND_FRAMES); byte[] classData = writer.toByteArray(); Class clazz = new MyClassLoader().defineClass(className, classData); Object personObj = clazz.getDeclaredConstructor().newInstance(); Field targetField = clazz.getDeclaredFields()[0]; targetField.setAccessible(true); Pair<String, String> p = (Pair<String, String>) targetField.get(personObj); System.out.println(p.getFirst()); System.out.println(p.getSecond()); System.out.println(ASMTargetClass.target.getFirst()); System.out.println(ASMTargetClass.target.getSecond());这里我们获取到了要替换的类的全名，然后用它创造了一个ClassReader。之后我们还创建了一个ClassWriter，它类似于我们平时用的Writer，能够向其中写入数据。最后我们实例化我们自定义的Visitor，因为他要以writer作为默认实现，就是说我们没有动的地方，就按照ClassWriter的实现原封不动的写入到新的class中。对于我们覆盖了的方法，按照我们写的代码执行，这样我们就能够复述原来的Class，并在我们想要的地方做出修改。之后使用了一个自定义的ClassLoader将写好的新class加载进来，因为我们这个Class和原来的Class是一个名字，并且没有对应的文件，所以不能直接让默认的加载器干活。其实现如下：package info.skyblond.jvm.asm; public class MyClassLoader extends ClassLoader { public final Class<?> defineClass(String name, byte[] b) throws ClassFormatError { return defineClass(name, b, 0, b.length); } }其实就是把字节数组转换成一个Class对象，之后利用反射即可拿到我们声明的第一个变量（也就是静态的target变量）的值，将他转换为Pair<String, String>类型后就可以正常操作了。最后四行代码打印了修改前后的不同：Replace! Nothing Something Nothing可以看到通过反射获取到的修改的类，它的Something已经被替换成了Replace!，而后面的Nothing和原来的一致。对于合约来说，我们不需要自定义类加载器，因为合约的编译器允许我们给他一个Class文件的InputStream，它会通过这个InputStream读取class并编译成合约，因此我们只需要将新的Class用ByteArrayInputStream包装一下即可。Tree APITree API则是将Class文件转换成一颗树，根节点ClassNode指向了整个树的根节点，而MethodNode则表示某一个方法的根节点，最后还有InsnNode，每一个node表示一条指令。我们可以在程序中找到不同的节点进行不同的操作以实现目的。使用Tree API写的程序比起Visitor API的更为简洁，只需要一个主函数即可：package info.skyblond.jvm.asm; import org.objectweb.asm.ClassReader; import org.objectweb.asm.ClassWriter; import org.objectweb.asm.tree.AbstractInsnNode; import org.objectweb.asm.tree.ClassNode; import org.objectweb.asm.tree.LdcInsnNode; import org.objectweb.asm.tree.MethodNode; import java.lang.reflect.Field; public class TreeDemo { public static void main(String[] args) throws Exception { String className = ASMTargetClass.class.getCanonicalName(); ClassReader reader = new ClassReader(className); ClassNode classNode = new ClassNode(); reader.accept(classNode, ClassReader.EXPAND_FRAMES); for (MethodNode methodNode : classNode.methods) { if (methodNode.name.equals("<clinit>")) { for (AbstractInsnNode insnNode : methodNode.instructions) { if (insnNode.getType() == AbstractInsnNode.LDC_INSN) { LdcInsnNode node = (LdcInsnNode) insnNode; if (node.cst.equals("Something")) { node.cst = "Replace!"; } } } } } ClassWriter writer = new ClassWriter(ClassWriter.COMPUTE_MAXS); classNode.accept(writer); byte[] classData = writer.toByteArray(); Class clazz = new MyClassLoader().defineClass(className, classData); Object personObj = clazz.getDeclaredConstructor().newInstance(); Field targetField = clazz.getDeclaredFields()[0]; targetField.setAccessible(true); Pair<String, String> p = (Pair<String, String>) targetField.get(personObj); System.out.println(p.getFirst()); System.out.println(p.getSecond()); System.out.println(ASMTargetClass.target.getFirst()); System.out.println(ASMTargetClass.target.getSecond()); } }可以看到主函数的后半部分几乎Visitor API的一模一样，不同指出在于前半部分： ClassReader reader = new ClassReader(className); ClassNode classNode = new ClassNode(); reader.accept(classNode, ClassReader.EXPAND_FRAMES); for (MethodNode methodNode : classNode.methods) { if (methodNode.name.equals("<clinit>")) { for (AbstractInsnNode insnNode : methodNode.instructions) { if (insnNode.getType() == AbstractInsnNode.LDC_INSN) { LdcInsnNode node = (LdcInsnNode) insnNode; if (node.cst.equals("Something")) { node.cst = "Replace!"; } } } } }首先通过ClassReader读取要修改的类，然后创建一个ClassNode，让reader将类读取的结果转换成ClassNode，然后我们遍历classNode的方法节点，如果找到了名为<clinit>的节点，那么我们就开始遍历这个方法的指令节点。通过判别每一个insnNode的类型（注意是Type而不是OpCode），如果是LDC_INSN，即LDC指令，我们需要将他的类型转换为LdcInsnNode，而这种node的cst字段即是该字段载入的常量的值，它可以是String，可以是Integer，也可以是其他类型。总之我们找到我们想要修改的值之后，可以直接修改成目标值，然后利用如下代码将修改后的classNode写成class即可： ClassWriter writer = new ClassWriter(ClassWriter.COMPUTE_MAXS); classNode.accept(writer); byte[] classData = writer.toByteArray();后面的验证代码和Visitor API的一样，而效果也是一样的。-全文完-
上一篇文章记述了使用LWJGL提供的OpenCL绑定的HelloWorld，之后我尝试使用JOCL重写了代码，获得了翻倍的性能，于是本文使用JOCL模拟双摆。前言双摆是将一根单摆连接在另一个单摆的尾部所构成的系统。双摆同时拥有着简单的构造和复杂的行为。双摆的摆动轨迹表现出对于初始状态的极端敏感：两个初始状态差异极小的双摆在一段时间的运行后表现非常不同。本文将编写程序，使用显卡同时计算多个双摆，并将它们叠加渲染在窗口上，以直观的方式体现出双摆对于初始条件的敏感程度。关于双摆问题的物理描述和数学公式，本文参照这个网页进行实现，值得一提的是本文只注重于数学公式的实现，而非关注数学公式的推导。多个双摆的计算依赖于OpenCL在显卡的多个计算核心上同时计算。通过编写Kernel，使得显卡上的每一个计算核心在一次计算中计算某一个双摆的物理量变化，多个Kernel同时运行即达到了并行计算的目的。程序实现下面我们来说一说程序的整体实现。本文代码目前已经公开到了GitHub Repo中：hurui200320/DoublePendulum。Kernel编写下面先来说一说Kernel编写，在明确了每一个计算核心要做的事情之后，Kernel的编写就很容易实现了。根据参照文献提供个公式，我们可以利用双摆的属性计算出每一个单摆的角加速度。于是Kernel的参数就是双摆的基础属性：__kernel void pendulum( __global float *length1, __global float *length2, __global float *mass1, __global float *mass2, __global float *theta1, __global float *theta2, __global float *omega1, __global float *omega2 )左侧一列分别对应第一个单摆的轻杆长度、小球质量、当前摆角（竖直向下为0，取逆时针为正方向）和当前角速度（同摆角）；类似地，右侧一列表示第二个单摆的。除了双摆本身的属性参与计算，这里还有两个常量：#define G $G_CONSTANT$ #define DT $DT_CONSTANT$第一个常量是重力加速度$g$，由于C语言命名规范中常量要全部大写，所以就不得不写成G，所以需要注意的是这个G不是引力常量，而是双摆所在环境的重力加速度。第二个常量用于计算积分的数值解。在参考文献中，他们使用了龙格-库塔法利用计算出来的角加速度计算出对应的速度变化和角度变化，为了图省事儿（就是懒），我是用普通的矩形法来计算，即直接用角加速度乘以一个非常小的$\Delta T$作为角速度的增量，以此更新角速度；角度值类似。出于灵活性考虑，这里两个常量的值被设定为占位符，目的是能够在程序中读取源程序后进行替换。内核的具体实现可以移步这里。基本上就是公示的实现，以及利用矩形法更新角速度和角度。JOCL加载并执行内核与上文，在使用JOCL之前先要确定要使用的OpenCL设备，与上文中的思路完全一致，这里就不多赘述了，相关的代码在这里。初始化内核能够选择出要使用的设备后，可以开始利用JOCL加载并执行内核了。这里将JOCL相关的操作抽象为PendulumSimulator类，这个类在实例化时需要以下参数：双摆的总数pendulumCount局部核心数量localWorkerNum，这个数量决定了同时在设备中进行计算的核心数，取决于OpenCL设备的不同以及双摆总数的不同，这个值需要用户提供。时间片长度deltaT，对应前面Kernel的DT重力加速度g，对应Kernel里面的G对应Kernel中的参数，每个数组在JVM下有三个变量，以第一个参数length1为例，该参数表示第一个单摆的摆长： private val pendulumLength1 = FloatArray(pendulumCount) private val pendulumLength1Pointer = Pointer.to(pendulumLength1) private val pendulumLength1Buffer: cl_mem // later in init{...} pendulumLength1Buffer = createClMem()pendulumLength1是Float数组，也是在JVM上实际存储数据的变量。pendulumLength1Pointer是指向该数组的指针表示，用于与JOCL交互，在需要拷贝数据时，需要用Pointer来告诉JOCL把数据放到那里。pendulumLength1Buffer是OpenCL在GPU内存中保存数据的一个对象，在拷贝数据时需要通过指定该变量来告诉OpenCL要放在GPU内存中的哪个地方。需要注意的是创建cl_mem需要有上下文和命令队列的支持，由于目前还没有开始初始化，所以这个字段要等到之后在初始化环境之后创建。这里createClMem()就是简单的把clCreateBuffer包装了一下，默认创建一个可读可写的GPU内存缓冲区，创建后检查是否出现错误。在没有额外参数的情况下，默认大小为Sizeof.cl_float * pendulumCount个字节。在数据准备妥当之后，在类的初始化过程中即可完成内核的编译： init { logger.info("Using device: ${clDeviceInfo.deviceName} by ${clDeviceInfo.deviceVendor}") // create context val contextProperties = cl_context_properties() contextProperties.addProperty(CL.CL_CONTEXT_PLATFORM.toLong(), clDeviceInfo.platformId) context = CL.clCreateContext( contextProperties, 1, arrayOf(clDeviceInfo.deviceId), { errInfo, _, _, _ -> logger.error("[LWJGL] cl_context_callback\n\tInfo: $errInfo") }, null, errCodeRet ) checkCLError(errCodeRet) // create command queue val commandQueueProperties = cl_queue_properties() commandQueue = CL.clCreateCommandQueueWithProperties( context, clDeviceInfo.deviceId, commandQueueProperties, errCodeRet ) checkCLError(errCodeRet) // create cl_mem, GPU memory reference pendulumTheta1Buffer = createClMem() pendulumTheta2Buffer = createClMem() pendulumOmega1Buffer = createClMem() pendulumOmega2Buffer = createClMem() pendulumLength1Buffer = createClMem() pendulumLength2Buffer = createClMem() pendulumMass1Buffer = createClMem() pendulumMass2Buffer = createClMem() // compile program // set lengths to null means all string a terminated by \0 program = CL.clCreateProgramWithSource( context, 1, arrayOf( readResourceFileContent("/kernel/pendulum.cl") .replace("\$G_CONSTANT\$", String.format("%.6f", g)) .replace("\$DT_CONSTANT\$", String.format("%.6f", deltaT)) ), null, errCodeRet ) checkCLError(errCodeRet) checkCLError(CL.clBuildProgram(program, 1, arrayOf(clDeviceInfo.deviceId), "", null, null)) // build kernel kernel = CL.clCreateKernel(program, "pendulum", errCodeRet) checkCLError(errCodeRet) // Set the arguments of the kernel checkCLError(CL.clSetKernelArg(kernel, 0, Sizeof.cl_mem.toLong(), Pointer.to(pendulumLength1Buffer))) checkCLError(CL.clSetKernelArg(kernel, 1, Sizeof.cl_mem.toLong(), Pointer.to(pendulumLength2Buffer))) checkCLError(CL.clSetKernelArg(kernel, 2, Sizeof.cl_mem.toLong(), Pointer.to(pendulumMass1Buffer))) checkCLError(CL.clSetKernelArg(kernel, 3, Sizeof.cl_mem.toLong(), Pointer.to(pendulumMass2Buffer))) checkCLError(CL.clSetKernelArg(kernel, 4, Sizeof.cl_mem.toLong(), Pointer.to(pendulumTheta1Buffer))) checkCLError(CL.clSetKernelArg(kernel, 5, Sizeof.cl_mem.toLong(), Pointer.to(pendulumTheta2Buffer))) checkCLError(CL.clSetKernelArg(kernel, 6, Sizeof.cl_mem.toLong(), Pointer.to(pendulumOmega1Buffer))) checkCLError(CL.clSetKernelArg(kernel, 7, Sizeof.cl_mem.toLong(), Pointer.to(pendulumOmega2Buffer))) // init is done }传递双摆的初始数据在内核准备妥当之后，接下来应当设计一些接口，让使用者能够方便的传入或读出双摆的数据：fun getPendulumPosition(): List<Pair<Double, Double>> { val theta1 = pendulumTheta1.toList().map { it.toDouble() } val theta2 = pendulumTheta2.toList().map { it.toDouble() } return theta1.zip(theta2) } fun setPendulumPosition(position: List<Pair<Float, Float>>) { require(position.size == pendulumCount) position.forEachIndexed { index, pair -> pendulumTheta1[index] = pair.first pendulumTheta2[index] = pair.second } }以双摆的位置（两个单摆的角度）为例，getter将第一个单摆的角度和第二个单摆的角度以Pair的形式打包后返回，考虑到Java中的实数计算基本以Double为主，故给出的时候也转换为Double给出。读入时为了让使用者知晓计算的精度是Float型，所以读入数据为Pair<Float, Float>，在setter中自动展开。其他数据类似。在全部数据设置妥当后，需要显示调用来将内存中的数据拷贝给GPU：fun sendInitData() { // theta clWriteBuffer(pendulumTheta1Buffer, pendulumTheta1Pointer) clWriteBuffer(pendulumTheta2Buffer, pendulumTheta2Pointer) // omega clWriteBuffer(pendulumOmega1Buffer, pendulumOmega1Pointer) clWriteBuffer(pendulumOmega2Buffer, pendulumOmega2Pointer) // length clWriteBuffer(pendulumLength1Buffer, pendulumLength1Pointer) clWriteBuffer(pendulumLength2Buffer, pendulumLength2Pointer) // mass clWriteBuffer(pendulumMass1Buffer, pendulumMass1Pointer) clWriteBuffer(pendulumMass2Buffer, pendulumMass2Pointer) }其中clWriteBuffer是对clEnqueueWriteBuffer的简单包装，给定GPU内存的Buffer和CPU内存中的Pointer，将数据复制过去并检查错误。执行计算由于需要多次执行计算，所以将计算包装成一个同步函数：private val globalWorkerOffset = longArrayOf(0) private val globalWorkerCount = longArrayOf(pendulumCount.toLong()) private val localWorkerCount = longArrayOf(localWorkerNum.toLong()) private var oldTime = System.nanoTime() private var recentTimePerStep = Long.MAX_VALUE fun getNanosPerStep(): Long { return recentTimePerStep } fun execute() { checkCLError( CL.clEnqueueNDRangeKernel( commandQueue, kernel, 1, globalWorkerOffset, globalWorkerCount, localWorkerCount, 0, null, null ) ) // wait all operation is done CL.clFinish(commandQueue) // update counter val currentTime = System.nanoTime() recentTimePerStep = currentTime - oldTime oldTime = currentTime }execute函数将开始计算，并等到GPU完成计算后才返回控制权。为了便于调试，在执行阶段加入了时间计算的功能，能够方便的供使用者获知两次计算之间的耗时，用以配合FPS控制模拟的速度。将运算结果读回CPU内存每完成一次计算，程序需要将运算结果，主要是双摆的角度（位置）数据读回CPU内存以供其他代码将其渲染到屏幕上。所以单独设计一个函数完成这个功能：fun syncData(readOmega: Boolean = false) { // wait computing is done CL.clFinish(commandQueue) // read theta clReadBuffer(pendulumTheta1Buffer, pendulumTheta1Pointer) clReadBuffer(pendulumTheta2Buffer, pendulumTheta2Pointer) if (readOmega) { // read omega clReadBuffer(pendulumOmega1Buffer, pendulumOmega1Pointer) clReadBuffer(pendulumOmega2Buffer, pendulumOmega2Pointer) } }在读取数据之前需要等待全部操作完成，以此避免数据不一致的现象发生。默认不读取角速度，但通过传入参数，可以在读取角度数据之后读取角速度。其中clReadBuffer是对clEnqueueReadBuffer的简单包装，将数据从给定的Buffer写到Pointer里，并检查错误。资源回收由于JOCL底层还是C语言，如果JVM垃圾回收清理掉了Java中对应的对象，C语言管理的内存还是不会归还给操作系统，久而久之会成为内存泄漏，因此PendulumSimulator类继承了AutoCloseable接口，并有如下实现在关闭时自动回收资源：override fun close() { checkCLError(CL.clFlush(commandQueue)) checkCLError(CL.clFinish(commandQueue)) checkCLError(CL.clReleaseKernel(kernel)) checkCLError(CL.clReleaseProgram(program)) checkCLError(CL.clReleaseMemObject(pendulumTheta1Buffer)) checkCLError(CL.clReleaseMemObject(pendulumTheta2Buffer)) checkCLError(CL.clReleaseMemObject(pendulumOmega1Buffer)) checkCLError(CL.clReleaseMemObject(pendulumOmega2Buffer)) checkCLError(CL.clReleaseMemObject(pendulumLength1Buffer)) checkCLError(CL.clReleaseMemObject(pendulumLength2Buffer)) checkCLError(CL.clReleaseMemObject(pendulumMass1Buffer)) checkCLError(CL.clReleaseMemObject(pendulumMass2Buffer)) checkCLError(CL.clReleaseCommandQueue(commandQueue)) checkCLError(CL.clReleaseContext(context)) }至此OpenCL的部分全部完成，PendulumSimulator的完整代码可以移步GitHub。JavaFX渲染画面为了简单起见，我使用JavaFX的Canvas组件来绘制图形，CPU绘制图形的能力显然不如OpenGL。可是考虑到OpenGL太麻烦了，于是就只好忍耐了。关于JVM，我使用的是Zulu JDK，这个JDK自带JavaFX，虽然开发时可以通过Gradle解决JavaFX的问题，但运行一些JavaFX开发的程序时会非常方便。主窗口初始化主窗口内有如下成员变量： private var cpuRenderLimit = 64 private var scale = 150 private lateinit var renderChoice: List<Int> private val colorList = ColorList(true, Random(System.currentTimeMillis())) private var lastUpdateTimeMs = System.currentTimeMillis()考虑到CPU往往并不能把显卡计算出来的双摆全都展现在屏幕上，因此在设计上通过选择CPU能够模拟的数量cpuRenderLimit，随机挑选一些双摆进行展示。默认值是64。另外物理上的摆长以米为单位计算，但屏幕上以像素来计算，所以需要一个缩放来将双摆的摆长缩放到一个合适的屏幕尺寸，默认值是150。而renderChoice则包含了被随机选中的双摆的索引。colorList是一个存储了各种Color的列表，为此我单独实现了一个类，将在后文详述。lastUpdateTimeMs则用于衡量当前的FPS。主窗体构造使用JavaFX构造主窗体，这个窗体简单到只有一个Pane和一个Canvas:val root = Pane() val scene = Scene(root, windowWidth, windowHeight) val canvas = Canvas() canvas.widthProperty().bind(root.widthProperty()) canvas.heightProperty().bind(root.heightProperty()) root.children.add(canvas) root.style = "-fx-background-color: #2F2F2F"由于Canvas是透明的，所以为了设置底色，通过设置CSS的方式将Pane的背景颜色设置为#2F2F2F灰。接下来选取随机选中的双摆索引：// choose which pendulum we want to render require(cpuRenderLimit <= pendulumCount) { "Cannot render non-exists pendulum" } renderChoice = List(pendulumCount) { it }.toList().shuffled().take(cpuRenderLimit)首先检查数据的合理性，显然CPU选择渲染的数量不能超过双摆总数。然后将所有可能的索引做成列表、随机打散，再取出前n个，就是我们要的列表了。定时刷新Canvas既然要渲染，那肯定得定时刷新Canvas。好在JavaFX为我们提供了一个方便的AnimationTimer，但是这个定时器的帧率控制没有什么好的办法，最快我这边测试是60FPS，可能是根据屏幕同步的，由于切换到240FPS需要重启到BIOS里切换显卡，太麻烦了我就没测，姑且认为它是锁60帧吧。定时器如下：val timer = object : AnimationTimer() { private val nodeRadius = 8.0 private val lineWidth = 3.0 override fun handle(now: Long) { // read data from GPU pendulumSimulator.syncData() val position = pendulumSimulator.getPendulumPosition() val length = pendulumSimulator.getPendulumLength() val centerX = canvas.width / 2 // center positioned at top 1/3 val centerY = canvas.height / 3 val graphicsContext = canvas.graphicsContext2D graphicsContext.clearRect(0.0, 0.0, canvas.width, canvas.height) // reader pendulums for (i in renderChoice.indices) { val x1 = centerX + scale * length[i].first * sin(position[i].first) val y1 = centerY + scale * length[i].first * cos(position[i].first) val x2 = x1 + scale * length[i].second * sin(position[i].second) val y2 = y1 + scale * length[i].second * cos(position[i].second) graphicsContext.stroke = colorList[i].brighter() graphicsContext.lineWidth = lineWidth graphicsContext.beginPath() graphicsContext.moveTo(centerX, centerY) graphicsContext.lineTo(x1, y1) graphicsContext.lineTo(x2, y2) graphicsContext.stroke() graphicsContext.fill = colorList[i].brighter() graphicsContext.fillOval(x1 - nodeRadius, y1 - nodeRadius, 2 * nodeRadius, 2 * nodeRadius) graphicsContext.fillOval(x2 - nodeRadius, y2 - nodeRadius, 2 * nodeRadius, 2 * nodeRadius) } // render some status graphicsContext.fill = Color.WHITE graphicsContext.fillText( "Pendulum count: $cpuRenderLimit${if (cpuRenderLimit != renderChoice.size) ", click to apply" else ""}", 5.0, 15.0 ) graphicsContext.fillText( "Scale: $scale", 5.0, 30.0 ) val currentTime = System.currentTimeMillis() graphicsContext.fillText( "FPS: ${1000 / (currentTime - lastUpdateTimeMs)}", 5.0, 45.0 ) lastUpdateTimeMs = currentTime graphicsContext.fillText( "Step time: ${pendulumSimulator.getNanosPerStep() / 1000_000.0}ms", 5.0, 60.0 ) graphicsContext.fillText( "SPS: ${1_000_000_000 / pendulumSimulator.getNanosPerStep()}", 5.0, 75.0 ) } }首先从GPU中将数据读出来，调用我们准备的pendulumSimulator.syncData()函数即可。然后将长度和位置取出来，计算第一个单摆的中心点。由于双摆的主要移动区域在屏幕下半边，所以我这里Y轴的中心点选取屏幕上三分之一的地方，而不是正中间，这样看起来会舒服一些。之后就是拿着Canvas的GraphicsContext绘图了。首先就是清空整个旧的画面，然后在循环中依次渲染我们选定的双摆。根据三角函数很容易算出第一个单摆的位置，然后在此基础上计算出第二个单摆的位置。每个单摆的摆球半径姑且定义为8个像素（nodeRadius）。画完之后再写一些调试信息，诸如当前画面中的双摆数量，缩放程度，OpenCL模拟的性能（StepPerSecond和每一步用时），以及当前窗体的刷新率等。最后别忘了启动这个定时器：timer.start()交互只是死板的显示预先选定的双摆多少有些没有意思，所以我决定加一些交互功能：鼠标左键单击可以重新随机选取要渲染的双摆索引使用鼠标滚轮可以改变渲染数量按住Shift再使用鼠标滚轮可以改变缩放级别于是有如下代码：primaryStage.scene = scene primaryStage.title = "Double pendulum simulation using OpenCL" primaryStage.isResizable = false primaryStage.setOnCloseRequest { logger.info("Application shutdown") timer.stop() shutdownFlag.set(true) } // Left click to re-chosen pendulums canvas.onMouseClicked = EventHandler { event -> if (event.button == MouseButton.PRIMARY) { renderChoice = List(pendulumCount) { it }.toList().shuffled().take(cpuRenderLimit) colorList.reset() } } // scroll to change pendulum count and rod scale canvas.onScroll = EventHandler { cpuRenderLimit = when { it.deltaY > 0 -> { min(cpuRenderLimit + 1, Int.MAX_VALUE) } it.deltaY < 0 -> { max(1, cpuRenderLimit - 1) } else -> { cpuRenderLimit } } scale = when { it.deltaX > 0 -> { min(scale + 1, Int.MAX_VALUE) } it.deltaX < 0 -> { max(1, scale - 1) } else -> { scale } } } primaryStage.show()首先是设定窗体的标题等，这里禁用了窗体缩放。然后设置了窗体关闭时进行的操作，主要是停止前面的定时器，然后通知主线程窗体已经关闭（通过信号量shutdownFlag）。接下来就是鼠标左键重选索引的代码，在之后是监听OnScroll事件，如果是Y方向上的滚动，就是对渲染数量的调整，如果是X方向的滚动，就是对缩放的调整。最后显示主窗口。主窗口的完整代码可以移步GitHub。ColorList前面说为了实现每一个显示的双摆都有一个独一无二的颜色，于是实现了这个类。在JavaFX的Color类中已经预先定义了一些颜色，但这些颜色只有148个，当需要的颜色超过148个时，就要随机生成一些颜色。由于Color中没有已定义颜色的列表（JDK11），所以不得已只能把定义的语句复制出来，用常量名组成列表：private val predefined = mutableListOf( Color.ALICEBLUE, Color.ANTIQUEWHITE, // ... )除了预定义的颜色，我们还得存储随机生成的颜色：private val generatedColorTable = HashMap<Int, Color>() private val uniqueColorSet = HashSet<Color>()其中generatedColorTable记录每个索引对应的颜色，而uniqueColorSet则用来保证后续随机生成的颜色是唯一的。初始化时需要将预定义的颜色放进这个Set中：init { if (randomized) { predefined.shuffle() } for (color in predefined) { uniqueColorSet.add(color) } }如果有需要，还可以在初始化时将预定义的颜色随机排序。通过重载get函数，我们可以利用[123]来像数组一样获取颜色数据：operator fun get(index: Int): Color { return when { index < predefined.size -> { predefined[index] } else -> { generatedColorTable[index] ?: generateRandomColor(random).also { generatedColorTable[index] = it } } } }如果索引小于预定义的颜色数量，则从预定义的颜色表中取颜色，如果没有，则从随机生成的颜色表中取，如果这个索引还没有颜色，就随机生成一个并放到生成表里。生成颜色代码如下:private fun generateRandomColor(random: Random): Color { var color: Color do { color = Color.rgb(random.nextInt(0, 256), random.nextInt(0, 256), random.nextInt(0, 256)) } while (uniqueColorSet.contains(color)) uniqueColorSet.add(color) return color }有时候我们想给每个双摆换一个颜色，那么就通过这个函数来实现：fun reset(){ if (randomized) { predefined.shuffle() } uniqueColorSet.clear() for (color in predefined) { uniqueColorSet.add(color) } generatedColorTable.clear() }这个类的完整代码可以在这里找到。主函数现在程序的每一个组件都已经准备完毕，于是可以在主程序中将他们串起来了。主函数位于Main.kt，文件中定义了一些常量，需要使用者按照运行的硬件和自己的需求自行修改：const val pendulumCount = 81920 const val localWorkerNum = 512 const val windowWidth = 800.0 const val windowHeight = 600.0 const val targetSPS = 200这里定义了双摆的总数、局部核心数量、窗口的尺寸和模拟的目标StepPerSecond。最后一个参数越大，模拟的精确度越高，但是受制于Java的实现，通过Thread.sleep只能达到1ms精度的时间控制，当targetSPS超过1000时，每一步占用的时间小于1ms，如果用while循环硬等，感觉不太环保。于是要求targetSPS不能超过1000。另外通过targetSPS可以算出每一步的deltaT：1.0 / targetSPS在主函数中会创建双摆的初始数据：// rod length of each double pendulum pendulumSimulator.setPendulumLength(Array(pendulumCount) { Pair(1.0f, 1.0f) }.toList()) // mass of each double pendulum pendulumSimulator.setPendulumMass(Array(pendulumCount) { Pair(2.0f, 2.0f) }.toList()) // initial position pendulumSimulator.setPendulumPosition(Array(pendulumCount) { Pair( PI.toFloat() / 2 + Random.nextDouble(-0.05, 0.05).toFloat(), PI.toFloat() + Random.nextDouble(-0.05, 0.05).toFloat() ) }.toList()) // initial angular velocity pendulumSimulator.setPendulumVelocity(Array(pendulumCount) { Pair(0f, 0f) }.toList())这里我选取每一个双摆的两个摆长都是1米，摆球重量2公斤，初始位置形成一个左右翻转的L形，并在此基础上添加0.1弧度（大约0.5度）的随机变化。摆球的初速度则设为0。随后就可以开始模拟了：// send data to GPU pendulumSimulator.sendInitData() // launch window Thread { launch(MainWindow::class.java) }.start() // translate second into ms second require(targetSPS <= 1000) { "Max time resolution exceeds" } val targetStepTime = (1000.0 / targetSPS).toLong() // control SFS while (!shutdownFlag.get()) { val start = System.currentTimeMillis() pendulumSimulator.execute() while (System.currentTimeMillis() - start < targetStepTime) { Thread.sleep(1) } } pendulumSimulator.close()主函数还要负责限制SPS，这样才能保证模拟出来的速度是正确的。如果SPS超高，则模拟出来的结果会很鬼畜；如果SPS过低，就会肉眼可见的感觉卡顿。所以这里以1ms为单位控制每一步的用时。主函数的完整代码在这里。结果讨论单从性能来说，我的笔记本RTX3070显卡可以在目标SPS为1000的状态下模拟255000（25万）个双摆，保证大多数时候的SPS都在1000附近。而CPU则比较一般，如前文所说，由于使用CPU渲染，画到256个双摆的时候就已经只有30FPS了，512个双摆只有15FPS，1000个双摆时只有7FPS，同时渲染2500个双摆，直接变成PPT：3FPS。但是退一步说，谁会一起看2500个双摆啊，那眼睛不都看花了。如果把数量调小一些，这个程序所达到的效果还是挺成功的：一开始每个双摆的位置都差不多一样，但随着时间的推移，每个双摆之间的差距开始增加，直到后来每个双摆都各不相同。本文的全部代码已经公开到了GitHub中，所以欢迎大家将工程克隆下来运行体验一下。目前Gradle中已经包含了程序运行的全部依赖，只需要克隆工程后让Gradle准备好依赖，之后便可以无痛运行了。-全文完-
前几篇文章中简述了OpenGL的入门过程，本文将简述LWJGL提供的OpenCL绑定下，OpenCL的入门过程。OpenCLOpenGL中的GL表示Graphics Library，而OpenCL则是用于通用计算的：Open Computing Language。早期人们使用显卡进行图形渲染，但后来人们逐渐意识到，显卡上每一个运行着色器的单元就如同一个小CPU——它不如正经CPU那么复杂，频率不快，可用内存也少，还缺乏高级的分支预测和乱序执行能力，但它数量多啊。以我新换的雷蛇笔记本为例：CPU是英特尔的i7-10875H，8核16线程，如果在Java中处理CPU密集型的任务，一般会选择17个线程来执行，如果是I/O密集型任务，CPU空闲时间比较多，则选择33个线程来执行。但是GPU呢？对于RTX3070来说，它有5120个CUDA核心，这意味着原则上我们可以同时在GPU中执行5120个代码，即5120个线程。虽然CPU能跑到5.1GHz，而GPU最高1.62GHz，但在需要高并发的任务中，GPU确实脱颖而出。前几天我在Youtube上看到一个视频：「Fully OpenCL accelerated space battle. (rts rpg game)」，视频作者利用OpenCL加速游戏。这个游戏是一个类似太空大战的游戏，是建立在二维平面上的，每艘船的行为使用OpenCL得出，而不再使用CPU遍历处理。这样得到的性能提升是什么呢？可以实时模拟接近7万个实体，游戏没有任何卡顿。但使用OpenCL是有代价的。OpenCL最初设计的目标并非只是为了在GPU上运算，实际上OpenCL的目标是异构计算，即同一段代码可以在CPU、GPU、FPGA中的任意一种上直接运行，而不必做出修改。这意味着OpenCL必须在设计上保证不依赖某一种平台的结构或特性，而提供一种通用的计算结构，因此我们平时习以为常的CPU内存结构和计算结构，在OpenCL中将不复存在。另一方面说，GPU虽然运算快，但是把数据从CPU内存送到GPU内存并不快。普通游戏显卡通常用于渲染游戏画面，即CPU把当前画面的数据送给显卡，显卡进行渲染，随后CPU送来新的一帧数据，数据是只进不出的；而为了实现通用计算，我们必须在运算结束后把数据从GPU内存读回CPU内存，游戏卡并非做不到，但没有经过特殊的设计与优化，会对速度造成一些影响，这一点在文章最后将代码跑起来后能够有所体现。LWJGL's OpenCL由于OpenCL和OpenGL一样是用C写的，因此Java并不能直接调用他们。于是为了拉齐Java与C之间的鸿沟，和OpenGL一样，LWJGL也提供了OpenCL的绑定，使得我们可以像在C语言中那样直接调用对应的函数就可以完成对应的功能。值得一提的是，LWJGL的OpenCL绑定并非最好，也非唯一。实际上隔壁JOCL库做的更加面向对象一些，用起来也更加舒服，而且文档也很丰富。目前LWJGL3看起来正在重构，OpenCL没有任何文档，只能去他们的Github Repo中读一些测试代码，或者参考OpenCL在C语言中的用法，结合OpenGL绑定中与C交互的部分去猜测代码应该如何编写。所以我的建议是，如果不使用LWJGL提供的OpenGL绑定而只需要使用OpenCL，取决于你是否对编写C语言内核（即着色器，实际跑在GPU上的代码）心存芥蒂，你可以使用JOCL来更加面向对象的加载你编写的C内核；或者直接使用Aparapi库将你的Java代码自动翻译成OpenCL需要的形式。本文将使用LWJGL提供的OpenCL绑定，这个绑定更接近原始C接口，用起来更加复杂一些。如无意外，在未来我将使用JOCL进行OpenCL计算，届时会有对应的文章发表。Hello, World闲话少说，书归正传。要使用LWJGL的OpenCL绑定，只需要在其官网配置项目的时候选定OpenCL就可以了。OpenCL内核就一般的开发流程而言，应当是先搭出来程序的架子，然后再去谈什么样的代码跑在GPU上，但是出于演示的目的，这里先给出OpenCL内核：__kernel void demo(__global float *a, __global float *b, __global float *answer) { int xid = get_global_id(0); answer[xid] = cos(a[xid]) + sin(b[xid]); }内核是同时运行在每一个CUDA核心上的程序，因此我们并不能像CPU那样使用循环来完成两个数组的按项求和。正相反，我们要展开这个操作：每一个Cuda核心只负责将数组中的一个索引位置上的数据相加。于是对于每一个核心，我们先要获取OpenGL给这个核心的编号，然后再根据这个编号将对应位置上的数据相加。为了增加操作难度，我还在两个位置上套了个Sin和Cos，以此来拉开GPU和CPU的表现。关于核心编号的安排，OpenCL提供了最多三维的组织方式。这里get_global_id(0)是取第一维的编号，类似于x，取决于我们在Java代码中如何编写，根据处理数据的不同，我们可以给核心按(x, y)方式编号，此时我们利用0来取x，1取y；或者按(x, y, z)编号。至于运算所需的数据，我们定义两个存储于全局内存（GPU中最慢的内存）的两个浮点型数组a和b作为要相加的数据，将计算结果写回存储于全局内存中的answer数组。准备之准备在正式准备OpenCL的运行时环境之前，我们得先知道系统中有哪些OpenCL设备可供使用。在双显卡环境中，通常是CPU的核显提供一个基于Intel平台的OpenCL设备，英伟达的独显提供一个基于英伟达平台的设备。为了查询系统中有哪些OpenCL设备，并读取他们相关的信息，有如下辅助函数：fun getPlatformInfoStringUTF8(cl_platform_id: Long, param_name: Int): String { stackPush().use { stack -> val returnValueSize = stack.mallocPointer(1) // query the return value size first checkCLError(clGetPlatformInfo(cl_platform_id, param_name, null as ByteBuffer?, returnValueSize)) val bytes = returnValueSize[0].toInt() val buffer = stack.malloc(bytes) // query the value checkCLError(clGetPlatformInfo(cl_platform_id, param_name, buffer, returnValueSize)) return memUTF8(buffer, bytes - 1) } } fun getDeviceInfoStringUTF8(cl_device_id: Long, param_name: Int): String { stackPush().use { stack -> val returnValueSize = stack.mallocPointer(1) checkCLError(clGetDeviceInfo(cl_device_id, param_name, null as ByteBuffer?, returnValueSize)) val bytes = returnValueSize[0].toInt() val buffer = stack.malloc(bytes) checkCLError(clGetDeviceInfo(cl_device_id, param_name, buffer, returnValueSize)) return memUTF8(buffer, bytes - 1) } } fun getDeviceInfoInt(cl_device_id: Long, param_name: Int): Int { stackPush().use { stack -> val pl = stack.mallocInt(1) checkCLError(clGetDeviceInfo(cl_device_id, param_name, pl, null)) return pl[0] } } fun getDeviceInfoLong(cl_device_id: Long, param_name: Int): Long { stackPush().use { stack -> val pl = stack.mallocLong(1) checkCLError(clGetDeviceInfo(cl_device_id, param_name, pl, null)) return pl[0] } } fun checkCLError(code: Int) { require(code == CL_SUCCESS) { "OpenCL error code: $code" } } fun checkCLError(code: IntBuffer) { checkCLError(code[code.position()]) }其中getxxxStringUTF8的函数负责将C返回的字符串数据翻译成Java能够识别的UTF8字符串。这个过程需要两次查询：第一次查询返回数据的大小，然后创建对应的缓存区域，第二次查询才将真正的字符串数据写入缓存，然后Java代码将缓存中的数据转换成字符串。而getxxxInt或类似的函数则简单许多了，知道返回值的类型（Int或Long），则可以一次查询获取到返回值。最后的checkCLError则是检查返回值是否标识成功。OpenCL的返回值一般有两种返回方式。一些函数将返回值作为函数调用的返回值，另一些函数将返回值作为函数参数以缓冲区的方式传入，函数执行完毕时返回值将写入缓冲区。除了能够“听懂”OpenCL返回的数据之外，我们还得自己定义一下OpenCL设备的描述：data class CLDeviceInfo( val platformId: Long, val deviceId: Long, val deviceType: Long, val deviceName: String, val computeUnitCount: Int, val clockFrequency: Int, val localMemorySize: Long, val globalMemorySize: Long )OpenCL设备按照平台定义，每个平台具有唯一编号，而平台内的设备也具有唯一的编号。除此之外我们还将查询设备的类型（CPU、GPU或者其他硬件）、设备的名称（便于我们识别）、最大的运算核心数量（将依据此选择最佳设备），除此之外是一些演示用的信息，比如时钟频率、局部内存大小和全局内存大小。如下函数将查询系统中所有的OpenCL设备，并择其中运算核心数量最大的一个返回给调用者：/** * Choose best device by compute unit count. * */ fun getBestOpenCLDevice(): CLDeviceInfo { val deviceList = mutableListOf<CLDeviceInfo>() stackPush().use { stack -> // get total count val clCounter = stack.mallocInt(1) checkCLError(clGetPlatformIDs(null, clCounter)) val platforms: PointerBuffer = stackPush().mallocPointer(clCounter[0]) checkCLError(clGetPlatformIDs(platforms, clCounter)) for (platformIndex in 0 until platforms.capacity()) { val platformId = platforms[platformIndex] // query count checkCLError(clGetDeviceIDs(platformId, CL_DEVICE_TYPE_ALL.toLong(), null, clCounter)) // query value val devices = stack.mallocPointer(clCounter[0]) checkCLError(clGetDeviceIDs(platformId, CL_DEVICE_TYPE_ALL.toLong(), devices, clCounter)) for (deviceIndex in 0 until devices.capacity()) { val deviceId = devices[deviceIndex] deviceList.add( CLDeviceInfo( platformId = platformId, deviceId = deviceId, deviceType = getDeviceInfoLong(deviceId, CL_DEVICE_TYPE), deviceName = getDeviceInfoStringUTF8(deviceId, CL_DEVICE_NAME), computeUnitCount = getDeviceInfoInt(deviceId, CL_DEVICE_MAX_COMPUTE_UNITS), clockFrequency = getDeviceInfoInt(deviceId, CL_DEVICE_MAX_CLOCK_FREQUENCY), localMemorySize = getDeviceInfoLong(deviceId, CL_DEVICE_LOCAL_MEM_SIZE), globalMemorySize = getDeviceInfoLong(deviceId, CL_DEVICE_GLOBAL_MEM_SIZE) ) ) } } } return deviceList.maxByOrNull { it.computeUnitCount }!! }如同之前所说的，我们先查询系统中一共有多少个平台，然后创建对应大小的缓冲区，再读取每一个平台的编号。遍历平台编号，查询平台下的每一个设备，这里也是同理：先查询多少个设备，再根据大小创建缓冲区读入每个设备的编号。最终对每个设备我们需要查询出我们需要的信息。全部查询完毕后，我们选出核心数量最多的设备作为本例使用的设备。至此，准备之准备可以告一段落，开始着手OpenCL运行时的准备了。准备数据在主函数一开头我们需要准备本次计算需要的数据。由于GPU计算浮点型只能达到单精度（高贵的Quadro和Telsa用户请无视这句话），所以给GPU的数据应该是浮点型的，而给CPU的数据要再转换成双精度，因为Java中的cos和sin函数都是在汇编指令（指JVM Bytecode）级别优化的，因此只接受双精度浮点，又由于将单精度转换为双精度耗时相对更多，所以转换用时自然不能算在CPU时间里，需要我们提前准备好：// GPU val n = 30000000 val inputA = FloatArray(n) { (Random.nextFloat() * 2 * Math.PI).toFloat() } val inputB = FloatArray(n) { (Random.nextFloat() * 2 * Math.PI).toFloat() } val answer = FloatArray(n) // also choose the device val clDeviceInfo = getBestOpenCLDevice() // CPU val a = DoubleArray(n) { inputA[it].toDouble() } val b = DoubleArray(n) { inputB[it].toDouble() } val c = DoubleArray(n)我们准备了三千万个数据。准备施法数据已经准备妥当，现在可以专注于OpenCL的吟唱准备工作了。首先我们最好拿到一个MemoryStack，它是LWJGL提供的便于内存管理的类。利用它我们可以方便的创建缓冲区之类的对象： val stack = stackPush() val errCodeRet = stack.mallocInt(1)这里我们利用MemoryStack对象创建了一个大小为1个整型的缓冲区，用于接收前面说的以参数形式将返回值写入缓冲区的函数的返回值。和创建OpenGL窗口一样，我们不能上来就创建窗口，得先设置一些Hint。类似地，OpenCL需要Context Properties： // Specifies a list of context property names and their corresponding values. // Each property name is immediately followed by the corresponding desired value. // The list is terminated with 0 val contextProperties = stack.mallocPointer(3) contextProperties.put(0, CL_CONTEXT_PLATFORM.toLong()) contextProperties.put(1, clDeviceInfo.platformId) contextProperties.put(2, 0L)这里具有误导性的地方在于mallocPointer，看名字可能以为是声明一个用来存放指针的缓冲区，但实际上指针就是Long型，所以将里面的数据视为长整型数据即可。唯一的区别就是这个函数返回一个PointerBuffer，本意是将内部的数据作为指针数据解释；而mallocLong返回LongBuffer，它的本意是将内部的数据作为长整型解读。根据OpenCL官方手册，Context Properties是一个列表。每一个属性的名字后面立刻跟着它对应的值，并最终以一个0结尾。这里我们要确定所使用的平台编号，之后的OpenCL将面向这个平台执行操作（不同的平台编译后产生的二进制将不一样）。随后我们就可以创建上下文对象。上下文对象的作用是管理程序运行所需的数据。假如你一边玩Minecraft一边运行程序，显卡同一时间只能干同一件事，我们的程序将和Minecraft争抢显卡的使用权，如果我们的程序刚刚从MC那里抢过显卡，显卡里还是MC的数据，我们直接拿来做运算，结果一定是错的。因此OpenCL将根据上下文设置GPU内存中的数据，让我们无需关心数据的调度问题。创建上下文的代码如下： var contextCallback: CLContextCallback? val context: Long = clCreateContext( contextProperties, clDeviceInfo.deviceId, CLContextCallback.create { errInfo: Long, private_info: Long, _: Long, _: Long -> System.err.println("[LWJGL] cl_context_callback") System.err.println("\tInfo: " + memUTF8(errInfo)) System.err.println("\tPrivateInfo: " + memUTF8(private_info)) }.also { contextCallback = it }, NULL, // no user data errCodeRet ) checkCLError(errCodeRet)这里有一个回调函数，将在创建失败时被调用。这里函数的返回值将写入到缓冲区中，而函数调用的返回值则给出上下文对象的编号。我们可以通过观察回调函数是否被调用知道上下文是否创建失败，但程序需要通过检查返回值确保继续前进之前，我们成功创建了上下文对象。随后我们创建命令队列。由于命令在GPU上的执行独立于程序在CPU上执行，因此我们需要将命令放入队列中供GPU慢慢执行。 // create command queue val commandQueue = clCreateCommandQueue(context, clDeviceInfo.deviceId, 0, errCodeRet) checkCLError(errCodeRet)有了命令队列之后，我们就可以将内核需要的数据送给GPU了。 val inputABuffer: Long = clCreateBuffer(context, CL_MEM_READ_ONLY.toLong(), n.toLong() * Float.SIZE_BYTES, errCodeRet) checkCLError(errCodeRet) checkCLError( clEnqueueWriteBuffer( commandQueue, inputABuffer, true, 0, inputA, null as PointerBuffer?, null as PointerBuffer? ) ) val inputBBuffer: Long = clCreateBuffer(context, CL_MEM_READ_ONLY.toLong(), n.toLong() * Float.SIZE_BYTES, errCodeRet) checkCLError(errCodeRet) checkCLError( clEnqueueWriteBuffer( commandQueue, inputBBuffer, true, 0, inputB, null as PointerBuffer?, null as PointerBuffer? ) ) val answerBuffer: Long = clCreateBuffer(context, CL_MEM_WRITE_ONLY.toLong(), n.toLong() * Float.SIZE_BYTES, errCodeRet) checkCLError(errCodeRet)我们依次针对两个输入和一个输出创建对应的缓冲区。这里和OpenGL不同，OpenCL的缓冲区大小的单位是字节，而非元素个数。我们在创建缓冲区的时候还将指定它的读写属性，对于两个输入，我们想要只读，而对于输出，我们要只写。随后针对两个输入缓冲区，我们要将数组数据写入进去： clEnqueueWriteBuffer( commandQueue, inputABuffer, true, 0, inputA, null as PointerBuffer?, null as PointerBuffer? )这个函数需要指定命令队列和要写入的缓冲区。第三个参数表示是否为同步操作。为True表示函数将一直阻塞直到操作完成，如果我们使用数组传入数据，我们必须使用同步操作，而如果从各种Buffer中写入数据，则可以选为异步操作，GPU将在其他线程拷贝数据。如果使用异步操作，我们可以在进行运算之前调用clFinish(commandQueue)确保开始运算之前所有操作已经就绪，该函数将一直阻塞直到命令队列全部执行完毕。数据准备妥当之后，我们可以着手编译内核了： // compile program val program = clCreateProgramWithSource(context, readResourceFileContent("/kernels/demo.cl"), errCodeRet) checkCLError(errCodeRet) checkCLError(clBuildProgram(program, clDeviceInfo.deviceId, "", null, NULL)) // build kernel val kernel = clCreateKernel(program, "demo", errCodeRet) checkCLError(errCodeRet)首先从resources中读取源代码，然后以此创建一个程序，并编译之。编译成功后创建内核，创建内核的第二个参数是源码中的函数名。这里还需要一个额外的步骤就是将前面创建的CLBuffer包装成PointerBuffer： val inputAPointer = stack.mallocPointer(1) inputAPointer.put(0, inputABuffer) val inputBPointer = stack.mallocPointer(1) inputBPointer.put(0, inputBBuffer) val answerPointer = stack.mallocPointer(1) answerPointer.put(0, answerBuffer)然后利用这些参数设置内核工作需要的参数： // Set the arguments of the kernel checkCLError(clSetKernelArg(kernel, 0, inputAPointer)) checkCLError(clSetKernelArg(kernel, 1, inputBPointer)) checkCLError(clSetKernelArg(kernel, 2, answerPointer))这里的0、1、2分别表示内核程序的第一个参数、第二个参数和第三个参数。如果你不将CLBuffer包装成PointerBuffer而直接作为clSetKernelArg的第三个参数传入，那么它将被解读成「参数大小」。所以为了将其作为参数所在的缓冲区传入内核，必须将他们包装成PointerBuffer。别说文档了，LWJGL关于OpenCL连个JavaDoc都没有，我真服了。这块坑了我好一阵子。最后我们等待全部操作完成，准备计算： // wait all memory copy is done clFinish(commandQueue)开始施法与其说通过一个函数开始计算，不如说开始计算的过程更像是一个安排计算方式的过程。还记得一开始我说OpenCL提供多种核心的安排方式吗，一维的、二维的、三维的？在这里一步，我们将通过定义NDRange来开始计算。整体代码如下： // execute kernel val globalWorkerOffset = stack.mallocPointer(1) globalWorkerOffset.put(0, NULL) val globalWorkerCount = stack.mallocPointer(1) globalWorkerCount.put(0, n.toLong()) val localWorkerCount = stack.mallocPointer(1) localWorkerCount.put(0, 64L) checkCLError( clEnqueueNDRangeKernel( commandQueue, kernel, 1, globalWorkerOffset, globalWorkerCount, localWorkerCount, null as PointerBuffer?, null as PointerBuffer? ) )其中最为关键的还是clEnqueueNDRangeKernel函数。首先我们需要确定在哪一个命令队列上运行哪一个内核，因此我们将commandQueue和kernel传进去。其次我们还想告诉OpenCL以几维的方式安排核心，这里我们选1维。如果是二维的话就写2，最大是3维。下一个参数取决于设备支持的OpenCL版本，在OpenCL版本中它必须为NULL，而在2.0及以上版本中可以指定全局编号的开始位置，如果是NULL的话就从0开始（对应二维的(0, 0)和三维的(0, 0, 0,)），否则按照你传入的这1/2/3个数作为起点开始分配全局编号。然后是全局编号的总大小，即我们一共需要多少个核心来参与运算。这个数量是多维的，所以可以按照维数的不同精确控制唯一维度上核心的数量。下一个参数是局部核心数量，局部核心数量的定义与全局核心数量一样是多维的。局部核心数量决定了一个Worker Group（核心构成的组）的大小，OpenCL中是以Worker Group为单位进行计算的：要么整个组一起在设备上运算，要不谁也不能单独运算。这个大小的选择一般根据clinfo给出的Preferred work group size multiple (kernel)和Max work group size及全局核心数量得出的。其中Preferred work group size multiple (kernel)给出这个设备更倾向于将Work Group的数量定位谁的倍数，我这里给出的是32，因此将其定义为32的倍数会好一些；Max work group size则对设备最大的Work Group大小做出的限制，太大了显卡装不下，我这里的限制是1024。最后一个条件最为关键：Work Group的数量必须能整除全局的核心数（在对应维度上），否则将会得到-54错误：CL_INVALID_WORK_GROUP_SIZE。最后两个参数是定义哪些事件必须在计算之前完成，由于我们之前显示调用了clFinish，所以不必理会这两个参数，直接传入null。这条命令一结束，GPU便开始执行运算。由于clEnqueueNDRangeKernel函数是非阻塞的，所以函数返回时并不保证运算完毕，因此在读回结果之前我们还得调用clFinish来确保运算完成。取回数据前面说过，和渲染画面不同，我们做通用计算是要拿回运算结果的。运算完毕后结果存在GPU内存中，我们需要将其读回CPU内存才能继续处理。和写入类似，读取的操作是这样： // read out result to answer checkCLError( clEnqueueReadBuffer( commandQueue, answerBuffer, true, 0, answer, null as PointerBuffer?, null as PointerBuffer? ) )我们将缓冲区的数据读回数组answer里。清理运算结果有了，但是先前创建的那些缓冲区什么的并不能置之不理，否则随着程序的运行将会产生内存泄漏。好在清理并不难，注意顺序：最先创建的最后释放。 // clean up checkCLError(clFlush(commandQueue)) checkCLError(clFinish(commandQueue)) checkCLError(clReleaseKernel(kernel)) checkCLError(clReleaseProgram(program)) checkCLError(clReleaseMemObject(inputABuffer)) checkCLError(clReleaseMemObject(inputBBuffer)) checkCLError(clReleaseMemObject(answerBuffer)) checkCLError(clReleaseCommandQueue(commandQueue)) checkCLError(clReleaseContext(context)) contextCallback?.free() CL.destroy()CPU性能对比本节编写对应的CPU代码并与GPU性能进行对比： for (i in inputA.indices) { c[i] = cos(a[i]) + sin(b[i]) }这是内核对应的等效的代码。我们在val stack = stackPush()之前获取当前系统时间，在clEnqueueNDRangeKernel之前再获取一次系统时间，然后在clEnqueueReadBuffer之后获取一次系统时间。这样就能够通过时间差算出来从创建上下文环境到最后读出运算结果的总耗时，以及其中从开始运算到读回结果的耗时，由此我们能更加直观的感受将数据从CPU送到GPU的耗时。同样的我们在for循环之前获取系统时间，再在循环结束后获取一次系统时间，得到CPU的纯运算时间，因为数据就在内存里，所以不需要将他们复制到其他地方。最终得到的数据是这样的：设备耗时（ms）CPU641GPU全程322GPU从开始运算计时79可见GPU全称耗时322毫秒，而真正的计算加上取回数据只用了79毫秒，剩下的二百多毫秒全部用在数据传送以及Java和C的交互上。而CPU是单线程运算，耗时641毫秒。虽然数据按项相加并不是什么露脸的多线程任务，但毫无疑问作为一个入门程序，它体现出了GPU在并行计算上的潜力。主函数代码package info.skyblond.antSimu import info.skyblond.antSimu.opencl.checkCLError import info.skyblond.antSimu.opencl.getBestOpenCLDevice import info.skyblond.antSimu.utils.ResourceUtils.readResourceFileContent import org.lwjgl.PointerBuffer import org.lwjgl.opencl.CL import org.lwjgl.opencl.CL10.* import org.lwjgl.opencl.CLContextCallback import org.lwjgl.system.MemoryStack.stackPush import org.lwjgl.system.MemoryUtil.NULL import org.lwjgl.system.MemoryUtil.memUTF8 import kotlin.math.cos import kotlin.math.sin import kotlin.random.Random fun main() { // data set val n = 30000000 val inputA = FloatArray(n) { (Random.nextFloat() * 2 * Math.PI).toFloat() } val inputB = FloatArray(n) { (Random.nextFloat() * 2 * Math.PI).toFloat() } val answer = FloatArray(n) // choose best device by core count val clDeviceInfo = getBestOpenCLDevice() val gpuStartTime = System.currentTimeMillis() val stack = stackPush() // Specifies a list of context property names and their corresponding values. // Each property name is immediately followed by the corresponding desired value. // The list is terminated with 0 val contextProperties = stack.mallocPointer(3) contextProperties.put(0, CL_CONTEXT_PLATFORM.toLong()) contextProperties.put(1, clDeviceInfo.platformId) contextProperties.put(2, 0L) val errCodeRet = stack.mallocInt(1) var contextCallback: CLContextCallback? val context: Long = clCreateContext( contextProperties, clDeviceInfo.deviceId, CLContextCallback.create { errInfo: Long, private_info: Long, _: Long, _: Long -> System.err.println("[LWJGL] cl_context_callback") System.err.println("\tInfo: " + memUTF8(errInfo)) System.err.println("\tPrivateInfo: " + memUTF8(private_info)) }.also { contextCallback = it }, NULL, // no user data errCodeRet ) checkCLError(errCodeRet) // create command queue val commandQueue = clCreateCommandQueue(context, clDeviceInfo.deviceId, 0, errCodeRet) checkCLError(errCodeRet) // n * sizeof(float) = n * 8 val inputABuffer: Long = clCreateBuffer(context, CL_MEM_READ_ONLY.toLong(), n.toLong() * Float.SIZE_BYTES, errCodeRet) checkCLError(errCodeRet) checkCLError( clEnqueueWriteBuffer( commandQueue, inputABuffer, true, 0, inputA, null as PointerBuffer?, null as PointerBuffer? ) ) val inputBBuffer: Long = clCreateBuffer(context, CL_MEM_READ_ONLY.toLong(), n.toLong() * Float.SIZE_BYTES, errCodeRet) checkCLError(errCodeRet) checkCLError( clEnqueueWriteBuffer( commandQueue, inputBBuffer, true, 0, inputB, null as PointerBuffer?, null as PointerBuffer? ) ) val answerBuffer: Long = clCreateBuffer(context, CL_MEM_WRITE_ONLY.toLong(), n.toLong() * Float.SIZE_BYTES, errCodeRet) checkCLError(errCodeRet) // compile program val program = clCreateProgramWithSource(context, readResourceFileContent("/kernels/demo.cl"), errCodeRet) checkCLError(errCodeRet) checkCLError(clBuildProgram(program, clDeviceInfo.deviceId, "", null, NULL)) // build kernel val kernel = clCreateKernel(program, "demo", errCodeRet) checkCLError(errCodeRet) val inputAPointer = stack.mallocPointer(1) inputAPointer.put(0, inputABuffer) val inputBPointer = stack.mallocPointer(1) inputBPointer.put(0, inputBBuffer) val answerPointer = stack.mallocPointer(1) answerPointer.put(0, answerBuffer) // Set the arguments of the kernel checkCLError(clSetKernelArg(kernel, 0, inputAPointer)) checkCLError(clSetKernelArg(kernel, 1, inputBPointer)) checkCLError(clSetKernelArg(kernel, 2, answerPointer)) // wait all memory copy is done clFinish(commandQueue) // execute kernel val globalWorkerOffset = stack.mallocPointer(1) globalWorkerOffset.put(0, NULL) val globalWorkerCount = stack.mallocPointer(1) globalWorkerCount.put(0, n.toLong()) val localWorkerCount = stack.mallocPointer(1) localWorkerCount.put(0, 640L) val gpuComputingStartTime = System.currentTimeMillis() checkCLError( clEnqueueNDRangeKernel( commandQueue, kernel, 1, globalWorkerOffset, globalWorkerCount, localWorkerCount, null as PointerBuffer?, null as PointerBuffer? ) ) clFinish(commandQueue) // read out result to answer checkCLError( clEnqueueReadBuffer( commandQueue, answerBuffer, true, 0, answer, null as PointerBuffer?, null as PointerBuffer? ) ) val gpuEndTime = System.currentTimeMillis() println("${gpuEndTime - gpuStartTime}ms consumed by GPU") println("${gpuEndTime - gpuComputingStartTime}ms for GPU computing") // clean up checkCLError(clFlush(commandQueue)) checkCLError(clFinish(commandQueue)) checkCLError(clReleaseKernel(kernel)) checkCLError(clReleaseProgram(program)) checkCLError(clReleaseMemObject(inputABuffer)) checkCLError(clReleaseMemObject(inputBBuffer)) checkCLError(clReleaseMemObject(answerBuffer)) checkCLError(clReleaseCommandQueue(commandQueue)) checkCLError(clReleaseContext(context)) contextCallback?.free() CL.destroy() val a = DoubleArray(n) { inputA[it].toDouble() } val b = DoubleArray(n) { inputB[it].toDouble() } val c = DoubleArray(n) val cpuStartTime = System.currentTimeMillis() for (i in inputA.indices) { c[i] = cos(a[i]) + sin(b[i]) } val cpuEndTime = System.currentTimeMillis() println("${cpuEndTime - cpuStartTime}ms for CPU computing") answer.forEachIndexed { index, fl -> require(c[index] - fl < 1e-6) { "WRONG! ${c[index]} $fl" } } }最后为了保证运算结果正确，还对GPU运算结果做了校验。-全文完-