Three potential additions to stdlib

[wclodius2]

I now find myself with some free time that I would like to put in to extending the STDLIB. I have some preliminary work on three topics that might be useful to users of STDLIB: error codes, hash tables/unordered maps, and the unicode database. I would appreciate some guidance as to which topic people would find most useful and whether the interest in any topic is high enough to justify inclusion in STDLIB.

For error codes the idea is to standardize how the stdlib identifies and distinguises error conditions. I have a list of 100+ error code names, each with unique integer values. The names currently follow a pattern language in which a suffix is used to indicate the general source of the error: _failure, in which the outside world is not as expected, _error, in which the programmer likely made a mistake, and _fault, in which the processor is likely at fault. This pattern language makes the names a little unwieldy so I am considering dropping it. I have also defined a subroutine that takes an error code as an argument and stops processing with an error stop with an error code dependent string as the stop code. The resulting codes could be made part of stdlib_error.f90 and the subroutine part of an overloaded error_stop. FWIW this approach was inspired by a [posting by Richard A. O'Keefe in the Erlang mail list] (http://erlang.org/pipermail/erlang-questions/2015-March/083608.html).

The hash tables/unordered maps are composed of two or three modules: a module of hash functions, a module of hash tables using key/value pairs to implement an unordered map, and perhaps a module of hash tables using keys to implement an unordered set. The hash functions would have to be non-cryptographic to be legal in the US. Ideally there should be several different functions so the function can be changed in the event of excessive collisions. My idea is to use 64 bit hashes as reasonable for large data sets, though I can be persuaded to use 32 bit hashes. I have tentatively identified the Fowler-Noll-Voh (FNV) hash, the Murmur hash, and the Spooky hash as 64 bit public domain hash functions of interest. If anyone believes that any of these hashes are cryptographic let me know, or if you know of "better" hash functions. The hashes will be a transliteration to signed arithmetic assuming two's complement arithmetic and overflow detection can be turned off. The hash table will store the key and the value as (transferred) eight bit integer arrays. The tables can come in two implementations: chaining and open tables. They will use power of two table sizes, which assumes that the hash functions do an excellent job of randomizing bits.

The Unicode consortium maintains a database of character properties for the UCS character set. This database is the basis of the Python module unicodedata. This database is necessary for assigning code points to categories (e.g., number, letter, and punctuation), converting strings to one of the four normalization forms, and case folding. I consider this data necessary for the implementation of a UCS based varying string module. The initial implementation would be a module with procedures that use 32 bit integer scalars and arrays to represent UCS code points and strings. Several of the Unicode categories ("Bidi", "General Category", "Decomposition", and "Numerical") would be represented by enumerations in category specific types whose only components are eight bit integers. The text files in the UCD and Unihan directories that make up the database take up about 70.5 MBytes, so supporting this database requires a very significant download. The rank one arrays implementing this database take up a comparable amount of runtime storage.

[everythingfunctional]

I personally would vote for hash tables.

[jvdp1]

Needing often hash tables in my work, I am in favor of hash tables ;) I often use a lookup3-based function.

Note that standardizing the error codes in stdlib would be useful too.

[wclodius2]

@jvdp1 I have experimented with lookup3 and could include it. Which version do you use, the single 32 bit integer result or the dual 32 bit integer result?

[jvdp1]

@jvdp1 I have experimented with lookup3 and could include it. Which version do you use, the single 32 bit integer result or the dual 32 bit integer result?

I use a simplified version of the single 32 bit integer function. Is it relevant to implement lookup3 if Spooky hash is available? Starting with the 3 hash functions you proposed would be already nice IMO.

[wclodius2]

I guess the question is whether it would be useful to have a 32 bit specific hash in addition to the 64 bit hashes? A 32 bit hash:

1. Is probably sufficient for the vast majority of hash table usages, i.e. tables with significantly less than one million entries;
2. Will reduce memory traffic in hash comparisons and computations;
3. Will slightly reduce memory requirements, though the requirements will likely be dominated by the keys and associated data.

[jvdp1]

I think it could be good to start with 64 bit hashes. 32 bit hash functions may be implemented later if there is interest, or if it is straighforward ti implement..

[wclodius2]

Generally a thirty two bit hash is simpler than a sixty four bit one. FWIW I want to include a salt (an arbitrary integer of the appropriate kind that changes the mapping of the hash to potentially reduce hash bucket collisions) in the hash function algorithms. I can see two ways of doing it:

1. Associate with each algorithm a derived type with different implementations (int8 arrays, int16 arrays, character strings, etc) as type bound procedures and the salt as its sole component; or
2. Have the different implementations be stand alone procedures, with the salt as one argument and a component of the hash table, with the table initialization and remapping setting the salt and mapping of entries using the salt.

My initial implementation used the first, but now I am inclined to the second. Any preferences?

[jvdp1]

Generally a thirty two bit hash is simpler than a sixty four bit one. FWIW I want to include a salt (an arbitrary integer of the appropriate kind that changes the mapping of the hash to potentially reduce hash bucket collisions) in the hash function algorithms. I can see two ways of doing it:

1. Associate with each algorithm a derived type with different implementations (int8 arrays, int16 arrays, character strings, etc) as type bound procedures and the salt as its sole component; or
2. Have the different implementations be stand alone procedures, with the salt as one argument and a component of the hash table, with the table initialization and remapping setting the salt and mapping of entries using the salt.

My initial implementation used the first, but now I am inclined to the second. Any preferences?

I would prefer the second one. But the first one sounds also good!

[milancurcic]

I prefer the second implementation. Thank you for taking the lead, @wclodius2!

[wclodius2]

With @milancurcic weighing in we now have three people interested in hash functions/tables. Maybe that's enough for inclusion in stdlib. If so the first thing we should do is agree on an API for the hash "functions."

Currently I have two modules for hash functions. stdlib_32_bit_hash_functions.f90 and stdlib_64_bit_hash_functions.f90, for 32 bit and 64 bit hashes respectively. All of the algorithms are implemented in Fortran (I believe F2008), transliterated to signed arithmetic under the assumption that the two's complement arithmetic, used by all modern Fortran processors, will, at the bit level, behave the same as unsigned arithmetic for multiplication, XOR, rotation, and addition. Currently the procedures are functions, as that felt more natural to me, but that is awkward if incremental hashing is desired. Conversion to subroutines for incremental hashing is straightforward, if tedious. All of the algorithm's are in the public domain, but Austin Appleby's Murmur Hashes require that all implementations be in the public domain. I take that to mean that the code if distributed with stdlib can be MIT license, but must be available independent of stdlib as public domain source code, but we should probably check this. All algorithms come in five versions, one each for integer vectors of kinds INT8, INT16, INT32, and INT64, and one for default character strings.

stdlib_32_bit_hash_functions.f90 currently implements 4 hash algorithms: a 32 bit FNV-1 algorithm of Fowler, Noll and Vo that implements a multiply and XOR algorithm; a 32 bit FNV-1a algorithm that reverses the order of the multiply and XOR; the 32 bit Murmur Hash 3 of Austin Appleby that multiplies the current block of input, rotates the product, and XORs with the current hash; and the lookup 3 hash of Bob Jenkins, that uses additions, subtractions, rotations, and xors. FNV-1 and FNV-1a use no salt. Murmur Hash 3 uses a 32 bit integer for its salt that can also be used for incremental hashing. Lookup 3 uses two 32 bit integers for its salt that can also be used for incremental hashing if the option to return two 32 bit integers as its hash is used.

stdlib_64_bit_hash_functions.f90 currently implements 4 hash algorithms: a 64 bit FNV-1 algorithm of Fowler, Noll and Vo that implements a multiply and XOR algorithm; a 64 bit FNV-1a algorithm that reverses the order of the multiply and XOR; the 64 bit Murmur Hash 2 of Austin Appleby that multiplies the current block of input, rotates the product, and XORs with the current hash; and the 64 bit Spooky hash of Bob Jenkins, that uses additions, subtractions, rotations, and xors. FNV-1 and FNV-1a use no salt. Murmur Hash 3 uses a 32 bit integer for its salt that can also be used for incremental hashing. Spooky uses two 64 bit integers for its salt that can also be used for incremental hashing if the option to return two 64 bit integers as its hash is used.

The functions have been tested using a code that generates 2**30 random bytes, and processes them in blocks of 16, 64, 256, and 1024 bytes. Compilation was using ifort 17 as it was giving better error messages than gfortran. For ifort on a MacBook Pro, 2.3 GHz Quad-Core Intel Core i5, with 8 GB 2133 MHz LPDDR3 memory, the hashes of Bob Jenkins were generally the fastest, followed by the hashes of Austin Appleby, followed by the FNV hashes. The 64 bit hashes could be processed in larger chunks than the 32 bit hashes, so the 64 bit hashes were generally faster than the equivalent 32 bit hash. The times in seconds for the different algorithms on the different block sizes ar shown in the tables below where the small the time the faster the processing.

Algorithm	Key Size Bytes	Key #	Time (s)
FNV-1	1024	1048576	8.054
FNV-1	256	4194304	8.056
FNV-1	64	16777216	8.080
FNV-1	16	67108864	8.397
FNV-1a	1024	1048576	8.975
FNV-1a	256	4194304	8.953
FNV-1a	64	16777216	9.090
FNV-1a	16	67108864	9.240
Murmur3	1024	1048576	3.875
Murmur3	256	4194304	3.962
Murmur3	64	16777216	4.057
Murmur3	16	67108864	4.428
Lookup3	1024	1048576	3.558
Lookup3	256	4194304	3.573
Lookup3	64	16777216	3.728
Lookup3	16	67108864	4.156

Algorithm	Key Size Bytes	Key #	Time (s)
FNV-1	1024	1048576	6.002
FNV-1	256	4194304	6.007
FNV-1	64	16777216	6.092
FNV-1	16	67108864	6.399
FNV-1a	1024	1048576	6.508
FNV-1a	256	4194304	6.564
FNV-1a	64	16777216	6.625
FNV-1a	16	67108864	6.933
Murmur2	1024	1048576	1.605
Murmur2	256	4194304	1.625
Murmur2	64	16777216	1.723
Murmur2	16	67108864	2.113
Spooky	1024	1048576	0.370
Spooky	256	4194304	0.631
Spooky	64	16777216	1.321
Spooky	16	67108864	4.512

[jvdp1]

@wclodius2 Thanks for all these details and implementations. Times look good IMO.

Regarding the API, I would implement them as functions too. I don't see the issue with functions and incremental hashing.

[wclodius2]

@jvdp1 thanks for the interest.

The timings may be misleading as all of the tests are of multiples of 16 bytes. If the number of bytes in the key is not a multiple of four for the 32 bit hashes, or eight for the 64 bit hashes then Austin Appleby and Bob Jenkins treat the trailing bytes using a switch statement that by itself introduces overhead. Unfortunately, the Fortran equivalent of the switch statement, a computed go to, is deprecated, so I replaced it by a select case statement whose cases are all go to statements to the fall through code of the switch statement. This can in principle be optimized to the equivalent of the switch statement, but I don't know if all compilers can optimize the consecutive double jumps to their equivalent single jump. Therefore I expect that the overhead may be larger for my code.

With regard to functions versus subroutines, I let myself be misled by Bob Jenkins' comments that he recommended the two word 32 bit hashes of Lookup3, and the two word 64 bit hashes of Spooky Hash and based my code on the void function versions of his hashes that input and returned the values in two pointers to unsigned integers. The code would be more natural if I based it on his integer returning functions. The rewrite would be relatively small and would make the API for the hash tables slightly simpler so I plan to implement it over the next week.

[jvdp1]

Thank you @wclodius2 for the details.
I also used select case statement to "translate" the switch statement in the Lookup3 functions. I don't see how to avoid it.

Re: functions vs subroutines, I think that subroutines are ok when returning 2 integers.

[wclodius2]

I have some new numbers for the runtimes of the various algorithms that include small size keys.

Algorithm	Key Size Bytes	Key #	Time (s)
FNV-1	1	1073741824	12.947
FNV-1	2	536870912	10.383
FNV-1	4	268435456	9.102
FNV-1	8	134217728	8.425
FNV-1	16	67108864	8.286
FNV-1	64	16777216	7.853
FNV-1	256	4194304	7.792
FNV-1	1024	1048576	7.763
FNV-1a	1	1073741824	13.565
FNV-1a	2	536870912	11.181
FNV-1a	4	268435456	9.948
FNV-1a	8	134217728	9.226
FNV-1a	16	67108864	8.959
FNV-1a	64	16777216	8.725
FNV-1a	256	4194304	8.660
FNV-1a	1024	1048576	8.935
murmur3	1	1073741824	19.123
murmur3	2	536870912	13.627
murmur3	4	268435456	5.931
murmur3	8	134217728	4.985
murmur3	16	67108864	4.281
murmur3	64	16777216	3.883
murmur3	256	4194304	3.771
murmur3	1024	1048576	3.750
Lookup3	1	1073741824	18.478
Lookup3	2	536870912	9.323
Lookup3	4	268435456	5.377
Lookup3	8	134217728	4.312
Lookup3	16	67108864	3.983
Lookup3	64	16777216	3.551
Lookup3	256	4194304	3.438
Lookup3	1024	1048576	3.410

Algorithm	Key Size Bytes	Key #	Time (s)
FNV-1	1	1073741824	12.426
FNV-1	2	536870912	9.122
FNV-1	4	268435456	7.525
FNV-1	8	134217728	7.014
FNV-1	16	67108864	6.211
FNV-1	64	16777216	5.888
FNV-1	256	4194304	5.831
FNV-1	1024	1048576	5.788
FNV-1a	1	1073741824	12.860
FNV-1a	2	536870912	9.669
FNV-1a	4	268435456	8.130
FNV-1a	8	134217728	7.268
FNV-1a	16	67108864	6.753
FNV-1a	64	16777216	6.434
FNV-1a	256	4194304	6.555
FNV-1a	1024	1048576	6.699
Murmur2	1	1073741824	14.914
Murmur2	2	536870912	10.898
Murmur2	4	268435456	8.541
Murmur2	8	134217728	2.550
Murmur2	16	67108864	2.040
Murmur2	64	16777216	1.673
Murmur2	256	4194304	1.572
Murmur2	1024	1048576	1.540
Spooky	1	1073741824	25.808
Spooky	2	536870912	16.345
Spooky	4	268435456	8.723
Spooky	8	134217728	3.415
Spooky	16	67108864	2.413
Spooky	64	16777216	0.750
Spooky	256	4194304	0.424
Spooky	1024	1048576	0.294

I propose for the API of the 32 bit hash functions the following

interface hashname_32_bits
    function int8_hashname_wo_seed(key)
        import int8, int32
        integer(int32) :: hashname_wo_seed
        integer(int8), intent(in) :: key(:)
    end function int8_hashname_wo_seed
    function int16_hashname_wo_seed(key)
        import int15, int32
        integer(int32) :: hashname_wo_seed
        integer(int16), intent(in) :: key(:)
    end function int16_hashname_wo_seed
    ...
    function int8_hashname_w_seed(key, seed)
        import int8, int32
        integer(int32) :: hashname_w_seed
        integer(int8), intent(in) :: key(:)
        integer(int32), intent(in) :: seed !  perhaps pass by value
    end function int8_hashname_w_seed
    ...
end interface hashname_32_bits

with something similar for 64 bit hash functions.

I suspect the primary primary use of the hash functions will be for hash tables with typically 4-16 element keys, probably weighted to the low end of that number, typically drawn from the ASCII character set. For UTF-8 character sets, e.g. Linux and Macs, these will probably be be 8-16 bytes, while for UTF-16, e.g., Windows platforms, this might translate to 8-32 byte keys. For these applications 128 bits are overkill. The 32 bit architectures are fading fast, so we should emphasize algorithms tuned for 64 bit architectures. The 32 bit hashes are the best performing for 4 byte keys, while the 64 bit hashes are the best performing for the 16 and 32 byte keys. For the size range of primary interest the FNV hashes perform worst than the other 32 bit hashes, while for 64 bits the FNV hashes are better for the four byte keys, but worse for anything as large as or larger than 8 bytes. The FNV hashes are also generally more prone to collisions than the other hashes and do not show up as well in the SMHasher tests or other tests. The FNV also do not support a seed argument. I therefore propose to replace the FNV hashes.

The most detailed analysis of a large variety of hash functions is that of Jim Apple and Reini Urban, which uses an extended version of SMHasher. This analysis finds the following hashes to be the best performing with no detected problems:

• xxh3low
• wyhash
• t1ha2_atonce
• FarmHash (not portable, too machine specific: 64 vs 32bit, old gcc, ...)
• halftime_hash128
• Spooky32
• pengyhash
• mx3
• MUM/mir (different results on 32/64-bit archs)
• fasthash32

In addition a 32 bit hash inspired by the wyhash, the waterhash, claims to also pass the SMHasher tests.

The first question that comes to mind in incorporating translated code is would the associated license allow incorporation in MIT licensed code. The following hashes are obviously compatible as they use the MIT license: Farmhash, [Fasthash}(https://code.google.com/archive/p/fast-hash/), and Mir. The hashes that use the unlicense also appear to be compatible: water hash and wyhash. The BSD 2-clause license requirement to list the copyrights seems to me to be incompatible with the MIT License: so pengyhash and xxh3 appear to be excluded. The mum license also requires copyright publication, but is clearer that modifications are allowed, so I think it is MIT compatible. Halftime hash has no explicit license associated with it so I think it must be excluded. The zlib license of t1ha2 reads to me as compatible with the MIT license. Spooky doesn't have an explicit license, but I have put in a lot of work on it so I am going to send enquiries to Bob Jenkins. Mx3 uses the CC0 (creative commons) license with "no rights reserved" that seems to me to be very MIT compatible.

Another determining factor for me is practicality of implementation. I am not an expert in C++, so I have less confidence in accurately translating longer codes. As a rough rule of thumb I think I can handle codes originally less than 500 Simple Lines of Cod (SLOC) and unwilling to tackle codes longer than 750 SLOC. The results of the above analysis are summarized in the table below.

Hash	License	MIT compatible	SLOC	Acceptable Complexity	Library Acceptable
Farmhash	MIT license	Yes	~11,650	No	No
Fasthash	MIT license	Yes	~80	Yes	Yes
Halftime hash	?	No?	951	No	No
Mir Hash	MIT license	Yes	82	Yes	Yes
Mum hash	Public domain	Yes?	380	Yes	Yes?
Mx3	CC0	Yes	63	Yes	Yes
Pengy hash	BSD 2-Clause	No?	29	Yes	No?
t1ha2	zlib	Yes?	~1500	No	No
Spooky	Public Domain	?	400?	Yes	?
waterhash	unlicense	Yes	50	Yes	Yes
wyhash	unlicense	Yes	142	Yes	Yes
xxh3	BSD 2-Clause	No?	5020	No	No

The reported peak processing speed in MiB/sec (representative of processing large keys) for the acceptable hashes are

Hash	MiB/sec
Fasthash	4737.61
Mir Hash	5413.73
Mum hash	7134.56
Mx3	6146.02
Spooky	9747.13
water hash	8421.17 (different processor)
wyhash	14789.93

Obviously wyhash is of particular interest for processing large keys. For processing small keys we want a code with high performance and negligible startup cost. The startup cost tends to increase with the overall size of the code so for small keys we want high performance with relatively small size. That suggests that one of Mir hash, Mx3, or water hash would be best for small keys. FWIW waterhash is a 32 bit hash, while Mir hash and Mx3 are 64 bit hashes.