bertdobbelaere
commented
1 year ago Thank you for your suggestion. It contains certainly a valuable insight. I performed some analysis based on ~10^8 iterations using the two sample configuration files I included with the code. Based on sample_config.txt, I obtained the following stats: Using current algorithm:
- 96.442% of the networks were rejected based on the first 64 vectors
- 0.600% of the networks were rejected in later verification rounds
- 2.958% of the networks were accepted With initial "input coverage" based check:
- 10.694% of the networks were rejected based on coverage failure
- 85.751% of the networks were rejected based on the first 64 vectors (after coverage check)
- 0.597% of the networks were rejected in later verification rounds
- 2.958% of the networks were accepted (should be identical - OK) Overall, adding the "input coverage" check resulted in 4.9% speed increase Based on sample_config2.txt however, there was a 6.2% speed loss. This can easily be explained because the prefix used in that example is already fully connected, hence the rejection rate of the coverage test is 0.
I have to admit that I was surprised to see a speed improvement at all in the first example. The coverage test is clearly sufficiently "cheaper" in terms of CPU cycles than sorting the first 64 test vectors to compensate for its relatively low rejection rate. The overall gain obviously depends largely on the prefix network: for small or poorly connected prefixes, the coverage check may give a meaningful speedup. As the prefix becomes more powerful, the gain is expected to dwindle.
As most recent improvements are using highly connected prefixes I will not add an option for a check based on connectivity coverage for now, but thanks again for bringing it to my attention.
If an output row can't "see" every input then it can't be a complete sort. So a quick test for validity is to initialise an array of bit vectors with one set bit representing their own index, and then to iterate through the network oring those vectors together in the same way as the bitwise sort does. At the end, if any of the bitsets are not fully populated then that row is inaccessible to the corresponding input and the sort cannot be complete.
I tried this and the cull rate was initially very poor (few candidates were rejected), but as the candidate quality improved (contained fewer redundant comparators) the cull rate climbed to about 30%, which meant no trial sorts needed to be run. I'm not sure what the rejection rate of the first batch of trial sorts is, but squinting at the timing output looked like testing was about 10% faster overall.