popcount & google.sparsegroup

ubuntu+gcc4.3 ，尝试修改 google.sparsetable 中的 sparsegroup，修改完成，不启用 -mpopcnt，sparsetable_unittest 和 hashtable_unittest 都通过了。启用-mpopcnt以后，发现硬件不支持，报非法指令错误，公司的电脑太烂了！

换到服务器上，是64位至强，gcc4.1.2，启用 -mpopcnt 再加 -O1/-O2/-O3 任何一个，导致编译失败：internal compiler error: in memory_address_length, at config/i386/i386.c:13816

呜呼！

反复尝试后发现，如果把 __builtin_popcountl 包装进一个 __attribute__((noinline)) 函数就可以编译过了：

__attribute__((noinline))
int fast_popcount64(unsigned long x)
{
   return __builtin_popcountl(x);
}

然而这样得到的测试结果只比软件实现的 popcount 快20%：

 

time is in ns	google	use my optimization , delete num_buckets, GROUP_SIZE == 64
use int16 num_buckets	__builtin_popcountl	my soft popcount
GROUP_SIZE == 48	without -mpopcnt	with -mpopcnt
	noinline function wrapped	direct use
map_grow	271	300	231	compile	263
map_predict/grow	121	160	76	failed,	104
map_replace	55	70	44	does not	45
map_fetch	51	70	38	available.	39
map_fetch_empty	8	10	10	who can	10
map_remove	71	90	51	give this	51
map_toggle	231	309.9	202	test	201

在工作电脑上（32位奔腾M），还发现，__builtin_popcount l 会生成硬件 popcount 指令，而 __builtin_popcount ll 不会，这是gcc4.3呀，很新的版本了！不得已，自己再写一下：

		inline int fast_popcount64(unsigned long long x)
		{
			return
				__builtin_popcountl((unsigned long)(x      )) +
				__builtin_popcountl((unsigned long)(x >> 32));
		}

这个实现版明显要比软__builtin_popcount ll 快很多。

另外，visual C++ 也支持popcount，我只在 visual c++ 2008 的文档中找到：

#if defined(_MSC_VER) && _MSC_VER >= 1500 // VC 2008
//  different popcount instructions in different headers
//	#include <nmmintrin.h> // for _mm_popcnt_u32, _mm_popcnt_u64
	#include <intrin.h> // for __popcnt16, __popcnt, __popcnt64
	#if defined(_M_X64)
//		#define fast_popcount64 _mm_popcnt_u64
		#define fast_popcount64 __popcnt64
	#else
		inline int fast_popcount64(unsigned __int64 x)
		{
			return
//			   	_mm_popcnt_u32((unsigned int)(x      )) + 
//				_mm_popcnt_u32((unsigned int)(x >> 32));
				
			   	__popcnt((unsigned int)(x      )) + 
				__popcnt((unsigned int)(x >> 32));
		}
	#endif

明显比 gcc 要罗嗦很多，而且有不同的 popcount 版本，文档中还建议先使用__cpuid 测试硬件是否支持popcount。

我修改过的sparsetable 在这里

 

################################################################

2010-02-23 新增以下内容：

################################################################

在服务器上编译了gcc4.4.3，虽然费了一番周折，最后却也成功了。

使用gcc4.4.3 带 -mpopcnt -O2 编译、测试被我修改过 sparsegroup 的 sparsehash，结果如下：

Tables <!-- "G_PLUGIN_FOR_HTML" --> tt { font-family: courier; } td { font-family: helvetica, sans-serif; } caption { font-family: helvetica, sans-serif; font-size: 14pt; text-align: left; }

time is in ns	machine popcount with my optimization	google
map_grow	252	311
map_predict/grow	95	138
map_replace	36	59
map_fetch	34	56
map_fetch_empty	24	13
map_remove	46	80
map_toggle	191	250

评论

7 楼 febird 2010-02-28  

wkoffee 写道

Popcnt还是很新的指令，要sse4.2才支持，我家里的几台pc都不支持。你的fast_popcount不能inline还是有性能损失的,最好直接嵌入汇编

sse4已经支持popcnt，到 sse4.2 又有了不同的popcnt指令，不知道啥原因，gcc中有生成旧popcnt还是新popcnt指令的选项

6 楼 febird 2010-02-28  

wkoffee 写道

mikeandmore 写道

febird 写道

在这种情况下，还是虚拟机好，总是可以选择最优实现。

前提是，你的虚拟机知道要用popcnt。。。这个JIT已经强悍到一定程度了

最新的hotspot代码已经能支持popcnt了，其实并不复杂，将Integer.bitCount,和Long.bitCount注册为intrinsics就可以了

谁可以改一个java版的

5 楼 wkoffee 2010-02-28  

mikeandmore 写道

febird 写道

在这种情况下，还是虚拟机好，总是可以选择最优实现。

前提是，你的虚拟机知道要用popcnt。。。这个JIT已经强悍到一定程度了

最新的hotspot代码已经能支持popcnt了，其实并不复杂，将Integer.bitCount,和Long.bitCount注册为intrinsics就可以了

4 楼 wkoffee 2010-02-28  

Popcnt还是很新的指令，要sse4.2才支持，我家里的几台pc都不支持。你的fast_popcount不能inline还是有性能损失的,最好直接嵌入汇编

3 楼 mikeandmore 2010-02-24  

febird 写道

在这种情况下，还是虚拟机好，总是可以选择最优实现。

前提是，你的虚拟机知道要用popcnt。。。这个JIT已经强悍到一定程度了

2 楼 febird 2010-02-23  

在这种情况下，还是虚拟机好，总是可以选择最优实现。

1 楼 mikeandmore 2010-02-23  

都是硬件指令支持不全的缘故啊。。。