[PATCH] [rmap] operator-sparse Fibonacci hashing of waitqueues

[PATCH] [rmap] operator-sparse Fibonacci hashing of waitqueues

[William Lee Irwin III]

After distilling with hpa's help the results of some weeks-old
numerological experiments^W^Wnumber crunching, I've devised a patch
here for -rmap to make the waitqueue hashing somewhat more palatable
for SPARC and several others.

This patch uses some operator-sparse Fibonacci hashing primes in order
to allow shift/add implementations of the hash function used for hashed
waitqueues.


Dan, Dave, could you take a look here and please comment?

Randy, any chance you could benchmark -rmap with this on top for
comparison against standard -rmap to ensure there is no regression?


Thanks,
Bill

P.S.: Dave: Sorry I took so long to get this thing out, but here it is.


# This is a BitKeeper generated patch for the following project:
# Project Name: Long-term Linux VM development
# This patch format is intended for GNU patch command version 2.5 or higher.
# This patch includes the following deltas:
#	           ChangeSet	1.199   ->        
#	include/linux/mm_inline.h	1.14    -> 1.15   
#	        mm/filemap.c	1.52    -> 1.53   
#
# The following is the BitKeeper ChangeSet Log
# --------------------------------------------
# 02/02/17	wli@holomorphy.com	1.200
# Use operator-sparse Fibonacci hashing primes for the hashed waitqueues so as to reduce the cost of
# the hashing computation on several major RISC architectures and most 64-bit machines.
# 
# Specifically the search for operator-sparse primes was documented around the definitions of the
# GOLDEN_RATIO_PRIME values, where the number of terms in the sum of powers of 2 was chosen in
# advance and the numbers generated this way were sorted by their continued fraction expansion
# and then filtered for primality.
# 
# In turn the definition of page_waitqueue() also needed to be altered so that for 64-bit machines,
# whose compilers cannot perform the transformation of multiplication by a constant to shifts and
# adds, the transformation is explcitly coded, and documentation is included for it describing how
# the shifts and adds correspond to the signed sum of powers of two representation of the golden
# ratio prime.
# --------------------------------------------
#
diff -Nru a/include/linux/mm_inline.h b/include/linux/mm_inline.h
--- a/include/linux/mm_inline.h	Sun Feb 17 00:49:26 2002
+++ b/include/linux/mm_inline.h	Sun Feb 17 00:49:26 2002
@@ -9,12 +9,43 @@
  * Chuck Lever verified the effectiveness of this technique for several
  * hash tables in his paper documenting the benchmark results:
  * http://www.citi.umich.edu/techreports/reports/citi-tr-00-1.pdf
+ *
+ * These prime numbers were determined by searching all numbers
+ * composed of sums of seven terms of the form 2^n with n decreasing
+ * with the index of the summand and sorting by the continued fraction
+ * expansion of p/2^BITS_PER_LONG, then filtering for primality.
+ * Verifying that the confidence tests on the chi^2 statistics passed
+ * is necessary because this process can produce "bad" factors, but on
+ * the other hand it often produces excellent factors, so it's a very
+ * useful process for generating hash functions.
  */
+
 #if BITS_PER_LONG == 32
-#define GOLDEN_RATIO_PRIME 2654435761UL
+/*
+ * 2654404609 / 2^32 has the continued fraction expansion
+ * 0,1,1,1,1,1,1,1,1,1,1,1,1,18,7,1,3,7,18,1,1,1,1,1,1,1,1,1,1,2,0
+ * which is very close to phi.
+ * It is of the form 2^31 + 2^29 - 2^25 + 2^22 - 2^19 - 2^16 + 1
+ * which makes it suitable for compiler optimization to shift/add
+ * implementations on machines where multiplication is a slow operation.
+ * gcc is successfully able to optimize this on 32-bit SPARC and MIPS.
+ */
+#define GOLDEN_RATIO_PRIME 0x9e370001UL
 
 #elif BITS_PER_LONG == 64
-#define GOLDEN_RATIO_PRIME 11400714819323198549UL
+/*
+ * 11400862456688148481 / 2^64 has the continued fraction expansion
+ * 0,1,1,1,1,1,1,1,1,1,1,1,2,1,14,1,1048579,15,1,2,1,1,3,9,1,1,8,3,1,7,
+ *    1,1,9,1,2,1,1,1,1,2,0
+ * which is very close to phi = (sqrt(5)-1)/2 = 0,1,1,1,....
+ *
+ * It is of the form 2^63 + 2^61 - 2^57 + 2^54 - 2^51 - 2^18 + 1
+ * which makes it suitable for shift/add implementations of the hash
+ * function. 64-bit architectures typically have slow multiplies (or
+ * no hardware multiply) and also gcc is unable to optimize 64-bit
+ * multiplies for these bit patterns so explicit expansion is used.
+ */
+#define GOLDEN_RATIO_PRIME 0x9e37fffffffc0001UL
 
 #else
 #error Define GOLDEN_RATIO_PRIME in mm_inline.h for your wordsize.
diff -Nru a/mm/filemap.c b/mm/filemap.c
--- a/mm/filemap.c	Sun Feb 17 00:49:26 2002
+++ b/mm/filemap.c	Sun Feb 17 00:49:26 2002
@@ -787,6 +787,9 @@
  * collisions. This cost is great enough that effective hashing
  * is necessary to maintain performance.
  */
+
+#if BITS_PER_LONG == 32
+
 static inline wait_queue_head_t *page_waitqueue(struct page *page)
 {
 	const zone_t *zone = page_zone(page);
@@ -798,6 +801,50 @@
 
 	return &wait[hash];
 }
+
+#elif BITS_PER_LONG == 64
+
+static inline wait_queue_head_t *page_waitqueue(struct page *page)
+{
+	const zone_t *zone = page_zone(page);
+	wait_queue_head_t *wait = zone->wait_table;
+	unsigned long hash = (unsigned long)page;
+	unsigned long n;
+
+	/*
+	 * The bit-sparse GOLDEN_RATIO_PRIME is a sum of powers of 2
+	 * with varying signs: 2^63 + 2^61 - 2^57 + 2^54 - 2^51 - 2^18 + 1
+	 * The shifts in the code below correspond to the differences
+	 * in the exponents above.
+	 * The primary reason why the work of expanding the multiplication
+	 * this way is not given to the compiler is because 64-bit code
+	 * generation does not seem to be capable of doing it. So the code
+	 * here manually expands it.
+	 * The differences are used in order to both reduce the number of
+	 * variables used and also to reduce the size of the immediates
+	 * needed for the shift instructions, whose precision is limited
+	 * on some architectures.
+	 */
+
+	n = hash;
+	n <<= 18;
+	hash -= n;
+	n <<= 33;
+	hash -= n;
+	n <<= 3;
+	hash += n;
+	n <<= 3;
+	hash -= n;
+	n <<= 4;
+	hash += n;
+	n <<= 2;
+	hash += n;
+
+	hash >>= zone->wait_table_shift;
+	return &wait[hash];
+}
+
+#endif /* BITS_PER_LONG == 64 */
 
 
 /* 

[PATCH] [rmap] operator-sparse Fibonacci hashing of waitqueues

[rwhron]

> Randy, any chance you could benchmark -rmap with this on top for
> comparison against standard -rmap to ensure there is no regression?

System is k6-2 475 mhz and 384 MB ram with IDE disks.
Here it is with a few notes on things I looked at more closely.
I also have the output of readprofile between each test.

dbench 128 processes
2.4.17-rmap12f       **********   5.0  MB/sec
2.4.17-rmap12f-wli   **********   5.1  MB/sec

unixbench-4.1.0         2.4.17-rmap12f-wli  2.4.17-rmap12f
Execl Throughput                  293.5           303.7  lps (3  samples)
Pipe Throughput                395378.4        391759.4  lps (10 samples)
Pipe-based Context Switching    78095.8        117697.0  lps (10 samples)
Process Creation                 1181.5          1143.0  lps (3  samples)
System Call Overhead           335203.8        335211.1  lps (10 samples)
Shell Scripts (1 concurrent)      586.9           591.0  lpm (3  samples)

pipe context switching in unixbench results initially looked concerning,
but looking at how the test varies, and context switch and pipe tests
in lmbench suggest that the lower number may not be significant.


LMbench-2.0p2 average of 9 samples.
-------------
Processor, Processes - times in microseconds - smaller is better
OS                  null null      open  slct sig  sig   fork  exec   sh
                    call I/O  stat clos  TCP  inst hndl  proc  proc  proc
2.4.17-rmap12f      0.43 0.71 3.43 5.47  49.3 1.46 3.25   904  3606 14035
2.4.17-rmap12f-wli  0.43 0.71 3.20 5.32  44.9 1.44 3.35   951  3671 13960


Context switching - times in microseconds - smaller is better
OS                  2p/0K  2p/16K  2p/64K  8p/16K 8p/64K  16p/16K 16p/64K
                    ctxsw  ctxsw   ctxsw   ctxsw  ctxsw   ctxsw   ctxsw
2.4.17-rmap12f       0.91   24.52  195.18  58.21  211.57  60.72   227.85
2.4.17-rmap12f-wli   1.07   22.21  189.00  56.71  206.15  60.90   226.34


*Local* Communication latencies in microseconds - smaller is better
OS                  Pipe    AF    UDP    RPC/   TCP    RPC/   TCP
                           UNIX           UDP           TCP   conn
2.4.17-rmap12f      10.52  20.22  40.52  147.4  68.74  198.0  279.52
2.4.17-rmap12f-wli  11.06  19.85  40.39  142.1  66.52  191.3  274.65


File & VM system latencies in microseconds - smaller is better
OS                    0K    File     10K    File     Mmap    Prot   Page
                    Create  Delete  Create  Delete  Latency  Fault  Fault
2.4.17-rmap12f      121.02  164.96  566.05  248.88   3300.3  1.18    3.8
2.4.17-rmap12f-wli  134.03  171.19  690.52  254.61   3314.6  1.17    4.0


*Local* Communication bandwidths in MB/s - bigger is better
OS                  Pipe   AF   TCP    File   Mmap   Bcopy  Bcopy  Mem  
                          UNIX        reread reread (libc) (hand)  read 
2.4.17-rmap12f      64.04 48.73 60.15  58.62 237.62  58.48  59.62 237.43
2.4.17-rmap12f-wli  64.93 41.48 42.89  62.43 237.59  58.43  59.57 237.42

The TCP and AF bandwdith numbers vary a lot between tests.  Oddly, the TCP
test appears to vary by almost 100% between iterations.  Here are the 
individual test results;

OS                           AF     TCP 
                            UNIX        
--------------------------  -----  -----
Linux 2.4.17-rmap12f        46.47  39.43
Linux 2.4.17-rmap12f        51.26  78.44
Linux 2.4.17-rmap12f        51.31  77.34
Linux 2.4.17-rmap12f        50.52  74.49
Linux 2.4.17-rmap12f        47.49  40.32
Linux 2.4.17-rmap12f        48.20  79.06
Linux 2.4.17-rmap12f        44.00  38.66
Linux 2.4.17-rmap12f        48.65  38.14
Linux 2.4.17-rmap12f        50.63  75.50
Linux 2.4.17-rmap12f-wli    43.24  39.72
Linux 2.4.17-rmap12f-wli    42.92  82.14
Linux 2.4.17-rmap12f-wli    40.96  38.19
Linux 2.4.17-rmap12f-wli    42.46  37.77
Linux 2.4.17-rmap12f-wli    44.61  38.10
Linux 2.4.17-rmap12f-wli    40.86  37.15
Linux 2.4.17-rmap12f-wli    39.26  40.63
Linux 2.4.17-rmap12f-wli    38.35  36.27
Linux 2.4.17-rmap12f-wli    40.63  36.04

The tbench test below doesn't show a large variation between the
two kernels.


Memory latencies in nanoseconds - smaller is better
OS                  Mhz   L1 $   L2 $    Main mem
2.4.17-rmap12f       476   4.20  190.41  261.95
2.4.17-rmap12f-wli   476   4.20  186.52  262.02


tiobench Average of 3 samples.
--------
2048 MB worth of files on ext2 fs. (filesize = 2048MB / num_threads)
Read, write, and seek rates in MB/sec. 
Latency in milliseconds.
Percent of requests that took longer than 2 and 10 seconds.


Sequential Reads   Num                  Avg     Maximum   Lat%    Lat%  CPU
Kernel             Thr  Rate  (CPU%)  Latency   Latency    >2s    >0s   Eff
------------------ --- ----------------------------------------------------
2.4.17-rmap12f       8   9.37 13.97%    9.788    980.34 0.00000 0.00000  67
2.4.17-rmap12f-wli   8   9.38 13.74%    9.759    886.07 0.00000 0.00000  68

2.4.17-rmap12f      16   9.90 14.99%   18.234   1301.80 0.00000 0.00000  66
2.4.17-rmap12f-wli  16   9.89 14.72%   18.311   1330.12 0.00000 0.00000  67

2.4.17-rmap12f      32  10.05 16.46%   35.398   2455.18 0.00000 0.00000  61
2.4.17-rmap12f-wli  32  10.14 16.61%   35.303   2483.88 0.00000 0.00000  61

2.4.17-rmap12f      64   9.65 18.54%   71.995   4745.45 0.00000 0.00000  52
2.4.17-rmap12f-wli  64   9.65 18.29%   71.986   4792.92 0.00000 0.00000  53

2.4.17-rmap12f     128   9.25 26.66%  148.095 136165.27 4.71210 0.02498  35
2.4.17-rmap12f-wli 128   9.31 27.08%  146.307 111566.57 4.54960 0.01964  34


Random Reads       Num                  Avg     Maximum   Lat%    Lat%  CPU
Kernel             Thr  Rate  (CPU%)  Latency   Latency    >2s    >10s  Eff
------------------ --- ----------------------------------------------------
2.4.17-rmap12f       8   0.42 1.058%  217.323    852.61 0.00000 0.00000  40
2.4.17-rmap12f-wli   8   0.42 1.073%  217.232   1016.86 0.00000 0.00000  39

2.4.17-rmap12f      16   0.48 1.406%  375.897   1485.76 0.00000 0.00000  34
2.4.17-rmap12f-wli  16   0.47 1.296%  375.872   1537.88 0.00000 0.00000  37

2.4.17-rmap12f      32   0.52 1.760%  667.107   3468.37 0.00000 0.00000  30
2.4.17-rmap12f-wli  32   0.53 1.640%  655.669   3331.63 0.00000 0.00000  32

2.4.17-rmap12f      64   0.53 2.176% 1283.121   8672.69 0.75605 0.00000  24
2.4.17-rmap12f-wli  64   0.54 1.784% 1288.162   7699.61 0.90726 0.00000  30

2.4.17-rmap12f     128   0.54 3.198% 2508.958  16549.40 5.24697 0.00000  17
2.4.17-rmap12f-wli 128   0.54 3.071% 2492.784  17542.43 5.80141 0.00000  18


Sequential Writes  Num                  Avg     Maximum   Lat%    Lat%  CPU
Kernel             Thr  Rate  (CPU%)  Latency   Latency    >2s    >10s  Eff
------------------ --- ----------------------------------------------------
2.4.17-rmap12f       8  18.11 82.47%    4.542   4140.63 0.00000 0.00000  22
2.4.17-rmap12f-wli   8  18.06 82.49%    4.553   5403.78 0.00306 0.00000  22

2.4.17-rmap12f      16  18.04 81.69%    8.921   7486.25 0.00744 0.00000  22
2.4.17-rmap12f-wli  16  17.99 82.15%    8.893   5086.09 0.00076 0.00000  22

2.4.17-rmap12f      32  17.31 76.08%   17.610  10609.26 0.02595 0.00000  23
2.4.17-rmap12f-wli  32  17.31 77.04%   17.808  11199.52 0.03033 0.00000  22

2.4.17-rmap12f      64  15.07 60.04%   40.287  15381.66 0.39444 0.00000  25
2.4.17-rmap12f-wli  64  15.18 61.79%   40.052  20057.21 0.37003 0.00000  25

2.4.17-rmap12f     128  12.52 47.48%   95.497  31261.15 1.64452 0.00095  26
2.4.17-rmap12f-wli 128  12.62 46.73%   94.113  29901.54 1.50032 0.00114  27


Random Writes      Num                  Avg     Maximum   Lat%    Lat%  CPU
Kernel             Thr  Rate  (CPU%)  Latency   Latency    >2s    >10s  Eff
------------------ --- ----------------------------------------------------
2.4.17-rmap12f       8   0.67 4.278%    0.490    666.50 0.00000 0.00000  16
2.4.17-rmap12f-wli   8   0.66 4.322%    0.659    688.43 0.00000 0.00000  15

2.4.17-rmap12f      16   0.68 4.492%    1.941    578.57 0.00000 0.00000  15
2.4.17-rmap12f-wli  16   0.68 4.419%    2.249    632.19 0.00000 0.00000  15

2.4.17-rmap12f      32   0.67 4.467%    0.818    835.38 0.00000 0.00000  15
2.4.17-rmap12f-wli  32   0.68 4.550%    0.663    562.35 0.00000 0.00000  15

2.4.17-rmap12f      64   0.69 4.668%    1.076    621.97 0.00000 0.00000  15
2.4.17-rmap12f-wli  64   0.69 4.585%    0.980    861.52 0.00000 0.00000  15

2.4.17-rmap12f     128   0.71 4.973%    0.975    917.19 0.00000 0.00000  14
2.4.17-rmap12f-wli 128   0.70 4.990%    0.803    940.80 0.00000 0.00000  14


bonnie++ average of 3 samples
1024MB file
Version 1.02a      --------------------Sequential Output-------------------
                   -----Per Char----- ------Block------- -----Rewrite------
Kernel             MB/sec  %CPU   Eff MB/sec  %CPU   Eff MB/sec  %CPU   Eff
2.4.17-rmap12f       3.38  99.0  3.41  15.12  97.0 15.58   5.14  40.7 12.64
2.4.17-rmap12f-wli   3.38  99.0  3.42  15.16  97.0 15.63   5.66  45.3 12.48

                    -----------Sequential Input----------- -----Random-----
                    -----Per Char-----  ------Block------- -----Seeks------
Kernel              MB/sec  %CPU   Eff  MB/sec  %CPU   Eff /sec  %CPU   Eff
2.4.17-rmap12f        3.55  85.0  4.17   19.07  23.7 80.57  122   2.0  6096
2.4.17-rmap12f-wli    3.56  85.0  4.19   19.14  23.7 80.87  123   2.0  6140

16384 small files
                   -------------Sequential Create-------
                   ------Create-----    -----Delete-----
                    /sec  %CPU   Eff    /sec  %CPU   Eff
2.4.17-rmap12f      4395  95.7  4594    4548  99.3  4578
2.4.17-rmap12f-wli  4214  98.3  4286    4268  91.7  4655

                   -------------Random Create------------
                   ------Create-----     -----Delete-----
                    /sec  %CPU   Eff     /sec  %CPU   Eff
2.4.17-rmap12f      4460  99.0  4504     3927  93.3  4207
2.4.17-rmap12f-wli  4154  97.7  4253     4109  96.3  4265


Time in seconds to build/run things.
kernel             autoconf    perl    kernel  updatedb  updatedb 5x
2.4.17-rmap12f     1217        1589    1295    29        44       
2.4.17-rmap12f-wli 1218        1609    1270    28        45       


tbench 32 processes (average of 3 runs)
2.4.17-rmap12f       ********************************  16.3  MB/sec
2.4.17-rmap12f-wli   ********************************  16.2  MB/sec


More details on testing method and other kernels tested at
http://home.earthlink.net/~rwhron/kernel/k6-2-475.html

-- 
Randy Hron

Re: [PATCH] [rmap] operator-sparse Fibonacci hashing of waitqueues

[William Lee Irwin III]

At some point in the past, I wrote:
>> Randy, any chance you could benchmark -rmap with this on top for
>> comparison against standard -rmap to ensure there is no regression?

On Sun, Feb 17, 2002 at 06:01:59PM -0500, rwhron@earthlink.net wrote:
> System is k6-2 475 mhz and 384 MB ram with IDE disks.
> Here it is with a few notes on things I looked at more closely.
> I also have the output of readprofile between each test.

Excellent! Thank you very much.

On Sun, Feb 17, 2002 at 06:01:59PM -0500, rwhron@earthlink.net wrote:
> pipe context switching in unixbench results initially looked concerning,
> but looking at how the test varies, and context switch and pipe tests
> in lmbench suggest that the lower number may not be significant.

It's unclear what effect, if any, the waitqueue hashing should have on
pipes and context switching in general. There are waitqueues involved
but they are not associated with pages.

On Sun, Feb 17, 2002 at 06:01:59PM -0500, rwhron@earthlink.net wrote:
> The TCP and AF bandwdith numbers vary a lot between tests.  Oddly, the TCP
> test appears to vary by almost 100% between iterations.  Here are the 
> individual test results;

I'm not sure why this would be affected either, but again, it's certainly
useful to check these things for unanticipated effects.

Dave, Rik, Dan, do you know of any reason why there would be an effect
here (or with pipes)?

On Sun, Feb 17, 2002 at 06:01:59PM -0500, rwhron@earthlink.net wrote:
> The tbench test below doesn't show a large variation between the
> two kernels.

This is excellent, and largely the desired result. This sort of benchmark
is what I believe what would demonstrate any degradation in performance
during a real workload.

More detailed analysis could show that I need to adjust the multipliers
to eliminate the ones I've chosen as one of the occasional poor
multipliers chosen by this process, but I have a steady and large
supply of these multipliers, and these macro-throughput results seem to
indicate it is almost certainly not one of those (bad ones should cause
noticeable degradation, especially with the wake-all then sleep if wrong
object semantics), so it's already fairly unlikely it's one of those.
I'll try to get whatever hash table profiling I can on this thing as well.

Anton, Rusty, I could use help on extracting hash table stats here,
I can compute confidernce intervals etc. at will but extraction...

Dave, it would be useful to hear from you on this issue as you have
closer connections to machines where multiplication is expensive.


Cheers,
Bill

Re: [PATCH] [rmap] operator-sparse Fibonacci hashing of waitqueues

[Daniel Phillips]

On February 17, 2002 10:01 am, William Lee Irwin III wrote:
> After distilling with hpa's help the results of some weeks-old
> numerological experiments^W^Wnumber crunching, I've devised a patch
> here for -rmap to make the waitqueue hashing somewhat more palatable
> for SPARC and several others.
> 
> This patch uses some operator-sparse Fibonacci hashing primes in order
> to allow shift/add implementations of the hash function used for hashed
> waitqueues.
> 
> Dan, Dave, could you take a look here and please comment?

Could you explain in very simple terms, suitable for Aunt Tillie (ok, not
*that* simple) how the continued fraction works, how it's notated, and how
the terms of the expansion relate to good performance as a hash?

--
Daniel

> Randy, any chance you could benchmark -rmap with this on top for
> comparison against standard -rmap to ensure there is no regression?
> 
> 
> Thanks,
> Bill
> 
> P.S.: Dave: Sorry I took so long to get this thing out, but here it is.
> 
> 
> # This is a BitKeeper generated patch for the following project:
> # Project Name: Long-term Linux VM development
> # This patch format is intended for GNU patch command version 2.5 or higher.
> # This patch includes the following deltas:
> #	           ChangeSet	1.199   ->        
> #	include/linux/mm_inline.h	1.14    -> 1.15   
> #	        mm/filemap.c	1.52    -> 1.53   
> #
> # The following is the BitKeeper ChangeSet Log
> # --------------------------------------------
> # 02/02/17	wli@holomorphy.com	1.200
> # Use operator-sparse Fibonacci hashing primes for the hashed waitqueues so as to reduce the cost of
> # the hashing computation on several major RISC architectures and most 64-bit machines.
> # 
> # Specifically the search for operator-sparse primes was documented around the definitions of the
> # GOLDEN_RATIO_PRIME values, where the number of terms in the sum of powers of 2 was chosen in
> # advance and the numbers generated this way were sorted by their continued fraction expansion
> # and then filtered for primality.
> # 
> # In turn the definition of page_waitqueue() also needed to be altered so that for 64-bit machines,
> # whose compilers cannot perform the transformation of multiplication by a constant to shifts and
> # adds, the transformation is explcitly coded, and documentation is included for it describing how
> # the shifts and adds correspond to the signed sum of powers of two representation of the golden
> # ratio prime.
> # --------------------------------------------
> #
> diff -Nru a/include/linux/mm_inline.h b/include/linux/mm_inline.h
> --- a/include/linux/mm_inline.h	Sun Feb 17 00:49:26 2002
> +++ b/include/linux/mm_inline.h	Sun Feb 17 00:49:26 2002
> @@ -9,12 +9,43 @@
>   * Chuck Lever verified the effectiveness of this technique for several
>   * hash tables in his paper documenting the benchmark results:
>   * http://www.citi.umich.edu/techreports/reports/citi-tr-00-1.pdf
> + *
> + * These prime numbers were determined by searching all numbers
> + * composed of sums of seven terms of the form 2^n with n decreasing
> + * with the index of the summand and sorting by the continued fraction
> + * expansion of p/2^BITS_PER_LONG, then filtering for primality.
> + * Verifying that the confidence tests on the chi^2 statistics passed
> + * is necessary because this process can produce "bad" factors, but on
> + * the other hand it often produces excellent factors, so it's a very
> + * useful process for generating hash functions.
>   */
> +
>  #if BITS_PER_LONG == 32
> -#define GOLDEN_RATIO_PRIME 2654435761UL
> +/*
> + * 2654404609 / 2^32 has the continued fraction expansion
> + * 0,1,1,1,1,1,1,1,1,1,1,1,1,18,7,1,3,7,18,1,1,1,1,1,1,1,1,1,1,2,0
> + * which is very close to phi.
> + * It is of the form 2^31 + 2^29 - 2^25 + 2^22 - 2^19 - 2^16 + 1
> + * which makes it suitable for compiler optimization to shift/add
> + * implementations on machines where multiplication is a slow operation.
> + * gcc is successfully able to optimize this on 32-bit SPARC and MIPS.
> + */
> +#define GOLDEN_RATIO_PRIME 0x9e370001UL
>  
>  #elif BITS_PER_LONG == 64
> -#define GOLDEN_RATIO_PRIME 11400714819323198549UL
> +/*
> + * 11400862456688148481 / 2^64 has the continued fraction expansion
> + * 0,1,1,1,1,1,1,1,1,1,1,1,2,1,14,1,1048579,15,1,2,1,1,3,9,1,1,8,3,1,7,
> + *    1,1,9,1,2,1,1,1,1,2,0
> + * which is very close to phi = (sqrt(5)-1)/2 = 0,1,1,1,....
> + *
> + * It is of the form 2^63 + 2^61 - 2^57 + 2^54 - 2^51 - 2^18 + 1
> + * which makes it suitable for shift/add implementations of the hash
> + * function. 64-bit architectures typically have slow multiplies (or
> + * no hardware multiply) and also gcc is unable to optimize 64-bit
> + * multiplies for these bit patterns so explicit expansion is used.
> + */
> +#define GOLDEN_RATIO_PRIME 0x9e37fffffffc0001UL
>  
>  #else
>  #error Define GOLDEN_RATIO_PRIME in mm_inline.h for your wordsize.
> diff -Nru a/mm/filemap.c b/mm/filemap.c
> --- a/mm/filemap.c	Sun Feb 17 00:49:26 2002
> +++ b/mm/filemap.c	Sun Feb 17 00:49:26 2002
> @@ -787,6 +787,9 @@
>   * collisions. This cost is great enough that effective hashing
>   * is necessary to maintain performance.
>   */
> +
> +#if BITS_PER_LONG == 32
> +
>  static inline wait_queue_head_t *page_waitqueue(struct page *page)
>  {
>  	const zone_t *zone = page_zone(page);
> @@ -798,6 +801,50 @@
>  
>  	return &wait[hash];
>  }
> +
> +#elif BITS_PER_LONG == 64
> +
> +static inline wait_queue_head_t *page_waitqueue(struct page *page)
> +{
> +	const zone_t *zone = page_zone(page);
> +	wait_queue_head_t *wait = zone->wait_table;
> +	unsigned long hash = (unsigned long)page;
> +	unsigned long n;
> +
> +	/*
> +	 * The bit-sparse GOLDEN_RATIO_PRIME is a sum of powers of 2
> +	 * with varying signs: 2^63 + 2^61 - 2^57 + 2^54 - 2^51 - 2^18 + 1
> +	 * The shifts in the code below correspond to the differences
> +	 * in the exponents above.
> +	 * The primary reason why the work of expanding the multiplication
> +	 * this way is not given to the compiler is because 64-bit code
> +	 * generation does not seem to be capable of doing it. So the code
> +	 * here manually expands it.
> +	 * The differences are used in order to both reduce the number of
> +	 * variables used and also to reduce the size of the immediates
> +	 * needed for the shift instructions, whose precision is limited
> +	 * on some architectures.
> +	 */
> +
> +	n = hash;
> +	n <<= 18;
> +	hash -= n;
> +	n <<= 33;
> +	hash -= n;
> +	n <<= 3;
> +	hash += n;
> +	n <<= 3;
> +	hash -= n;
> +	n <<= 4;
> +	hash += n;
> +	n <<= 2;
> +	hash += n;
> +
> +	hash >>= zone->wait_table_shift;
> +	return &wait[hash];
> +}
> +
> +#endif /* BITS_PER_LONG == 64 */
>  
>  
>  /* 
> -
> To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html
> Please read the FAQ at  http://www.tux.org/lkml/
> 
> 

-- 
Daniel

Re: [PATCH] [rmap] operator-sparse Fibonacci hashing of waitqueues

[William Lee Irwin III]

On February 17, 2002 10:01 am, William Lee Irwin III wrote:
>> After distilling with hpa's help the results of some weeks-old
>> numerological experiments^W^Wnumber crunching, I've devised a patch
>> here for -rmap to make the waitqueue hashing somewhat more palatable
>> for SPARC and several others.
>> 
>> This patch uses some operator-sparse Fibonacci hashing primes in order
>> to allow shift/add implementations of the hash function used for hashed
>> waitqueues.
>> 
>> Dan, Dave, could you take a look here and please comment?

On Mon, Feb 18, 2002 at 11:31:15PM +0100, Daniel Phillips wrote:
> Could you explain in very simple terms, suitable for Aunt Tillie (ok, not
> *that* simple) how the continued fraction works, how it's notated, and how
> the terms of the expansion relate to good performance as a hash?

Do you want it just in a post or in-line?

Here's the posted brief version:

Numbers have "integer parts" and "fractional parts", for instance, if
you have a number such as 10 1/2 (ten and one half) the integer part
is 10 and the fractional part is 1/2. The fractional part of a number
x is written {x}.

Now, there is something called the "spectrum" of a number, which for
a number x is the set of all the numbers of the form n * x, where n
is an integer. So we have {1*x}, {2*x}, {3*x}, and so on.

If we want to measure how well a number distributes things we can try
to see how uniform the spectrum is as a distribution. There is a
theorem which states the "most uniform" distribution results from the
number phi = (sqrt(5)-1)/2, which is related to Fibonacci numbers.

The continued fraction of phi is

0 + 1
   -----
   1 + 1
      -----
      1 + 1
         -----
         1 + 1
            -----
            1 + 1
                ...

where it's 1's all the way down. Some additional study also revealed
that how close the continued fraction of a number is to phi is related
to how uniform the spectrum is. For brevity, I write continued fractions
in-line, for instance, 0,1,1,1,1,... for phi, or 0,1,2,3,4,... for

0 + 1
   -----
   1 + 2
      -----
      1 + 3
         -----
         1 + 4
            ....

One way to evaluate these is to "chop off" the fraction at some point
(for instance, where I put ...) and then reduce it like an ordinary
fraction expression.

Fibonacci hashing considers the number p/2^n where n is BITS_PER_LONG
and p is a prime number, and this is supposed to have a relationship
to how evenly-distributed all the n-bit numbers multiplied by p in
n-bit arithmetic are. Which is where the hash functions come in, since
you want hash functions to evenly distribute things. There are reasons
why primes are better, too.

And I think that covers most of what you had in mind.

In my own opinion, this stuff borders on numerology, but it seems to be
a convenient supply of hash functions that pass chi^2 tests on the
bucket distributions, so I sort of tolerate it. If I'm not using a strict
enough test then I'm all ears...

Cheers,
Bill

Re: [PATCH] [rmap] operator-sparse Fibonacci hashing of waitqueues

[William Lee Irwin III]

On Mon, Feb 18, 2002 at 04:34:50PM -0800, William Lee Irwin III wrote:
> where it's 1's all the way down. Some additional study also revealed
> that how close the continued fraction of a number is to phi is related
> to how uniform the spectrum is. For brevity, I write continued fractions
> in-line, for instance, 0,1,1,1,1,... for phi, or 0,1,2,3,4,... for
> 
> 0 + 1
>    -----
>    1 + 2
>       -----
>       1 + 3
>          -----
>          1 + 4
>             ....

doh! Sorry, I just woke up

0 + 1
   -----
   1 + 1
      -----
      2 + 1
         -----
         3 + 1
            -----
            4 + 1
               ...


Cheers,
Bill

Re: [PATCH] [rmap] operator-sparse Fibonacci hashing of waitqueues

[Daniel Phillips]

On February 19, 2002 01:34 am, William Lee Irwin III wrote:
> On February 17, 2002 10:01 am, William Lee Irwin III wrote:
> >> After distilling with hpa's help the results of some weeks-old
> >> numerological experiments^W^Wnumber crunching, I've devised a patch
> >> here for -rmap to make the waitqueue hashing somewhat more palatable
> >> for SPARC and several others.
> >> 
> >> This patch uses some operator-sparse Fibonacci hashing primes in order
> >> to allow shift/add implementations of the hash function used for hashed
> >> waitqueues.
> >> 
> >> Dan, Dave, could you take a look here and please comment?
> 
> On Mon, Feb 18, 2002 at 11:31:15PM +0100, Daniel Phillips wrote:
> > Could you explain in very simple terms, suitable for Aunt Tillie (ok, not
> > *that* simple) how the continued fraction works, how it's notated, and how
> > the terms of the expansion relate to good performance as a hash?
> 
> Do you want it just in a post or in-line?
> 
> Here's the posted brief version:
> 
> Numbers have "integer parts" and "fractional parts", for instance, if
> you have a number such as 10 1/2 (ten and one half) the integer part
> is 10 and the fractional part is 1/2. The fractional part of a number
> x is written {x}.
> 
> Now, there is something called the "spectrum" of a number, which for
> a number x is the set of all the numbers of the form n * x, where n
> is an integer. So we have {1*x}, {2*x}, {3*x}, and so on.
> 
> If we want to measure how well a number distributes things we can try
> to see how uniform the spectrum is as a distribution. There is a
> theorem which states the "most uniform" distribution results from the
> number phi = (sqrt(5)-1)/2, which is related to Fibonacci numbers.
> 
> The continued fraction of phi is
> 
> 0 + 1
>    -----
>    1 + 1
>       -----
>       1 + 1
>          -----
>          1 + 1
>             -----
>             1 + 1
>                 ...
> 
> where it's 1's all the way down. Some additional study also revealed
> that how close the continued fraction of a number is to phi is related
> to how uniform the spectrum is. For brevity, I write continued fractions
> in-line, for instance, 0,1,1,1,1,... for phi, or 0,1,2,3,4,... for
> 
> 0 + 1
>    -----
>    1 + 2
>       -----
>       1 + 3
>          -----
>          1 + 4
>             ....
> 
> One way to evaluate these is to "chop off" the fraction at some point
> (for instance, where I put ...) and then reduce it like an ordinary
> fraction expression.
> 
> Fibonacci hashing considers the number p/2^n where n is BITS_PER_LONG
> and p is a prime number, and this is supposed to have a relationship
> to how evenly-distributed all the n-bit numbers multiplied by p in
> n-bit arithmetic are. Which is where the hash functions come in, since
> you want hash functions to evenly distribute things. There are reasons
> why primes are better, too.
> 
> And I think that covers most of what you had in mind.

Yes, it sure does, thanks a lot.

> In my own opinion, this stuff borders on numerology, but it seems to be
> a convenient supply of hash functions that pass chi^2 tests on the
> bucket distributions, so I sort of tolerate it. If I'm not using a strict
> enough test then I'm all ears...

/me resolves to get back to htree hashing very soon.

-- 
Daniel

Re: [PATCH] [rmap] operator-sparse Fibonacci hashing of waitqueues

[William Lee Irwin III]

On Mon, Feb 18, 2002 at 04:34:50PM -0800, William Lee Irwin III wrote:
> Now, there is something called the "spectrum" of a number, which for
> a number x is the set of all the numbers of the form n * x, where n
> is an integer. So we have {1*x}, {2*x}, {3*x}, and so on.

Argh! Spec(x) is the multiset [1*x], [2*x], [3*x] where [x] is the
integer part of x.


Cheers,
Bill