devfs: Add siphash comparison

[manu]

Summary

Instead of always comparing device path, use the SipHash algorithm
to compute a hash of the device path and compare that.
Since this is not a perfect hash algorithm we still do a strcmp if
the hashes match.

When importing a zpool with ~1000 zvol, this improve import time by ~3%.

Sponsored By: Gandi.net
MFC After: 1 month

Test Plan

ministat import_time_stable import_time_hash                                                                                                                                                         
x import_time_stable
+ import_time_hash
+------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
|                                                             +                                                                                                                                                    |
|+       +             +        +           +                 +  +              x x x+                x x   x            x                                                                 x                      x|
|             |____________________________AM__________________________| |______________________________M_______________A______________________________________________|                                           |
+------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
    N           Min           Max        Median           Avg        Stddev
x   9         76.24         80.11         76.97     77.434444      1.397615
+   9         73.91         76.41         75.19     75.142222    0.84381245
Difference at 95.0% confidence
        -2.29222 +/- 1.1537
        -2.96021% +/- 1.45771%
        (Student's t, pooled s = 1.15441)

[manu]

This is the kernel stack generated with pmcstat during a import : https://people.freebsd.org/~manu/import_zvol.svg
And this one is with this patch : https://people.freebsd.org/~manu/import-hash.svg

I have a another patch coming for ZFS with improve again import time by ~3%

[kib]

Try to compare lengths before committing to strcmp(). Does it help ?

Also, if calculating a hash, I do not see why not use it to store the strings in the hasharray instead of plain list.

[manu]

In D13395#279745, @kib wrote:

Try to compare lengths before committing to strcmp(). Does it help ?

Almost all my zvol have the same name so this would not help me.

Also, if calculating a hash, I do not see why not use it to store the strings in the hasharray instead of plain list.

Which hasharray ?

[kib]

In D13395#279754, @manu wrote:

In D13395#279745, @kib wrote:

Also, if calculating a hash, I do not see why not use it to store the strings in the hasharray instead of plain list.

Which hasharray ?

A new hasharray replacing the list.

[manu]

No plan to update this now.