Trying to reduce memory usage

[Jon Degenhardt]

On Tuesday, 23 February 2021 at 00:08:40 UTC, tsbockman wrote:
> On Friday, 19 February 2021 at 00:13:19 UTC, Jon Degenhardt 
> wrote:
>> It would be interesting to see how the performance compares to 
>> tsv-uniq 
>> (https://github.com/eBay/tsv-utils/tree/master/tsv-uniq). The 
>> prebuilt binaries turn on all the optimizations 
>> (https://github.com/eBay/tsv-utils/releases).
>
> My program (called line-dedup below) is modestly faster than 
> yours, with the gap gradually widening as files get bigger. 
> Similarly, when not using a memory-mapped scratch file, my 
> program is modestly less memory hungry than yours, with the gap 
> gradually widening as files get bigger.
>
> In neither case is the difference very exciting though; the 
> real benefit of my algorithm is that it can process files too 
> large for physical memory. It might also handle frequent hash 
> collisions better, and could be upgraded to handle huge numbers 
> of very short lines efficiently.

Thanks for running the comparison! I appreciate seeing how other 
implementations compare.

I'd characterize the results a differently though. Based on the 
numbers, line-dedup is materially faster than tsv-uniq, at least 
on the tests run. To your point, it may not make much practical 
difference on data sets that fit in memory. tsv-uniq is fast 
enough for most needs. But it's still a material performance 
delta. Nice job!

I agree also that the bigger pragmatic benefit is fast processing 
of files much larger than will fit in memory. There are other 
useful problems like this. One I often need is creating a random 
weighted ordering. Easy to do for data sets that fit in memory, 
but hard to do fast for data sets that do not.

--Jon