Branch: refs/heads/main
Revision: be5adc1
Author: bmcdonald3
Log Message:
Merge pull request #18427 from bmcdonald3/map-probe
[ reviewed by (and help from) @mppf - thank you! ]
This PR changes the ChapelHashtable implementation to use a power of 2 table size as opposed to a prime table size. This was done so that we could change to "triangular numbers" probing, removing a % when looking for open slots, which was causing a performance degradation. The results of this are an increase in performance and a triangular probing approach, which seems to have some academic support in terms of guaranteeing open slots efficiently.
Benefits of triangular probing:
- the resulting probe sequence will visit every element of a power-of-2 sized hash table exactly once
- this is the only quadratic probing method that guarantees finding a slot with table more than half full
- we can avoid needing to use
%for our probing (due to the power-of-2 table size) - we can avoid having to use a
*, which can be replaced by a+instead
Proof for probe sequence: Triangular numbers mod 2^n | The ryg blog
- [x] update tests
- [x] standard paratest
Motivated by: https://github.com/Cray/chapel-private/issues/2365
Modified Files:
A test/library/packages/TOML/test/actual.test
A test/library/packages/TOML/test/arrays.test
A test/mason/pkgconfig-tests/openssl.lock
M modules/internal/ChapelHashtable.chpl
M test/arrays/deitz/domains/test_domain_arg2.good
M test/associative/diten/enumArrays.good
M test/classes/bradc/arrayInClass/arrayOfArithInClass.good
M test/classes/bradc/arrayInClass/genericArrayInClass-arith.good
M test/classes/bradc/arrayInClass/genericArrayInClass-otharrs.good
M test/classes/bradc/arrayInClass/genericArrayInClass-real.good
M test/classes/bradc/arrayInClass/genericClassArray-named.good
M test/distributions/bharshbarg/forwardDomDist.good
M test/domains/johnk/capacityTooBig.good
M test/functions/promotion/issue-12736-ok.good
M test/io/ferguson/issue-18156.good
M test/library/packages/Itertools/repeat/check_Parallel_zippered.good
M test/library/packages/TOML/test/TomlTest.execopts
M test/library/packages/TOML/test/UTomlTest.good
M test/library/packages/TOML/test/actual.good
M test/library/packages/TOML/test/arrayCorner.good
M test/library/packages/TOML/test/arrays.good
M test/library/packages/TOML/test/checkParseLoop.good
M test/library/packages/TOML/test/example.good
M test/library/packages/TOML/test/fileTest.execopts
M test/library/packages/TOML/test/mason-1.good
M test/library/packages/TOML/test/subTable.good
M test/library/packages/TOML/test/subTable2.good
M test/library/standard/DataFrames/psahabu/HelloDataFrame.good
M test/library/standard/DataFrames/psahabu/MutateDataFrame.good
M test/library/standard/Map/testBorrowedMap.good
M test/library/standard/Map/testGetBorrowed.good
M test/library/standard/Map/testGetReference.good
M test/library/standard/Map/testGetValue.good
M test/library/standard/Map/useMapper.good
M test/mason/chplVersion/tomls/fail/failMultipleDeps.good
M test/mason/chplVersion/tomls/fail/ivrsTwo.good
M test/mason/chplVersion/tomls/format/noBug.good
M test/mason/chplVersion/tomls/format/unbounded.good
M test/mason/chplVersion/tomls/pass/ivrsChooses.good
M test/mason/chplVersion/tomls/pass/simpleDep.good
M test/mason/chplVersion/tomls/pass/simpleSolo.good
M test/mason/mason-modify/addWithDep.good
M test/mason/mason-modify/rmWithDep.good
M test/mason/noDep.good
M test/mason/pkgconfig-tests/openssl.good
M test/mason/pkgconfig-tests/zlib.good
M test/mason/search/showCapsize.good
M test/mason/simple.good
M test/release/examples/patterns/readcsv.good
M test/studies/labelprop/labelprop-tweets.good
M test/types/chplhashtable/check-look-for-slots.chpl
M test/users/shetag/assocarr.good
Compare: https://github.com/chapel-lang/chapel/compare/d5f0b2d6417f...be5adc1bcb62