Improve Memory Efficiency with CDF contests

[yezr]

While researching memory usage for #962 I created 1 million ballot tests for all providers. The goal with these tests was to feel confident that RCTab can run a 1 million ballot contests for any provider, given our suggested minimum hardware guidelines of 16GB of memory. Given Java defaults, RCTab sets aside ~4GB of heap space when running on machines with 16GB of memory.

During 1 million ballot testing, the CDF provider was consistently running close to the 4GB memory usage. Can we look into the CommonDataFormatReader and see if there are any opportunities to be more efficient with our memory usage?

I copy/pasted within one of our shared Unisyn CVRs at test_data/unisyn_cvrs/101-RCV-CVT_TEST_3_UNIOVS2103-2.xml to get 50k votes within one file. That 50k vote file is 536MB and can be downloaded here. I made twenty copies of that on my machine to get to 1,176,000 total votes for this test.

[artoonie]

Looking into this, it seems the memory usage doesn't grow much as we add more CVRs -- on my machine, it uses about 5gb of ram whether I have 500k or 3 million ballots. I'll still investigate why it's using so much, but it does seem like under the hood, something is intelligently using as much memory as it is allocated without going over.

[artoonie]

On a 16gb machine, I was able to tabulate 7,467,600 CVRs from 127 sources in 851 seconds. The memory usage peaked at 5gb. It oscillated a bit as we cleared the GUI logs and they repopulated. I've profiled the memory and most of it is "working" memory, i.e. Java only knows about ~1gb of memory but the System Monitor believes it's using ~4gb of memory. That tells me the OS is providing Java with more memory that it needs just because it's allocating and deallocating so much.

The system memory usage was between 80% and 95% for the duration of the tabulation, again telling me that it's the OS giving the tabulator wiggle room, not this CVR reader using too much memory.

I did a thorough investigation here and have lots of profiling logs from across Windows and MacOS which show similar behavior on both.

[yezr]

Did some of my own research testing CDF tabulation.

On My Macbook - 16GB RAM, 10 core mac silicon processor

• 452MB before check ballot counts
• 4.37GB after check ballot count
• 4.5GB max during tabulation CVR reading

On 16GB VM hosted in Windows, 4 core processor

• 202MB after config loaded
• 844MB after first 58k read
• 1250MB after second 58k read
• 1733, 1763, 1853 after 5 sources read, 2083, 2220, … 2466 after 11…2451 after 14…2747 after 20 (1,176,000 CVRs)
• Tabulate! … 2750 after 11 sources read
• 2714 while calculating round 1
• 3489 calculating round 11
• 3490 at the end took 700 seconds
• Clicking tabulate again it remains around ~3500 throughout CVR read
• Finished another tabulation in 676 seconds, at 3653MB

Takeaways
As @artoonie mentioned, it looks like it's taking as much as it can. Not necessarily running up against hard limits. Not sure why it is 4.5GB ceiling on 16GB macbook vs. 3.5GB ceiling on 16GB VM.

Next I'm going to move the VM to 8GB memory and report back.

[artoonie]

I was worried about the silent hangs we discussed. Here's how to reproduce the issue:

1. Limit heap size to 2gb
2. Copy the Unisyn Mayor CVR 64 times
3. When reading the 63rd file, the process hangs silently

I investigated and found that indeed, it is running out of heap space. This is 3.2 million ballots, which takes up:

1. 472mb in byte[] and 307mb in strings. Biggest issue: The string header takes 24 bytes per string. The suppliedId data is 4 bytes and the computedId is 64 bytes. Total, that's 417.6Mb of data for the computed and supplied Ids.
2. 352mb in Hashmaps. Biggest issue: 48 bytes of headers with no corresponding data at CastVoteRecord.java:48.
3. 218mb in String[]. Biggest issue: candidateRankings in CastVoteRecord.

Everything else used less than 150 MB in this test run.

Recommended Resolutions:

1. Save 88 bytes per CVR by replacing computedId with an integer and simply incrementing.
2. Save 28 bytes per CVR by using file-backed scratch space for the suppliedId, mapping each computedId to the corresponding suppliedId string. Since this is only needed when writing output files, it should be acceptable.
3. Save 48 bytes per CVR by initializing cdfSnapshotData to null and only loading as needed
4. Save 20-80 bytes per CVR per ranking (depending on candidate name length) by intern()ing the candidate name strings when creating the CastVoteRecord. I'm not 100% sure that interning isn't already happening, but it seems like it's not.
5. Detect Heap OOM and stop running the program and print a message to the console.

If all of this works, it could cut memory usage nearly in half, meaning you could tabulate around 6 million votes on a 2gb of ram. I don't think we need to push beyond that, but we could by:
6. Ensure that CVRs hold no references to strings whatsoever. Everything they hold on to should be an integer, reference, or a map.

I recommend we make a separate task for 1-5 so we can evaluate each individually. I recommend we skip 6.

Note: these optimizations apply to more than just the CDF reader. I recommend we start with (5) since that's the real issue: seemingly hanging indefinitely as the process thrashes.

[yezr]

Armin thank you for digging so deep into this. Limiting the heap to 2GB mimics a machine with 8GB ram since the default is 1/4 ram allocated to the heap by our JVM. Given that we are going to make minimum hardware requirements 16GB I feel confident that we will run successfully with those hardware minimums up to 1m+ ballots.

I am very interested in option 5 - detecting Heap OOM and alerting the user. I'd also like to research if it's possible to have a menu option that would re-launch RCTab with the 80% of total RAM allocated to the heap as we recommend in the user guide. I dug around a little here about how to accomplish that. That would be great if we could have that as a one click option in the UI instead of requiring the user to pull out the CMD prompt. I still want the user to have to opt-in before RCTab takes up that much resources.