noamteyssier

Good question! I just added that comparison and the rust uutils coreutils port is significantly faster than the standard coreutils.

I think this could potentially really reduce the amount of memory required - especially in cases where there is a lot of repetitive prefixes.

Would be interesting to try this out

I think you'd still need to go through that if you were really optimizing both `sort` and `uniq` working with their constraints.

What I'm really optimizing here is the functional equivalent of `sort | uniq -c | sort -n`

yeah that's right - there are trade-offs in doing so as it can require much more memory. So like everything it's an application specific decision

I've added this functionality to `hist-0.1.5` with a benchmark of other tools that do this on the CLI

this looks very interesting and I'd love to add it to the benchmarking! I was interested in trying it but unfortunately got an installation error on my macbook where I'm running the benchmarks:

``` clang \ -g -ggdb -O3 \ -Wall -Wextra -Wpointer-arith \ -D_FORTIFY_SOURCE=2 -fPIE \ mmuniq.c \ -lm \ -Wl,-z,now -Wl,-z,relro \ -o mmuniq mmuniq.c:1:10: fatal error: 'byteswap.h' file not found 1 | #include <byteswap.h> | ^~~~~~~~~~~~ 1 error generated. make: ** [mmuniq] Error 1 ```

I've actually added a benchmark for this specific task and added `unic` to it.

It may not be the most fair comparison because with these random fastqs I'm generating the vast majority of the input is unique so it could be overloading the cuckoo filter.

Shows up a lot in bioinformatics actually - trying to identify sequences with a specific subsequence (grep) and how many of each unique sequence there are. The number of lines here could be massive (order of 1-10's of GB)

You don't really end up using these results in any specific analysis but it's super helpful for troubleshooting tools or edge-cases.

I've added awk into the benchmarks also!

Yeah I'm using it to serialize the output lines as a TSV. Rust's `println!` is notoriously slow and using `csv` to serialize the output is a nice way to boost throughput

Yes you're right, it's not trying to do what `sort` is doing, it's trying to reproduce the output of `sort | uniq -c | sort -n` which is a more specialized but common task.

But you're right - it will be limited by RAM in a way the unix tools are not.

I did add a test with sort using a larger buffer size to the benchmarks as well.

Thanks for sharing!

You're right that the `cat` is unnecessary - and removing it actually had some marginal gains to the naive solution. I've updated the benchmarks to show this

Cheers

Yeah definitely, it's always a trade-off. I think in many cases where I use it especially the number of unique values is actually not crazy high (much less than the required RAM) and the number of lines is crazy high.

So in those settings I think it's absolutely worth it

I didn't know that - I've added in buffer size with a fairly large buffer to the benchmarks as well

Cool suggestions! I definitely would be interested in exploring other hash functions for this (and other binf works) so I'll definitely take a look at your stringzilla lib.