October 16th, 2006

fedora 蓝色小药丸

关于 .gnu.hash

irc://freenode/fedora-cn

gagag 说,fc6 里面 KDE 速度快了。我想他指的应该是 .gnu.hash

http://fedoraproject.org/wiki/Docs/Beats/Devel/Tools

..changes in the ELF .hash section that provides symbols for dynamic linking...It provides an approximately 50% increase in dynamic linking speed.

正好 zhllg 上线,就问了下。果然,他七月份的一篇文章提到了,当时还看过呢。还有几个链接

http://lwn.net/Articles/192082/
http://sourceware.org/ml/libc-alpha/2006-06/msg00095.html
http://forums.gentoo.org/viewtopic-t-435659.html

觉得 gentoo 的 overlay 机制是 fedora 和 deb/ubuntu 系统远远比不上的。overlay 可以创造无限的可能,为不同的用户量身定制。那么好用的 use 是什么时候开发出来的呢。期待 hellwolf 的新作!

那,所谓 .gnu.hash 是使用了新的 hash 算法和 hash 布局。

The .gnu.hash section uses always sh_entsize 4 (so doesn't repeat the
historic mistakes on Alpha/s390x with .hash). The first word there is
nbuckets like in .hash section, followed by nbuckets offsets into the
chains area of the new section. If the offset is 0xffffffff, it means
there are no defined symbol names with hash % nbuckets equal to the
offset's position. Otherwise, offset N means the corresponding chain
starts at offset (1 + nbuckets + N) * 4 into .gnu.hash section. The
chain are does not mirror in size the symbol table anymore.

那个算法没看懂:

The hash function used is

static uint_fast32_t
dl_new_hash (const char *s)
{
uint_fast32_t h = 5381;
for (unsigned char c = *s; c != '\0'; c = *++s)
h = h * 33 + c;
return h & 0xffffffff;
}

(Dan Bernstein's string hash function posted eons ago on comp.lang.c.)



扩大了 hash 之后,冲突也就变少了;即使冲突,需要比较的内容也少了;最后,因为新的布局是把可选的值放在相邻的地址里,局部性更好了。所以才说在动态链接的查找符号时有了 50% 性能提升。预先编译的符号表是什么?<- 这说明,我根本就没懂~~ 睡了睡了。

Collapse )