Unsigned BytePrimeCache Upgrade

[DK96-OS]

Upgrade BytePrimeCache to support unsigned bytes.

Resolve #19

Performance testing and iteration.

[DK96-OS]

Test results from the BytePrimeCacheTest: Test Result Table 1 : 240,000 runs of empty cache targeted prime number access Note: The tests in this report have been sorted by test name, not by order of execution or input parameter, which would be ideal for comparing results.

Technical Background

• The initial cache size is 16, which means that accessing primes up to index 15 are the fastest possible operations.
• The queue size was 8 for this test. The ideal queue size is not the target at this stage of the investigation, but was observed to have no impact on the highest indices (40+), as expected.
• Accessing a prime number at index 24 or higher exceeds the queue (15 + 8), and causes the array to be rebuilt.

Data Analysis and Uncertainties

Timing results from these unit test results may contain a significant degree of uncertainty.

• Optimizations occur during the first few tests, making later tests run faster.
• Fluctuations in timing results appear every few tests. To ensure that these are not caused by a specific test case, multiple identical tests should be run and the corresponding data should be compared.

[DK96-OS]

A hidden contributing factor to the rapid increase is the local average distance between prime numbers, which also increases as index increases. This should cause the difference between consecutive indices to vary, and increase overall.

This may be the cause of the rapid increase, however some other algorithmic inefficiency may be producing these results.

[DK96-OS]

Graphing the recent results: Test Result Table 2 Comparing the data from Table 1 with the results following some minor code simplification, including the removal of If statements.

Data Trends

It appears that there is a loss of time efficiency at indices 15 and lower. Test 2 numbers are consistently higher, often 2 or 3 times as much. There are spikes in the middle of the graph that seem to correspond with the indices where the queue begins to be used, and where the array begins to be resized. These spikes are likely caused by optimization, although it is unclear why they do not appear in the first test. At higher indices, after the spikes have disappeared, the two test results correlate well together.

Interpretation

Only a few small changes have occurred in the source code, and none of them should be encountered at lower indices up to 15. This fact casts uncertainty onto this data. Potential differences in computing resources, or perhaps the change to the build file which triggered the build cache to be invalidated, could be a source of instability.

The reduction in time at the highest indices can be attributed to multiple code changes, such as removing If statements, and replacing a while loop with a for loop.

[DK96-OS]

Recent Results from BytePrimeCacheTest: Test Result Table 3 The most recent results following PrimeCacheBase refactoring.

Interpretation

Low Indices (0, 15): The most recent Test 3 performs nearly identically to the data in Table 1 in this range. In Test 2, these numbers were consistently higher, suggesting that a recent change had a negative impact. In Test 3, the suspected change was reimplemented to avoid using UByte conversion, instead converting directly to Int and adding 256 if the value was negative. This result appears to indicate that an intermediary UByte conversion has a time cost that exceeds that of an if statement and an addition operation.

Higher Indices (30 - 53): Higher indices rely on the findPrime and quickIsPrime methods. These methods (in PrimeCacheBase) were refactored in commit 7d0d671. This data shows a clear loss in performance resulting from these changes.

[DK96-OS]

Rerunning the tests on the same code produces inconsistent results. This method of measuring performance is not accurate or consistent enough to show the effects of changes to the source code.

[DK96-OS]

Test Result Table 4 Tests 4 and 5 use the same source code, the most recent commit being a revert to the previous QuickIsPrime method.

These results demonstrate that this method of measuring performance is not consistent enough for this purpose. A new method must be used. However, this pull request has served it's primary purpose and should be merged. Performance tuning will involve investigation of multiple new techniques, and mathematical conditions, each in their own branch of development.