Performance improvement to `recalculateBins`

[odmir]

Around the end of last year I noticed that the time the tests were taking was starting to become a burden, especially when doing quick iterative work. After investigating I saw that a big chunk of it was due to the increase in histogram tests at that time, which were really exercising one specific method which took a big slice of the testing time and is called several times for each test, at least twice per output file. Due to this, I decided to change the algorithm used in recalculateBins to speed it up considerably, and consequently the testing time as well.

The algorithms are documented in the code. I tried giving them big O notation in the comments for performance comparison, but I have never done this before, so if it is stupidly wrong please tell me 😜.

Regarding the performance wins when executing all of the tests on my machine, the new tests report this:

before:

after:

they are two tests testing two different algorithms, one used when the data is sorted and another for when its not;

and when executing all the tests:

	Without New Tests	With New Tests
master	~ 10.1 s	~ 13.7 s
new algorithms	~ 7.3 s	~ 8.1 s

The new tests added by this PR add some time to the overall testing time, but it is still an improvement on how it was before, even without the new tests.

Now the time recalculateBins takes is basically negligible.

At the time the improvements in testing speed seemed better because there are more tests now and it looks less impressive 😜.

Please tell me about any issues you encounter. I only wanted to test that specific method, but it was marked private so I created another internal method that just calls it for testing purposes. I don't know if there is a better approach other than measuring the performance of that private method indirectly by measuring the whole rendering process, or just by changing the access of that method back to public like it was before. @KarthikRIyer @karwa.

[KarthikRIyer]

I like this approach! I hadn't paid much attention to the time complexity of this function although I knew it wasn't good. I tried to improve it once but messed it up and forgot about it later 😅. This looks good to me. But I'm not sure of the O() notation for the sorted case. I think it would be O(n) generally (for the case Karl specified above).

[odmir]

Ok I've changed the class back into a struct. Regarding the O notation in the sorted case it should become O(n) and in the unsorted case it should be O(n log(m)) as well assuming n >> m right? If we assume that in general m ~= sqrt(n) then it should be something like: O(n) if sorted; O(n log(√n)) = O(n log(n)/2 ) if unsorted; right?

[odmir]

Unfortunately, XCTest performance tests are kind of useless for CI, because we can't set the baseline measurements. I would really like them, but there's not much point to adding them at this time :(

@karwa is there some solution that you know of? Also is there any way to disable some tests, or separate them into another "module" so that CI only runs the non-performance related tests for now?

[odmir]

Ok the build seems to be failing because some other behaviour is dependent on the data being sorted, it would have broken sooner or later, at least as soon as someone tried to plot a histogram after manually changing data.

[odmir]

I had to put a workaround in layoutData because code over there was getting the max and min X by getting the first and last elements from data causing trouble later on. I added a comment documenting the workaround and the why as well as a FIXME because we are not handling when the user uses an empty array, and a "performance" TODO because now we are going through the entire data, however many series the histogram has.

[karwa]

is there some solution that you know of? Also is there any way to disable some tests, or separate them into another "module" so that CI only runs the non-performance related tests for now?

I don't know of a solution. The problem appears to be that Xcode records and saves baseline measurements as plist files, and that the package manager has no knowledge of those files or any parameters where you can specify them.

In any case, we would likely want those tests to be run on CI. It's less important that CI is fast, and more important that it is accurate and doesn't let us accidentally commit a major performance regression without realising it.

I had to put a workaround in layoutData because code over there was getting the max and min X by getting the first and last elements from data causing trouble later on. I added a comment documenting the workaround and the why as well as a FIXME because we are not handling when the user uses an empty array, and a "performance" TODO because now we are going through the entire data, however many series the histogram has.

Well that's unfortunate. What does this do to performance? Is there still an overall improvement by disabling sorting?

Just by thinking about it, I would assume there is still an improvement, at least in our tests. Our data is defined as static let constants, so when we sort it we'll be making a copy in O(n) before doing the sorting in O(n log(n)). By getting the min/max without mutating, we can turn that in to a single O(n) operation.

[odmir]

Yes it is still better. For the benchmarks I created:

1. one branch from a commit where we had: sorting, faster algorithm and fast maxX, minX;
2. another branch from latest commit with: no sorting, fast algorithm and slower maxX, minX.

From both branches I removed the performance tests because they only exercised the algorithm and sorting parts but never touched the maxX and minX.

Then I measured only the HistogramTests test suite:

Branch	Average Time (s)
1	1.648
2	1.567

so we are better now with an improvement of about 80 ms.

[odmir]

and compared to master:

Branch	Average Time (s)
2	1.567
master	4.323

an improvement of 2.756 s.

[odmir]

If everyone agrees this is ready to be merged!

@KarthikRIyer @karwa

[karwa]

Could you maybe move the test to a new test suite? Maybe PerformanceTests? Then we could add performance tests for other plots there, and you can easily exclude them all if you don't want to run them.

[odmir]

There you go! 😊

[karwa]

Nice. Looks good to me 👍

[KarthikRIyer]

Great! Thanks @odmir . Merging.