The awk script is probably the fastest way to do this still, and it's faster if you use gawk or something similar rather than default awk. Most people also don't need ordering, so you can get away with only the awk part and you don't need the sort.

Totally agree it's a bit of weird benchmark - it was just the first thing that I thought of to generate a huge amount of lines to test throughput.

There are definitely other benchmarks that we could try as well to test other characteristics as well.

I've actually just added in this `awk` implementation you provided to the benchmarks well.

Cheers!

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.

Nice tool!

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

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.

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

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

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, it’s used just for writing

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.

We had similar thoughts about "premature optimisation" in the games industry. That is it's better to have prematurely optimised things than finding "everything is slow". But I guess in that context there are many many "inner-most loops" to optimise.

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 believe, given its reliance on the Bloom filter, that it doesn't actually report occurrences count?

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`

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'm sure you're doing it in a sensible way, but... the thought that played out in my head went a little like this {apologies, I'm not well today, this might be a fever dream}:

Interviewer: "Welcome to your hammer-stuff interview, hope you're ready to show your hammering skills, we see from your resumé you've been hammering for a while now."

Schmuck: "Yeah, I just love to make my bosses rich by hammering things!"

Interviewer: "Great, let's get right into the hammer use ... here's a screw, show me how you'd hammer that."

Schmuck: (Thinks - "Well, of course, I wouldn't normally hammer those; but I know interviewers like to see weird things hammered! Here goes...")

[Hammering commences]

Interviewer: "Well thanks for flying in, but you've failed the interview. We were very impressed that you demonstrated some of the best hammering we've ever seen. But, of course, wanted to see you use a screwdriver here in your hammering interview at We Hammer All The Things."

One of the cooler Unix command utilities is tsort, which performs a topological sort. Basically you give it a list of items (first word in each line) and their dependencies (subsequent words on each line) and it sorts them accordingly, similar to how, e.g., Make builds a graph of targets and dependencies to run recipes in the correct order. https://en.wikipedia.org/wiki/Tsort https://pubs.opengroup.org/onlinepubs/9799919799/utilities/t...

However, I've never found a use for it. Apparently it was written for the Version 7 Unix build system to sort libraries for passing to the linker. And still used.[1][2] But of the few times I've needed a topological sort, it was part of a much larger problem where shell scripting was inappropriate, and implementing it from scratch using a typical sort routine isn't that difficult. Still, I'm waiting for an excuse to use it someday, hopefully in something high visibility so I can blow people's minds.

[1] https://github.com/openbsd/src/blob/17290de/share/mk/bsd.lib... [2] https://github.com/NetBSD/src/blob/7d8184e/share/mk/bsd.lib....

Your loss, not theirs. Lots of good developers are not expert at unix commands, many of which spend most of their time on Windows. They may be "wasting" 2 minutes on this specific task with their "inefficient" method, but they may perform much better on other tasks, to the point that 2 minutes saved here is nothing.

Not to mention that these days people often ask ChatGPT "what's the best way to do this" before proceeding, and whatever you ask in interviews is completely irrelevant.

It is exactly for these reasons we never ask such questions in our interviews. There are much more important aspects of a candidate to evaluate.

This depends on the context... If a file is pretty small, I would avoid sort pipes when there is a Python codebase. It's only useful when the files are pretty big (1-5GB+)

They are tricky and not very portable. Sorting depends on locales and the GNU tools implementation.

you can develop just as fast or even faster with python once you develop a good enough utility library for it.

For example my python interpreter imports my custom List and Path classes and I could just do the following to get the same result:

List(List(Path("filepath").read_text_file().splitlines()).group_by_key(lambda x:x).items()).map(lambda x:(len(x[1]),x[0])).sorted()

and if used often enough, it could made an utility method:

Path("filepath").read_sorted_by_most_common()

So I find it shortsighted to reject someone based on that without giving them a chance to explain their reasoning.

I think generally people really underestimate how much more productive you can be with a good utility library.

> Wasting developer time

What is the definition of wasting developer time? If a developer takes a 2 hours break to recover mental power and avoid burnout, is it considered time wasted?

But GNU coreutils would reject a new flag, you'd need to add it to BSD or Rust uutils.

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.

Reasonably often in ETL type tasks.

To me, the really big win would be _not_ to have to sort at all. Have an option to keep first or last duplicate and remove all others while keeping line order is usually what I need.

I've added awk into the benchmarks also!

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

I think that it's a pretty common use case for text processing - I end up needing to use it a lot in bioinformatics where there is a lot of text processing.

It's great when you quickly need to see what the distribution of classes in an input stream is. This pops up all the time. Like measuring different types of log messages, counting the variants of a field in a csv, finding the most common word or substring, etc.

The first "sort" sorts the input lines lexicographically (which is required for "uniq" to work); the second "sort" sorts the output of "uniq" numerically (so that lines are ordered from most-frequent to least-frequent):

  $ echo c a b c | tr ' ' '\n'
  c
  a
  b
  c
  
  $ echo c a b c | tr ' ' '\n' | sort
  a
  b
  c
  c
  
  $ echo c a b c | tr ' ' '\n' | sort | uniq -c
        1 a
        1 b
        2 c
  
  $ echo c a b c | tr ' ' '\n' | sort | uniq -c | sort -rn
        2 c
        1 b
        1 a

`uniq -c` introduces a "count" at the beginning of the line, so what we are then sorting is on frequency of the unique terms in the output, not sorting the unique terms again (which indeed would be kindof nonsensical)

  sort | uniq -c | sort -n

It's something I've done myself in the past. First sort is because it needs to be sorted for uniq -c to count it proper, second sort because uniq doesn't always give the output in the right order.

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

Disclaimer: the author of the comment is the founder and CTO of ClickHouse

When using clickhouse-local like this, does it build a logical plan and run the optimizer on it? Does it have any kind of code generation, since it knows the query (and physical data layout) ahead of time?

Exactly. I love this and DuckDb and other such amazing tools.

Just noting that in your benchmark (which we know nothing about), your "naive" data point is just 2.29x slower than hist. In their testing it was 27x slower! And it's not quite the same naive shell command, which isn't helpful.

I'd not heard of clickhouse before. It does seem interesting, but I just can't get behind a project that says:

> The easiest way to download the latest version is with the following command:

> curl https://clickhouse.com/ | sh

Like, sure, there is some risk downloading a binary or running an arbitrary installer. But this is just nuts.

To be more fair you could also add SETTINGS max_threads=1 though?