An Overengineered Solution to `sort | Uniq -C` with 25x Throughput (hist)

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.

  sort | uniq -c | sort -n

  $ 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

> 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.

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

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.

Would be interesting to try this out

``` 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 ```

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....

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.

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.

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."

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?

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

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

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!

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.

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

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