An interesting performance thing ?

An interesting performance thing ?

[Iozone]

[-- Attachment #1: Type: text/plain, Size: 35414 bytes --]

Neil,

    I think I have discovered an interesting performance anomaly.

    In the svcauth code there are places that do:

       hash_long((unsigned long)item->m_addr.s_addr, IP_HASHBITS);

    Ok... That seems reasonable, but then again...maybe not....

    I believe that s_addr is an IP address in Network Neutral format. 
     (Big Endian)

    So... When one is on a Little Endian system, the hash_long
    function gets handed a Big Endian value as a long, and
    later, via the magic of being a Little Endian system,
    gets byte swapped.

    Step 1. 192.168.1.2 becomes 2.1.168.192 (byte swap)

    Step 2.  The 32 bit IP address becomes a 64 bit long when
                 this code is compiled and run on an Opteron, or
                 an IA-64 system.
                 2.1.168.192 -> 0.0.0.0.2.1.168.192
    Step 3. Call the hash_long() and get back a hash value
                that is IP_HASHBITS (8) in size.

    You'll notice that the hash distribution is not nearly as
    good as one might believe.  If one would have done:

        hash_long( inet_lnaof(item->m_addr.s_addr)),IP_HASHBITS)

    Then the hash_long function would have done a nice job.  Since
    one is not converting the network neutral IP address into a 
    host binary format, here is an example of the hash distribution
    that, I believe via experimentation, is currently being seen on 
    Little Endian 64 Bit systems....

------------------------------------------------
Testing byte 4 (least significant)
Input: 192.168.0.0 Hash-> 3e
Input: 192.168.0.1 Hash-> 3e
Input: 192.168.0.2 Hash-> 3e
Input: 192.168.0.3 Hash-> 3e
Input: 192.168.0.4 Hash-> 3e
Input: 192.168.0.5 Hash-> 3e
Input: 192.168.0.6 Hash-> 3e
Input: 192.168.0.7 Hash-> 3e
Input: 192.168.0.8 Hash-> 3e
Input: 192.168.0.9 Hash-> 3e
Input: 192.168.0.10 Hash-> 3e
Input: 192.168.0.11 Hash-> 3e
Input: 192.168.0.12 Hash-> 3e
Input: 192.168.0.13 Hash-> 3e
Input: 192.168.0.14 Hash-> 3e
Input: 192.168.0.15 Hash-> 3e
Input: 192.168.0.16 Hash-> 3e
Input: 192.168.0.17 Hash-> 3e
Input: 192.168.0.18 Hash-> 3e
Input: 192.168.0.19 Hash-> 3e
Input: 192.168.0.20 Hash-> 3e
Input: 192.168.0.21 Hash-> 3e
Input: 192.168.0.22 Hash-> 3e
Input: 192.168.0.23 Hash-> 3e
Input: 192.168.0.24 Hash-> 3e
Input: 192.168.0.25 Hash-> 3e
Input: 192.168.0.26 Hash-> 3e
Input: 192.168.0.27 Hash-> 3e
Input: 192.168.0.28 Hash-> 3e
Input: 192.168.0.29 Hash-> 3e
Input: 192.168.0.30 Hash-> 3e
Input: 192.168.0.31 Hash-> 3e
Input: 192.168.0.32 Hash-> 3e
Input: 192.168.0.33 Hash-> 3e
Input: 192.168.0.34 Hash-> 3e
Input: 192.168.0.35 Hash-> 3e
Input: 192.168.0.36 Hash-> 3e
Input: 192.168.0.37 Hash-> 3e
Input: 192.168.0.38 Hash-> 3e
Input: 192.168.0.39 Hash-> 3e
Input: 192.168.0.40 Hash-> 3e
Input: 192.168.0.41 Hash-> 3e
Input: 192.168.0.42 Hash-> 3e
Input: 192.168.0.43 Hash-> 3e
Input: 192.168.0.44 Hash-> 3e
Input: 192.168.0.45 Hash-> 3e
Input: 192.168.0.46 Hash-> 3e
Input: 192.168.0.47 Hash-> 3e
Input: 192.168.0.48 Hash-> 3e
Input: 192.168.0.49 Hash-> 3e
Input: 192.168.0.50 Hash-> 3e
Input: 192.168.0.51 Hash-> 3e
Input: 192.168.0.52 Hash-> 3e
Input: 192.168.0.53 Hash-> 3e
Input: 192.168.0.54 Hash-> 3e
Input: 192.168.0.55 Hash-> 3e
Input: 192.168.0.56 Hash-> 3e
Input: 192.168.0.57 Hash-> 3e
Input: 192.168.0.58 Hash-> 3e
Input: 192.168.0.59 Hash-> 3e
Input: 192.168.0.60 Hash-> 3e
Input: 192.168.0.61 Hash-> 3e
Input: 192.168.0.62 Hash-> 3e
Input: 192.168.0.63 Hash-> 3e
Input: 192.168.0.64 Hash-> 3e
Input: 192.168.0.65 Hash-> 3e
Input: 192.168.0.66 Hash-> 3e
Input: 192.168.0.67 Hash-> 3e
Input: 192.168.0.68 Hash-> 3e
Input: 192.168.0.69 Hash-> 3e
Input: 192.168.0.70 Hash-> 3e
Input: 192.168.0.71 Hash-> 3e
Input: 192.168.0.72 Hash-> 3e
Input: 192.168.0.73 Hash-> 3e
Input: 192.168.0.74 Hash-> 3e
Input: 192.168.0.75 Hash-> 3e
Input: 192.168.0.76 Hash-> 3e
Input: 192.168.0.77 Hash-> 3e
Input: 192.168.0.78 Hash-> 3e
Input: 192.168.0.79 Hash-> 3e
Input: 192.168.0.80 Hash-> 3e
Input: 192.168.0.81 Hash-> 3e
Input: 192.168.0.82 Hash-> 3e
Input: 192.168.0.83 Hash-> 3e
Input: 192.168.0.84 Hash-> 3e
Input: 192.168.0.85 Hash-> 3e
Input: 192.168.0.86 Hash-> 3e
Input: 192.168.0.87 Hash-> 3e
Input: 192.168.0.88 Hash-> 3e
Input: 192.168.0.89 Hash-> 3e
Input: 192.168.0.90 Hash-> 3e
Input: 192.168.0.91 Hash-> 3e
Input: 192.168.0.92 Hash-> 3e
Input: 192.168.0.93 Hash-> 3e
Input: 192.168.0.94 Hash-> 3e
Input: 192.168.0.95 Hash-> 3e
Input: 192.168.0.96 Hash-> 3e
Input: 192.168.0.97 Hash-> 3e
Input: 192.168.0.98 Hash-> 3e
Input: 192.168.0.99 Hash-> 3e
Input: 192.168.0.100 Hash-> 3e
Input: 192.168.0.101 Hash-> 3e
Input: 192.168.0.102 Hash-> 3e
Input: 192.168.0.103 Hash-> 3e
Input: 192.168.0.104 Hash-> 3e
Input: 192.168.0.105 Hash-> 3e
Input: 192.168.0.106 Hash-> 3e
Input: 192.168.0.107 Hash-> 3e
Input: 192.168.0.108 Hash-> 3e
Input: 192.168.0.109 Hash-> 3e
Input: 192.168.0.110 Hash-> 3e
Input: 192.168.0.111 Hash-> 3e
Input: 192.168.0.112 Hash-> 3e
Input: 192.168.0.113 Hash-> 3e
Input: 192.168.0.114 Hash-> 3e
Input: 192.168.0.115 Hash-> 3e
Input: 192.168.0.116 Hash-> 3e
Input: 192.168.0.117 Hash-> 3e
Input: 192.168.0.118 Hash-> 3e
Input: 192.168.0.119 Hash-> 3e
Input: 192.168.0.120 Hash-> 3e
Input: 192.168.0.121 Hash-> 3e
Input: 192.168.0.122 Hash-> 3e
Input: 192.168.0.123 Hash-> 3e
Input: 192.168.0.124 Hash-> 3e
Input: 192.168.0.125 Hash-> 3e
Input: 192.168.0.126 Hash-> 3e
Input: 192.168.0.127 Hash-> 3e
Input: 192.168.0.128 Hash-> 3d
Input: 192.168.0.129 Hash-> 3d
Input: 192.168.0.130 Hash-> 3d
Input: 192.168.0.131 Hash-> 3d
Input: 192.168.0.132 Hash-> 3d
Input: 192.168.0.133 Hash-> 3d
Input: 192.168.0.134 Hash-> 3d
Input: 192.168.0.135 Hash-> 3d
Input: 192.168.0.136 Hash-> 3d
Input: 192.168.0.137 Hash-> 3d
Input: 192.168.0.138 Hash-> 3d
Input: 192.168.0.139 Hash-> 3d
Input: 192.168.0.140 Hash-> 3d
Input: 192.168.0.141 Hash-> 3d
Input: 192.168.0.142 Hash-> 3d
Input: 192.168.0.143 Hash-> 3d
Input: 192.168.0.144 Hash-> 3d
Input: 192.168.0.145 Hash-> 3d
Input: 192.168.0.146 Hash-> 3d
Input: 192.168.0.147 Hash-> 3d
Input: 192.168.0.148 Hash-> 3d
Input: 192.168.0.149 Hash-> 3d
Input: 192.168.0.150 Hash-> 3d
Input: 192.168.0.151 Hash-> 3d
Input: 192.168.0.152 Hash-> 3d
Input: 192.168.0.153 Hash-> 3d
Input: 192.168.0.154 Hash-> 3d
Input: 192.168.0.155 Hash-> 3d
Input: 192.168.0.156 Hash-> 3d
Input: 192.168.0.157 Hash-> 3d
Input: 192.168.0.158 Hash-> 3d
Input: 192.168.0.159 Hash-> 3d
Input: 192.168.0.160 Hash-> 3d
Input: 192.168.0.161 Hash-> 3d
Input: 192.168.0.162 Hash-> 3d
Input: 192.168.0.163 Hash-> 3d
Input: 192.168.0.164 Hash-> 3d
Input: 192.168.0.165 Hash-> 3d
Input: 192.168.0.166 Hash-> 3d
Input: 192.168.0.167 Hash-> 3d
Input: 192.168.0.168 Hash-> 3d
Input: 192.168.0.169 Hash-> 3d
Input: 192.168.0.170 Hash-> 3d
Input: 192.168.0.171 Hash-> 3d
Input: 192.168.0.172 Hash-> 3d
Input: 192.168.0.173 Hash-> 3d
Input: 192.168.0.174 Hash-> 3d
Input: 192.168.0.175 Hash-> 3d
Input: 192.168.0.176 Hash-> 3d
Input: 192.168.0.177 Hash-> 3d
Input: 192.168.0.178 Hash-> 3d
Input: 192.168.0.179 Hash-> 3d
Input: 192.168.0.180 Hash-> 3d
Input: 192.168.0.181 Hash-> 3d
Input: 192.168.0.182 Hash-> 3d
Input: 192.168.0.183 Hash-> 3d
Input: 192.168.0.184 Hash-> 3d
Input: 192.168.0.185 Hash-> 3d
Input: 192.168.0.186 Hash-> 3d
Input: 192.168.0.187 Hash-> 3d
Input: 192.168.0.188 Hash-> 3d
Input: 192.168.0.189 Hash-> 3d
Input: 192.168.0.190 Hash-> 3d
Input: 192.168.0.191 Hash-> 3d
Input: 192.168.0.192 Hash-> 3d
Input: 192.168.0.193 Hash-> 3d
Input: 192.168.0.194 Hash-> 3d
Input: 192.168.0.195 Hash-> 3d
Input: 192.168.0.196 Hash-> 3d
Input: 192.168.0.197 Hash-> 3d
Input: 192.168.0.198 Hash-> 3d
Input: 192.168.0.199 Hash-> 3d
Input: 192.168.0.200 Hash-> 3d
Input: 192.168.0.201 Hash-> 3d
Input: 192.168.0.202 Hash-> 3d
Input: 192.168.0.203 Hash-> 3d
Input: 192.168.0.204 Hash-> 3d
Input: 192.168.0.205 Hash-> 3d
Input: 192.168.0.206 Hash-> 3d
Input: 192.168.0.207 Hash-> 3d
Input: 192.168.0.208 Hash-> 3d
Input: 192.168.0.209 Hash-> 3d
Input: 192.168.0.210 Hash-> 3d
Input: 192.168.0.211 Hash-> 3d
Input: 192.168.0.212 Hash-> 3d
Input: 192.168.0.213 Hash-> 3d
Input: 192.168.0.214 Hash-> 3d
Input: 192.168.0.215 Hash-> 3d
Input: 192.168.0.216 Hash-> 3d
Input: 192.168.0.217 Hash-> 3d
Input: 192.168.0.218 Hash-> 3d
Input: 192.168.0.219 Hash-> 3d
Input: 192.168.0.220 Hash-> 3d
Input: 192.168.0.221 Hash-> 3d
Input: 192.168.0.222 Hash-> 3d
Input: 192.168.0.223 Hash-> 3d
Input: 192.168.0.224 Hash-> 3d
Input: 192.168.0.225 Hash-> 3d
Input: 192.168.0.226 Hash-> 3d
Input: 192.168.0.227 Hash-> 3d
Input: 192.168.0.228 Hash-> 3d
Input: 192.168.0.229 Hash-> 3d
Input: 192.168.0.230 Hash-> 3d
Input: 192.168.0.231 Hash-> 3d
Input: 192.168.0.232 Hash-> 3d
Input: 192.168.0.233 Hash-> 3d
Input: 192.168.0.234 Hash-> 3d
Input: 192.168.0.235 Hash-> 3d
Input: 192.168.0.236 Hash-> 3d
Input: 192.168.0.237 Hash-> 3d
Input: 192.168.0.238 Hash-> 3d
Input: 192.168.0.239 Hash-> 3d
Input: 192.168.0.240 Hash-> 3d
Input: 192.168.0.241 Hash-> 3d
Input: 192.168.0.242 Hash-> 3d
Input: 192.168.0.243 Hash-> 3d
Input: 192.168.0.244 Hash-> 3d
Input: 192.168.0.245 Hash-> 3d
Input: 192.168.0.246 Hash-> 3d
Input: 192.168.0.247 Hash-> 3d
Input: 192.168.0.248 Hash-> 3d
Input: 192.168.0.249 Hash-> 3d
Input: 192.168.0.250 Hash-> 3d
Input: 192.168.0.251 Hash-> 3d
Input: 192.168.0.252 Hash-> 3d
Input: 192.168.0.253 Hash-> 3d
Input: 192.168.0.254 Hash-> 3d
Input: 192.168.0.255 Hash-> 3d
Testing byte 3 
Input: 192.168.1.0 Hash-> 3e
Input: 192.168.1.1 Hash-> 3e
Input: 192.168.1.2 Hash-> 3e
Input: 192.168.1.3 Hash-> 3e
Input: 192.168.1.4 Hash-> 3e
Input: 192.168.1.5 Hash-> 3e
Input: 192.168.1.6 Hash-> 3e
Input: 192.168.1.7 Hash-> 3e
Input: 192.168.1.8 Hash-> 3e
Input: 192.168.1.9 Hash-> 3e
Input: 192.168.1.10 Hash-> 3e
Input: 192.168.1.11 Hash-> 3e
Input: 192.168.1.12 Hash-> 3e
Input: 192.168.1.13 Hash-> 3e
Input: 192.168.1.14 Hash-> 3e
Input: 192.168.1.15 Hash-> 3e
Input: 192.168.1.16 Hash-> 3e
Input: 192.168.1.17 Hash-> 3e
Input: 192.168.1.18 Hash-> 3e
Input: 192.168.1.19 Hash-> 3e
Input: 192.168.1.20 Hash-> 3e
Input: 192.168.1.21 Hash-> 3e
Input: 192.168.1.22 Hash-> 3e
Input: 192.168.1.23 Hash-> 3e
Input: 192.168.1.24 Hash-> 3e
Input: 192.168.1.25 Hash-> 3e
Input: 192.168.1.26 Hash-> 3e
Input: 192.168.1.27 Hash-> 3e
Input: 192.168.1.28 Hash-> 3e
Input: 192.168.1.29 Hash-> 3e
Input: 192.168.1.30 Hash-> 3e
Input: 192.168.1.31 Hash-> 3e
Input: 192.168.1.32 Hash-> 3e
Input: 192.168.1.33 Hash-> 3e
Input: 192.168.1.34 Hash-> 3e
Input: 192.168.1.35 Hash-> 3e
Input: 192.168.1.36 Hash-> 3e
Input: 192.168.1.37 Hash-> 3e
Input: 192.168.1.38 Hash-> 3e
Input: 192.168.1.39 Hash-> 3e
Input: 192.168.1.40 Hash-> 3e
Input: 192.168.1.41 Hash-> 3e
Input: 192.168.1.42 Hash-> 3e
Input: 192.168.1.43 Hash-> 3e
Input: 192.168.1.44 Hash-> 3e
Input: 192.168.1.45 Hash-> 3e
Input: 192.168.1.46 Hash-> 3e
Input: 192.168.1.47 Hash-> 3e
Input: 192.168.1.48 Hash-> 3e
Input: 192.168.1.49 Hash-> 3e
Input: 192.168.1.50 Hash-> 3e
Input: 192.168.1.51 Hash-> 3e
Input: 192.168.1.52 Hash-> 3e
Input: 192.168.1.53 Hash-> 3e
Input: 192.168.1.54 Hash-> 3e
Input: 192.168.1.55 Hash-> 3e
Input: 192.168.1.56 Hash-> 3e
Input: 192.168.1.57 Hash-> 3e
Input: 192.168.1.58 Hash-> 3e
Input: 192.168.1.59 Hash-> 3e
Input: 192.168.1.60 Hash-> 3e
Input: 192.168.1.61 Hash-> 3e
Input: 192.168.1.62 Hash-> 3e
Input: 192.168.1.63 Hash-> 3e
Input: 192.168.1.64 Hash-> 3e
Input: 192.168.1.65 Hash-> 3e
Input: 192.168.1.66 Hash-> 3e
Input: 192.168.1.67 Hash-> 3e
Input: 192.168.1.68 Hash-> 3e
Input: 192.168.1.69 Hash-> 3e
Input: 192.168.1.70 Hash-> 3e
Input: 192.168.1.71 Hash-> 3e
Input: 192.168.1.72 Hash-> 3e
Input: 192.168.1.73 Hash-> 3e
Input: 192.168.1.74 Hash-> 3e
Input: 192.168.1.75 Hash-> 3e
Input: 192.168.1.76 Hash-> 3e
Input: 192.168.1.77 Hash-> 3e
Input: 192.168.1.78 Hash-> 3e
Input: 192.168.1.79 Hash-> 3e
Input: 192.168.1.80 Hash-> 3e
Input: 192.168.1.81 Hash-> 3e
Input: 192.168.1.82 Hash-> 3e
Input: 192.168.1.83 Hash-> 3e
Input: 192.168.1.84 Hash-> 3e
Input: 192.168.1.85 Hash-> 3e
Input: 192.168.1.86 Hash-> 3e
Input: 192.168.1.87 Hash-> 3e
Input: 192.168.1.88 Hash-> 3e
Input: 192.168.1.89 Hash-> 3e
Input: 192.168.1.90 Hash-> 3e
Input: 192.168.1.91 Hash-> 3e
Input: 192.168.1.92 Hash-> 3e
Input: 192.168.1.93 Hash-> 3e
Input: 192.168.1.94 Hash-> 3e
Input: 192.168.1.95 Hash-> 3e
Input: 192.168.1.96 Hash-> 3e
Input: 192.168.1.97 Hash-> 3e
Input: 192.168.1.98 Hash-> 3e
Input: 192.168.1.99 Hash-> 3e
Input: 192.168.1.100 Hash-> 3e
Input: 192.168.1.101 Hash-> 3e
Input: 192.168.1.102 Hash-> 3e
Input: 192.168.1.103 Hash-> 3e
Input: 192.168.1.104 Hash-> 3e
Input: 192.168.1.105 Hash-> 3e
Input: 192.168.1.106 Hash-> 3e
Input: 192.168.1.107 Hash-> 3e
Input: 192.168.1.108 Hash-> 3e
Input: 192.168.1.109 Hash-> 3e
Input: 192.168.1.110 Hash-> 3e
Input: 192.168.1.111 Hash-> 3e
Input: 192.168.1.112 Hash-> 3e
Input: 192.168.1.113 Hash-> 3e
Input: 192.168.1.114 Hash-> 3e
Input: 192.168.1.115 Hash-> 3e
Input: 192.168.1.116 Hash-> 3e
Input: 192.168.1.117 Hash-> 3e
Input: 192.168.1.118 Hash-> 3e
Input: 192.168.1.119 Hash-> 3e
Input: 192.168.1.120 Hash-> 3e
Input: 192.168.1.121 Hash-> 3e
Input: 192.168.1.122 Hash-> 3e
Input: 192.168.1.123 Hash-> 3e
Input: 192.168.1.124 Hash-> 3e
Input: 192.168.1.125 Hash-> 3e
Input: 192.168.1.126 Hash-> 3e
Input: 192.168.1.127 Hash-> 3e
Input: 192.168.1.128 Hash-> 3d
Input: 192.168.1.129 Hash-> 3d
Input: 192.168.1.130 Hash-> 3d
Input: 192.168.1.131 Hash-> 3d
Input: 192.168.1.132 Hash-> 3d
Input: 192.168.1.133 Hash-> 3d
Input: 192.168.1.134 Hash-> 3d
Input: 192.168.1.135 Hash-> 3d
Input: 192.168.1.136 Hash-> 3d
Input: 192.168.1.137 Hash-> 3d
Input: 192.168.1.138 Hash-> 3d
Input: 192.168.1.139 Hash-> 3d
Input: 192.168.1.140 Hash-> 3d
Input: 192.168.1.141 Hash-> 3d
Input: 192.168.1.142 Hash-> 3d
Input: 192.168.1.143 Hash-> 3d
Input: 192.168.1.144 Hash-> 3d
Input: 192.168.1.145 Hash-> 3d
Input: 192.168.1.146 Hash-> 3d
Input: 192.168.1.147 Hash-> 3d
Input: 192.168.1.148 Hash-> 3d
Input: 192.168.1.149 Hash-> 3d
Input: 192.168.1.150 Hash-> 3d
Input: 192.168.1.151 Hash-> 3d
Input: 192.168.1.152 Hash-> 3d
Input: 192.168.1.153 Hash-> 3d
Input: 192.168.1.154 Hash-> 3d
Input: 192.168.1.155 Hash-> 3d
Input: 192.168.1.156 Hash-> 3d
Input: 192.168.1.157 Hash-> 3d
Input: 192.168.1.158 Hash-> 3d
Input: 192.168.1.159 Hash-> 3d
Input: 192.168.1.160 Hash-> 3d
Input: 192.168.1.161 Hash-> 3d
Input: 192.168.1.162 Hash-> 3d
Input: 192.168.1.163 Hash-> 3d
Input: 192.168.1.164 Hash-> 3d
Input: 192.168.1.165 Hash-> 3d
Input: 192.168.1.166 Hash-> 3d
Input: 192.168.1.167 Hash-> 3d
Input: 192.168.1.168 Hash-> 3d
Input: 192.168.1.169 Hash-> 3d
Input: 192.168.1.170 Hash-> 3d
Input: 192.168.1.171 Hash-> 3d
Input: 192.168.1.172 Hash-> 3d
Input: 192.168.1.173 Hash-> 3d
Input: 192.168.1.174 Hash-> 3d
Input: 192.168.1.175 Hash-> 3d
Input: 192.168.1.176 Hash-> 3d
Input: 192.168.1.177 Hash-> 3d
Input: 192.168.1.178 Hash-> 3d
Input: 192.168.1.179 Hash-> 3d
Input: 192.168.1.180 Hash-> 3d
Input: 192.168.1.181 Hash-> 3d
Input: 192.168.1.182 Hash-> 3d
Input: 192.168.1.183 Hash-> 3d
Input: 192.168.1.184 Hash-> 3d
Input: 192.168.1.185 Hash-> 3d
Input: 192.168.1.186 Hash-> 3d
Input: 192.168.1.187 Hash-> 3d
Input: 192.168.1.188 Hash-> 3d
Input: 192.168.1.189 Hash-> 3d
Input: 192.168.1.190 Hash-> 3d
Input: 192.168.1.191 Hash-> 3d
Input: 192.168.1.192 Hash-> 3d
Input: 192.168.1.193 Hash-> 3d
Input: 192.168.1.194 Hash-> 3d
Input: 192.168.1.195 Hash-> 3d
Input: 192.168.1.196 Hash-> 3d
Input: 192.168.1.197 Hash-> 3d
Input: 192.168.1.198 Hash-> 3d
Input: 192.168.1.199 Hash-> 3d
Input: 192.168.1.200 Hash-> 3d
Input: 192.168.1.201 Hash-> 3d
Input: 192.168.1.202 Hash-> 3d
Input: 192.168.1.203 Hash-> 3d
Input: 192.168.1.204 Hash-> 3d
Input: 192.168.1.205 Hash-> 3d
Input: 192.168.1.206 Hash-> 3d
Input: 192.168.1.207 Hash-> 3d
Input: 192.168.1.208 Hash-> 3d
Input: 192.168.1.209 Hash-> 3d
Input: 192.168.1.210 Hash-> 3d
Input: 192.168.1.211 Hash-> 3d
Input: 192.168.1.212 Hash-> 3d
Input: 192.168.1.213 Hash-> 3d
Input: 192.168.1.214 Hash-> 3d
Input: 192.168.1.215 Hash-> 3d
Input: 192.168.1.216 Hash-> 3d
Input: 192.168.1.217 Hash-> 3d
Input: 192.168.1.218 Hash-> 3d
Input: 192.168.1.219 Hash-> 3d
Input: 192.168.1.220 Hash-> 3d
Input: 192.168.1.221 Hash-> 3d
Input: 192.168.1.222 Hash-> 3d
Input: 192.168.1.223 Hash-> 3d
Input: 192.168.1.224 Hash-> 3d
Input: 192.168.1.225 Hash-> 3d
Input: 192.168.1.226 Hash-> 3d
Input: 192.168.1.227 Hash-> 3d
Input: 192.168.1.228 Hash-> 3d
Input: 192.168.1.229 Hash-> 3d
Input: 192.168.1.230 Hash-> 3d
Input: 192.168.1.231 Hash-> 3d
Input: 192.168.1.232 Hash-> 3d
Input: 192.168.1.233 Hash-> 3d
Input: 192.168.1.234 Hash-> 3d
Input: 192.168.1.235 Hash-> 3d
Input: 192.168.1.236 Hash-> 3d
Input: 192.168.1.237 Hash-> 3d
Input: 192.168.1.238 Hash-> 3d
Input: 192.168.1.239 Hash-> 3d
Input: 192.168.1.240 Hash-> 3d
Input: 192.168.1.241 Hash-> 3d
Input: 192.168.1.242 Hash-> 3d
Input: 192.168.1.243 Hash-> 3d
Input: 192.168.1.244 Hash-> 3d
Input: 192.168.1.245 Hash-> 3d
Input: 192.168.1.246 Hash-> 3d
Input: 192.168.1.247 Hash-> 3d
Input: 192.168.1.248 Hash-> 3d
Input: 192.168.1.249 Hash-> 3d
Input: 192.168.1.250 Hash-> 3d
Input: 192.168.1.251 Hash-> 3d
Input: 192.168.1.252 Hash-> 3d
Input: 192.168.1.253 Hash-> 3d
Input: 192.168.1.254 Hash-> 3d
Input: 192.168.1.255 Hash-> 3d
Testing byte 2 
Input: 192.169.0.0 Hash-> f6
Input: 192.169.0.1 Hash-> f6
Input: 192.169.0.2 Hash-> f6
Input: 192.169.0.3 Hash-> f6
Input: 192.169.0.4 Hash-> f6
Input: 192.169.0.5 Hash-> f6
Input: 192.169.0.6 Hash-> f6
Input: 192.169.0.7 Hash-> f6
Input: 192.169.0.8 Hash-> f6
Input: 192.169.0.9 Hash-> f6
Input: 192.169.0.10 Hash-> f6
Input: 192.169.0.11 Hash-> f6
Input: 192.169.0.12 Hash-> f6
Input: 192.169.0.13 Hash-> f6
Input: 192.169.0.14 Hash-> f6
Input: 192.169.0.15 Hash-> f6
Input: 192.169.0.16 Hash-> f6
Input: 192.169.0.17 Hash-> f6
Input: 192.169.0.18 Hash-> f6
Input: 192.169.0.19 Hash-> f6
Input: 192.169.0.20 Hash-> f6
Input: 192.169.0.21 Hash-> f6
Input: 192.169.0.22 Hash-> f6
Input: 192.169.0.23 Hash-> f6
Input: 192.169.0.24 Hash-> f6
Input: 192.169.0.25 Hash-> f6
Input: 192.169.0.26 Hash-> f6
Input: 192.169.0.27 Hash-> f6
Input: 192.169.0.28 Hash-> f6
Input: 192.169.0.29 Hash-> f6
Input: 192.169.0.30 Hash-> f6
Input: 192.169.0.31 Hash-> f6
Input: 192.169.0.32 Hash-> f6
Input: 192.169.0.33 Hash-> f6
Input: 192.169.0.34 Hash-> f6
Input: 192.169.0.35 Hash-> f6
Input: 192.169.0.36 Hash-> f6
Input: 192.169.0.37 Hash-> f6
Input: 192.169.0.38 Hash-> f6
Input: 192.169.0.39 Hash-> f6
Input: 192.169.0.40 Hash-> f6
Input: 192.169.0.41 Hash-> f6
Input: 192.169.0.42 Hash-> f6
Input: 192.169.0.43 Hash-> f6
Input: 192.169.0.44 Hash-> f6
Input: 192.169.0.45 Hash-> f6
Input: 192.169.0.46 Hash-> f6
Input: 192.169.0.47 Hash-> f6
Input: 192.169.0.48 Hash-> f6
Input: 192.169.0.49 Hash-> f6
Input: 192.169.0.50 Hash-> f6
Input: 192.169.0.51 Hash-> f6
Input: 192.169.0.52 Hash-> f6
Input: 192.169.0.53 Hash-> f6
Input: 192.169.0.54 Hash-> f6
Input: 192.169.0.55 Hash-> f6
Input: 192.169.0.56 Hash-> f6
Input: 192.169.0.57 Hash-> f6
Input: 192.169.0.58 Hash-> f6
Input: 192.169.0.59 Hash-> f6
Input: 192.169.0.60 Hash-> f6
Input: 192.169.0.61 Hash-> f6
Input: 192.169.0.62 Hash-> f6
Input: 192.169.0.63 Hash-> f6
Input: 192.169.0.64 Hash-> f6
Input: 192.169.0.65 Hash-> f6
Input: 192.169.0.66 Hash-> f6
Input: 192.169.0.67 Hash-> f6
Input: 192.169.0.68 Hash-> f6
Input: 192.169.0.69 Hash-> f6
Input: 192.169.0.70 Hash-> f6
Input: 192.169.0.71 Hash-> f6
Input: 192.169.0.72 Hash-> f6
Input: 192.169.0.73 Hash-> f6
Input: 192.169.0.74 Hash-> f6
Input: 192.169.0.75 Hash-> f6
Input: 192.169.0.76 Hash-> f6
Input: 192.169.0.77 Hash-> f6
Input: 192.169.0.78 Hash-> f6
Input: 192.169.0.79 Hash-> f6
Input: 192.169.0.80 Hash-> f6
Input: 192.169.0.81 Hash-> f6
Input: 192.169.0.82 Hash-> f6
Input: 192.169.0.83 Hash-> f6
Input: 192.169.0.84 Hash-> f6
Input: 192.169.0.85 Hash-> f6
Input: 192.169.0.86 Hash-> f6
Input: 192.169.0.87 Hash-> f6
Input: 192.169.0.88 Hash-> f6
Input: 192.169.0.89 Hash-> f6
Input: 192.169.0.90 Hash-> f6
Input: 192.169.0.91 Hash-> f6
Input: 192.169.0.92 Hash-> f6
Input: 192.169.0.93 Hash-> f6
Input: 192.169.0.94 Hash-> f6
Input: 192.169.0.95 Hash-> f6
Input: 192.169.0.96 Hash-> f6
Input: 192.169.0.97 Hash-> f6
Input: 192.169.0.98 Hash-> f6
Input: 192.169.0.99 Hash-> f6
Input: 192.169.0.100 Hash-> f6
Input: 192.169.0.101 Hash-> f6
Input: 192.169.0.102 Hash-> f6
Input: 192.169.0.103 Hash-> f6
Input: 192.169.0.104 Hash-> f6
Input: 192.169.0.105 Hash-> f6
Input: 192.169.0.106 Hash-> f6
Input: 192.169.0.107 Hash-> f6
Input: 192.169.0.108 Hash-> f6
Input: 192.169.0.109 Hash-> f6
Input: 192.169.0.110 Hash-> f6
Input: 192.169.0.111 Hash-> f6
Input: 192.169.0.112 Hash-> f6
Input: 192.169.0.113 Hash-> f6
Input: 192.169.0.114 Hash-> f6
Input: 192.169.0.115 Hash-> f6
Input: 192.169.0.116 Hash-> f6
Input: 192.169.0.117 Hash-> f6
Input: 192.169.0.118 Hash-> f6
Input: 192.169.0.119 Hash-> f6
Input: 192.169.0.120 Hash-> f6
Input: 192.169.0.121 Hash-> f6
Input: 192.169.0.122 Hash-> f6
Input: 192.169.0.123 Hash-> f6
Input: 192.169.0.124 Hash-> f6
Input: 192.169.0.125 Hash-> f6
Input: 192.169.0.126 Hash-> f6
Input: 192.169.0.127 Hash-> f6
Input: 192.169.0.128 Hash-> f5
Input: 192.169.0.129 Hash-> f5
Input: 192.169.0.130 Hash-> f5
Input: 192.169.0.131 Hash-> f5
Input: 192.169.0.132 Hash-> f5
Input: 192.169.0.133 Hash-> f5
Input: 192.169.0.134 Hash-> f5
Input: 192.169.0.135 Hash-> f5
Input: 192.169.0.136 Hash-> f5
Input: 192.169.0.137 Hash-> f5
Input: 192.169.0.138 Hash-> f5
Input: 192.169.0.139 Hash-> f5
Input: 192.169.0.140 Hash-> f5
Input: 192.169.0.141 Hash-> f5
Input: 192.169.0.142 Hash-> f5
Input: 192.169.0.143 Hash-> f5
Input: 192.169.0.144 Hash-> f5
Input: 192.169.0.145 Hash-> f5
Input: 192.169.0.146 Hash-> f5
Input: 192.169.0.147 Hash-> f5
Input: 192.169.0.148 Hash-> f5
Input: 192.169.0.149 Hash-> f5
Input: 192.169.0.150 Hash-> f5
Input: 192.169.0.151 Hash-> f5
Input: 192.169.0.152 Hash-> f5
Input: 192.169.0.153 Hash-> f5
Input: 192.169.0.154 Hash-> f5
Input: 192.169.0.155 Hash-> f5
Input: 192.169.0.156 Hash-> f5
Input: 192.169.0.157 Hash-> f5
Input: 192.169.0.158 Hash-> f5
Input: 192.169.0.159 Hash-> f5
Input: 192.169.0.160 Hash-> f5
Input: 192.169.0.161 Hash-> f5
Input: 192.169.0.162 Hash-> f5
Input: 192.169.0.163 Hash-> f5
Input: 192.169.0.164 Hash-> f5
Input: 192.169.0.165 Hash-> f5
Input: 192.169.0.166 Hash-> f5
Input: 192.169.0.167 Hash-> f5
Input: 192.169.0.168 Hash-> f5
Input: 192.169.0.169 Hash-> f5
Input: 192.169.0.170 Hash-> f5
Input: 192.169.0.171 Hash-> f5
Input: 192.169.0.172 Hash-> f5
Input: 192.169.0.173 Hash-> f5
Input: 192.169.0.174 Hash-> f5
Input: 192.169.0.175 Hash-> f5
Input: 192.169.0.176 Hash-> f5
Input: 192.169.0.177 Hash-> f5
Input: 192.169.0.178 Hash-> f5
Input: 192.169.0.179 Hash-> f5
Input: 192.169.0.180 Hash-> f5
Input: 192.169.0.181 Hash-> f5
Input: 192.169.0.182 Hash-> f5
Input: 192.169.0.183 Hash-> f5
Input: 192.169.0.184 Hash-> f5
Input: 192.169.0.185 Hash-> f5
Input: 192.169.0.186 Hash-> f5
Input: 192.169.0.187 Hash-> f5
Input: 192.169.0.188 Hash-> f5
Input: 192.169.0.189 Hash-> f5
Input: 192.169.0.190 Hash-> f5
Input: 192.169.0.191 Hash-> f5
Input: 192.169.0.192 Hash-> f5
Input: 192.169.0.193 Hash-> f5
Input: 192.169.0.194 Hash-> f5
Input: 192.169.0.195 Hash-> f5
Input: 192.169.0.196 Hash-> f5
Input: 192.169.0.197 Hash-> f5
Input: 192.169.0.198 Hash-> f5
Input: 192.169.0.199 Hash-> f5
Input: 192.169.0.200 Hash-> f5
Input: 192.169.0.201 Hash-> f5
Input: 192.169.0.202 Hash-> f5
Input: 192.169.0.203 Hash-> f5
Input: 192.169.0.204 Hash-> f5
Input: 192.169.0.205 Hash-> f5
Input: 192.169.0.206 Hash-> f5
Input: 192.169.0.207 Hash-> f5
Input: 192.169.0.208 Hash-> f5
Input: 192.169.0.209 Hash-> f5
Input: 192.169.0.210 Hash-> f5
Input: 192.169.0.211 Hash-> f5
Input: 192.169.0.212 Hash-> f5
Input: 192.169.0.213 Hash-> f5
Input: 192.169.0.214 Hash-> f5
Input: 192.169.0.215 Hash-> f5
Input: 192.169.0.216 Hash-> f5
Input: 192.169.0.217 Hash-> f5
Input: 192.169.0.218 Hash-> f5
Input: 192.169.0.219 Hash-> f5
Input: 192.169.0.220 Hash-> f5
Input: 192.169.0.221 Hash-> f5
Input: 192.169.0.222 Hash-> f5
Input: 192.169.0.223 Hash-> f5
Input: 192.169.0.224 Hash-> f5
Input: 192.169.0.225 Hash-> f5
Input: 192.169.0.226 Hash-> f5
Input: 192.169.0.227 Hash-> f5
Input: 192.169.0.228 Hash-> f5
Input: 192.169.0.229 Hash-> f5
Input: 192.169.0.230 Hash-> f5
Input: 192.169.0.231 Hash-> f5
Input: 192.169.0.232 Hash-> f5
Input: 192.169.0.233 Hash-> f5
Input: 192.169.0.234 Hash-> f5
Input: 192.169.0.235 Hash-> f5
Input: 192.169.0.236 Hash-> f5
Input: 192.169.0.237 Hash-> f5
Input: 192.169.0.238 Hash-> f5
Input: 192.169.0.239 Hash-> f5
Input: 192.169.0.240 Hash-> f5
Input: 192.169.0.241 Hash-> f5
Input: 192.169.0.242 Hash-> f5
Input: 192.169.0.243 Hash-> f5
Input: 192.169.0.244 Hash-> f5
Input: 192.169.0.245 Hash-> f5
Input: 192.169.0.246 Hash-> f5
Input: 192.169.0.247 Hash-> f5
Input: 192.169.0.248 Hash-> f5
Input: 192.169.0.249 Hash-> f5
Input: 192.169.0.250 Hash-> f5
Input: 192.169.0.251 Hash-> f5
Input: 192.169.0.252 Hash-> f5
Input: 192.169.0.253 Hash-> f5
Input: 192.169.0.254 Hash-> f5
Input: 192.169.0.255 Hash-> f5
Testing byte 1 (Most significant byte)
Input: 193.169.2.0 Hash-> 17
Input: 193.169.2.1 Hash-> 17
Input: 193.169.2.2 Hash-> 17
Input: 193.169.2.3 Hash-> 17
Input: 193.169.2.4 Hash-> 17
Input: 193.169.2.5 Hash-> 17
Input: 193.169.2.6 Hash-> 17
Input: 193.169.2.7 Hash-> 17
Input: 193.169.2.8 Hash-> 17
Input: 193.169.2.9 Hash-> 17
Input: 193.169.2.10 Hash-> 17
Input: 193.169.2.11 Hash-> 17
Input: 193.169.2.12 Hash-> 17
Input: 193.169.2.13 Hash-> 17
Input: 193.169.2.14 Hash-> 17
Input: 193.169.2.15 Hash-> 17
Input: 193.169.2.16 Hash-> 17
Input: 193.169.2.17 Hash-> 17
Input: 193.169.2.18 Hash-> 17
Input: 193.169.2.19 Hash-> 17
Input: 193.169.2.20 Hash-> 17
Input: 193.169.2.21 Hash-> 17
Input: 193.169.2.22 Hash-> 17
Input: 193.169.2.23 Hash-> 17
Input: 193.169.2.24 Hash-> 17
Input: 193.169.2.25 Hash-> 17
Input: 193.169.2.26 Hash-> 17
Input: 193.169.2.27 Hash-> 17
Input: 193.169.2.28 Hash-> 17
Input: 193.169.2.29 Hash-> 17
Input: 193.169.2.30 Hash-> 17
Input: 193.169.2.31 Hash-> 17
Input: 193.169.2.32 Hash-> 17
Input: 193.169.2.33 Hash-> 17
Input: 193.169.2.34 Hash-> 17
Input: 193.169.2.35 Hash-> 17
Input: 193.169.2.36 Hash-> 17
Input: 193.169.2.37 Hash-> 17
Input: 193.169.2.38 Hash-> 17
Input: 193.169.2.39 Hash-> 17
Input: 193.169.2.40 Hash-> 17
Input: 193.169.2.41 Hash-> 17
Input: 193.169.2.42 Hash-> 17
Input: 193.169.2.43 Hash-> 17
Input: 193.169.2.44 Hash-> 17
Input: 193.169.2.45 Hash-> 17
Input: 193.169.2.46 Hash-> 17
Input: 193.169.2.47 Hash-> 17
Input: 193.169.2.48 Hash-> 17
Input: 193.169.2.49 Hash-> 17
Input: 193.169.2.50 Hash-> 17
Input: 193.169.2.51 Hash-> 17
Input: 193.169.2.52 Hash-> 17
Input: 193.169.2.53 Hash-> 17
Input: 193.169.2.54 Hash-> 17
Input: 193.169.2.55 Hash-> 17
Input: 193.169.2.56 Hash-> 17
Input: 193.169.2.57 Hash-> 17
Input: 193.169.2.58 Hash-> 17
Input: 193.169.2.59 Hash-> 17
Input: 193.169.2.60 Hash-> 17
Input: 193.169.2.61 Hash-> 17
Input: 193.169.2.62 Hash-> 17
Input: 193.169.2.63 Hash-> 17
Input: 193.169.2.64 Hash-> 17
Input: 193.169.2.65 Hash-> 17
Input: 193.169.2.66 Hash-> 17
Input: 193.169.2.67 Hash-> 17
Input: 193.169.2.68 Hash-> 17
Input: 193.169.2.69 Hash-> 17
Input: 193.169.2.70 Hash-> 17
Input: 193.169.2.71 Hash-> 17
Input: 193.169.2.72 Hash-> 17
Input: 193.169.2.73 Hash-> 17
Input: 193.169.2.74 Hash-> 17
Input: 193.169.2.75 Hash-> 17
Input: 193.169.2.76 Hash-> 17
Input: 193.169.2.77 Hash-> 17
Input: 193.169.2.78 Hash-> 17
Input: 193.169.2.79 Hash-> 17
Input: 193.169.2.80 Hash-> 17
Input: 193.169.2.81 Hash-> 17
Input: 193.169.2.82 Hash-> 17
Input: 193.169.2.83 Hash-> 17
Input: 193.169.2.84 Hash-> 17
Input: 193.169.2.85 Hash-> 17
Input: 193.169.2.86 Hash-> 17
Input: 193.169.2.87 Hash-> 17
Input: 193.169.2.88 Hash-> 17
Input: 193.169.2.89 Hash-> 17
Input: 193.169.2.90 Hash-> 17
Input: 193.169.2.91 Hash-> 17
Input: 193.169.2.92 Hash-> 17
Input: 193.169.2.93 Hash-> 17
Input: 193.169.2.94 Hash-> 17
Input: 193.169.2.95 Hash-> 17
Input: 193.169.2.96 Hash-> 17
Input: 193.169.2.97 Hash-> 17
Input: 193.169.2.98 Hash-> 17
Input: 193.169.2.99 Hash-> 17
Input: 193.169.2.100 Hash-> 17
Input: 193.169.2.101 Hash-> 17
Input: 193.169.2.102 Hash-> 17
Input: 193.169.2.103 Hash-> 17
Input: 193.169.2.104 Hash-> 17
Input: 193.169.2.105 Hash-> 17
Input: 193.169.2.106 Hash-> 17
Input: 193.169.2.107 Hash-> 17
Input: 193.169.2.108 Hash-> 17
Input: 193.169.2.109 Hash-> 17
Input: 193.169.2.110 Hash-> 17
Input: 193.169.2.111 Hash-> 17
Input: 193.169.2.112 Hash-> 17
Input: 193.169.2.113 Hash-> 17
Input: 193.169.2.114 Hash-> 17
Input: 193.169.2.115 Hash-> 17
Input: 193.169.2.116 Hash-> 17
Input: 193.169.2.117 Hash-> 17
Input: 193.169.2.118 Hash-> 17
Input: 193.169.2.119 Hash-> 17
Input: 193.169.2.120 Hash-> 17
Input: 193.169.2.121 Hash-> 17
Input: 193.169.2.122 Hash-> 17
Input: 193.169.2.123 Hash-> 17
Input: 193.169.2.124 Hash-> 17
Input: 193.169.2.125 Hash-> 17
Input: 193.169.2.126 Hash-> 17
Input: 193.169.2.127 Hash-> 17
Input: 193.169.2.128 Hash-> 17
Input: 193.169.2.129 Hash-> 17
Input: 193.169.2.130 Hash-> 17
Input: 193.169.2.131 Hash-> 17
Input: 193.169.2.132 Hash-> 17
Input: 193.169.2.133 Hash-> 17
Input: 193.169.2.134 Hash-> 17
Input: 193.169.2.135 Hash-> 17
Input: 193.169.2.136 Hash-> 17
Input: 193.169.2.137 Hash-> 17
Input: 193.169.2.138 Hash-> 17
Input: 193.169.2.139 Hash-> 17
Input: 193.169.2.140 Hash-> 17
Input: 193.169.2.141 Hash-> 17
Input: 193.169.2.142 Hash-> 17
Input: 193.169.2.143 Hash-> 17
Input: 193.169.2.144 Hash-> 17
Input: 193.169.2.145 Hash-> 17
Input: 193.169.2.146 Hash-> 17
Input: 193.169.2.147 Hash-> 17
Input: 193.169.2.148 Hash-> 17
Input: 193.169.2.149 Hash-> 17
Input: 193.169.2.150 Hash-> 17
Input: 193.169.2.151 Hash-> 17
Input: 193.169.2.152 Hash-> 17
Input: 193.169.2.153 Hash-> 17
Input: 193.169.2.154 Hash-> 17
Input: 193.169.2.155 Hash-> 17
Input: 193.169.2.156 Hash-> 17
Input: 193.169.2.157 Hash-> 17
Input: 193.169.2.158 Hash-> 17
Input: 193.169.2.159 Hash-> 17
Input: 193.169.2.160 Hash-> 17
Input: 193.169.2.161 Hash-> 17
Input: 193.169.2.162 Hash-> 17
Input: 193.169.2.163 Hash-> 17
Input: 193.169.2.164 Hash-> 17
Input: 193.169.2.165 Hash-> 17
Input: 193.169.2.166 Hash-> 17
Input: 193.169.2.167 Hash-> 17
Input: 193.169.2.168 Hash-> 17
Input: 193.169.2.169 Hash-> 17
Input: 193.169.2.170 Hash-> 17
Input: 193.169.2.171 Hash-> 17
Input: 193.169.2.172 Hash-> 17
Input: 193.169.2.173 Hash-> 17
Input: 193.169.2.174 Hash-> 17
Input: 193.169.2.175 Hash-> 17
Input: 193.169.2.176 Hash-> 17
Input: 193.169.2.177 Hash-> 17
Input: 193.169.2.178 Hash-> 17
Input: 193.169.2.179 Hash-> 17
Input: 193.169.2.180 Hash-> 17
Input: 193.169.2.181 Hash-> 17
Input: 193.169.2.182 Hash-> 17
Input: 193.169.2.183 Hash-> 17
Input: 193.169.2.184 Hash-> 17
Input: 193.169.2.185 Hash-> 17
Input: 193.169.2.186 Hash-> 17
Input: 193.169.2.187 Hash-> 17
Input: 193.169.2.188 Hash-> 17
Input: 193.169.2.189 Hash-> 17
Input: 193.169.2.190 Hash-> 17
Input: 193.169.2.191 Hash-> 17
Input: 193.169.2.192 Hash-> 17
Input: 193.169.2.193 Hash-> 17
Input: 193.169.2.194 Hash-> 17
Input: 193.169.2.195 Hash-> 17
Input: 193.169.2.196 Hash-> 17
Input: 193.169.2.197 Hash-> 17
Input: 193.169.2.198 Hash-> 17
Input: 193.169.2.199 Hash-> 17
Input: 193.169.2.200 Hash-> 17
Input: 193.169.2.201 Hash-> 17
Input: 193.169.2.202 Hash-> 17
Input: 193.169.2.203 Hash-> 17
Input: 193.169.2.204 Hash-> 17
Input: 193.169.2.205 Hash-> 17
Input: 193.169.2.206 Hash-> 17
Input: 193.169.2.207 Hash-> 17
Input: 193.169.2.208 Hash-> 17
Input: 193.169.2.209 Hash-> 17
Input: 193.169.2.210 Hash-> 17
Input: 193.169.2.211 Hash-> 17
Input: 193.169.2.212 Hash-> 17
Input: 193.169.2.213 Hash-> 17
Input: 193.169.2.214 Hash-> 17
Input: 193.169.2.215 Hash-> 17
Input: 193.169.2.216 Hash-> 17
Input: 193.169.2.217 Hash-> 17
Input: 193.169.2.218 Hash-> 17
Input: 193.169.2.219 Hash-> 17
Input: 193.169.2.220 Hash-> 17
Input: 193.169.2.221 Hash-> 17
Input: 193.169.2.222 Hash-> 17
Input: 193.169.2.223 Hash-> 17
Input: 193.169.2.224 Hash-> 17
Input: 193.169.2.225 Hash-> 17
Input: 193.169.2.226 Hash-> 17
Input: 193.169.2.227 Hash-> 17
Input: 193.169.2.228 Hash-> 17
Input: 193.169.2.229 Hash-> 17
Input: 193.169.2.230 Hash-> 17
Input: 193.169.2.231 Hash-> 17
Input: 193.169.2.232 Hash-> 17
Input: 193.169.2.233 Hash-> 17
Input: 193.169.2.234 Hash-> 17
Input: 193.169.2.235 Hash-> 17
Input: 193.169.2.236 Hash-> 17
Input: 193.169.2.237 Hash-> 17
Input: 193.169.2.238 Hash-> 17
Input: 193.169.2.239 Hash-> 17
Input: 193.169.2.240 Hash-> 17
Input: 193.169.2.241 Hash-> 17
Input: 193.169.2.242 Hash-> 17
Input: 193.169.2.243 Hash-> 17
Input: 193.169.2.244 Hash-> 17
Input: 193.169.2.245 Hash-> 17
Input: 193.169.2.246 Hash-> 17
Input: 193.169.2.247 Hash-> 17
Input: 193.169.2.248 Hash-> 17
Input: 193.169.2.249 Hash-> 17
Input: 193.169.2.250 Hash-> 17
Input: 193.169.2.251 Hash-> 17
Input: 193.169.2.252 Hash-> 17
Input: 193.169.2.253 Hash-> 17
Input: 193.169.2.254 Hash-> 17
Input: 193.169.2.255 Hash-> 17
------------

---------

    Now you say "Ok that's not too cool, but why is this really important ?"

        Well, it turns out that the RedHat EL 4 release has some issues
    with the locking around the buckets that this hash is being
    used to index into, and with the distribution being so not... it
    leads to a lock race, followed by a kernel dereference of null,
    followed shortly by angry phone calls.... True, the race needs
    to be fixed, but it sure would be nice if the pressure were a 
    tad lower on the lock. It would greatly reduce the probability
    of the panic, and also improve the performance (scaling) of
    the system, if a few more buckets were used :-)

    I've talked this over with Charles, and Bruce, and they pointed
    me in your direction ... 
    
    How would you prefer to proceed ?

        A. It's your code, and you would prefer to tinker without
            some bozo adding his two bits.

        B. You're way too busy to go after this, and would 
            welcome a diff -u patch.

        C. You'll scratch your head, think about it, and get back
            after morning coffee :-)

        D. It will only take a few seconds to add the 
                inet_lnaof( ) to the offending lines, and it will be
                done before you can say Jack Flash :-)
    
        E. Go away, you're bothering me :-)

Enjoy,
Don Capps
capps_at_iozone_dot_org





[-- Attachment #2: Type: text/html, Size: 46659 bytes --]

Re: An interesting performance thing ?

[Neil Brown]

On Wednesday December 14, capps@iozone.org wrote:
> Neil,

Hi, Don,

> 
>     I think I have discovered an interesting performance anomaly.

Indeed you have, thanks.

> 
>     In the svcauth code there are places that do:
> 
>        hash_long((unsigned long)item->m_addr.s_addr, IP_HASHBITS);
> 
>     Ok... That seems reasonable, but then again...maybe not....

No, perfectly reasonable.  I don't write "maybe reasonable" code.  It
is either perfect, or rubbish :-)

> 
>     I believe that s_addr is an IP address in Network Neutral format. 
>      (Big Endian)
> 
>     So... When one is on a Little Endian system, the hash_long
>     function gets handed a Big Endian value as a long, and
>     later, via the magic of being a Little Endian system,
>     gets byte swapped.
> 
>     Step 1. 192.168.1.2 becomes 2.1.168.192 (byte swap)
> 
>     Step 2.  The 32 bit IP address becomes a 64 bit long when
>                  this code is compiled and run on an Opteron, or
>                  an IA-64 system.
>                  2.1.168.192 -> 0.0.0.0.2.1.168.192
>     Step 3. Call the hash_long() and get back a hash value
>                 that is IP_HASHBITS (8) in size.
> 
>     You'll notice that the hash distribution is not nearly as
>     good as one might believe.  If one would have done:
> 
>         hash_long( inet_lnaof(item->m_addr.s_addr)),IP_HASHBITS)
> 
>     Then the hash_long function would have done a nice job. 

True, but irrelevant. 
hash_long(X, 8) will take the top 8 bits of the result.  So pushing
the noisy bits into the low order bits should have no significant
effect.
The fact that it does suggests that hash_long is broken.

I wonder if I blame William or Chuck?  Maybe I'll just blame both.
After all it is Christmas time and we should share the good will
around :-)

> 
> ---------
> 
>     Now you say "Ok that's not too cool, but why is this really
>     important ?"

Oh, no.  I can easily see that it is important.  And I agree it is
seriously uncool (like the weather down here is oz (aka .au)).


> 
>         Well, it turns out that the RedHat EL 4 release has some issues
>     with the locking around the buckets that this hash is being
>     used to index into, and with the distribution being so not... it
>     leads to a lock race, followed by a kernel dereference of null,
>     followed shortly by angry phone calls.... True, the race needs
>     to be fixed, but it sure would be nice if the pressure were a 
>     tad lower on the lock. It would greatly reduce the probability
>     of the panic, and also improve the performance (scaling) of
>     the system, if a few more buckets were used :-)

What mainline kernel is RedHat EL 4 based on?
I think I know the race you mean.... Funny how one writes buggy code,
then fixes it, then finds it still existing in "enterprise" kernels
months later. (SLES only gets it fixed in 9SP3).

> 
>     I've talked this over with Charles, and Bruce, and they pointed
>     me in your direction ... 

Go back to Charles and tell him I sent you :-)

>     
>     How would you prefer to proceed ?
> 
>         A. It's your code, and you would prefer to tinker without
>             some bozo adding his two bits.

Nonono, bozo bits are worth their weight in gold (sometimes).

> 
>         B. You're way too busy to go after this, and would 
>             welcome a diff -u patch.

In general, yes.  In this case, the patch would have been wrong.

> 
>         C. You'll scratch your head, think about it, and get back
>             after morning coffee :-)

I'm a tea drinker, so that wouldn't work.

> 
>         D. It will only take a few seconds to add the 
>                 inet_lnaof( ) to the offending lines, and it will be
>                 done before you can say Jack Flash :-)

It was 'Jack Robinson' in my day - no idea why.

>     
>         E. Go away, you're bothering me :-)
> 

Yeh, stop bothering me with such interesting puzzles.....

If you look at the top of include/linux/hash.h  you will see a very
helpful comment:

/*
 * Knuth recommends primes in approximately golden ratio to the maximum
 * integer representable by a machine word for multiplicative hashing.
 * Chuck Lever verified the effectiveness of this technique:
 * http://www.citi.umich.edu/techreports/reports/citi-tr-00-1.pdf
 *
 * These primes are chosen to be bit-sparse, that is operations on
 * them can use shifts and additions instead of multiplications for
 * machines where multiplications are slow.
 */

I think there is a tension between the 'close to golden ratio'
requirement and the 'bit-sparse' requirement.  The prime chosen for
64bit work is 
#define GOLDEN_RATIO_PRIME 0x9e37fffffffc0001UL
which is nicely bit-sparse, bit is a long way from the golden ratio
which is 0x9E3779B97F4A7C15
The closest prime to this is 
         0x9E3779B97F4A7C55
which is not particularly bit-sparse, but produces much better
distribution of hashes for IP addresses.

In fact, I wouldn't be at all surprised if 'bit-sparse' tends to have a
directly negative effect on hash quality when the variations in the
input line up with the sparse bits (so to speak).

Now I don't really know how much of an issue this 'bit sparseness' is
for speed, and how much cost it would be to just change those
shift/adds into a multiply.  But there is something definitely wrong
with hash_long on 64bit, and I suspect it could affect more than just
IP addresses.

William, Chunk:  Any suggestions on whether a straight multiply would
be too expensive, or what else we could do to make hash_long both fast
and effective?
Maybe we should just have 'hash32' and write 'hash64' as 
  hash32(x ^ hash32(x>>32));

But then the current hash_long for 32bit doesn't work brilliantly when
the variation is in the 3rd byte (i.e. within the mask 0x0f00).

I wonder if http://burtleburtle.net/bob/hash/evahash.html might end up
being better ... would need to do some serious tests.

Help?

NeilBrown

btw, I did testing with the following little program
called like:
  for i in 0 8 16 24 ; do ./hashtest 0x00007659 $i 256; done
                                       ^^^^^^^ random number.

#include <stdio.h>

unsigned hash(unsigned long val)
{
	unsigned long long hash = val;
	/* hash *=  0x9e37fffffffc0001ULL;*/
	hash *= 11400714819323198549ULL;
	return (hash >> (64-8)) & 255;
}

main(int argc, char*argv[])
{
	unsigned long start = strtoul(argv[1], 0);
	int shift = strtoul(argv[2], 0);
	int count = strtoul(argv[3], 0);
	int max = 0;

	int cnt[256];
	int i;
	
	for (i=0; i<256; i++)
		cnt[i] = 0;

	while (count) {
		cnt[hash(start)] ++;
		start += (1<<shift);
		count--;
	}
	count = 0;
	for (i=0; i<256; i++) {
		if (cnt[i])
			count++;
		if (cnt[i] > max)
			max = cnt[i];
	}
	printf("count %d/256 max %d\n", count, max);
}



-------------------------------------------------------
This SF.net email is sponsored by: Splunk Inc. Do you grep through log files
for problems?  Stop!  Download the new AJAX search engine that makes
searching your log files as easy as surfing the  web.  DOWNLOAD SPLUNK!
http://ads.osdn.com/?ad_id=7637&alloc_id=16865&op=click
_______________________________________________
NFS maillist  -  NFS@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/nfs

Re: An interesting performance thing ?

[Chuck Lever]

[-- Attachment #1: Type: text/plain, Size: 614 bytes --]

Neil Brown wrote:
> William, Chunk:  Any suggestions on whether a straight multiply would
> be too expensive, or what else we could do to make hash_long both fast
> and effective?

my original proposal was a hash function which computed the index by a 
single multiplication with a large prime number.  i was told that 
multiplication was too expensive, especially on older platforms, so the 
existing computation took its place.  but i don't think anyone ever did 
any real studies.  i can't imagine that multiplication would be worse 
than extra elements in a hash chain, especially on modern CPU architectures.

[-- Attachment #2: cel.vcf --]
[-- Type: text/x-vcard, Size: 253 bytes --]

begin:vcard
fn:Chuck Lever
n:Lever;Chuck
org:Network Appliance, Incorporated;Open Source NFS Client Engineering
email;internet:cel@citi.umich.edu
title:Member of Technical Staff
x-mozilla-html:FALSE
url:http://www.monkey.org/~cel
version:2.1
end:vcard

Re: An interesting performance thing ?

[Iozone]

Neil,

    Post at bottom:

----- Original Message ----- 
From: "Neil Brown" <neilb@suse.de>
To: "Iozone" <capps@iozone.org>
Cc: <wli@holomorphy.com>; "Chuck Lever" <cel@citi.umich.edu>; 
<nfs@lists.sourceforge.net>
Sent: Wednesday, December 14, 2005 4:26 PM
Subject: Re: An interesting performance thing ?


> On Wednesday December 14, capps@iozone.org wrote:
>> Neil,
>
> Hi, Don,
>
>>
>>     I think I have discovered an interesting performance anomaly.
>
> Indeed you have, thanks.
>
>>
>>     In the svcauth code there are places that do:
>>
>>        hash_long((unsigned long)item->m_addr.s_addr, IP_HASHBITS);
>>
>>     Ok... That seems reasonable, but then again...maybe not....
>
> No, perfectly reasonable.  I don't write "maybe reasonable" code.  It
> is either perfect, or rubbish :-)
>
>>
>>     I believe that s_addr is an IP address in Network Neutral format.
>>      (Big Endian)
>>
>>     So... When one is on a Little Endian system, the hash_long
>>     function gets handed a Big Endian value as a long, and
>>     later, via the magic of being a Little Endian system,
>>     gets byte swapped.
>>
>>     Step 1. 192.168.1.2 becomes 2.1.168.192 (byte swap)
>>
>>     Step 2.  The 32 bit IP address becomes a 64 bit long when
>>                  this code is compiled and run on an Opteron, or
>>                  an IA-64 system.
>>                  2.1.168.192 -> 0.0.0.0.2.1.168.192
>>     Step 3. Call the hash_long() and get back a hash value
>>                 that is IP_HASHBITS (8) in size.
>>
>>     You'll notice that the hash distribution is not nearly as
>>     good as one might believe.  If one would have done:
>>
>>         hash_long( inet_lnaof(item->m_addr.s_addr)),IP_HASHBITS)
>>
>>     Then the hash_long function would have done a nice job.
>
> True, but irrelevant.
> hash_long(X, 8) will take the top 8 bits of the result.  So pushing
> the noisy bits into the low order bits should have no significant
> effect.
> The fact that it does suggests that hash_long is broken.
>
> I wonder if I blame William or Chuck?  Maybe I'll just blame both.
> After all it is Christmas time and we should share the good will
> around :-)
>
>>
>> ---------
>>
>>     Now you say "Ok that's not too cool, but why is this really
>>     important ?"
>
> Oh, no.  I can easily see that it is important.  And I agree it is
> seriously uncool (like the weather down here is oz (aka .au)).
>
>
>>
>>         Well, it turns out that the RedHat EL 4 release has some issues
>>     with the locking around the buckets that this hash is being
>>     used to index into, and with the distribution being so not... it
>>     leads to a lock race, followed by a kernel dereference of null,
>>     followed shortly by angry phone calls.... True, the race needs
>>     to be fixed, but it sure would be nice if the pressure were a
>>     tad lower on the lock. It would greatly reduce the probability
>>     of the panic, and also improve the performance (scaling) of
>>     the system, if a few more buckets were used :-)
>
> What mainline kernel is RedHat EL 4 based on?
> I think I know the race you mean.... Funny how one writes buggy code,
> then fixes it, then finds it still existing in "enterprise" kernels
> months later. (SLES only gets it fixed in 9SP3).
>
>>
>>     I've talked this over with Charles, and Bruce, and they pointed
>>     me in your direction ...
>
> Go back to Charles and tell him I sent you :-)
>
>>
>>     How would you prefer to proceed ?
>>
>>         A. It's your code, and you would prefer to tinker without
>>             some bozo adding his two bits.
>
> Nonono, bozo bits are worth their weight in gold (sometimes).
>
>>
>>         B. You're way too busy to go after this, and would
>>             welcome a diff -u patch.
>
> In general, yes.  In this case, the patch would have been wrong.
>
>>
>>         C. You'll scratch your head, think about it, and get back
>>             after morning coffee :-)
>
> I'm a tea drinker, so that wouldn't work.
>
>>
>>         D. It will only take a few seconds to add the
>>                 inet_lnaof( ) to the offending lines, and it will be
>>                 done before you can say Jack Flash :-)
>
> It was 'Jack Robinson' in my day - no idea why.
>
>>
>>         E. Go away, you're bothering me :-)
>>
>
> Yeh, stop bothering me with such interesting puzzles.....
>
> If you look at the top of include/linux/hash.h  you will see a very
> helpful comment:
>
> /*
> * Knuth recommends primes in approximately golden ratio to the maximum
> * integer representable by a machine word for multiplicative hashing.
> * Chuck Lever verified the effectiveness of this technique:
> * http://www.citi.umich.edu/techreports/reports/citi-tr-00-1.pdf
> *
> * These primes are chosen to be bit-sparse, that is operations on
> * them can use shifts and additions instead of multiplications for
> * machines where multiplications are slow.
> */
>
> I think there is a tension between the 'close to golden ratio'
> requirement and the 'bit-sparse' requirement.  The prime chosen for
> 64bit work is
> #define GOLDEN_RATIO_PRIME 0x9e37fffffffc0001UL
> which is nicely bit-sparse, bit is a long way from the golden ratio
> which is 0x9E3779B97F4A7C15
> The closest prime to this is
>         0x9E3779B97F4A7C55
> which is not particularly bit-sparse, but produces much better
> distribution of hashes for IP addresses.
>
> In fact, I wouldn't be at all surprised if 'bit-sparse' tends to have a
> directly negative effect on hash quality when the variations in the
> input line up with the sparse bits (so to speak).
>
> Now I don't really know how much of an issue this 'bit sparseness' is
> for speed, and how much cost it would be to just change those
> shift/adds into a multiply.  But there is something definitely wrong
> with hash_long on 64bit, and I suspect it could affect more than just
> IP addresses.
>
> William, Chunk:  Any suggestions on whether a straight multiply would
> be too expensive, or what else we could do to make hash_long both fast
> and effective?
> Maybe we should just have 'hash32' and write 'hash64' as
>  hash32(x ^ hash32(x>>32));
>
> But then the current hash_long for 32bit doesn't work brilliantly when
> the variation is in the 3rd byte (i.e. within the mask 0x0f00).
>
> I wonder if http://burtleburtle.net/bob/hash/evahash.html might end up
> being better ... would need to do some serious tests.
>
> Help?
>
> NeilBrown
>
> btw, I did testing with the following little program
> called like:
>  for i in 0 8 16 24 ; do ./hashtest 0x00007659 $i 256; done
>                                       ^^^^^^^ random number.
>
> #include <stdio.h>
>
> unsigned hash(unsigned long val)
> {
> unsigned long long hash = val;
> /* hash *=  0x9e37fffffffc0001ULL;*/
> hash *= 11400714819323198549ULL;
> return (hash >> (64-8)) & 255;
> }
>
> main(int argc, char*argv[])
> {
> unsigned long start = strtoul(argv[1], 0);
> int shift = strtoul(argv[2], 0);
> int count = strtoul(argv[3], 0);
> int max = 0;
>
> int cnt[256];
> int i;
>
> for (i=0; i<256; i++)
> cnt[i] = 0;
>
> while (count) {
> cnt[hash(start)] ++;
> start += (1<<shift);
> count--;
> }
> count = 0;
> for (i=0; i<256; i++) {
> if (cnt[i])
> count++;
> if (cnt[i] > max)
> max = cnt[i];
> }
> printf("count %d/256 max %d\n", count, max);
> }
>
>

    In my tests I tried several IP addresses, and watched the resultant 
hash.
    I then tried the same experiment with inet_lnaof(x) and watched
    the resultant hash. In both cases on a 64 bit Little Endian system.

    Test results:

Testing byte 4 (least significant)
Input: 192.168.1.0 Hash-> 3e
Input: 192.168.1.0 Hash-with-inet_lnaof() -> 57
Input: 192.168.1.1 Hash-> 3e
Input: 192.168.1.1 Hash-with-inet_lnaof() -> c9
Input: 192.168.1.2 Hash-> 3e
Input: 192.168.1.2 Hash-with-inet_lnaof() -> 6b
Input: 192.168.1.3 Hash-> 3e
Input: 192.168.1.3 Hash-with-inet_lnaof() -> 8d
Input: 192.168.1.4 Hash-> 3e
Input: 192.168.1.4 Hash-with-inet_lnaof() -> 2f
Input: 192.168.1.5 Hash-> 3e
Input: 192.168.1.5 Hash-with-inet_lnaof() -> 40
Input: 192.168.1.6 Hash-> 3e
Input: 192.168.1.6 Hash-with-inet_lnaof() -> e2
Input: 192.168.1.7 Hash-> 3e
Input: 192.168.1.7 Hash-with-inet_lnaof() -> 4

    It looks like simply adding the hash_long(inet_lnaof(s_sddr),8)
    seems to do a better job than hash_long(s_addr,8) and is a
    pretty simple change.
    (low risk).

    I'll leave the discussion on GOLDEN to others, and
    go with simple/easy/works.  :-)

Enjoy,
Don Capps





-------------------------------------------------------
This SF.net email is sponsored by: Splunk Inc. Do you grep through log files
for problems?  Stop!  Download the new AJAX search engine that makes
searching your log files as easy as surfing the  web.  DOWNLOAD SPLUNK!
http://ads.osdn.com/?ad_id=7637&alloc_id=16865&op=click
_______________________________________________
NFS maillist  -  NFS@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/nfs

Re: An interesting performance thing ?

[Iozone]

----- Original Message ----- 
From: "Chuck Lever" <cel@citi.umich.edu>
To: "Neil Brown" <neilb@suse.de>
Cc: "Iozone" <capps@iozone.org>; <wli@holomorphy.com>; 
<nfs@lists.sourceforge.net>
Sent: Wednesday, December 14, 2005 4:46 PM
Subject: Re: An interesting performance thing ?


> Neil Brown wrote:
>> William, Chunk:  Any suggestions on whether a straight multiply would
>> be too expensive, or what else we could do to make hash_long both fast
>> and effective?
>
> my original proposal was a hash function which computed the index by a
> single multiplication with a large prime number.  i was told that
> multiplication was too expensive, especially on older platforms, so the
> existing computation took its place.  but i don't think anyone ever did
> any real studies.  i can't imagine that multiplication would be worse
> than extra elements in a hash chain, especially on modern CPU 
> architectures.
>

Neil,

    In a perfect world, a perfect hash would be ideal...but,

    1. It is fairly normal practice for code to call inet_lnaof( in_addr )
        so that the host native format is used by the host. Just
        grabbing s_addr is a bit odd.
    2. Simply adding the inet_lnaof( in_addr ) would do nice
        things with the existing hash algorithm, for CDIR allocated
        monotonically incremented IP address spaces.
    3. Gosh, it seems like a pretty easy and safe change.

        I think I understand Neil's position. If one hands a 64 bit
    opaque object to a hash function, it should do a better
    job of distribution, so who cares if it was in the native
    format or not.  Ok..  But, given 1->3 above, it seems
    like there might be a lower risk, less controversial, solution
    for the immediate future, and permit folks to do a study
    while the world goes on its happy way :-)

    Thanks again for being kind to new kid tossing
    spitballs :-)

Enjoy,
Don Capps





-------------------------------------------------------
This SF.net email is sponsored by: Splunk Inc. Do you grep through log files
for problems?  Stop!  Download the new AJAX search engine that makes
searching your log files as easy as surfing the  web.  DOWNLOAD SPLUNK!
http://ads.osdn.com/?ad_id=7637&alloc_id=16865&op=click
_______________________________________________
NFS maillist  -  NFS@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/nfs

Re: An interesting performance thing ?

[Neil Brown]

On Wednesday December 14, capps@iozone.org wrote:
> 
> Neil,
> 
>     In a perfect world, a perfect hash would be ideal...but,
> 
>     1. It is fairly normal practice for code to call inet_lnaof( in_addr )
>         so that the host native format is used by the host. Just
>         grabbing s_addr is a bit odd.
>     2. Simply adding the inet_lnaof( in_addr ) would do nice
>         things with the existing hash algorithm, for CDIR allocated
>         monotonically incremented IP address spaces.
>     3. Gosh, it seems like a pretty easy and safe change.
> 
>         I think I understand Neil's position. If one hands a 64 bit
>     opaque object to a hash function, it should do a better
>     job of distribution, so who cares if it was in the native
>     format or not.  Ok..  But, given 1->3 above, it seems
>     like there might be a lower risk, less controversial, solution
>     for the immediate future, and permit folks to do a study
>     while the world goes on its happy way :-)

The trouble is that just because inet_lnaof makes the final hash
better for your mix of clients, that doesn't mean it won't make it
worse for someone else.  I admit that I cannot provide a like sample
mix of clients what would be worse with inet_lnaof, but that doesn't
mean they don't exist.

If the only symptom that has been identified is that it makes a
locking race easier to hit, then the obvious first solution is to fix
that locking race, and I believe such a fix is available.

If anyone were experiencing a measurable slowness due to the bad hash,
then I would have not problem suggesting they try the inet_lnaof
solution.

But I don't propose submitting it to Linus because - useful as it is -
it is simply wrong.
We need to fix that hash function, and this clear problem is a good
motivation to do that.

Or to put it another way, I don't think it is clear that we *need* a
solution for the immediate future.

NeilBrown




-------------------------------------------------------
This SF.net email is sponsored by: Splunk Inc. Do you grep through log files
for problems?  Stop!  Download the new AJAX search engine that makes
searching your log files as easy as surfing the  web.  DOWNLOAD SPLUNK!
http://ads.osdn.com/?ad_id=7637&alloc_id=16865&op=click
_______________________________________________
NFS maillist  -  NFS@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/nfs

Re: Re: An interesting performance thing ?

[Chuck Lever]

[-- Attachment #1: Type: text/plain, Size: 1255 bytes --]

Neil Brown wrote:
> The trouble is that just because inet_lnaof makes the final hash
> better for your mix of clients, that doesn't mean it won't make it
> worse for someone else.  I admit that I cannot provide a like sample
> mix of clients what would be worse with inet_lnaof, but that doesn't
> mean they don't exist.
> 
> If the only symptom that has been identified is that it makes a
> locking race easier to hit, then the obvious first solution is to fix
> that locking race, and I believe such a fix is available.
> 
> If anyone were experiencing a measurable slowness due to the bad hash,
> then I would have not problem suggesting they try the inet_lnaof
> solution.
> 
> But I don't propose submitting it to Linus because - useful as it is -
> it is simply wrong.
> We need to fix that hash function, and this clear problem is a good
> motivation to do that.
> 
> Or to put it another way, I don't think it is clear that we *need* a
> solution for the immediate future.

we might also think a little bit of the future (IPv6).

IPv6 addresses are larger than IPv4 addresses, so they will need their 
own hash function, *or* we will have to design a reasonable hash 
function for variably-sized addresses now, which seems like a harder 
problem.

[-- Attachment #2: cel.vcf --]
[-- Type: text/x-vcard, Size: 451 bytes --]

begin:vcard
fn:Chuck Lever
n:Lever;Charles
org:Network Appliance, Incorporated;Open Source NFS Client Development
adr:535 West William Street, Suite 3100;;Center for Information Technology Integration;Ann Arbor;MI;48103-4943;USA
email;internet:cel@citi.umich.edu
title:Member of Technical Staff
tel;work:+1 734 763-4415
tel;fax:+1 734 763 4434
tel;home:+1 734 668-1089
x-mozilla-html:FALSE
url:http://troy.citi.umich.edu/u/cel/
version:2.1
end:vcard

Re: Re: An interesting performance thing ?

[Neil Brown]

On Wednesday December 14, cel@citi.umich.edu wrote:
> 
> we might also think a little bit of the future (IPv6).
> 
> IPv6 addresses are larger than IPv4 addresses, so they will need their 
> own hash function, *or* we will have to design a reasonable hash 
> function for variably-sized addresses now, which seems like a harder 
> problem.

A hash for a variable sized value isn't really a problem.
Just break it into small bits and compose the hashes, similar
to what hash_str in include/linux/sunrpc/svcauth.h does.

A good question is:  Do we ever need more than 4 bytes of hash
value?
We wouldn't for hash tables, but they may well be other uses of
hashes.

If we don't then a function that maps and arbitrary mem buffer into
a u32 would be suitable general for all uses or all architectures,
though some special cases like 4byte and 8byte inputs could probably
be optimised sensibly.

 I suspect the function given in
   http://burtleburtle.net/bob/hash/evahash.html

my really be a good choice.  
It does about 40 add/subtracts for each 4bytes, but seems to have good
properties.
(Hmm.. that is probably similar to a constant 32bit multiply, but
 maybe the current code with a better non-sparse prime is just as
 good).

NeilBrown



-------------------------------------------------------
This SF.net email is sponsored by: Splunk Inc. Do you grep through log files
for problems?  Stop!  Download the new AJAX search engine that makes
searching your log files as easy as surfing the  web.  DOWNLOAD SPLUNK!
http://ads.osdn.com/?ad_id=7637&alloc_id=16865&op=click
_______________________________________________
NFS maillist  -  NFS@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/nfs

Re: Re: An interesting performance thing ?

[Chuck Lever]

[-- Attachment #1: Type: text/plain, Size: 894 bytes --]

Neil Brown wrote:
> A good question is:  Do we ever need more than 4 bytes of hash
> value?
> We wouldn't for hash tables, but they may well be other uses of
> hashes.
> 
> If we don't then a function that maps and arbitrary mem buffer into
> a u32 would be suitable general for all uses or all architectures,
> though some special cases like 4byte and 8byte inputs could probably
> be optimised sensibly.
> 
>  I suspect the function given in
>    http://burtleburtle.net/bob/hash/evahash.html
> 
> my really be a good choice.  
> It does about 40 add/subtracts for each 4bytes, but seems to have good
> properties.
> (Hmm.. that is probably similar to a constant 32bit multiply, but
>  maybe the current code with a better non-sparse prime is just as
>  good).

i haven't looked at how the network layer handles this issue, but it 
might be a good start if there is something there to reuse.

[-- Attachment #2: cel.vcf --]
[-- Type: text/x-vcard, Size: 451 bytes --]

begin:vcard
fn:Chuck Lever
n:Lever;Charles
org:Network Appliance, Incorporated;Open Source NFS Client Development
adr:535 West William Street, Suite 3100;;Center for Information Technology Integration;Ann Arbor;MI;48103-4943;USA
email;internet:cel@citi.umich.edu
title:Member of Technical Staff
tel;work:+1 734 763-4415
tel;fax:+1 734 763 4434
tel;home:+1 734 668-1089
x-mozilla-html:FALSE
url:http://troy.citi.umich.edu/u/cel/
version:2.1
end:vcard

Re: An interesting performance thing ?

[J. Bruce Fields]

On Wed, Dec 14, 2005 at 12:22:38PM -0600, Iozone wrote:
>     Then the hash_long function would have done a nice job.  Since
>     one is not converting the network neutral IP address into a 
>     host binary format, here is an example of the hash distribution
>     that, I believe via experimentation, is currently being seen on 
>     Little Endian 64 Bit systems....

A little bit of fiddling about with pencil and paper shows what's
happening:  suppose longs are 64 bits and let x be a long.  Then
hash_long operates on x by multiplying it by

	 1 - 2^18 - 2^51 + 2^54 - 2^57 + 2^61 + 2^63

and then taking the high bits.

You can think of that as adding and subtracting a bunch of left-shifts.
Note that the last four terms are all shifts by at least 51 bits, so
wipe out all but the lowest 13 bits.  So if those low 13 bits are all
constant, then the only variation is from multiplication by (1 - 2^18).
But if the input is small (say the top 32 bits are all zero...) then
multiplying by (1 - 2^18) doesn't affect the high bits of the output at
all.

So in our case, where the 32 high bits are zero and we're only asking
for the top 8 bits, it looks like all but the bottom 13 bits of x (the
top 13 bits of the IP address) are ignored.

--b.


-------------------------------------------------------
This SF.net email is sponsored by: Splunk Inc. Do you grep through log files
for problems?  Stop!  Download the new AJAX search engine that makes
searching your log files as easy as surfing the  web.  DOWNLOAD SPLUNK!
http://ads.osdn.com/?ad_id=7637&alloc_id=16865&op=click
_______________________________________________
NFS maillist  -  NFS@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/nfs

Re: Re: An interesting performance thing ?

[J. Bruce Fields]

On Thu, Dec 15, 2005 at 11:02:22AM +1100, Neil Brown wrote:
> The trouble is that just because inet_lnaof makes the final hash
> better for your mix of clients, that doesn't mean it won't make it
> worse for someone else.  I admit that I cannot provide a like sample
> mix of clients what would be worse with inet_lnaof, but that doesn't
> mean they don't exist.

It strikes me as extremely unlikely that any set of clients would have
good variation in the *high* 13 bits of their IP addresses.

In fact, in the common case the high 13 bits are probably completely
constant.

So for these architectures, the ip address lookup is probably usually
degenerating to a linear search.  Since that lookup has to be performed
on every rpc call, this is likely to be painful.

> But I don't propose submitting it to Linus because - useful as it is -
> it is simply wrong.  We need to fix that hash function, and this clear
> problem is a good motivation to do that.

It'd be worth checking whether other callers may be giving hash_long
32-bit inputs, since they might have similar problems.

--b.


-------------------------------------------------------
This SF.net email is sponsored by: Splunk Inc. Do you grep through log files
for problems?  Stop!  Download the new AJAX search engine that makes
searching your log files as easy as surfing the  web.  DOWNLOAD SPLUNK!
http://ads.osdn.com/?ad_id=7637&alloc_id=16865&op=click
_______________________________________________
NFS maillist  -  NFS@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/nfs

Re: Re: An interesting performance thing ?

[Iozone]

----- Original Message ----- 
From: "J. Bruce Fields" <bfields@fieldses.org>
To: "Neil Brown" <neilb@suse.de>
Cc: "Iozone" <capps@iozone.org>; <cel@citi.umich.edu>; <wli@holomorphy.com>; 
<nfs@lists.sourceforge.net>
Sent: Wednesday, December 14, 2005 8:32 PM
Subject: Re: [NFS] Re: An interesting performance thing ?


> On Thu, Dec 15, 2005 at 11:02:22AM +1100, Neil Brown wrote:
>> The trouble is that just because inet_lnaof makes the final hash
>> better for your mix of clients, that doesn't mean it won't make it
>> worse for someone else.  I admit that I cannot provide a like sample
>> mix of clients what would be worse with inet_lnaof, but that doesn't
>> mean they don't exist.
>
> It strikes me as extremely unlikely that any set of clients would have
> good variation in the *high* 13 bits of their IP addresses.
>
> In fact, in the common case the high 13 bits are probably completely
> constant.
>
> So for these architectures, the ip address lookup is probably usually
> degenerating to a linear search.  Since that lookup has to be performed
> on every rpc call, this is likely to be painful.
>
>> But I don't propose submitting it to Linus because - useful as it is -
>> it is simply wrong.  We need to fix that hash function, and this clear
>> problem is a good motivation to do that.
>
> It'd be worth checking whether other callers may be giving hash_long
> 32-bit inputs, since they might have similar problems.
>
> --b.
>

Bruce,

        One of the interesting things I noticed is that the general
    purpose hash_long() function may not be as optimal
    as a more focused hash_IP_addr() function might be,
    even if GOLDEN were GOLDEN :-) And, trying
    to smash 128 bit IPV6 addresses into a 8 bit hash
    value, that is somehow uniformly distributed, well,
    that's going to be quite a neat trick, and making it
    work for 32 bit, 64, and 128 bit objects, with uniform
    distribution over a variable number of output bits,
    is approaching magical.

        If one knows that the frequency of change of the
    bytes in the value, to be hashed, then a more targeted hash
    algorithm might take advantage of this pre-knowledge
    to contribute to the uniformity of the output hash.

    With respect to IPV4 addresses:

        aa.bb.cc.dd

    where dd changes the fastest, then cc, then bb, then aa.

    Thus the bits in dd are more interesting than the bits in
    cc, and the bits in cc are more interesting than in bb,
    and the bits in aa are pretty much static.
        (Not many NFS servers have clients that span
         large numbers of class "A networks :-)

    Hash_long(), being general purpose, could not take
    advantage of this, but something else might ?

    Bruce:  You noticed that my suggestion of inet_lnaof()
    didn't cure the hash_long limitations, just moved the
    frequently modified bits into an active region of the
    hash algorithm :-) Sort of like tricking hash_long() into
    a performing like a more targeted hash, just for IPV4
    address ranges that an NFS server would be most likely
    to see....... :-)

    You did raise an interesting question...Are other 32 bit values
    being handed to hash_long() ? Good question. Wonder
    if these callers also have particular needs that might
    be addressed by a targeted hash algorithm ? Hmmmmm...

Enjoy,
Don Capps




-------------------------------------------------------
This SF.net email is sponsored by: Splunk Inc. Do you grep through log files
for problems?  Stop!  Download the new AJAX search engine that makes
searching your log files as easy as surfing the  web.  DOWNLOAD SPLUNK!
http://ads.osdn.com/?ad_id=7637&alloc_id=16865&op=click
_______________________________________________
NFS maillist  -  NFS@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/nfs

Re: Re: An interesting performance thing ?

[J. Bruce Fields]

On Wed, Dec 14, 2005 at 10:51:40PM -0600, Iozone wrote:
>        One of the interesting things I noticed is that the general
>    purpose hash_long() function may not be as optimal
>    as a more focused hash_IP_addr() function might be,
>    even if GOLDEN were GOLDEN :-) And, trying
>    to smash 128 bit IPV6 addresses into a 8 bit hash
>    value, that is somehow uniformly distributed, well,
>    that's going to be quite a neat trick, and making it
>    work for 32 bit, 64, and 128 bit objects, with uniform
>    distribution over a variable number of output bits,
>    is approaching magical.

I'm not so pessimistic, but I'm also not expert enough about hash
functions to know how much magic is reasonable to expect out of a good
one.  Time to pull out Knuth, maybe.

There might also be an argument for experimenting with different data
structures.  I'd expect high temporal locality--in typical situations a
server with lots of clients may have only a few that are active at a
particular time--so one of those balanced trees that migrates recently
looked-up items to the top might be helpful.

Aside from seeing the race condition triggered, have you done any
profiling to make sure this is actually a big problem, even with the
current worst-case linear-search behaviour?

--b.


-------------------------------------------------------
This SF.net email is sponsored by: Splunk Inc. Do you grep through log files
for problems?  Stop!  Download the new AJAX search engine that makes
searching your log files as easy as surfing the  web.  DOWNLOAD SPLUNK!
http://ads.osdn.com/?ad_id=7637&alloc_id=16865&op=click
_______________________________________________
NFS maillist  -  NFS@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/nfs

Re: Re: An interesting performance thing ?

[Iozone]

----- Original Message ----- 
From: "J. Bruce Fields" <bfields@fieldses.org>
To: "Iozone" <capps@iozone.org>
Cc: "Neil Brown" <neilb@suse.de>; <cel@citi.umich.edu>; 
<wli@holomorphy.com>; <nfs@lists.sourceforge.net>
Sent: Thursday, December 15, 2005 8:49 AM
Subject: Re: [NFS] Re: An interesting performance thing ?


> On Wed, Dec 14, 2005 at 10:51:40PM -0600, Iozone wrote:
>>        One of the interesting things I noticed is that the general
>>    purpose hash_long() function may not be as optimal
>>    as a more focused hash_IP_addr() function might be,
>>    even if GOLDEN were GOLDEN :-) And, trying
>>    to smash 128 bit IPV6 addresses into a 8 bit hash
>>    value, that is somehow uniformly distributed, well,
>>    that's going to be quite a neat trick, and making it
>>    work for 32 bit, 64, and 128 bit objects, with uniform
>>    distribution over a variable number of output bits,
>>    is approaching magical.
>
> I'm not so pessimistic, but I'm also not expert enough about hash
> functions to know how much magic is reasonable to expect out of a good
> one.  Time to pull out Knuth, maybe.
>
> There might also be an argument for experimenting with different data
> structures.  I'd expect high temporal locality--in typical situations a
> server with lots of clients may have only a few that are active at a
> particular time--so one of those balanced trees that migrates recently
> looked-up items to the top might be helpful.
>
> Aside from seeing the race condition triggered, have you done any
> profiling to make sure this is actually a big problem, even with the
> current worst-case linear-search behaviour?
>
> --b.
>

Bruce,

        I have not done a comprehensive profile analysis, but
    have some data I can share.

        At the time when the race caused the system to crash,
    there were 47 NFS clients currently all stacked up
    on one queue. No other queues had any items due
    to the fact that the hash_long function had placed
    all clients on a single queue.
        With the current behavior of hash_long, one
    can reasonably expect queue depths of 127 items
    per queue, (see earlier post demonstrating the hash distribution
    over a block of IP addresses where low order byte is
    monotonimically incremented) and very few queues to be
    active.
        With IP_HASHBITS = 8, there were 256 queues,
    but only one was active. If the hash distribution were
    uniform, then the queue depth could have been 1 (one)
    but instead is a linear search of a relatively large number
    of items.

    Does that help ?

Enjoy,
Don Capps


 




-------------------------------------------------------
This SF.net email is sponsored by: Splunk Inc. Do you grep through log files
for problems?  Stop!  Download the new AJAX search engine that makes
searching your log files as easy as surfing the  web.  DOWNLOAD SPLUNK!
http://ads.osdn.com/?ad_id=7637&alloc_id=16865&op=click
_______________________________________________
NFS maillist  -  NFS@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/nfs

Re: Re: An interesting performance thing ?

[J. Bruce Fields]

On Thu, Dec 15, 2005 at 09:36:37AM -0600, Iozone wrote:
>        With IP_HASHBITS = 8, there were 256 queues,
>    but only one was active. If the hash distribution were
>    uniform, then the queue depth could have been 1 (one)
>    but instead is a linear search of a relatively large number
>    of items.
> 
>    Does that help ?

I'm mainly curious how much effort it's worth expending on optimizing
that hash.  If it turns out that even the current linear search isn't
that expensive, then that's an argument against doing any more
optimizing (beyond just fixing the current obvious problem).

So maybe playing with oprofile or something would help answer my
question.

--b.


-------------------------------------------------------
This SF.net email is sponsored by: Splunk Inc. Do you grep through log files
for problems?  Stop!  Download the new AJAX search engine that makes
searching your log files as easy as surfing the  web.  DOWNLOAD SPLUNK!
http://ads.osdn.com/?ad_id=7637&alloc_id=16865&op=click
_______________________________________________
NFS maillist  -  NFS@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/nfs

Re: Re: An interesting performance thing ?

[Iozone]

----- Original Message ----- 
From: "J. Bruce Fields" <bfields@fieldses.org>
To: "Iozone" <capps@iozone.org>
Cc: "Neil Brown" <neilb@suse.de>; <cel@citi.umich.edu>; 
<wli@holomorphy.com>; <nfs@lists.sourceforge.net>
Sent: Thursday, December 15, 2005 10:14 AM
Subject: Re: [NFS] Re: An interesting performance thing ?


> On Thu, Dec 15, 2005 at 09:36:37AM -0600, Iozone wrote:
>>        With IP_HASHBITS = 8, there were 256 queues,
>>    but only one was active. If the hash distribution were
>>    uniform, then the queue depth could have been 1 (one)
>>    but instead is a linear search of a relatively large number
>>    of items.
>>
>>    Does that help ?
>
> I'm mainly curious how much effort it's worth expending on optimizing
> that hash.  If it turns out that even the current linear search isn't
> that expensive, then that's an argument against doing any more
> optimizing (beyond just fixing the current obvious problem).
>
> So maybe playing with oprofile or something would help answer my
> question.
>
> --b.
>
Bruce,

        I'm still working on trying to track down the patch to
    fix RedHat EL 4  (2.6.9-11) so that it will not panic.
    Until I get that patch located and installed, the profiling
    may not be very successful :-(

    It's a good idea, I'm just not able to grant your wish
    at this point in time. Please try your wish again later :-)
    ( EAGAIN ? :-)

Enjoy,
Don Capps




-------------------------------------------------------
This SF.net email is sponsored by: Splunk Inc. Do you grep through log files
for problems?  Stop!  Download the new AJAX search engine that makes
searching your log files as easy as surfing the  web.  DOWNLOAD SPLUNK!
http://ads.osdn.com/?ad_id=7637&alloc_id=16865&op=click
_______________________________________________
NFS maillist  -  NFS@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/nfs

Re: Re: An interesting performance thing ?

[J. Bruce Fields]

On Thu, Dec 15, 2005 at 10:41:19AM -0600, Iozone wrote:
>        I'm still working on trying to track down the patch to
>    fix RedHat EL 4  (2.6.9-11) so that it will not panic.
>    Until I get that patch located and installed, the profiling
>    may not be very successful :-(

OK!

I think I'd start by looking through patches that touched
include/linux/sunrpc/cache.h:

http://kernel.org/git/?p=linux/kernel/git/torvalds/old-2.6-bkcvs.git;a=history;h=9839690102056c6515cff426221522b73eb1a94d;f=include/linux/sunrpc/cache.h

or net/sunrpc/cache.c:

http://kernel.org/git/?p=linux/kernel/git/torvalds/old-2.6-bkcvs.git;a=history;h=9839690102056c6515cff426221522b73eb1a94d;f=net/sunrpc/cache.c

The topmost commit there looks like a likely candidate.

--b.


-------------------------------------------------------
This SF.net email is sponsored by: Splunk Inc. Do you grep through log files
for problems?  Stop!  Download the new AJAX search engine that makes
searching your log files as easy as surfing the  web.  DOWNLOAD SPLUNK!
http://ads.osdn.com/?ad_id=7637&alloc_id=16865&op=click
_______________________________________________
NFS maillist  -  NFS@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/nfs

Re: Re: An interesting performance thing ?

[Neil Brown]

On Thursday December 15, bfields@fieldses.org wrote:
> I'm mainly curious how much effort it's worth expending on optimizing
> that hash.  If it turns out that even the current linear search isn't
> that expensive, then that's an argument against doing any more
> optimizing (beyond just fixing the current obvious problem).
> 

Thinking a bit more about this, a very suitable hash to produce 8 bits
from an IPv4 address would be to xor all the bytes together:
       hash = addr ^ (addr>>16);
       hash = (hash ^ (hash>>8)) & 0xff;

I think this would have good properties on any natural set of IP
addresses.

I'd still prefer to use a good general purpose hash function because
it is conceptually simpler.  But when one isn't available....

NeilBrown


-------------------------------------------------------
This SF.net email is sponsored by: Splunk Inc. Do you grep through log files
for problems?  Stop!  Download the new AJAX search engine that makes
searching your log files as easy as surfing the  web.  DOWNLOAD SPLUNK!
http://ads.osdn.com/?ad_id=7637&alloc_id=16865&op=click
_______________________________________________
NFS maillist  -  NFS@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/nfs

Re: Re: An interesting performance thing ?

[Iozone]

----- Original Message ----- 
From: "Neil Brown" <neilb@suse.de>
To: "J. Bruce Fields" <bfields@fieldses.org>
Cc: "Iozone" <capps@iozone.org>; <cel@citi.umich.edu>; <wli@holomorphy.com>; 
<nfs@lists.sourceforge.net>
Sent: Thursday, December 15, 2005 7:25 PM
Subject: Re: [NFS] Re: An interesting performance thing ?


> On Thursday December 15, bfields@fieldses.org wrote:
>> I'm mainly curious how much effort it's worth expending on optimizing
>> that hash.  If it turns out that even the current linear search isn't
>> that expensive, then that's an argument against doing any more
>> optimizing (beyond just fixing the current obvious problem).
>>
>
> Thinking a bit more about this, a very suitable hash to produce 8 bits
> from an IPv4 address would be to xor all the bytes together:
>       hash = addr ^ (addr>>16);
>       hash = (hash ^ (hash>>8)) & 0xff;
>
> I think this would have good properties on any natural set of IP
> addresses.
>
> I'd still prefer to use a good general purpose hash function because
> it is conceptually simpler.  But when one isn't available....
>
> NeilBrown
>

Neil,

        I think we're in phase :-)  I too was thinking of
    something much simpler and faster, that took advantage
    of the pre-knowledge of variably of the input, the
    needed size, and distribution of the hash output.

    This approach has some interesting benefits:

    1) Runs faster, and consumes far fewer CPU cycles.
        Zero multiples, or golden primes, and a bunch fewer
        other instructions.
    2) Does a better distribution than any general purpose hash function.
    3) Can easily be adapted for IPV6
    4) Needs far less testing, than a one fits all model.
    5) Can be implemented quickly, easily, and has low risk
        of affecting un-related subsystems.
    6) Will not need a PHD (strong in number theory) to understand that
        it's actually doing a good job.

        Don't get me wrong, I still see a need for a generalized hash
    algorithm that needs primes, and heavy magic. Its needed for
    nodalization with unpredictable invariant bit pattern inputs (due to 
compiler
    alignments of native data types, and structure alignments, on pointers)
    and other non-predictive input data sets. But with IP addresses, the
    natural distribution does not have the same issues, and can
    be solved much more effectively, and efficiently. As is
    demonstrated so well, by you, above :-)

    Is it too late to place an order for one of these for Christmas ?

Enjoy,
Don Capps

P.S. If you go with your algorithm above, I'll concede the
        need for inet_lnaof(s_addr)  The folding and XORs
        work fine on either native or network neutral formats.
         :-)






-------------------------------------------------------
This SF.net email is sponsored by: Splunk Inc. Do you grep through log files
for problems?  Stop!  Download the new AJAX search engine that makes
searching your log files as easy as surfing the  web.  DOWNLOAD SPLUNK!
http://ads.osdn.com/?ad_id=7637&alloc_id=16865&op=click
_______________________________________________
NFS maillist  -  NFS@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/nfs

Re: Re: An interesting performance thing ?

[Aurélien Charbon]

Chuck Lever wrote:

> we might also think a little bit of the future (IPv6).
>
> IPv6 addresses are larger than IPv4 addresses, so they will need their=20
> own hash function, *or* we will have to design a reasonable hash=20
> function for variably-sized addresses now, which seems like a harder=20
> problem.

For information, in the IPv6 client support, we are currently using the=20
hash_long function by doing a xor operation between the four 32 bit=20
parts or an IPv6 address.

 static inline int ip_map_hash(struct ip_map *item)
 {
 	return hash_str(item->m_class, IP_HASHBITS) ^=20
-		hash_long((unsigned long)item->m_addr.s_addr, IP_HASHBITS);
+		hash_long((unsigned long)(item->m_addr.s6_addr32[0] ^
+			    item->m_addr.s6_addr32[1] ^
+			    item->m_addr.s6_addr32[2] ^
+			    item->m_addr.s6_addr32[3]), IP_HASHBITS);
 }

Regards,

Aur=E9lien



-------------------------------------------------------
This SF.net email is sponsored by: Splunk Inc. Do you grep through log files
for problems?  Stop!  Download the new AJAX search engine that makes
searching your log files as easy as surfing the  web.  DOWNLOAD SPLUNK!
http://ads.osdn.com/?ad_id=7637&alloc_id=16865&op=click
_______________________________________________
NFS maillist  -  NFS@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/nfs

Re: Re: An interesting performance thing ?

[Iozone]

----- Original Message -----=20
=46rom: "Aur=E9lien Charbon" <aurelien.charbon@ext.bull.net>
To: <cel@citi.umich.edu>
Cc: "Neil Brown" <neilb@suse.de>; "Iozone" <capps@iozone.org>;=20
<wli@holomorphy.com>; <nfs@lists.sourceforge.net>
Sent: Friday, December 16, 2005 4:15 AM
Subject: Re: [NFS] Re: An interesting performance thing ?


Chuck Lever wrote:

> we might also think a little bit of the future (IPv6).
>
> IPv6 addresses are larger than IPv4 addresses, so they will need th=
eir own=20
> hash function, *or* we will have to design a reasonable hash functi=
on for=20
> variably-sized addresses now, which seems like a harder problem.

For information, in the IPv6 client support, we are currently using t=
he
hash_long function by doing a xor operation between the four 32 bit
parts or an IPv6 address.

 static inline int ip_map_hash(struct ip_map *item)
 {
  return hash_str(item->m_class, IP_HASHBITS) ^
- hash_long((unsigned long)item->m_addr.s_addr, IP_HASHBITS);
+ hash_long((unsigned long)(item->m_addr.s6_addr32[0] ^
+     item->m_addr.s6_addr32[1] ^
+     item->m_addr.s6_addr32[2] ^
+     item->m_addr.s6_addr32[3]), IP_HASHBITS);
 }

Regards,

Aur=E9lien
-------------

Aur=E9lien,

    Perhaps in the future one might consider using Neil's new
    hash for IP addresses ?  Something like:

 static inline int ip_map_hash(struct ip_map *item)
 {
  return hash_str(item->m_class, IP_HASHBITS) ^
- hash_long((unsigned long)item->m_addr.s_addr, IP_HASHBITS);
+ hash_ip((unsigned long)(item->m_addr.s6_addr32[0] ^
+     item->m_addr.s6_addr32[1] ^
+     item->m_addr.s6_addr32[2] ^
+     item->m_addr.s6_addr32[3]));
 }

Enjoy,
Don Capps








-------------------------------------------------------
This SF.net email is sponsored by: Splunk Inc. Do you grep through log files
for problems?  Stop!  Download the new AJAX search engine that makes
searching your log files as easy as surfing the  web.  DOWNLOAD SPLUNK!
http://ads.osdn.com/?ad_id=7637&alloc_id=16865&op=click
_______________________________________________
NFS maillist  -  NFS@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/nfs