Re: [Committed] Use special-purpose hash table to speed up walk_tree

[Jakub Jelinek <jakub@redhat.com>]

On Thu, Oct 14, 2004 at 04:15:44PM -0700, Matt Austern wrote:
> This patch isn't really as big as it looks.  walk_tree allows you to 
> provide a hash table to keep track of which nodes have already been 
> seen.  We were using htab_t, a general-purpose hash table with lots of 
> knobs for the client to tweak.  This patch replaces it with a 
> special-purpose hash table that has no more functionality than 
> walk_tree needs.  In particular, this special-purpose hash table 
> doesn't support deletion, doesn't give its client control over resizing 
> policy, and doesn't allow its client to specify the hash function or 
> equality function.  (It just uses the values of the pointers 
> themselves.)
> 
> Bootstrapped and tested (C, C++, Java) on powerpc-apple-darwin.  This 
> gives a 2% speedup on building QT.

But on x86-64-redhat-linux essentially makes even bootstrap impossible
(well, I have killed it after it spent more than 10 minutes compiling
insn-recog or insn-attrtab by stage1/cc1).
hash1's distribution is less than perfect.

I have gathered statistics taken from the hash table at a random time
I Ctrl-C cc1 compiling insn-recog.c.

{log_slots = 16, n_slots = 65536, n_elements = 16385, slots = 0x2a9b261010}
average chain length 7991
hash 21703 count 887
hash 21705 count 882
hash 21704 count 856
hash 21706 count 817
hash 21702 count 780
hash 21696 count 726
hash 21686 count 722
hash 21693 count 709
hash 21689 count 695
hash 21690 count 692
hash 21695 count 686
hash 21697 count 680
hash 21691 count 666
hash 21684 count 653
hash 21687 count 650
hash 21685 count 633
hash 21694 count 607
hash 21692 count 588
hash 21688 count 571
hash 21698 count 541
hash 21683 count 539
hash 21681 count 522
hash 21682 count 520
hash 21680 count 324
hash 21701 count 183
hash 21699 count 41
hash 21343 count 31
hash 21342 count 24
hash 21707 count 22
hash 21346 count 16
hash 21249 count 16
hash 21344 count 14
hash 21315 count 11
all others count 81

The hash table contains 21249 NULLs, then full slots (with a couple
of NULLs near the beginning, but only a few), and from slot 37875
onwards till the end of the hash table there are NULLs again.

Shouldn't we multiply by 2^64 / phi instead of 2^32 / phi when
long is 64-bit?

	Jakub