Main

August 15, 2013

读了一点 go 的源码

首先是 runtime 里的 hashmap ,想看看 go 的 hashmap 和 lua 的有什么区别。

结论就是 go 的比 lua 的实现复杂的多 (lua 的 ltable.c 不到 600 行代码,go 的 hashmap.c 有超过 1500 行)。go 的 hashmap 更注重于空间效率。go 的 map 是有类型的,key value 类型都固定,存在类型描述结构里。key value 的大小在编译期都不固定,但在构造时就可以确定了。

hash 值是一个 uintptr ,在 64 位系统下是 8 字节。key 的 hash 值是不完整保存在 hashmap 的结构中,那样太浪费。Lua 同样也不会把 hash 值保存在表中,但 Lua 的类型很少且固定,所以比较好处理。

go 的 map key 类型可以用户自定义,每次重新调用类型的对应方法计算 hash 值恐怕有性能问题。go 的折中方法是,在 hash 表里只保存 hash 值中的一个字节。

key/value 对以 8 个一组保存在一个叫 Bucket 的结构中,这组 key 的 hash 值和表的大小(2 的整数次幂)取 and 后有相同的值,然后再用高位字节做进一步区分以加快检索效率。如果一个 Bucket 不只 8 对值,就用链表扩展。

注意:0 作为特殊 hash 值对待,表示 Bucket 中这一项为空。如果 hash 值的高字节的确是 0, 就改为 1 。

May 11, 2011

闲扯几句 GC 的话题

今天跟同事闲扯的时候谈到 GAE SDK 刚刚支持了 Go 语言。这对于 Go 语言爱好者来说是个让人欢心鼓舞的消息。几乎所有人都相信它能比 Python 的执行效率高一些。从开发效率上来说,不会比 Python 差,那么 Go 语言的支持可能是比 Java 更好的选择(开发效率和执行性能的均衡)?

这也让我想到了前段在北京时跟 Douban 的同学聊 Go 的事情。那天,有同学问起 GC 的事,是个 C++ 程序员。C++ 程序员对 GC 知之甚少是可以理解的。我大约花了 10 分钟介绍简单的 GC 算法(:根扫描清理、三色标记、移动或不移动内存等等。那段时间我正在研究 lua 的 gc 实现,刚巧看了不少文章。

May 05, 2011

写了一个 proxy 用途你懂的

用 linode 有一年多了 ,除了架设 blog ,我也折腾点小程序放在上面跑。在互联网上有一台自己的主机,对于一个程序员来说,还是很有必要的。当然这 vps 绝对不能选国内的,原因你懂的。这样,附带的一个好处就是可以用 ssh -D ,相信许多同学都喜欢用。

没来由的,我想自己写一个小程序,完成 ssh -D 一样的功能,不过,不走 SSL 加密。当然也不能走明文,由于众所周知的原因,明文通讯很容易引起奇异的连接断开或长期超时的 bug ,此 bug 绝对不在于你的程序。网络连接永远不是 100% 可靠的嘛。

我花了两天实现我的构想,本来第一天已经完成了,但实现的过于复杂,且 bug 重重。花了一个通宵都没完全解决。在补了个好觉后,我在梦中意识到,应该简化方案,然后在第二天重写了一遍,终于可以跑起来了。代码是用 Go 实现的,比较玩具,quick & dirty 。不过我还是把它们放在后面。有兴趣的同学可以拿去改进。目前这个雏形已经够我用了,所以即使有改进或许也懒得再贴出来了。

March 09, 2011

Go 语言初学实践(3)

这几天一直在写个小东西,基本也做完了。抽点时间贴段代码继续这个系列。

我写的 http server 在支持断点续传时碰到个小的算法问题。就是我希望用户在完整下载完一次指定文件后,就让这个文件 URL 失效。而如果用户不断的从中间开始分段下载的话,很难从统计下载字节数来判定整个文件是否下载完一次。

我希望把下载完一次的标准定为,文件的每个字节都至少被请求一次。这个问题用线段树来实现最为贴切。当然还会有各种其它方案,就不展开讨论了。

这里的代码有很大的优化余地,但是就具体应用来说,性能方面也足够了。严谨点来说,我在服务器上额外增加了一些判断,防止被恶意攻击。比如如果分段太多(恶意的每间隔一个字节请求一个字节)对于大文件会导致这个数据结构占据过多内存。这时直接掐断服务即可,这里不展开讨论。

March 02, 2011

Go 语言初学实践(2)

继续昨天的。

现在要实现一个特殊的 map ,支持 push 和 pop 两个操作。看起来是这样的:

type myMap interface {
    push(key string, e interface {}) interface{} 
    pop(key string) interface{}
}

当 push 的时候,如果 map 中 key 已存在,返回原来对应的 value ;若 key 不存在,则创建一个新的 key 把 value 放进去。

而 pop 操作,返回 key 对应的 value ,并把 key/value 对从 map 中删除。

鉴于 Go 程序中通常会使用大量 goroutine ,所以,这个 map 应该是线程安全的。那么用 Go 怎么实现它呢?最简单也就是最传统的方式是使用锁,即 sync.Mutex ,代码如下:

March 01, 2011

Go 语言初学实践(1)

今天想到个点子,做一个文件传输的服务。我觉得是个很简单的东西,可以满足自己的需要。写了篇 blog 理了一下思路。不过,如果光这口头说说其实是很偷懒的一件事情。我觉得,大部分网络产品弄个专职的所谓产品经理,光说想要啥自己不动手实现一下(或是不会写程序),是件极其不靠谱的事情。

说些啥都不如自己动手做出来。最近半年我好象老干这种事情,光说不练。最近一个月也没写什么大篇幅的代码,再老是这样,肯定会手生的。管它好不好,动手实现才是王道。正好最近想折腾一下 Go 语言,那么就拿 Go 来写写看吧。

新语言还是不熟的,老要翻资料。不过这也是学习的必经之路。晚上写了几百行程序,还经常出现语法错误,速度很慢,不过慢慢就有状态了。

在这里,就随便贴一小段代码,算是一点点初学实践吧。

这里有一个小需求,希望有一个 Go 函数,每次调用一次,就返回一个由英文大写字母构成的随机字符串。(用来生成一个短网址)那么用 Go 怎么实现好呢?

November 18, 2010

Go 语言初步

这几天认真玩起了 Go。所谓认真玩,就是拿 Go 写点程序,前后大约两千行吧。

据说 Go 的最佳开发平台是 Mac OS ,我没有。其次应该是 Linux 。Windows 版还没全部搞定,但是也可以用了。如果你用 google 搜索,很容易去到一个叫 go-windows 的开源项目上。千万别上当,这是个废弃的项目。如果你用这个,很多库都没有,而且语法也是老的。我在 Windows 下甚至不能正确链接自己写的多个 package 。活跃的 Windows 版是 gomingw ,对于 Windows 用户,装一个 mingw32 以后就可以开始玩了。

就三天来实战经历,我喜欢上这门新语言有如下原因:

mix-in 的接口风格。非常接近于我在用 C 时惯用的面向对象风格。有语法上的支持要舒服多了。以平坦的方式编写函数,没有层次。而后用 interface 把需要的功能聚合在一起。没有继承层次,只有组合功能。

强类型系统。使得犯错误的机会大大降低。正确通过编译,几乎就没有什么 bug 了。而编写程序又有点使用 lua 这种动态语言的感觉,总之,写起来很舒服。

内置的 string / slice 类型,以及 gc 。这是我觉得现代编程必须的东西。手工管理未必有更高的效率,但一定有更多的出错机会。至少,我一直主张有一个方便的 string 不变量的基本类型的(参见这一篇)。

defer 是个有趣使用的东西,用它来实现 RAII 比 C++ 利用栈上对象的析构函数的 trick 方案让人塌实多了。go 在语言设计上是很吝啬新的关键字的。但多出一个关键字 defer ,并用内建函数 panic / recover 来解决许多看似应该用 exception 解决的问题要漂亮的多。

zero 初始化。我一直觉得 C++ 的构造函数特别多余。按我用 C 的惯例,一切数据结构都应该用 0 初始化。所以 C 里有 calloc 这个函数。go 把这点贯彻了。不会再有未定义的数据。

包系统特别的好。而且严格定义了包的初始化过程,即 init 函数。在我自己的 C 语言构建的项目中,实现了几乎一样的机制,甚至也叫 init 。但是有语言层面的支持就是好。对,只有 init 没有 exit 。正合我意。

goroutine 是个相当有用的设计。8 年前,我给 C 实现了 coroutine 库,并用在项目里,并坚信,程序就应该这么写。但是没有语言级的支持,用起来还是很麻烦。goroutine 不仅简化了许多业务逻辑的编写,而且天生就是为并发编程而生的。select/chan 可能是唯一正确的并发编程的模型。Erlang 还是太小众了,而 Go 可以延用 Erlang 的模型,却有着纯正的 C 语言血统,我想会被更多人接受的。虽然 Go 依然可以用共享状态加锁的方案,但不推荐使用。chan 用习惯了,还是相当方便的。

{ 要不要独立占一行的信仰之争终于结束了。还记得前段时间有位同学来 email 指责我开源的代码没有章法。程序写的太乱。他的理由就是,我的 { 都没有独占一行。好了,争论可以结束了。在 Go 里,如果你把 { 从 if/for 语言的行末去掉,放在下一行。编译器是不会让你通过的。(除非你再加一个 ; )我很欣慰 ;)

我发现我花了四年时间锤炼自己用 C 语言构建系统的能力,试图找到一个规范,可以更好的编写软件。结果发现只是对 Go 的模仿。缺乏语言层面的支持,只能是一个拙劣的模仿。