Chunk file reading for large files

[ameenmaali]

There are some use cases that have been brought up for deduping large files (> 10gb). This will result in a crash if the system does not have enough RAM to deal with it, as the file is loaded into memory at this point. We will need to chunk the file into smaller buffers when loading in order to prevent this. It may also make sense to parallelize this process with the URL deduplication process as large files will take longer than necessary due to waiting for the entire file to be loaded. @larskraemer, any thoughts on approach for solving this issue?

[larskraemer]

In order to tackle this, we might need to rethink how we find duplicates.
Currently, we need to store all of the unique URLs, since Url stores the whole string.
Even if the url_string field is cleared after printing, the map in main holds a copy of the url_key, which we have to assume is similar in size to the original.
In order to be able to deal with really large files, we probably have to read one URL at a time, produce a unique hash of it and then free/reuse the memory. The hash could then be used to check for duplicates.

[larskraemer]

#17 reduces our maximum memory usage to 16 bytes per unique URL plus some constant amount. I don't think we can do much better, except in the constant amount part.

[larskraemer]

That wouldn't help after #17 is merged, I don't think, since at the end, we need to keep all unique URLs in memory at once (or an identifier based on them). Would be nice to know if that commit helps in your case, could you build that branch and give it a try?

[larskraemer]

@marcelo321
git clone https://github.com/larskraemer/urldedupe.git
cd urldedupe
git checkout store_hashes
Then build as usual

Been a while since I looked at the code, but that version shouldn't have the memory issue, i.e. it uses only as much memory as is needed for the hashes of all unique URLs. If you have 8GB of RAM, you should be able to handle about 500 million unique URLs.
Sorting probably makes it worse, since sorting the amount of URLs it takes to cause memory issues would probably take many times longer than just throwing them at urldedupe.

If you're still having issues with that version, please report back so I can debug your issue.